PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!! Let. a be an integer and let

Question

PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!!

Let. a be an integer and let n be a natural number. If ged (a, n) = 1, then their, exists an integer x such that n x = 1 (mod n). Let a = 10 an d n = 97. Use what we learned in class and in the study groups to find an integer x such that 10x = 1 (mod 97). Make your own examples. To make one, just choose an integer a and a natural number n that are relatively prime, and then find an integer x such that ax = 1 (mod n) for your a and n. Your examples should be neither too easy nor too hard. Make at least three of your own.

Explanation / Answer

Use the Euclidean algorithm. I will demonstrate the example of a=120, n=23 120=23*5+5 23=5*4+3 5=3*1+2 3=2*1+1 This can be rephrased into 5=120-23*5 3=23-5*4=23-(120-23*5)*4=-120*4+23*21 2=5-3*1=(120-23*5)-(-120*4+23*21)=120*5-26*23 1=3-2*1=(-120*4+23*21)-(120*5-26*23)=-9*120+23*47 So x=-9 In order to prove this in general we apply the same algorithm a=q1*n+r1 r1=a-q1*n n=q2*r1+r2 r2=n-q2*r1= r1=q3*r2+r3 r3=r1-q3*r2=(a-q1*n)-q3*(n-q2*(a-q1*n)) ... Therefore all of the rn's are combinations of a and n with integer coefficients. Eventually this process terminates with the gcd. Therefore there exists x,y such that ax+ny=1. This then implies the theorem.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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