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$
2
  • 1
    $\begingroup$ Just take the remainder of $53$ modulo $31$, $53 y \equiv 22 y \pmod{31}$. $\endgroup$ Sep 22, 2013 at 21:19
  • $\begingroup$ That's the key I was missing! Thanks! $\endgroup$
    – skbills
    Sep 22, 2013 at 21:33

2 Answers 2

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$
2
  • $\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, 2013 at 21:33
  • $\begingroup$ your welcome :) $\endgroup$
    – Mufasa
    Sep 22, 2013 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$
2
  • $\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, 2013 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, 2013 at 23:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .