# Prove that $10|n+3n^3+7n^7+9n^9$

Prove that $$10|n+3n^3+7n^7+9n^9$$ for every $$n\in \mathbb N$$

Only what i see that 10=5*2 and both number is free numbers, and if I show that $$5|n+3n^3+7n^7+9n^9$$ and $$2|n+3n^3+7n37+9n^9$$ that I prove, since 5 and 2 is free numbers i can use Fermat's little theorem such that $$5|n^5-n$$ and $$2|n^2-n$$ but i can not see that somehow help me, do you have some idea?

• Your tags are totally irrelevant to the question. – Batominovski Oct 31 '18 at 19:01

## 6 Answers

Method 1:We can try factoring but ... I don't want to.

Method 2: Euler's theorem. If $$\gcd(n, 10) = 1$$ then $$n^{\phi(10)}=n^4 \equiv 1\pmod {10}$$ So $$n + 3n^3 + 7n^7 + 9n^9 \equiv n + 3n^3 + 7n^3 + 9n = 10n + 10n^3 \equiv 0 \mod 10$$.

But if $$\gcd(n,10) \ne 1$$???

Well chinese remainder theorem.

$$\mod 2$$ we have $$0^k \equiv 0$$ and $$1^k \equiv 1$$ so $$n^k \equiv n$$ so

$$n + 3n^3 + 7n^7 + 9n^9 \equiv n + n^3 + n^7 + n^9 \pmod 2$$ and $$a^k \equiv a \pmod 2$$ so $$n + n^3 + n^7 + n^9 \equiv 4n \equiv 0 \pmod 2$$

$$\mod 5$$ we have $$\gcd(n,5)$$ means $$n^{5-1} \equiv 1 \pmod {10}$$.

If $$\gcd(n,5)= 1$$ then $$n+3n^3 + 7n^7 + 9n^9 \equiv n + 3n^3 + 2n^3 + 4n \mod 5\\ \equiv 5n +5n^3 \equiv 0 \mod 5$$ But if $$\gcd(n,5) \ne 1$$ the $$\gcd(n,5) = 5$$ so $$n + 3n^3 + 7n^7 + 9n^9 \equiv 0 \mod 5$$.

So $$2|n+3n^3 + 7n^7 + 9n^9$$ and $$5|n+3n^3 + 7n^7 + 9n^9$$ so $$10|n+3n^3 + 7n^7 + 9n^9$$. Always.

====

Actually since $$\phi(10) = \phi(5) = 4$$ we get $$n+3n^3 + 7n^7 + 9n^9 \equiv 10n + 10n^3$$ when $$\gcd(n, 5) \ne 0$$. so the only case to consider is if $$\gcd(n, 5) = 5$$.

i.e. if $$5|n$$.

Well if $$5|n$$ then obviously $$5| n+3n^3 + 7n^7 + 9n^9$$ and just remains to show $$n+3n^3 + 7n^7 + 9n^9$$ is even (when $$5|n$$).

Well, ... that's easy. If $$n$$ is even then it is the sum of four even terms. If $$n$$ is odd it is the sum of $$4$$ odd terms.

• and technically I never used Chinese remainder theorem as it turned out I didn't have to solve anything. – fleablood Oct 31 '18 at 20:11

Denote $$f(n) = n + 3n^3 + 7n^7 + 9n^9$$. The terms in $$f(n)$$ are either all odd or all even, so $$f(n)$$ is even.

By Fermat's little theorem, $$9n^9 \equiv 4n \bmod 5$$ and $$7n^7 \equiv 2n^3 \bmod 5$$. Therefore, $$5 | f(n)$$.

Combining these results, $$10 | f(n)$$.

• The most succint and short Answer among the 7 posted so far....+1 – DanielWainfleet Nov 1 '18 at 7:34

\begin{align} \bmod 10\!:\ f_n & = \ n+9n^9 +\ 3n^3\,+ 7n^7\\ &\equiv n(1\!-\!n^8) + 3n^3(1\!-\!n^4)\ \ \ {\rm by}\ \ \ 9\equiv -1,\,\ 7\equiv -3\\ &\equiv \color{#c00}{n(1\!-\!n^4)}\,g_n \end{align}

Notice that $$\,2,5\mid \color{#c00}{n\,-\,n^5}\$$ by Fermat.

Or, equivalently, $$\,\color{#c00}{n^5\equiv n}\,\Rightarrow\, n^7\equiv n^3,\, n^9\equiv n\$$ so $$\,f_n\equiv (1\!+\!9)n+(3\!+\!7)n^3\equiv 0$$

Hint: $$n+3n^3+7n^7+9n^9\equiv n+3n^3-3n^7-n^9\equiv -(n^4-1)(n)(n^4+3n^2+1)$$ mod 10, so prove $$2|n(n^4-1)$$ and $$5|n^4-1$$ when $$n\neq5k$$ and $$5|n$$ when $$n=5k$$.

• Note that $2$ does not always divide $n(n^4+3n^2+1)$, though. It does always divide $n(n^4-1)$. Likewise, $5$ does not always divide $n^4-1$, but it always divides $n(n^4-1)$. – Batominovski Oct 31 '18 at 19:06
• What about $n=5$? – Batominovski Oct 31 '18 at 19:18
• yes, thanks.... – Nosrati Oct 31 '18 at 19:20

Let $$p(n)=n+3n^3+7n^7+9n^9$$ and let $$r$$ be a remanider when $$n$$ divided by $$5$$. Then we have $$5\mid n-r$$ and $$n-r\mid p(n)-p(r)$$

So $$5\mid p(n) \iff 5\mid p(o)$$

So you have to check if $$p(o)$$ is divisible by $$5$$, for $$o\in\{0,1,2,3,4\}$$ and that shouldn't be difficult.

The same procedure do for $$2$$.

I see many ideas here bit I will try this too.

Notice that all terms are either all evens or all odds, and we have four terms, hence, the number is always even i.e. divisible by 2.

For divisibility by 5, you may check $$0, \pm 1, \pm 2 \pmod 5$$, they are all zero. This is very elementary but efficient since 5 is small.

Now you can conclude that the number is divisible by 10.