# Divisibility of an expression

Need some guidance

How to prove that $9\cdot n^9+7\cdot n^7+3\cdot n^3+n$ is divisible by $10$.

I've tried transforming the expression by adding $n^9$ and $-n^9$ in order to make a multiple of 10 but no use. I've even tried math. induction but got stuck, maybe this can not be proven. Are there any other methods?

• One thing that can be done for certain, although it might take some time is considering all five cases where $n$ gives different remainders mod $5$ and showing that your expression is always congruent to $0$ mod $5$. Then it's enough to show that it's even and that's pretty obious (if $n$ is even then you're looking at a sum of $4$ even numbers, if it's odd at a sum of $4$ odd numbers).
– Kuba
Nov 28, 2015 at 19:12
• In fact, you can see that if $n$ is even or odd, the expression is still even, so it is sufficient to check that it is congruent to $0$ mod $5$. Do you how to reduce the powers mod $5$? This will keep the numbers relatively small, and reduce the amount of manual checking you have to do.
– user208649
Nov 28, 2015 at 19:16

Let $P$ be a polynomial: $P(n)=9n^9+7n^7+3n^3+n$.

$P(n)$ is even for any $n$, because if $n$ is even then you're looking at a sum of $4$ even numbers, if it's odd at a sum of $4$ odd numbers.

Then you only have to prove that $5|P(n)$.

Notice that $n^5\equiv_5 n$ for any $n$. (Proved at the end)

Then $P(n)\equiv_5 -n^9-3n^7+3n^3+n \equiv_5 -n^4n^5-3n^2n^5+3n^3+n \equiv_5 -n^5 - 3n^3 + 3n^3 + n = \ \ n - n^5 \equiv_5 0$

Here's a nice proof of $5|n^5-n$:

$$n^5-n=n(n^4-1)=n(n^2-1)(n^2-1)=n(n^2-1)(n^2+5-4)=n(n^2-1)(n^2-4)+5n(n^2-1) = (n-2)(n-1)n(n+1)(n+2)+5(n-1)n(n+1)$$

Which is a sum of a product of five consecutive integers and something divisible by $5$.

It is sufficient to check 2 and 5 divide this expression. Since, you have an even number of terms with same parity, 2 divides it. $$9\cdot n^9+7\cdot n^7+3\cdot n^3+n \cong 4n^9 + 2n^7 + 3 n^3 +n\ mod\ 5$$

If $gcd(n, 5) =1$, then by Fermat little theorem: $$n^ 4 \cong 1\ mod \ 5$$ Therefore, $4n^9 + 2n^7 + 3 n^3 +n \cong 4n + 2n^3 + 3 n^3 +n \cong 5n + 5n^ 2 \ mod \ 5$

Note: If $gcd(n, 5) \neq 1 \Rightarrow gcd(n, 5) = 5$, which makes divisibility by 5 trivial.

• Not true if $5\mid n$. Nov 28, 2015 at 19:21
• @user236182 you are absolutely right, thank you for the correction. Nov 28, 2015 at 19:22