Prove that $3n^7 + 7n^3 + 11n$ is divisible by $21$ for all integers $n$

Question

Prove that $3n^7 + 7n^3 + 11n$ is divisible by $21$ for all integers $n$

I needed some help solving this. I know that we must show that it is divisible by 3 and 7 but how do I show that

$$ 3n^7 + 7n^3 + 11n \equiv 0 \mod{3} $$

Answer 1

Note that $n^3\equiv n\mod 3$ since $n^2\equiv 1\text{ or } 0\mod 3$. Thus the equation becomes $$0+n+2n \equiv 0\mod 3$$ which is clearly true. For $7$ the strategy is similar, since $n^7\equiv n\mod 7$ so the equation becomes $3n+0+4n\equiv 0\mod 7$ which is again clearly true.

Answer 2

$3n^7$ must be divisible by 3, so we dont have to worry about it. If n is 0 mod 3 then it always works out. If n is 1 mod 3, then n^3 will be 1 mod 3 and n will be 1 mod 3, and since there are 18 times 1 mod 3 terms, it is 0 mod 3 all together. If n is 2 mod 3 then n^3 will be 2 mod 3 and n will be 2 mod 3. Once again its 18*2 mod 3 =0.

Answer 3

Note that $$3n^7+7n^3+11n=3(n^7+2n^3+4n)+n^3-n=3(n^7-n)+7(n^3+2n)$$

And that $n^p\equiv n \mod p$.

For $n=3$ this is easy to see anyway because $n^3-n=(n-1)n(n+1)$ is the product of three consecutive integers.

Answer 4

Hint $\,\ \color{#c00}3\mid 7(\color{#c00}{n^3\!-\!n})+\color{#c00}3(6n\!+\!n^7)\,$ by $\,\color{#c00}3\mid\color{#c00}{n^3\!-\!n} = (n\!-\!1)n(n\!+\!1),\,$ by one of $\,3\,$ consecutive integers is a multiple of $\,3;\,$ or use little Fermat $\,n^3\equiv n\pmod 3,\,$ or use $\,n^3\!-n = 6 {n+1\choose 3}$.

Remark $\ $ Generally for primes $\,p\ne q\!:\,\ pq\mid pn^q\!+\!qn^p\! + (kpq-p-q)n =: r\ $ since

$\,{\rm mod}\ p\!:\ n^p\equiv p\,\Rightarrow\, r\equiv qn-qn\equiv 0,\,$ so $\,p\mid r.\,$ By $\,p\leftrightarrow\,q $ symmetry $\,q\mid r,\,$ hence $\,pq\mid r\,$ since $\,{\rm lcm}(p,q) = pq\, $ by $\,p,q\,$ coprime. Yours is the special case $\,k,p,q = 1,3,7.$

Answer 5

$$ \begin{align} &\small3n^7+7n^3+11n\\ &\small=21\left[720\binom{n}{7}+2160\binom{n}{6}+2400\binom{n}{5}+1200\binom{n}{4}+260\binom{n}{3}+20\binom{n}{2}+\binom{n}{1}\right] \end{align} $$