Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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

Definition:  

For nN, 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.

Example 6.2.5

Determine the value ϕ(n) for each integer n30.  For nN, ϕ(n) is defined to be the number of positive integers less than or equal to  n that are relatively prime to n.

Number of nN, Relatively Prime to n

n

ϕ(n)

Set of nN 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 nN.

 

Wilson's Theorem

Theorem 6.2.7

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

Proof:

Consider the product P=123(p1). Now, let's pair each number k from 1 to p1 with its modular inverse k1 modulo p

We know that for every k such that 1kp1, there exists a unique k1 such that kk11(modp). Moreover, these pairs will be distinct because if kk11(modp) and jj11(modp) for kj, then k=kj1 and j=jk1, implying k=j, which contradicts the distinctness of the pairs. 

Thus, we can pair each k with k1 such that the product of these pairs is congruent to 1(modp). Therefore, P(p1)!1(modp). Adding 1 to both sides gives (p1)!+10(modp), which means (p1)!+1 is divisible by p.

 

 

Fermat's Little Theorem

Theorem 6.2.8

 For any prime number p and any positive integer a such that p does not divide a, we have ap11(modp).

Euler's Theorem

Theorem 6.2.9

If a and n are relatively prime (i.e., gcd(a,n)=1), then aϕ(n)1(modn)

 
Theorem 6.2.10

 

1.  If p is prime then ϕ(p)=p1.

2. If p is prime and k is a positive integer then ϕ(pk)=pkpk1.

3. If m and n are relatively prime, then ϕ(mn)=ϕ(m)ϕ(n).

4. ϕ(n)=n×p|n(11p) where the product is taken over distinct prime factors p of n.

 

Example 6.2.6

Find ϕ(252).

Solution

Since 252=22327ϕ(252)=(222)(323)(71)=72.

 


This page titled 6.2: GCD, LCM and Prime factorization is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?