4
$\begingroup$

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.

2 Answers 2

8

$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$

  • 2
    @Nusha Marvis used $4^3=64=63+1$2012-11-29
4

$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}\}$