What are $2222^{5555}+5555^{2222} \pmod 7$ and $9^{2n+1}+8^{n+2} \pmod{73}$? Tell me hint for solve :
1) $ 2222^{5555}+5555^{2222} \equiv \mathord? \pmod 7$
2) $ 9^{2n+1}+8^{n+2} \equiv \mathord ?\pmod{73}$
thank you.
 A: for 2>
$9^2 \equiv 8(\mod  73)$ and $8^2 \equiv -9 (\mod73)$
then  $ 9^{2n+1}+8^{n+2} \equiv 9^{2n}.9 + 8^n.8^2 \equiv 8^n.9 + 8^n.(-9) \equiv 0 (\mod 73)$
A: For problem 1) You can show by elementary division that $$2222 \equiv 3 \mod 7$$
Now $$3^6 \equiv 1 \mod 7$$
And therefore (all mod 7)
$$2222^{5555} \equiv 3^{5555} \equiv 3^{6\times 925+5} \equiv 3^5 \mod 7 $$
Now since inverse of 3 is 5 in mod 7, the above becomes $3^6.3^{-1}\equiv 5 \mod 7$
Similarly you can show $5555 \equiv 4 \mod 7$. Now $4^3 \equiv 1\mod7$. So
$$5555^{2222} \equiv 4^{2222} \equiv 4^{3\times 740+2} \equiv 4^2 \equiv 2 \mod 7$$
Therefore the sum will be $0 \mod 7$. This means that it is divisible by 7.
A: (2)I was trying to figure out how the problem came to being.
Observe that $73=8\cdot9+1$
Replacing $8$ with $a$ we get $a(a+1)+1=a^2+a+1$
Now as the root of $a^2+a+1=0$  are the imaginary cube roots of $1,$
let $\omega$ be one of the imaginary cube roots of $1.$
So, $\omega^3=1\implies \omega^{3n}=1$ 
$\omega^{3n+2m+n}=\omega^{2m+n}$
Now,$\omega^{3n+2m+n}=(\omega^2)^{m+2n}=\{-(1+\omega)\}^{m+2n}=(-1)^m (1+\omega)^{m+2n}$
So, $\omega^{2m+n}=(-1)^m (1+\omega)^{m+2n}$
So, $\omega$ is a root of $x^{2m+n}-(-1)^m (1+x)^{m+2n}=0$
$\implies(x-\omega)\mid \{x^{2m+n}-(-1)^m (1+x)^{m+2n}\}$
Similarity, $\omega^2$ is a root,$\implies (x-\omega^2)\mid \{x^{2m+n}-(-1)^m (1+x)^{m+2n}\}$
But we know, $(x-\omega)(x-\omega^2)=x^2+x+1$
So, $$x^{2m+n}-(-1)^m (1+x)^{m+2n}\equiv0\pmod{x^2+x+1}$$ 
Once derived, it can be verified using Congruence like following:
As $1+x\equiv-x^2\pmod{x^2+x+1}$ and $x^3\equiv1\pmod{x^2+x+1},$
$(1+x)^{m+2n}\equiv(-x^2)^{m+2n}\pmod{x^2+x+1}\equiv(-1)^{m+2n} x^{2m+4n}\equiv(-1)^m x^{2m+n} (x^3)^n$
or, $(1+x)^{m+2n}\equiv (-1)^m x^{2m+n}\pmod{x^2+x+1}$
or, $(1+x)^{m+2n}(-1)^m\equiv  x^{2m+n}$
Here in this problem, $x=8,m=1$
(1)$$2222\equiv3\pmod 7\implies 2222^5\equiv 3^5\pmod 7\equiv3^3\cdot3^2\equiv(-1)9\equiv5$$
$$5555\equiv4\pmod 77\implies 5555^2\equiv4^2\pmod7\equiv 2$$
So, $$2222^5+5555^2\equiv5+2\pmod 7\equiv 0$$
But , $$(2222^5+5555^2)\mid\{(2222^5)^{1111}+(5555^2) ^{1111} \} $$
