a) Use the eucledean algorithm to the Greatest common divisor of 105 and 120

b. Find (7^4325) mod 13 by studying the pattern of "powers of 7" 

 

a)  Euclid's algorithm, is an efficient computing method for the greatest common divisor (GCD) of two integers (numbers) commonly known as the largest number that divides them both without a remainder. The following is the procedure for calculating the GCD of 105 and 120;

Step 1;

• Prime Factorization of 105

Prime factors of 105 are 3, 5, 7. Prime factorization of 105 in exponential form is:

105 = 3¹ × 5¹ × 7¹

• Prime Factorization of 120

Prime factors of 120 are 2, 3, 5. Prime factorization of 120 in exponential form is:

120 = 2³ × 3¹ × 5¹

Step 2;

• Factors of 105

List of positive integer factors of 105 that divides 105 without a remainder.

1, 3, 5, 7, 15, 21, 35

• Factors of 120

List of positive integer factors of 120 that divides 105 without a remainder.

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60

Step 3;

We found the factors and prime factorization of 105 and 120. The biggest common factor number is the GCF number.

The common numbers are 3 and 5

therefore the Greatest common factor will be calculated by ; 3*5 =15

• So the greatest common factor for 105 and 120 is 15.

b) 7⁴³²⁵ mod 13

7⁶ =12 mod 13

7⁶= (-1) mod 13

Raising 7 to power 4320

(7)⁷²⁰ =(-1)⁷²⁰ mod 13

7⁴³²⁰ = 1 mod 13

7⁴³²⁵=7⁵ mod 13

7⁴³²⁵= 11 mod 13

therefore 7⁴³²⁵ =11 mod 13