Theory of Numbers

Running head: THEORY OF NUMBERS
THEORY OF NUMBERS
Name of the Student
Name of the University
Author Note

1THEORY OF NUMBERS
Answer to Question No. 1
Using the Euclidean algorithm,
7700 = 3*2233 + 1001
2233 = 2*1001 + 231
1001 = 4*231 + 77
231 = 3*77
So gcd(7700, 2233) = 77.
Answer to Question No. 2
Using the Euclidean algorithm,
629 = 1*357 + 272
357 = 1*272 + 85
272 = 3*85 + 17
85 = 5*17
So, gcd(357, 629) = 17. Moreover,
17 = 272 – 3*85
= 272 – 3(357 – 1*272)
= 4*272 – 3*357

2THEORY OF NUMBERS
= 4(629 – 1*357) – 3*357
= 4*629 – 7*357
= -7*357 + 4*629
Therefore, s = -7 and t = 4.
Answer to Question No. 3
If gcd(a,b) = 1,
then there exist integers s and t such that
as + bt = 1.
Therefore,
cas + cbt = c.
Now since a|c and b|c,
there exist integers m and n such that
c = ma and c = nb.
Therefore,
nbas + mabt = c.
Since ab divides the entire left hand side, it must also divide the right hand side.
Therefore, ab|c.