Due date: Sep 18 Exercise 1. Use the extended Euclidean algorithm to find x,y E

Question

Due date: Sep 18 Exercise 1. Use the extended Euclidean algorithm to find x,y E Z satisfying gcd(a, b) - ax + biy for each of the following pairs of integers. (Show all work except for the long divisions.) 1. a 324,b 23 2. a 987,b 343 3. a = 98, b = 24 4. a 1003, b 25 5. a 341,b 88 Exercise 2. Write the following integers as a product of primes in standard form. Recall that standard from means that when we write a > 1 as a = p 1 · . .rn where pi is prime for all i e {1,... ,n), we also insist that pi

Explanation / Answer

Exercise 1.

1.

324 = 23 * (14) + 2
23 = 2 * (11) + 1
2 = 1 * (2) + 0
gcd (324,23) = 1 (Last non-zero remainder)

Now,this can be re-written as -
1 = 23 - 2 * (11)
1 = 23 + 2 * (-11)
1 = 23 + (324 - 23 * (14) )
1 = 23 + (324 + 23 * (-14) ) (-11)
1 = 23 + 324*(-11) + 23*154
1 = 324*(-11) + 23*155
gcd(a,b) = ax + by
That is x = -11 and y = 155

2.

987 = 343 * (2) + 301
343 = 301*(1) + 42
301 = 42*(7) + 7
42 = 7*(6) + 0
gcd (987,343) = 7 (Last non-zero remainder)

Now,this can be re-written as -
7 = 301 - 42 * (7)
7 = 301 + 42 * (-7)
7 = 301 + (343 - 301*(1)) * (-7)
7 = 301 + (343 + 301*(-1)) * (-7)
7 = 301 + 343*(-7) + 301*(7)
7 = 343*(-7) + 301*(8)
7 = 343*(-7) + (987 - 343*(2))*(8)
7 = 343*(-7) + (987 + 343*(-2))*(8)
7 = 343*(-7) + (987 + 343*(-2))*(8)
7 = 343*(-7) + 987*(8) + 343*(-16)
7 = 987*(8) + 343*(-23)
gcd(a,b) = ax + by
That is x = 8 and y = -23

3.

98 = 24 * (4) + 2
4 = 2*(2) + 0
gcd (98,24) = 2 (Last non-zero remainder)

Now,this can be re-written as -
2 = 98 - 24*(4)
2 = 98 + 24*(-4)
gcd(a,b) = ax + by
That is x = 1 and y = -4

4.

1003 = 25 * (40) + 3
25 = 3*(8) + 1
3 = 1*(3) + 0
gcd (1003,25) = 1 (Last non-zero remainder)

Now,this can be re-written as -
1 = 25 - 3*(8)
1 = 25 + 3*(-8)
1 = 25 + (1003 - 25*(40))*(-8)
1 = 25 + (1003 + 25*(-40))*(-8)
1 = 25 + 1003*(-8) + 25*(320)
1 = 1003*(-8) + 25*321
gcd(a,b) = ax + by
That is x = -8 and y = 321

I hope you can now do (5) by your own Its answer is gcd = 11 , x = -1 and y = 4 If you face any problem then leave a comment and i will solve it

Exercise 2.

1.

1416 = 2 * 708
708 = 2 * 354
354 = 2 * 177
177 = 3 * 59
Since 59 is prime hence stop

1416 = 2*2*2*3*59 = 23 x 31 x 591

2.

525 = 3 * 175
175 = 5 * 35
35 = 5 * 7
Since 7 is prime hence stop

525 = 3*5*5*7 = 31 x 52 x 71

3.

36414 = 2 * 18207
18207 = 3 * 6069
6069 = 3 * 2023
2023 = 7 * 289
289 = 17 * 17
Since 17 is prime hence stop

36414 = 2*3*3*7*17*17 = 21 x 32 x 71 x 172

4.

46000 = 2 * 23000
23000 = 2 * 11500
11500 = 2 * 5750
5750 = 2 * 2875
2875 = 5 * 575
575 = 5 * 115
115 = 5 *23
Since 23 is prime hence stop

46000 = 2*2*2*2*5*5*5*23 = 24 x 53 x 231

5.

829 is itself a prime number

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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