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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.