# Prove that $n^{30}-n^{14}-n^{18}+n^2$ is divisible by $46410$

I have the following question.

Prove that $n^{30}-n^{14}-n^{18}+n^2$ is divisible by $46410$ for all positive integer $n$.

My attempt:

Firstly, notice that $$n^{30}-n^{14}-n^{18}+n^2$$

$$=n^2(n-1)^2(n+1)^2(n^2+n+1)(n^2-n+1)(n^2+1)^2(n^4-n^2+1)(n^4+1)(n^8+1).$$

Also, $$46410=2\times3\times5\times7\times13\times17$$

My first thought was to use induction, maybe substitute $n+1$ into $n$, then find terms that was already divisible by $46410$, but then I don't think this is a smart way to do it.

Are there any better ways to do it?

• you have made all right, now you can Show the divisibility of $2,3,5,7,13,17$ – Dr. Sonnhard Graubner Aug 6 '17 at 9:23
• Use the fact that $n(n+1)$ is even, $n(n−1)(n+1)$ is multiple of $3$ etc – user261263 Aug 6 '17 at 9:24
• @EugenCovaci Yea I have the same idea, but how can I show the divisibility of $5,7,13,17$? I am stuck at $3$. – blastzit Aug 6 '17 at 9:25
• Prove, for example, $n^{30}-n^{14}-n^{18}+n^2 = 0 \mod 5$ by using Fermat little theorem. – user261263 Aug 6 '17 at 9:30
• – lab bhattacharjee Aug 6 '17 at 10:02

Because it divided by $n^2-n$, by $n^3-n$, by $n^5-n$, by $n^7-n$, by $n^{13}-n$ and by $n^{17}-n$ and use the Fermat's little theorem,

which gives that $n^2-n$ divided by $2$, $n^3-n$ divided by $3$,$n^5-n$ divided by $5$,

$n^7-n$ divided by $7$, $n^{13}-n$ divided by $13$ and $n^{17}-n$ divided by $17$,

which says that our number divided by $2\cdot3\cdot5\cdot7\cdot13\cdot17=46410$

• @Dietrich Burde because $n^{17}-n=n(n^8+1)(n^4+1)(n^2+1)(n-1)(n+1).$ – Michael Rozenberg Aug 6 '17 at 9:33
• @DietrichBurde Because it factors as $(n^{17}-n)(n^{13}-n)$ which gives the factors $13,17$ straight away. If you know you are using Fermat, you look for factors of this form. – Mark Bennet Aug 6 '17 at 9:34
• @DietrichBurde You can just check. – Arthur Aug 6 '17 at 9:34
• If it can be divided by the above, why must is divide 46410? I don't get it. – blastzit Aug 6 '17 at 9:36
• @Arthur oh I get it now! Is it because $n^2-n$ is a multiple of $2$ etc.? – blastzit Aug 6 '17 at 9:39

It's easier if you factor it as $f(n)=n^2(n^{16}-1)(n^{12}-1)$ rather than doing the complete factoring.

Then it is divisible by any prime $p$ such that $p-1\mid 12$ or $p-1\mid 16$. That includes, $2,3,5,7,13,17$.

You also get that if $\phi(p^2)=p(p-1)\mid 12$ or $p(p-1)\mid 16$, then $p^2\mid f(n)$. So you actually get a stronger result, that $2^2\cdot3^2\cdot5\cdot 7\cdot 13\cdot 17\mid f(n)$ for all $n$.

Let $$f(n):=n^{30}-n^{18}-n^{14}+n^2\,.$$ Thus, $$f(n)=\left(n^{13}-n\right)\,\left(n^{17}-n\right)\,.$$ Set $r(n):=n^{13}-n$ and $s(n):=n^{17}-n$.

From here, you can see that $$D(13,1)=\{3,5,7,13\}\,.$$ Thus, $$g(13,1)=2\cdot 3\cdot 5\cdot 7\cdot 13\,.$$ Therefore, $2\cdot 3\cdot 5\cdot 7\cdot 13$ is a factor of $r(n)$, whence also a factor of $f(n)$, for every integer $n$.

On the other hand, the same link gives $$D(17,1)=\{3,5,17\}\,.$$ Consequently, $$g(17,1)=2\cdot 3\cdot 5\cdot 17\,.$$ Ergo, $2\cdot 3\cdot 5\cdot 17$ is a factor of $s(n)$, whence also a factor of $f(n)$, for each $n\in\mathbb{Z}$.

As a result, $$(2\cdot 3\cdot 5\cdot 7\cdot 13)\cdot (2\cdot 3\cdot 5\cdot 17)=2^2\cdot 3^2\cdot 5^2\cdot 7\cdot 13\cdot 17=1392300=30\cdot 46410$$ is a factor of $f(n)$ for every $n\in\mathbb{Z}$. In fact, $$\underset{n\in\mathbb{Z}}{\gcd}\,f(n)=\gcd\big(f(2),f(3)\big)=2^2\cdot 3^2\cdot 5^2\cdot 7\cdot 13\cdot 17=1392300\,.$$

Hint:

Consider the factors of $n^{30}-n^{18}-n^{14}+n^2$ $$(n-1)^2,n^2,(n+1)^2,\left(n^2+1\right)^2,n^2-n+1,n^2+n+1,n^4+1,n^4-n^2+1,n^8+1$$ for any $n>1$ we have an even number and a multiple of $3$ in the first three factors.

With similar arguments it can be shown that at least one of the factor is a multiple of $5,7,11,13,17$ which are the other factors of $46410$.