# Congruences: stumped by minus sign

• May 2nd 2009, 10:21 AM
glowplug19
Congruences: stumped by minus sign
This is my first post. I am practicing simple congruence theory to solve divisibility problems.

For example, to show $13\mid3^{n+2}+4^{2n+1}$:
$3^n3^2+(4^2)^n4 \bmod 13 \equiv 3^n9+3^n4 \equiv 3^n(9+4) \equiv 3^n(13) \equiv 3^n(0) \equiv 0 \bmod 13$, which is what we set out to prove.

This works very well for all the problems I've been working on, but there is one with a minus sign that is throwing me off:

Show: $7\mid5^{2n}+3\cdot2^{5n-2}$.

Any suggestions?
• May 2nd 2009, 10:29 AM
Moo
Hello,

Yep !

Either you find the multiplicative inverse of $2^2$ modulo 7, that is a such that $4a\equiv 1(\bmod 7)$ (you can see that a=2)
And hence $2^{-2}=4^{-1} \equiv 2 (\bmod 7)$

Either you use Fermat's little theorem :
$\text{gcd}(2,7)=1 \Rightarrow 2^{7-1}=2^6 \equiv 1 (\bmod 7)$

So
\begin{aligned}
5^{2n}+3\cdot2^{5n-2} & \equiv 5^{2n}+3\cdot 2^{5n-2} \cdot 5^6 (\bmod 7) \\
&\equiv 5^{2n}+3\cdot 2^{5n+4} (\bmod 7) \end{aligned}
• May 3rd 2009, 10:01 AM
glowplug19
Great. Thanks. So I have to find a workaround to my original method for negatives, in this case, Fermat's little thm.

Thank you.
• May 3rd 2009, 12:57 PM
Moo
Quote:

Originally Posted by glowplug19
Great. Thanks. So I have to find a workaround to my original method for negatives, in this case, Fermat's little thm.

Thank you.

But remember that Fermat's little theorem works for prime numbers only ;)

If you had to deal modulo n, where n is not necessarily prime, use Euler's theorem (Euler's theorem - Wikipedia, the free encyclopedia)

Otherwise, in order to find the multiplicative inverse of a number modulo n (which exists if this number is coprime with n), use trial and error or (better :p) the extended Euclidean algorithm (Extended Euclidean algorithm - Wikipedia, the free encyclopedia)