Divisibility of $8^{2000}+12^{2000}-5^{2000}-1$

Question

Choose the correct option:

$8^{2000}+12^{2000}-5^{2000}-1$ is divisible by:

$(1)$ $323$

$(2)$ $221$

$(3)$ $299$

$(4)$ $237$

Could someone give me slight hint to solve this problem?

Answer 1

Actually, there are two correct options. $n=8^{2000}+12^{2000}-5^{2000}-1$ is divisible by the primes $13,17,23$ by Fermat's little theorem, so that option $(2)$ and option $(3)$ are correct. Indeed, $221=13\cdot 17$ and $299=13\cdot 23$. Of course, $n$ is also divisible by $2,7,11,41$ and so on, which is not helpful for the question. Concerning the computation, with say $p=13$. By Fermat, $$ 8^{2000}\equiv 1\bmod 13,\; 12^{2000}\equiv 1\bmod 13,\;5^{2000}\equiv 1\bmod 13,\; $$ hence $$ n\equiv 1+1-1-1=0\bmod 13. $$

Answer 2

The expression $E := 8^{2000}+12^{2000}-5^{2000}-1$ will obviously be divisible by $K$ if each term $ \equiv 1 \bmod K$, but may also be divisible by $K$ even if this is not true.

The first thing to do is factor the four numbers given : $323= 17\times 19$, $221 = 13 \times 17$, $299 = 13 \times 23$, $237=3 \times 79$.

Because $16$ divides $2000$, we know from Fermat's Little Theorem that $17$ divides $E$ -- for any $A$ not divisible by $17$, $A^{2000} \equiv (A^{16})^{125} \equiv 1^{125} \equiv 1 \bmod 17$, and then $E \equiv 1+1-1-1 \equiv 0 \bmod 17$

Similarly we know that $3 \not\mid E$, since $8^{2000} \equiv 5^{2000} \equiv 1 \bmod 3$ but $12^{2000} \equiv 0 \bmod 3$, so $E \equiv 1+0-1-1 \equiv -1 \bmod 3$ (eliminating option (4)).

Because $8 = 2^3$, we know that $8^4 \equiv 1 \bmod 13$, and since $5^2 =25 \equiv -1 \bmod 13$, $5^4 \equiv 1 \bmod 13$ also. Clearly $12^4 \equiv-1^4 \equiv 1 \bmod 13$ also and since $4 \mid 2000$ we know that $13 \mid E$.

This gives us answer (2), $221$ as a correct choice since we know $E$ is divisible by both $13$ and $17$.

As it happens, $E$ is also divisible by $23$ but in that case the components of $E$ do not come out to $1 \bmod 23$. So there is another valid answer on the list, $299$, but much more difficult to demonstrate.