Prime Numbers and Common Factors

Prime Numbers

Definition Prime Number

A prime number is a positive integer $p\ge 2$ whose only positive divisors are $1$ and $p$.
An integer $n\ge 2$ that is not prime is called composite.

Notes

$1$ is not a prime number because it has only one positive divisor: itself.
A prime number $p$ is a natural integer greater than or equal to $2$ ($p \geq 2$).
Except for $2$, all prime numbers are odd.
There are $25$ prime numbers less than $100$: $$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. $$
If a natural integer $n \geq 2$ is not prime, it has a proper divisor $d$ such that $1 < d < n$.

Proposition Existence of a Prime Divisor

Every integer $n \geq 2$ has at least one prime divisor.

Proof

Let $n \geq 2$ be an integer.

If $n$ is prime, then it is its own prime divisor and the property is true.
If $n$ is not prime, then it admits a divisor $a_1$ distinct from $1$ and $n$. By definition, $2 \le a_1 \le n-1$, so \(a_1
If $a_1$ is not prime, it is in turn divisible by an integer $a_2$ such that $2 \le a_2 < a_1$.
Continuing this process, if none of the integers obtained were prime, we would construct an infinite strictly decreasing sequence of positive integers $$ n > a_1 > a_2 > \cdots, $$ which is impossible.

Therefore, at least one of the integers $a_k$ must be prime, and it is also a divisor of $n$.

Theorem Infinitely many primes

There are infinitely many prime numbers.

Proof

Assume there are only $n$ primes $p_1,\dots,p_n$ and set $M=p_1p_2\cdots p_n+1$.
For every $k$, the Euclidean division of $M$ by $p_k$ leaves remainder $1$, so no $p_k$ divides $M$.
This contradicts the fact that every integer $\ge 2$ has a prime divisor. Hence, there are infinitely many primes.

Exercise

Prove that every natural integer $n \geq 2$ that is not prime admits a prime divisor $p$ such that $2 \le p \le \sqrt{n}$.
Show that the integer $53$ is a prime number.

Answer

Proof of the theorem:
Suppose $n \geq 2$ is a composite number. By definition, there exist two integers $a$ and $b$ such that: $$ n = a \times b \quad \text{with} \quad 1 < a \le b < n $$ If both $a > \sqrt{n}$ and $b > \sqrt{n}$, then: $$ a \times b > \sqrt{n} \times \sqrt{n} \implies n > n $$ This is a contradiction. Therefore, we must have $a \le \sqrt{n}$.
Since $a \ge 2$, according to the property of the existence of a prime divisor, $a$ admits at least one prime divisor $p$.
Because $p \mid a$ and $a \le \sqrt{n}$, it follows that $p \le \sqrt{n}$.
Since $p$ divides $a$ and $a$ divides $n$, then $p$ is a prime divisor of $n$ satisfying the condition.
Application to $n = 53$:
We calculate the square root: $\sqrt{53} \approx 7.28$.
According to the theorem, if $53$ is composite, it must have a prime divisor $p \le 7$.
The prime numbers less than or equal to $7$ are 2, 3, 5, and 7. Let's test them:
- 53 is odd, so it is not divisible by 2.
- The sum of the digits is $5+3=8$. 8 is not divisible by 3, so 53 is not divisible by 3.
- 53 does not end in 0 or 5, so it is not divisible by 5.
- $53 = 7 \times 7 + 4$. The remainder is not 0, so 53 is not divisible by 7.
Since $53$ is not divisible by any prime $p \le \sqrt{53}$, 53 is a prime number.

Method Test for primality

To determine if a natural integer $n \geq 2$ is prime, we limit the search for divisors using the following property: A natural integer $n \geq 2$ is composite if and only if it admits at least one prime divisor $p$ such that $2 \le p \le \sqrt{n}$.Steps to follow:

Calculate the approximate value of $\sqrt{n}$.
List all prime numbers $p$ in the interval $[2, \sqrt{n}]$.
Test the divisibility of $n$ by each of these prime numbers.
- If none of these prime numbers divide $n$, then $n$ is prime.
- If at least one of these prime numbers divides $n$, then $n$ is composite.

Example

Is 167 a prime number?

Answer

$\sqrt{167} \approx 12.9$.
The prime numbers to test are: 2, 3, 5, 7, and 11.
Divisibility tests:
- 167 is not even (not divisible by 2).
- $1+6+7 = 14$ (not divisible by 3).
- 167 does not end in 0 or 5 (not divisible by 5).
- $167 = 7 \times 23 + 6$ (not divisible by 7).
- $167 = 11 \times 15 + 2$ (not divisible by 11).
As no prime number $p \leq \sqrt{167}$ divides 167, 167 is a prime number.

Prime Factorization

Theorem Fundamental theorem of arithmetic

Every integer $n\ge 2$ can be written as$$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},$$where $p_1,\dots,p_k$ are distinct prime numbers and $\alpha_1,\dots,\alpha_k$ are positive integers.
This decomposition is unique up to the order of the factors.

