# Computing $7^{13} \mod 40$

I wanted to compute $7^{13} \mod 40$. I showed that $$7^{13} \equiv 2^{13} \equiv 2 \mod 5$$ and $$7^{13} \equiv (-1)^{13} \equiv -1 \mod 8$$.

Therefore, I have that $7^{13} - 2$ is a multiple of $5$, whereas $7^{13} +1$ is a multiple of $8$. I wanted to make both equal, so I solved $-2 + 5k = + 8n$ for natural numbers $n,k$ and found that $n = 9, k = 15$ gave a solution (just tried to make $3 + 8n$ a multiple of $5$. Therefore, I have that $$7^{13} \equiv -73 \equiv 7 \mod 40.$$

Is this correct? Moreover, is there an easier way? (I also tried to used the Euler totient function, but $\phi(40) = 16$, so $13 \equiv -3 \mod 16$, but I did not know how to proceed with this.)

• hint :$$7^{2} \mod 40 \equiv49\equiv9\\ 7^{4} \mod 40 \equiv9^2\equiv81\equiv81-2(40)=\equiv1\\ 7^{4k} \mod 40 \equiv1$$ Feb 17 '17 at 17:42
• You can also use the Chinese remainder theorem. Feb 17 '17 at 17:43

Yes, easier, by Fermat/Euler (or directly) $\ \color{}{7^{\large 4}\!\equiv 1}\,$ mod $\,5\,$ and $\,8,\,$ thus $\,5,8\mid 7^{\large 4}\!-1.\,$

Thus $\, {\rm lcm}(5,8)\!=\!40\mid \color{#c00}{7^{\large 4}\!-1}.\,$ So $\ {\rm mod}\ 40\!:\ 7^{\large 12}\!\equiv 7(\color{#c00}{7^{\large 4}})^{\large 3}\equiv 7(\color{#c00}1)^{\large 3}\equiv 7$

Remark $\$ See Carmichael's Lambda Theorem for a general way to do this (it combines the Euler totient exponents for each prime power more efficiently using lcm, as done implicitly above).

You don't necessarily have to use the fact $40=8\times 5$ (but if you do, look up "Chinese remainder theorem".)

Otherwise, you know that

$$7^2\equiv 49\equiv 9\pmod{40}.$$

So

$$7^3\equiv 63\equiv 23\pmod{40},$$

so

$$7^4\equiv 161\equiv 1\pmod{40}.$$

Then

$$7^{13}\equiv 7^{4\times 3}\times 7\equiv 1\times 7\equiv 7\pmod{40}.$$

• It’s easy enough to check that $7^4=2401$, maybe even faster than your method. Feb 17 '17 at 17:57
• I fixed a typo for you, assuming you didn't really mean to claim $1\times1\equiv 7$. Feb 17 '17 at 17:59
• Or more easily $7^4\equiv 9^2\equiv 81\equiv 1\bmod 40$ Feb 17 '17 at 18:19

The Carmichael function $\lambda$ is a stronger version of Euler totient function for this purpose which combines different prime factors by $\rm lcm$ rather than simple multiplication, and adjusts higher powers of $2$.

So $\lambda(40) = {\rm lcm}(\lambda(8),\lambda(5)) = {\rm lcm}(2,4) = 4$, and thus the cycle length of $7$ is divisible by $4$. Since $\gcd(7,40)=1$ and $13\equiv 1 \bmod 4$, this immediately gives $7^{13}\equiv 7 \bmod 40$.

$$\phi(40)=16 \to 7^{16}\equiv 1$$mod 40 $$7^{16}\equiv 1 \\7^{13}7^3\equiv 1\\ 343.7^{13}\equiv 1 \\ (320+23).7^{13}\equiv 1\\ 23.7^{13}\equiv 1\\ 23.7^{13}\equiv 1+40 \equiv 1+80\equiv 1+120\equiv 1+160\\ 23.7^{13}\equiv 161 \\23.7^{13}\equiv 7(23)$$ divide by $23$ , $(23,40)=1$ so $$23.7^{13}\equiv 7(23) \to 7^{13}\equiv 7$$

You could note that $\varphi(5) = 5-1 = 4$ and $\varphi(8) = 8- 4 = 4$. Hence $7^4 \equiv 1 \pmod 5$ and $7^4 \equiv 1 \pmod 8$, in which case $7^4 \equiv 1 \pmod{40}$.

Hence $7^{13} \equiv (7^4)^3 \cdot 7 \equiv 7 \pmod{40}$.