Number Theory | Modular Inverses: Example

We give an example of calculating inverses modulo n using two separate strategies.

[ekarata.]

I have been struggling with number theory and your channel by far the most helpful to me. Thank you!

[VivekSarkar-jpvr]

Another way to do it might be :
break 143 into 11 and 13
then 34inv(mod 143) =>
34 inv (mod 11) and 34 inv (mod 13)
34 inv (mod 11) and 8 inv (mod 13)
then apply the chinese remainder theorem to get
the required x(modulo 143).


Hope it helps!

[georgesadler]

Professor Penn, thank you for another step by step explanation of the Modulo Inverses.

[SatyamKumar-yksz]

Sir i am very thankful to God that i get teacher like you.

[PunmasterSTP]

Modulo? More like way-to-go! Thanks again for another wonderful demonstration.

[yifuxero]

Much easier way. (he wanted multiplicative inverse 9f 34 mod 143. No problem. First, find the continued fraction representation of 34/143. It's [4, 4, 1, 6]. Underneath we put in the convergents, = [1/4, 4/17, 5/24, 34/143]. From the rightmost denominator (143), subtract the denominator to the left (24), getting the answer (122). The rule is that if there's an even number of partial quotients (four in this case, [4, 4, 1, 6 ] perform the denominator subtraction procedure. But if the number of partial quotients is odd, just take the denominator to the left of rightmost denominator.. Example. multiplicative inverse of 5 mod 21. Data: [4, 4, 1], with convergents [1/4, 4/17, 5/21] Denominator to left of 21 = 17. That's the answer since 5 * 17 = 85 = 1 mod 21.

[artahir]

9:15
I am confused plz help me to understand
why the hell we are doing 143 -21 = 122 ?
whats the reason ? whats the logic ?
whats the in-depth reason ?

[skylardeslypere]

With the mod 20, you forgot the pairs {3, 17} and {7, 13}

[ramakrishnasen]

Well all of that is alright, I had my number theory class yesterday (I am a math olympiad student) and my teacher taught me this. To me this seemed very trivial and I am still not sure how is it useful. He even stressed the word 'powerful technique' during his lectures.
If anyone knows how, please do share