Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$

Question

I was checking the following Fermat's little theorem exercise:

Show that $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$

I've started by stating each congruence individually suposing that each $n,6n$ and $4n$ are primes with $11$, for the first one I have:

$$n^{10} \equiv 1 \mod {11}$$ $$ \equiv n^{3} \mod {11}$$

I've stated the second one this way

$$6n^{10} \equiv 1 \mod {11}$$

But honestly I don't know how to go ahead as long as I don't have a number to evaluate with $11$.

Also I'm considering that I have:

$$n + 6n + 4n = 11n$$

This may have some relation with the proof but could be affected because of the powers of each one. Any help will be really appreciated.

Answer 1

From what you shown, we have $$n^{10} \equiv n^{20} \equiv 1 \mod 11$$ and thus $$n^{23} \equiv n^3 \mod 11$$

We also have $$n^{10} \equiv 1 \mod 11$$ and thus we have $$6n^{13} \equiv 6n^3 \mod 11$$

Lastly, we have that the last term is: $$4n^3 \mod 11$$

Adding it all up, we have that this is equivalent to $$n^{23} + 6n^{13} + 4n^3 \equiv n^3 + 6n^3 + 4n^3 \equiv 0 \mod 11$$

Answer 2

Fermat's little theorem only applies when prime $p$ does not divide $a$ in $a^{p-1} \equiv 1 \pmod p$.

In your expression, if $n$ is a multiple of $11$ the theorem doesn't apply but the expression is trivially a multiple of $11$.

If $n$ is not a multiple of $11$ the theorem applies. Now note:

$n^{10} \equiv 1 \pmod{11}$

$n^{20} \equiv 1^2 = 1 \pmod {11}$

So modulo $11$, your expression reduces to $n^3 + 6n^3 + 4n^3 =11n^3$, which is clearly a multiple of $11$.

Answer 3

$$n^{23}+6n^{13}+4n^3\equiv n^3 *n^{20}+6n^3*n^{10}+4n^3(\mod11)$$ By Fermat's little thoerem, $n^{10}\equiv1(\mod 11)$ since 11 is prime.

Therefore $$n^{23}+6n^{13}+4n^3\equiv n^3 *n^{20}+6n^3*n^{10}+4n^3\equiv11n^3\equiv0(\mod 11)$$

Answer 4

You almost have it. By Fermat's theorem $n^{10}\equiv 1 \mod11 $ when $\gcd(n,11)=1$ so $$n^{23},n^{13},n^3\equiv n^3 \mod11$$ $$n^{23}+6n^{13}+4n^{3}\equiv 11n^3\mod11 $$ The result is obvious if $n$ is a multple of $11$. Hence $n^{23}+6n^{13}+4n^{3}$ is a multiple of $11$ for all $n$.

Answer 5

It all comes down to Fermat's little theorem in the end. Here is another way of proceeding, which is sometimes handy when there isn't an easy or obvious way forward. We work modulo $11$ and note that $11$ is prime, so it divides a product if it divides one of the factors.

$$n^{23}+6n^{13}+4n^3\equiv n^3\left(n^{20}-5n^{10}+4\right)\equiv n^3\left(n^{10}-1\right)\left(n^{10}-4\right)$$

[Adjusting the coefficients by multiples of $11$ to get an easy factorisation is the trick, and if it works it can make life somewhat easier]

And if the expression is divisible by $11$ one of the factors must be. And this indicates where to look. One danger here is that factorising further to obtain factors $(n^5\pm 1)$ and $(n^5\pm 2)$ doesn't help much.