$ 2222^{5555}+5555^{2222} \equiv \mathord? \pmod 7,\quad 9^{2n+1}+8^{n+2} \equiv\mathord ?\pmod{73}$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.