Thread: Congruences: stumped by minus sign

1. Congruences: stumped by minus sign

This is my first post. I am practicing simple congruence theory to solve divisibility problems.

For example, to show $\displaystyle 13\mid3^{n+2}+4^{2n+1}$:
$\displaystyle 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: $\displaystyle 7\mid5^{2n}+3\cdot2^{5n-2}$.

Any suggestions?

2. Hello,

Yep !

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

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

So
\displaystyle \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}

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

Thank you.

4. 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 ) the extended Euclidean algorithm (Extended Euclidean algorithm - Wikipedia, the free encyclopedia)