Prove that $11^{16} + 16^{11} \equiv 0 \mod {17}$

Question

I was checking the following Fermat's theorem exercise:

Prove that $11^{16} + 16^{11} \equiv 0 \mod {17}$

Because both $11$ and $16$ are primes with $17$ I applied the theorem individually, so the first one

$$11^{16}\equiv 1 \mod {17}$$

gives me a result directly.

But the after applying the theorem to the second one

$$16^{16} \equiv 1 \mod {17}$$

I don't know the way to go back in the power from $16$ to $11$ which is the number requested. Is that as easy as $16 \equiv -1 \mod {17}$? Any help will be really appreciated.

Answer 1

First of all, the Fermat's theorem states that $a^{p-1} \equiv 1 \mod p$ if $p$ is a prime and $p \nmid a$. There is a condition on the exponent. Certainly $11^{16}$ simplifies to $1$ mod $17$ using this theorem.

For the other term, you cannot apply Fermat's theorem, because the exponent is $11$, which although prime is not $17-1$. However, the fact that $16 \equiv -1 \mod 17$, tells you that $16^{11} \equiv (-1)^{11} \equiv -1$ mod $17$. Now you can combine the two terms and conclude.

Answer 2

$$2^4\equiv-1\pmod{17}$$

$$16^{2m+1}=(2^4)^{2m+1}\equiv(-1)^{2m+1}\pmod{17}\equiv?$$

Answer 3

One correct approach:

$11^{16} \equiv 1 \pmod{17}$ by Fermat's Little Theorem. The justification is that $17$ is prime, that $11$ does not divide $17$ and that $16$ is one less than $17$.

$16^{11} \equiv(-1)^{11} \equiv -1 \pmod {17}$. The justification is the rules of modular exponentiation.

Add them up, and you get the required result.