Prove that $(11 \cdot 31 \cdot 61) | (20^{15} - 1)$

Question

Prove that $$ \left( 11 \cdot 31 \cdot 61 \right) | \left( 20^{15} - 1 \right) $$

---

Attempt:

I have to prove that $20^{15}-1$ is a factor of $11$, $31$, and $61$. First, I will prove $$ 20^{15} \equiv 1 \bmod11 $$

Notice that $$ 20^{10} \equiv 1 \bmod 11$$ $$ 20^{5} \equiv 9^{5} \bmod 11 = 9^{4} 9 \bmod 11, \:\: 9^{2} \equiv 4 \bmod 11 $$ $$ \implies 9^{5} \equiv 144 \bmod 11 \implies 20^{5} \equiv 1 \bmod 11 $$ Then the proof is done.

Now I will prove: $$ 20^{15} \equiv 1 \bmod 31 $$

Notice $20^{2} \equiv 28 \bmod 31$, so $$20 \times (20^{2})^{7} \equiv 20 \times (28)^{7} \bmod 31 \equiv 20 \times (-3)^{7} \bmod 31 \equiv -60 \times 16 \bmod 31\equiv 32 \bmod 31 $$

then the proof is done.

Also, in similar way to prove the $20^{15} \equiv 1 \bmod 61$.

Are there shorter or more efficient proof?

Answer 1

$$20\equiv3^2\pmod{11}$$

$20^{15}\equiv(3^2)^{15}\equiv(3^{10})^3\equiv1^3$ by Fermat's Little Theorem

$$20=2^2\cdot5,\implies20^{15}\equiv2^{30}5^{15}$$

By Fermat's Little Theorem

$$2^{30}\equiv1\pmod{31},5^3\equiv1\pmod{31}\implies5^{15}=(5^3)^5\equiv1^5$$

Again $5^3\equiv3\pmod{61},2^6\equiv3$

$$20^{15}\equiv(2^6)^5(5^3)^5\equiv3^5\cdot3^5\pmod{61}$$

Finally $3^5=243\equiv-1\pmod{61}$

Answer 2

$20\equiv3^2\pmod{11}$ therefore $20^{15} \equiv 3^{30}\equiv 1 \bmod11$. $20\equiv12^2\pmod{31}$ therefore $20^{15} \equiv 12^{30}\equiv 1 \bmod31$. $20\equiv3^4\pmod{61}$ therefore $20^{15} \equiv 3^{60}\equiv 1 \bmod61$.

Answer 3

A variant, with lil' Fermat:

• As $20$ is not divisible by $11$, we have $20^{15}\equiv 1\mod11 $.

• $2^{30}\equiv 1\mod 31$ and $2^{15}\equiv-1\mod 31$, so $(-2)^{15}\equiv 5^{15}\equiv 1\mod 31$.

• $2^6\equiv 3\equiv 5^3$, so $\;2^{30}5^{15}\equiv 9^5\mod 61$. Now $9^2\equiv 20$, so $9^3\equiv 180\equiv-3$ and ultimately $9^5\equiv -60\equiv 1\mod 61$.

Answer 4

Alternatively: $$\left( 11 \cdot 31 \cdot 61 \right) | \left( 20^{15} - 1 \right)=(20^5-1)(20^{10}+20^5+1)\\ 20^5\equiv (-2)^5\equiv -32\equiv 1 \pmod{11}\\ 20^5\equiv 81^5\equiv 3^{20}\equiv (3^5)^4 \equiv1 \pmod{61}\\ 20^5 \equiv (2^{5})^2\cdot (5^2)^2\cdot 5\equiv 1^2\cdot (-6)^2\cdot 5\equiv 25\pmod{31}\\ 20^{10}\equiv (20^5)^2\equiv 25^2 \equiv (-6)^2\equiv 5\pmod{31}\\ 20^{10}+20^5+1\equiv 5+25+1\equiv 0\pmod{31}$$ Note: The idea is to use the formula $a^3-b^3=(a-b)(a^2+ab+b^2)$ and decrease the exponent.