# Modular equations

• Oct 11th 2012, 03:56 AM
Nora314
Modular equations
Hi everyone! :)

So, the question is, "Does the following modular equations have -7 as a solution?"

14169300 + 7x = 14(mod 31)

so first I was like hehe, this will be easy, just solve the first part, and check if it gives a remainder of 14 when divided by 31. Though, my official calculator can't handle these big numbers, so is there some other way of solving this?

Thanks to everyone who reads this :)!
• Oct 11th 2012, 05:25 AM
a tutor
Re: Modular equations
If a is not divisible by p then $\displaystyle a^{p-1}\equiv 1 \mod p$ [Fermat's little theorem]

So have a think about 14169^30.
• Oct 11th 2012, 07:44 AM
Soroban
Re: Modular equations
Hello, Nora314!

Quote:

Does the following modular equation have -7 as a solution?

. . $\displaystyle 14169^{300} + 7x \:\equiv\: 14\text{ (mod 31)}$

We note that: .$\displaystyle 14169\:\equiv\:2\text{ (mod 31)}$

. . The equation becomes: .$\displaystyle 2^{300} + 7x \:\equiv\:14\text{ (mod 31)}$

We further note that: .$\displaystyle 2^5 \:=\:32 \:\equiv\:1\text{ (mod 31)}$

. . The equation becomes: .$\displaystyle (2^5)^{60} + 7x \:\equiv\:14\text{ (mod 31)}$

We have: .$\displaystyle 1^{60} + 7x \:\equiv\:14\text{ (mod 31)}$

. . . . . . . . . $\displaystyle 1 + 7x \:\equiv\:14 \text{ (mod 31)}$

. . . . . . . . . . . .$\displaystyle 7x \:\equiv\:13\text{ (mod 31)}$

. . . . . . . . . . . . .$\displaystyle x \:\equiv\:24\text{ (mod 31)}$

Therefore: .$\displaystyle x \;=\;\{\hdots\:\text{-}69,\,\text{-}38,\, {\color{red}\text{-}7},\,24,\,55,\,86\,\hdots \}$