Exercises 12 : Using the extended Euclidean Algorithm, find the great common div

Question

Exercises 12 :

Using the extended Euclidean Algorithm, find the great common divisor (GCD) of the following pairs of integers:

(a). GCD(88, 220), and S, T such that GCD(88,220)=88S+220T; and

(b). GCD (300, 42),and S, T such that GCD(300,42)=300S+42T.

Exercises 13 :

Solve the following: (a). Given GCD (a, b)=24, find GCD(a,b,26);

(b). Given GCD (a, b, c)=12, find GCD(a,b,c,16).

Exercises 25 : We have been told in arithmetic that the reminder of an integer divided by 9 is the same as the reminder of division of the sum of its decimal digits by 9. In other words, the reminder of division 6371 by 9 is the same as dividing 17 by 9 because 6+3+7+1=17. Use the properties of the mod operator to prove this claim

Exercises 29: Let us assign numeric value to the uppercase alphabet (A=0, B=1, …, Z=25). We can now do modular arithmetic on the system using modulo 26.

(a). What is (A+N) mod (26) in this system:

(b). What is (A+6) mod (26) in this system:

(c). What is (Y-5) mod (26) in this system:

(d). What is (C-10) mod (26) in this system:

Explanation / Answer

a) GCD (88,220)

According to Euclidean Algorithm,

220 = 88(2) + 44, 88 = 44(2) + 0 .............(1)

so GCD (88,220) = 44

As given 44 = 88S + 220T --------(2)

Now By using extended Euclidean Algorithm Acc to (1)

44 = 88(-2) + 220(1)

therefore S = -2 and T = 1

b) GCD (300, 42)

According to Euclidean Algorithm,

300 = 42(9) + 6, 42 = 6(7) + 0 .......(3)

so GCD (300,42) = 6

As given 6 = 300S + 42T...................(4)

Now By using extended Euclidean Algorithm Acc to (4)

6 = 300(1) + 42(-9)

Therefore S = 1, T = -9

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.