Answer :
Answer:
307 is an inverse of 43 mod 660
Step-by-step explanation:
We know that given integers [tex]a[/tex] and [tex]n[/tex], if [tex]gcd(a, n) = 1[/tex], then [tex]a[/tex] has an inverse modulo [tex]n[/tex], and using Euclidean algorithm we find an inverse of [tex]a[/tex] expressing 1 as a linear combination of [tex]a[/tex] and [tex]n[/tex] finding integers [tex]s[/tex] and [tex]t[/tex] such that [tex]as+nt =1[/tex], in this case, [tex]s[/tex] is an inverse of [tex]a[/tex], i.e., [tex]as[/tex]≡[tex]mod[/tex][tex]n.[/tex]
To find the inverse of 43 mod 600, we need to do two steps:
- We need to calculate the Greatest Common Divisor of 660 and 43 (gcd(660, 43)) using the Euclidean algorithm and verify that gcd(a, n) = 1.
[tex]660=43*15+15,\\43=15*2+13,\\15=13*1+2;\\13= 2*6+1,\\2=2*1+0[/tex]
which implies that gcd(660, 43)= 1 and so 660 and 43 are relatively prime.
2. Express 1 as a linear combination of 43 and 600.
We work backwards using the equations derived by applying the Euclidean algorithm, expressing each remainder as a linear combination of the associated divisor and dividend:
[tex]1 = 13-2*6[/tex]
[tex]1=13-(15-13)*6[/tex] substitute [tex]2 = 15-13[/tex],
[tex]1=7*13-6*15[/tex] by algebra
[tex]1=7*(43-15*2)-6*15[/tex] substitute [tex]13 = 43-15*2[/tex]
[tex]1=7*43-20*15[/tex] by algebra
[tex]1=7*43-20(660-43*15)[/tex] substitute [tex]15 = 660-43*15[/tex]
[tex]1=307*43-20*660[/tex] by algebra.
Thus 43*307=1+20*660, then by definition of congruence modulo 660, 43*307 ≡ 1 (mod 600) and therefore 307 is an inverse of 43 mod 660.