Prime and Composite Numbers, Modular Arithmetic Review

# Prime and Composite Numbers, Modular Arithmetic Review

We will now review some of the recent material regarding prime numbers, composite numbers, and modular arithmetic.

• On the Prime and Composite Numbers we formally defined what it means for a number to be prime or composite. We said that an integer $p > 1$ is Prime if its only divisors are $\pm 1$ and $\pm p$. The first few primes are listed below for reference:
(1)
\begin{align} \quad \mathrm{Prime \: Numbers:} \: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... \end{align}
• We said that an integer $n \geq 1$ is Composite if it is not prime. In other words, there exists an integer $d \in \mathbb{Z}$ with $1 < d < n$ such that $d | n$ or $n = 1$. The first few composite numbers are listed below for reference:
(2)
\begin{align} \quad \mathrm{Composite \: Numbers:} \: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, .... \end{align}
• We then proved an important result regarding primes. If $a \in \mathbb{Z}$ and $p$ is a prime number, then the greatest common divisor $\gcd (a, p)$ can be one of two things.
• We noted that $\gcd (a, p) = 1$ if $p \not \mid a$.
• And otherwise, $\gcd (a, p) = p$ if $p \mid a$.
• For example, consider $a = 4$ and $p = 7$. Since $p \not \mid a$ we have that $\gcd (a, p) = \gcd (4, 7) = 1$. And if $a = 14$ and $p = 7$, then since $p \mid a$ we have that $\gcd (a, p) = \gcd (14, 7) = 7 = p$.
• We then proved that if $n \in \mathbb{Z}$ and $n > 1$ then $n$ has a prime divisor. For example, if $n = 16$ then $2$ is a prime divisor of $n$.
• On The Unique Prime Factorization Theorem page we looked at another famous theorem known as the Unique Prime Factorization Theorem. It states that if $n \in \mathbb{Z}$ and $n > 1$ then $n$ can be factored as a product of primes in a unique way apart from the ordering of the primes in the product.
• For example, consider $n = 20$. Then $n = 2 \cdot 2 \cdot 5$. There is no other way to write $20$ (apart from changing the order of $2$, $2$, and $5$ in the product) as a product of primes.
• On the Modular Arithmetic page we then began to look at modular arithmetic. We said that if $a, b \in \mathbb{Z}$ then $a$ is Congruent to $b$ modulo $m$ denoted $a \equiv b \pmod m$ if $m \mid (a - b)$. For example, $2$ is congruent to $5$ modulo $3$ since $3 \mid (2 - 5)$.
• We then stated that an integer $z \in \mathbb{Z}$ is Even if $z \equiv 0 \pmod 2$ and is Odd if $z \equiv 1 \pmod 2$.
• We then proved a bunch of basic properties regarding congruence which are summarized below.
Property
(a) If $a \equiv b \pmod m$ then $b \equiv a \pmod m$.
(b) $a \equiv a \pmod m$.
(c) If $a \equiv b \pmod m$ and $b \equiv c \pmod m$ then $a \equiv c \pmod m$.
(d) If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $(a + c) \equiv (b + d) \pmod m$.
(e) If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $ac \equiv bd \pmod m$.