A number theory problem by Manav Sinha

By Fermat's Little Theorem, for any natural number n n^{7}  n (mod 7): So for natural numbers q and r, n^{7q+r}  (n^{7})^{q}.n^{r} (mod 7)  n^{q}.n^{r] (mod 7)  n^{q}+r (mod 7): Below we will use this result repeatedly. First though, observe that 2222  3 (mod 7) and 5555  4  −3 (mod 7): Thus 22225555+ 55552222  35555 + (−3)2222 (mod 7)  3793+4 + (−3)317+3 (mod 7)  3113+6 + (−3)45+5 (mod 7)  317+0 + (−3)7+1 (mod 7)  32+3 + (−3)1+1 (mod 7)  32(33 + 1) (mod 7)  32:28 (mod 7)  0 (mod 7): Hence 7 22225555+ 55552222. Solution. (Alternative) The above solution is not a particularly clever way of using Fermat's Little Theorem. Since n^{7} − n factorises as n(n^{6} − 1), it follows from Fermat's Little Theorem that: If n is a natural number and n is not equal to 0 (mod 7) then n^{6} = 1 (mod 7). So for natural numbers n, q and r, if n 6 0 (mod 7) then n^{6q+r}  (n^{6})^{q}.n^{r} (mod 7)  1^{q}.n^{r] (mod 7)  n^{r} (mod 7): In other words, if n 6 0 (mod 7) then we can reduce the power of n modulo 6. (Check the three corollaries to Fermat's Little Theorem in the notes.) Thus 22225555+ 55552222  35555+ (−3)2222 (mod 7)  35 + (−3)2 (mod 7)  32(33 + 1) (mod 7)  32:28 (mod 7)  0 (mod 7):