Find an inverse for 43 modulo 660. That is, find an integer s such that 43s=1(mod 660)

Answer:307 is an inverse of 43 mod 660Step-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.