G+N

Question 0

What is the definition for the Euclidean Algorithm for the GCD and the equation for the least common multiple?

Answer 0

For (a,b): There exists some m,n in the integers such that d=(a,b)=ma+nb.

For [a,b]: LCM= |a•b|/GCD(a,b).

Question 1

Find the Greatest Common Divisor of d=(7469,2464).

And then find the LCM.

Answer 1

7469=3x2464+77
2464=32x77+0
So, (7469,2464)=77 and
77=1•7469+(-3)•2464. (m=1 and n=-3)

LCM=7469•2464/77

Question 2

Find x and y for 43x+64y=1.

Answer 2

Find the GCD: which is 1.
Work backwards from the Euclidean Algorithm: we obtain 1=3•43+(-2)•64.
Thus our x0=3 and y0=-2 such that we have x=3+64r and y=(-2)-43r.

Question 3

Find the solution to 57x==87(mod105).

Answer 3

1. Find the GCD of (57,105)=3, so there are 3 solutions.
2. Divide the entire equation by 3 to obtain 19x=29(mod35).
3. Then work backwards from the GCD process to get 1=6•35-11•19. So x==(-11)19x==(-11)29=-319==
   31mod35.
4. So the three solutions are {31,66,101} (adding 35).

Question 4

Solve 19x==1(mod140) by two different methods.

Answer 4

Look at solutions to G+N sheet 4 Q7

Question 5

What is Fermat’s Little Theorem?

Answer 5

A^p==amodp

A^(p-1)==1modp