3
$\begingroup$

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?

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

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$

$\endgroup$
  • $\begingroup$ @Dietrich Burde because $n^{17}-n=n(n^8+1)(n^4+1)(n^2+1)(n-1)(n+1).$ $\endgroup$ – Michael Rozenberg Aug 6 '17 at 9:33
  • $\begingroup$ @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. $\endgroup$ – Mark Bennet Aug 6 '17 at 9:34
  • $\begingroup$ @DietrichBurde You can just check. $\endgroup$ – Arthur Aug 6 '17 at 9:34
  • $\begingroup$ If it can be divided by the above, why must is divide 46410? I don't get it. $\endgroup$ – blastzit Aug 6 '17 at 9:36
  • 1
    $\begingroup$ @Arthur oh I get it now! Is it because $n^2-n$ is a multiple of $2$ etc.? $\endgroup$ – blastzit Aug 6 '17 at 9:39
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.