Prime and Composite Numbers, Modular Arithmetic Review

Table of Contents

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.

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

Mathonline