3
$\begingroup$

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.

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

$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)

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

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}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – skbills Sep 22 '13 at 21:32
  • $\begingroup$ 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. $\endgroup$ – DonAntonio Sep 22 '13 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.