# Congruence and division

How can I prove using congruence that $111^{333}+333^{111}$ is divided by 7?

I tried use each factor separately but I didn't really get anywhere. Will appreciate your help.

-

$$111 \equiv -1 \pmod{7} \implies 111^{333} \equiv -1 \pmod{7}$$ $$333 \equiv 4 \pmod{7} \implies 333^{3} \equiv 1 \pmod{7} \implies 333^{111} \equiv 1 \pmod{7}$$ Hence, you get $$111^{333} + 333^{111} \equiv 0 \pmod 7$$

-
how did you get in the second line from 4 mod 7 to 1 mod 7? This is where I was stuck when trying to solve.. –  Mary Nov 29 '12 at 17:35
@Nusha Marvis used $4^3=64=63+1$ –  Mark Bennet Nov 29 '12 at 18:03

$$111\equiv -1\pmod 7\implies 111^{333}\equiv (-1)^{333}=-1$$

$$333\equiv 4\pmod 7=2^2$$

Using Fermat's Little Theorem, $2^{7-1}\equiv 1\pmod 7$

$$333^{111}\equiv (2^2)^{111}\pmod 7\equiv (2^6)^{37}\equiv 1\pmod 7$$

Alternatively, $333^3\equiv 2^6\equiv1$ and $111^9\equiv-1\pmod 7$

So, $7\mid(333^3+111^9)$

But $(333^3+111^9)\mid \{(333^3)^{37}+(111^9)^{37}\}$

-