6.2: GCD, LCM and Prime factorization
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 6.2.1:
Determine gcd(39,38) and lcm(39,38)
Solution
gcd(39,38)=38 (the lowest powers of all prime factors that appear in both factorizations) and lcm(39,38)=39 (the largest powers of each prime factor that appear in factorizations).
Example 6.2.2:
Determine gcd(26×39,24×38×52) and lcm(26×39,24×38×52).
Solution
gcd(26×39,24×38×52)=24×38 (the lowest powers of all prime factors that appear in both factorizations) and lcm(26×39,24×38×52)=26×39×52 (the largest powers of each prime factors that appear in factorizations).
Example 6.2.3:
Find gcd(3915,825) and lcm(3915,825).
Solution
Since 3915=33×5×29 and 825=3×52×11, gcd(3915,825)=3×5 and lcm(3915,825)=33×52×11×29.
Example 6.2.4:
Find gcd(2420,230) and lcm(2420,230).
Solution
Since 2420=22×5×112 and 230=2×5×23, gcd(2420,230)=2×5 and lcm(2420,230)=22×5×112×23.
Another use of Prime factorization is as follows:
Euler's totient function
For n∈N, the Euler's totient function ϕ(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.
Determine the value ϕ(n) for each integer n≤30. For n∈N, ϕ(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∈N, Relatively Prime to n |
||
n |
ϕ(n) |
Set of n∈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ϕ(n) for n∈N.
Wilson's Theorem
Let p be a prime number. Then (p−1)!+1 is divisible by p.
- Proof:
-
Consider the product P=1⋅2⋅3⋯(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≤k≤p−1, there exists a unique k−1 such that kk−1≡1(modp). Moreover, these pairs will be distinct because if kk−1≡1(modp) and jj−1≡1(modp) for k≠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(modp). Therefore, P≡(p−1)!≡−1(modp). Adding 1 to both sides gives (p−1)!+1≡0(modp), which means (p−1)!+1 is divisible by p.
Fermat's Little Theorem
For any prime number p and any positive integer a such that p does not divide a, we have ap−1≡1(modp).
Euler's Theorem
If a and n are relatively prime (i.e., gcd(a,n)=1), then aϕ(n)≡1(modn)
1. If p is prime then ϕ(p)=p−1.
2. If p is prime and k is a positive integer then ϕ(pk)=pk−pk−1.
3. If m and n are relatively prime, then ϕ(mn)=ϕ(m)ϕ(n).
4. ϕ(n)=n×∏p|n(1−1p) where the product is taken over distinct prime factors p of n.
Find ϕ(252).
Solution
Since 252=22327, ϕ(252)=(22−2)(32−3)(7−1)=72.