Proof

Existence (by strong induction):
Let $P(n)$ be the property: ``The integer $n$ admits a decomposition into prime factors.''
- Initialization: For $n=2$. Since $2$ is a prime number, it is its own decomposition. Thus $P(2)$ is true.
- Heredity: Let $n \geq 2$ be an integer. Suppose that for every integer $k$ such that $2 \leq k \leq n$, $P(k)$ is true. Let us show that $P(n+1)$ is true.
  - If $n+1$ is prime, then it is its own decomposition.
  - If $n+1$ is composite, it admits a proper divisor $d$ such that $2 \leq d \leq n$. We can write $n+1 = d q$ with $q\ge 2$. Since $d \geq 2$, we have $q \leq n$. By the induction hypothesis, both $d$ and $q$ admit prime factorizations. The product of these factorizations provides a prime factorization for $n+1$.
- Conclusion: By the principle of strong induction, every integer $n \geq 2$ admits a prime factorization.
Uniqueness:
Suppose an integer $n$ has two decompositions:$$n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m,$$where all $p_i$ and $q_j$ are prime numbers.
Since $p_1$ is prime and divides the product $q_1 q_2 \cdots q_m$, Gauss's Theorem implies that $p_1$ divides at least one factor $q_j$. Because $q_j$ is prime, we must have $p_1=q_j$. By cancelling this common factor and repeating the argument, we conclude that the prime factors coincide, up to order.
Note: This part is admitted for now as it relies on Gauss's Theorem, which will be proven later.

Method Factor Tree

The factor tree method involves breaking down a composite number into smaller factors, then breaking down those factors further until you have only prime factors.

Place the number at the top of the factor tree.
Check if the number is prime.
1. If the number is prime: Circle it. You are done with this branch.
2. If the number is composite: Factor it into two smaller factors. Write these two factors as branches below the number. Repeat step 2 for each of these new factors.
The prime factorization is the product of all circled prime numbers on the tree.

Example

Find a prime factorization of $24$.

Answer

Step 1:
Step 2: $24$ is a composite number. $24 = 2 \times 12$.
Step 3: $12$ is a composite number. $12 = 2 \times 6$.
Step 4: $6$ is a composite number. $6 = 2 \times 3$.

A prime factorization is $24 = 2^3 \times 3$.

Greatest Common Divisor (GCD)

Proposition Existence of the GCD

Let $a$ and $b$ be two integers, not both zero. The set of common divisors of $a$ and $b$ has a greatest element.

Proof

Let $a$ and $b$ be two integers, not both zero.

The set of divisors of a non-zero integer is finite. Since at least one of $a$ or $b$ is non-zero, at least one of the two divisor sets is finite, hence their intersection (the set of common divisors) is finite.
The set of common divisors is not empty because $1$ divides both $a$ and $b$.
Every non-empty finite subset of $\mathbb{N}$ has a greatest element. Therefore, the set of common divisors has a greatest element.

Definition Greatest Common Divisor

Let $a$ and $b$ be two integers, not both zero. The greatest element of the set of common positive divisors of $a$ and $b$ is called the greatest common divisor. It is denoted $\gcd(a,b)$.

Example

$\gcd(24,18)=6$.

Proposition Properties of the GCD

Let $a$ and $b$ be non-zero integers.

