# Modular arithmetic problem (mod $22$)

$$\large29^{2013^{2014}} - 3^{2013^{2014}}\pmod{22}$$

I am practicing for my exam and I can solve almost all problem, but this type of problem is very hard to me. In this case, I have to compute this by modulo $22$.

This number is obviously even so let's look at it modulo $11$ :

$$29^{2013^{2014}}-3^{2013^{2014}} \equiv 7^{2013^{2014}}-3^{2013^{2014}} \pmod{11}$$

Now look at the powers $7^x$ modulo $11$ and notice that : $$7^{10} \equiv 1 \pmod{11}$$ (this follows also from Fermat's little theorem )

So we need to look at $2013^{2014} \pmod{10}$ .

Use the same method $3^4 \equiv 1 \pmod{10}$ so :

$$2013^{2014} \equiv 3^{2014} \equiv 3^{2012} \cdot 3^2 \equiv 1 \cdot 9 \equiv 9 \pmod{10}$$ Putting them together :

$$7^{2013^{2014}} \equiv 7^9 \equiv 7^{-1} \equiv 8 \pmod{11}$$

We can proceed similarly for the other term because $3^{10} \equiv 1 \pmod{11}$ :

$$3^{2013^{2014}} \equiv 3^9 \equiv 3^{-1} \equiv 4 \pmod{11}$$

This means that :

$$29^{2013^{2014}}-3^{2013^{2014}} \equiv 8-4 \equiv 4 \pmod{11}$$

This number is even so modulo $22$ :

$$29^{2013^{2014}}-3^{2013^{2014}} \equiv 4 \pmod{22}$$

$$29\equiv-4\implies29^{2013^{2014}}\equiv-(2^{\cdot2013^{2014}})^2$$

Again $3\equiv-8\pmod{11},8=-2^3$

$$\implies3^{2013^{2014}}\equiv-(2^{2013^{2014}})^3$$

Now $2^5\equiv-1\pmod{11}\implies2^{10}\equiv1$

and $2013\equiv3\pmod{10},2014\equiv2\pmod{\phi(10)}$

$\implies2013^{2014}\equiv3^2\pmod{10}\equiv-1$

$\implies2^{ 2013^{2014}}\equiv2^{-1}\pmod{11}\equiv6$

$\implies29^{2013^{2014}}-3^{2013^{2014}}\equiv-6^2+6^3=36(6-1)\equiv4\pmod{11}$

and $29^{2013^{2014}}-3^{2013^{2014}}\equiv0\pmod2\equiv4$

$\implies29^{2013^{2014}}-3^{2013^{2014}}\equiv4\pmod{\text{lvm}(11,2)}$

fermat's little theorem (and euler's theorem) is your friend.

22 is coprime to 29 so $29^{\phi(22)} = 29^ {10} \equiv 1 \mod 22$. So $29^{2013^{2014}} \equiv 29^k \mod 22$ where $2013^{2014} \equiv k \mod 10$.

As 10 and 2013 are co-prime $2013^{\phi (10)} = 2013^4 \equiv 1 \mod 10$ so$2013^{2014} \equiv 2013^2 \equiv 3^2 \equiv -1 \mod 10$.

So $29^{2013^{2014}} \equiv 29^{-1} \equiv 7^{-1} \mod 22$

As 22 is coprime to 3, by the exact same reasoning $3^{2013^{2014}} \equiv 3^{-1} \mod 22$.

So $29^{2013^{2014}} - 3^{2013^{2014}} \equiv 7^{-1} - 3^{-1} \equiv a \mod 22$.

Now $21a \equiv -a \equiv (7^{-1} - 3^{-1})7*3 \equiv 3 - 7 \equiv -4 \mod 22$.

So $29^{2013^{2014}} - 3^{2013^{2014}} \equiv a \equiv 4 \mod 22$.