5
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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}.$$

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

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

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.