6.2: GCD, LCM and Prime factorization

We have already discussed GCD and LCM in Chapter 4. This section will explore another method for finding GCD and LCM using prime factorization. In this method, we must first find the given integers' prime factorization.

Example $\PageIndex{1}$:

Determine $gcd( 3^9 , 3^8)$ and $lcm( 3^9, 3^8)$

Solution

$gcd( 3^9, 3^8)= 3^8$ (the lowest powers of all prime factors that appear in both factorizations) and $lcm( 3^9,3^8)=3^9$ (the largest powers of each prime factor that appear in factorizations).

Example $\PageIndex{2}$:

Determine $gcd( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)$ and $lcm( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)$.

Solution

$gcd( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)= 2^4 \times 3^8$ (the lowest powers of all prime factors that appear in both factorizations) and $lcm( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)= 2^6 \times 3^9 \times 5^2$ (the largest powers of each prime factors that appear in factorizations).

Example $\PageIndex{3}$:

Find $gcd(3915, 825)$ and $lcm(3915, 825).$

Solution

Since $3915 = 3^3 \times 5 \times 29$ and $825 = 3\times 5^2 \times 11$, $gcd(3915, 825)= 3 \times 5$ and $lcm(3915, 825)= 3^3 \times 5^2 \times 11 \times 29.$

Example $\PageIndex{4}$:

Find $gcd(2420, 230)$ and $lcm(2420, 230).$

Solution

Since $2420 = 2^2 \times 5 \times 11^2$ and $230 = 2 \times 5 \times 23$, $gcd(2420, 230)= 2 \times 5$ and $lcm(2420, 230)= 2^2 \times 5 \times 11^2 \times 23.$

Another use of Prime factorization is as follows:

  Euler's totient function

Definition:  

For $n \in \mathbb{N}$, the Euler's totient function $\phi(n)$ is defined to be the number of positive integers less than $n$ that are relatively prime to $n$.

Euler's totient function has numerous applications in number theory, cryptography, and other branches of mathematics. It plays a vital role in RSA encryption, where it is used to compute the encryption and decryption keys.

Example $\PageIndex{5}$

Determine the value $\phi(n)$ for each integer $n \le 30$.  For $n \in \mathbb{N}$, $\phi(n)$ is defined to be the number of positive integers less than or equal to  $n$ that are relatively prime to $n$.

Number of $n \in \mathbb{N}$, Relatively Prime to $n$
$n$	$\phi (n)$	Set of $n \in \mathbb{N}$ that are relatively Prime to $n$.
1	1	{1}
2	1	{1}
3	2	{1,2}
4	2	{1,3}
5	4	{1,2,3,4}
6	2	{1,5}
7	6	{1,2,3,4,5,6}
8	4	{1,3,5,7}
9	6	{1,2,4,5,7,8}
10	4	{1,3,7,9}
11	10	{1,2,3, … ,8,9,10}
12	4	{1,5,7,11}
13	12	{1,2,3, … ,10,11,12}
14	6	{1,3,5,9,11,13}
15	8	{1,2,4,7,8,11,13,14}
16	8	{1,3,5,7,9,11,13,15}
17	16	{1,2,3, … ,14,15,16}
18	6	{1,5,7,11,13,17}
19	18	{1,2,3, … ,16,17,18}
20	8	{1,3,7,9,11,13,17,19}
21	12	{1,2,4,5,8,10,11,13,16,17,19,20}
22	10	{1,3,5,7,9,13,15,17,19,21}
23	22	{1,2,3, … ,20,21,22}
24	8	{1,5,7,11,13,17,19,23}
25	20	{1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24}
26	12	{1,3,5,7,9,11,15,17,19,21,23,25}
27	18	{1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26}
28	12	{1,3,5,9,11,13,15,17,19,23,25,27}
29	28	{1,2,3, … ,26,27,28}
30	8	{1,7,11,13,17,19,23,29}

The following results will help us find Euler's totient function$\phi(n)$ for $n\in \mathbb{N}$.

 

Wilson's Theorem

Theorem $\PageIndex{7}$

Let $p$ be a prime number. Then $(p - 1)! + 1$ is divisible by $p$.

Proof:

Consider the product $P = 1 \cdot 2 \cdot 3 \cdots (p-1)$. Now, let's pair each number $k$ from $1$ to $p-1$ with its modular inverse $k^{-1}$ modulo $p$. 

We know that for every $k$ such that $1 \leq k \leq p-1$, there exists a unique $k^{-1}$ such that $kk^{-1} \equiv 1 \pmod{p}$. Moreover, these pairs will be distinct because if $kk^{-1} \equiv 1 \pmod{p}$ and $jj^{-1} \equiv 1 \pmod{p}$ for $k \neq j$, then $k = kj^{-1}$ and $j = jk^{-1}$, implying $k = j$, which contradicts the distinctness of the pairs. 

Thus, we can pair each $k$ with $k^{-1}$ such that the product of these pairs is congruent to $1 \pmod{p}$. Therefore, $P \equiv (p-1)! \equiv -1 \pmod{p}$. Adding $1$ to both sides gives $(p-1)! + 1 \equiv 0 \pmod{p}$, which means $(p-1)! + 1$ is divisible by $p$.

 

 

Fermat's Little Theorem

Theorem $\PageIndex{8}$

 For any prime number $p$ and any positive integer $a$ such that $p$ does not divide $a$, we have $a^{p-1} \equiv 1 \pmod{p}$.

Euler's Theorem

Theorem $\PageIndex{9}$

If $a$ and $n$ are relatively prime (i.e., $\gcd(a, n) = 1$), then $$a^{\phi(n)} \equiv 1 \pmod{n}$$

 

Theorem $\PageIndex{10}$

 

1.  If $p$ is prime then $\phi(p)=p-1.$

2. If $p$ is prime and $k$ is a positive integer then $\phi(p^k)=p^k-p^{k-1}.$

3. If $m$ and $n$ are relatively prime, then $\phi(mn)=\phi(m)\phi(n).$

4. $$\phi(n) = n \times \prod_{p|n} \left(1 - \frac{1}{p}\right)$$ where the product is taken over distinct prime factors $p$ of $n.$

 

Example $\PageIndex{6}$

Find $\phi(252)$.

Solution

Since $252= 2^2 3^2 7$,  $\phi(252)=(2^2-2)(3^2-3)(7-1)=72$.