1

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} $$

user132586
  • 125

5 Answers5

4

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.

Alex Becker
  • 60,569
  • @egreg Fixed. ${}$ – Alex Becker Apr 13 '14 at 19:47
  • 1
    It's $n^3\equiv n\pmod{3}$ by Fermat's little theorem! The same for $n^7\equiv n\pmod{7}$. – egreg Apr 13 '14 at 19:47
  • Why is $n^2 \equiv 1$? Cant it also be the case that $n^2 \equiv 2$? – user132586 Apr 13 '14 at 19:47
  • 1
    @user132586 Note that I also added $0$. This is Fermat's little theorem. It is also easy to check; $0^2\equiv 0, 1^2\equiv 1, 2^2=4\equiv 1$ and these are the only $3$ possibilities. – Alex Becker Apr 13 '14 at 19:50
  • OH! I see. Its because it is squared. So here is my understanding: We break down the problem into cases: n = 0, n = 1, n = 2. When n = 0, we are gold. When n = 1, we can say that $n \equiv 1 \mod{3}$ when n = 2, $n \equiv 2 \mod{3}$ which means $n^2 \equiv 1 \mod{3}$. This then reduces the entire problem. And for the case mod 7, we do the same for n = 0 - 6. – user132586 Apr 13 '14 at 19:56
  • @user132586 Yes. Although if you know Fermat's little theorem you don't even need to perform that check. – Alex Becker Apr 13 '14 at 19:58
  • I see. So by FlT, we can say that $n^6 \equiv 1 \mod{7}$ since 7 is prime and 7 doesn't divide n since $0 \le n < 7$. – user132586 Apr 13 '14 at 19:59
  • 1
    @user132586 Yes, unless $n\equiv 0\mod 7$. – Alex Becker Apr 13 '14 at 20:00
2

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.

Mark Bennet
  • 100,194
2

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.$

Bill Dubuque
  • 272,048
1

$$ \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} $$

robjohn
  • 345,667
1

$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.

Asimov
  • 3,024