If $b$ divides $a$, then $\gcd(a,b)=|b|$.
For any integer $k$, $\gcd(a,b)=\gcd(a-kb,b)$.
If \(0

Method Euclidean Algorithm

Let $a$ and $b$ be two integers such that $0 < b \leq a$. The following algorithm allows the calculation of the GCD of $a$ and $b$ in a finite number of steps:

Compute the remainder $r$ in the Euclidean division of $a$ by $b$.
While $r \neq 0$ do:
- $a \leftarrow b$,
- $b \leftarrow r$,
- compute the new remainder $r$ of the Euclidean division of $a$ by $b$.
End while
$\gcd(a,b)=b$.

Example

Compute $\gcd(1554,136)$ using the Euclidean algorithm.

Answer

$$\begin{aligned}1554 &= 136\times 11 + 58,\\ 136 &= 58\times 2 + 20,\\ 58 &= 20\times 2 + 18,\\ 20 &= 18\times 1 + 2,\\ 18 &= 2\times 9 + 0.\end{aligned}$$The last non-zero remainder is $2$, so $\gcd(1554,136)=2$.

Method Calculating the GCD using Prime Factorization

To find the GCD of two integers $a$ and $b$ using their prime factorizations, follow these steps:

Decompose both numbers $a$ and $b$ into products of prime factors.
Identify the prime factors that are common to both decompositions.
For each common prime factor, keep the power with the smallest exponent present in either decomposition.
The GCD is the product of these common prime factors raised to their respective smallest exponents.

Example

Find $\gcd(120, 84)$ using prime factorization.

Answer

We decompose the two numbers: $$ \begin{aligned} 120 &= 2^3 \times 3^1 \times 5^1 \\ 84 &= 2^2 \times 3^1 \times 7^1 \end{aligned} $$
The common prime factors are 2 and 3.
We choose the smallest exponents:
- For the factor 2: the exponents are 3 and 2. The smallest is 2.
- For the factor 3: the exponents are 1 and 1. The smallest is 1.
We calculate the product: $$ \gcd(120, 84) = 2^2 \times 3^1 = 4 \times 3 = \mathbf{12} $$

Definition Coprime Integers

Let $a$ and $b$ be two integers, not both zero.
We say that $a$ and $b$ are coprime if $\gcd(a,b)=1$.

Example

$\gcd(15,8)=1$, so $15$ and $8$ are coprime.
$\gcd(a,1)=1$ for any integer $a$, so $1$ is coprime with every integer.

Notes

Coprime integers should not be confused with prime numbers. The integers $15$ and $8$ are coprime, but neither of them is prime. However, two distinct prime numbers are always coprime.
An irreducible fraction $q$ can be written as a ratio of two coprime integers: $$ q=\frac{a}{b} \quad \text{with } a\in\mathbb{Z},\ b\in\mathbb{N}^*,\ \text{and } \gcd(a,b)=1. $$

Least Common Multiple (LCM)

Proposition Existence of the LCM

Let $a$ and $b$ be two non-zero integers. The set of common strictly positive multiples of $a$ and $b$ is non-empty and admits a smallest element.

Definition Least Common Multiple

Let $a$ and $b$ be two non-zero integers. The smallest strictly positive integer which is a common multiple of $a$ and $b$ is called the least common multiple.
We denote it as $\operatorname{lcm}(a, b)$ or $a \lor b$.

Proposition Relationship between GCD and LCM

Let $a>0$ and $b>0$ be two integers. We have:$$ \gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b $$More generally, for any non-zero integers $a, b \in \mathbb{Z}$:$$ \gcd(a, b) \times \operatorname{lcm}(a, b) = |ab| $$

Proof

Let $d = \gcd(a, b)$. There exist coprime integers $a'$ and $b'$ such that $a = da'$ and $b = db'$.
Let $m$ be a common multiple of $a$ and $b$.

Since $m$ is a multiple of $a$, there exists an integer $k$ such that $m = ka = kda'$.
Since $m$ is also a multiple of $b$, we have $b \mid kda'$, which implies $db' \mid kda'$.
By simplifying by $d$, we obtain $b' \mid ka'$.
Since $\gcd(a', b') = 1$, according to Gauss's Theorem, $b'$ must divide $k$.
The smallest strictly positive value for $k$ is therefore $k = b'$.

Thus, the smallest positive common multiple is:$$ \operatorname{lcm}(a, b) = b' \times a = b' \times (da') = d \times a' \times b' $$We can verify the product:$$ \gcd(a, b) \times \operatorname{lcm}(a, b) = d \times (d a' b') = (da') \times (db') = a \times b $$

Method LCM via Prime Factorization

To determine the LCM of two integers $a$ and $b$:

Write the prime factorization of both $a$ and $b$.
Identify every prime factor that appears in at least one of the decompositions.
For each of these factors, keep the highest exponent observed.
The LCM is the product of these factors raised to their respective highest exponents.

Example

Calculate $\operatorname{lcm}(120, 84)$.

Answer

Using prime factorizations:$$\begin{aligned}120 &= 2^3 \times 3^1 \times 5^1 \\ 84 &= 2^2 \times 3^1 \times 7^1\end{aligned}$$Taking the highest power for each factor $\{2, 3, 5, 7\}$:$$ \operatorname{lcm}(120, 84) = 2^3 \times 3^1 \times 5^1 \times 7^1 = 8 \times 3 \times 5 \times 7 = \mathbf{840} $$Verification via GCD: $\gcd(120, 84) = 2^2 \times 3^1 = 12$ and $12 \times 840 = 10\,080 = 120 \times 84$.