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:

\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:

\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
**Euclid's Theorem of the Existence of Infinitely Many Primes**page we proved a famous result known as Euclid's Theorem for the Existence of Infinitely Many Primes. Like the title suggests, this result states that there exists infinitely many prime numbers.

- 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$. |