# Modular Multiplicative Inverse when multiplier greater than mod?

I'm having some trouble with this discrete math problem.

I'm given this equation: $7x + 9y \equiv 0 \bmod 31$ and $2x -5y \equiv 2 \bmod 31$

And I've solved like I did my other one (which turned out correct), coming to $14x+18y-14x+35y=-14\pmod{31} \implies 53y=-14\mod31=17\pmod{31}$.

My question: how do you go about solving $53y=17\mod31$? I know how to do this when the multiplier on the left is smaller, using extended Euclid's algorithm, which is all I've learned from my class so far (no Euler thing). I know the answer is 5, but how do I arrive at that? This one doesn't seem to work with extended Euclid's.

• Just take the remainder of $53$ modulo $31$, $53 y \equiv 22 y \pmod{31}$. – Daniel Fischer Sep 22 '13 at 21:19
• That's the key I was missing! Thanks! – skbills Sep 22 '13 at 21:33

$53y=17$ mod $31$
$22y=17$ mod $31$ (because 53 mod 31 = (53-31) mod 31)
$22y=48$ mod $31$ (because 17 mod 31 = (17+31) mod 31)
$11y=24$ mod $31$ (divide both sides by 2)
$11y=55$ mod $31$ (because 24 mod 31 = (24+31) mod 31)
$y=5$ mod $31$ (divide both sides by 11)

• Thanks! Missed that key insight - 53 = 22 mod 31, doh! Didn't realize the mod could be applied there, but it makes sense now. – skbills Sep 22 '13 at 21:33
• your welcome :) – Mufasa Sep 22 '13 at 21:34

Ideas:

$$53=22=11\cdot 2\pmod{31}$$

$$2\cdot 16=1\pmod {31}\implies 2^{-1}=16\pmod {31}$$

$$11\cdot 3=2\pmod{31}\implies 11^{-1}=3\cdot2^{-1}=3\cdot16=17\pmod{31}$$

Thus

$$53^{-1}=11^{-1}2^{-1}=17\cdot 16=8\cdot(2\cdot16)+16=8+16=24\pmod {31}$$

And finally

$$53y=17\pmod{31}\implies y=53^{-1}\cdot17=24\cdot 17=(-7)17=-26=5\pmod{31}$$

• Wow, thanks! This proof involves some really good ideas I'll have to mull over, but it does seem like there's an extended Euclid's hidden in there. – skbills Sep 22 '13 at 21:32
• Not really, @skbills. What is there is decomposition of numbers in some factors whose inverses are easy, more or less, to find. For example, $\;22=11\cdot2\;$ , and we use the fact the inverse of two is very easy to find, and then we do $\;11\cdot 3=33=2\pmod{31}\implies 11^{-1}=3\cdot 2^{-1}\;$ and etc. – DonAntonio Sep 22 '13 at 23:29