4
$\begingroup$

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$.


I was thinking of using induction, but wasn't really sure how to do it.

$\endgroup$
12
  • 3
    $\begingroup$ Maybe you should use induction. $\endgroup$ – ThorbenK Apr 29 '15 at 14:48
  • $\begingroup$ That is what I was thinking, but wasn't really sure how to do it. $\endgroup$ – Riley Apr 29 '15 at 14:50
  • 1
    $\begingroup$ I think induction has no thing to do insuch questions, usually use conguruency $\endgroup$ – Nizar Apr 29 '15 at 14:51
  • 1
    $\begingroup$ $(k^2-1)k^2(k^2+1)$ divided by $3.4.5$ gives A213547 $\endgroup$ – JMP Apr 29 '15 at 15:22
  • 1
    $\begingroup$ @quid No, it isn't. It can use that approach or others. $\endgroup$ – Joffan Apr 29 '15 at 17:21

11 Answers 11

11
$\begingroup$

Hint: $$ n^2(n^2+1)(n^2−1)\cong n^2(n^2-4)(n^2−1) = (n-2)(n-1)(n^2)(n+1)(n+2) $$

$\endgroup$
1
  • 1
    $\begingroup$ This is by far the best answer. Definitely a very neat way to look at it. $\endgroup$ – Cameron Williams Apr 29 '15 at 16:05
7
$\begingroup$

Hint: Compute $n^2\bmod 5$ for $n=0,1,2,3,4$.

$\endgroup$
6
  • $\begingroup$ How can you justify that checking for these five cases settles the question for any $n$ ? $\endgroup$ – Yves Daoust Apr 29 '15 at 16:22
  • $\begingroup$ @YvesDaoust That's because we only need to consider $n^2(n^2+1)(n^2-1)\pmod5$ $\endgroup$ – Kitegi Apr 29 '15 at 16:32
  • $\begingroup$ @YvesDaoust If the only operations are addition and multiplication, then there are no problems. $$P(n)\pmod5 =P(n\pmod5)$$ $\endgroup$ – Kitegi Apr 29 '15 at 16:40
  • 1
    $\begingroup$ @Farnight: that needs to be said. $\endgroup$ – Yves Daoust Apr 29 '15 at 16:46
  • $\begingroup$ @YvesDaoust I don't think it needs to be mentioned. It's one of the most basic rules of modular arithmetic. $\endgroup$ – Kitegi Apr 29 '15 at 16:50
4
$\begingroup$

${\rm mod}\ 5\!:\,\ \color{#c00}n^2(\color{#0a0}{n^4-1})\equiv 0\, $ by $\,\color{#c00}{n\equiv 0}\,$ or $\,\color{#0a0}{n^4\equiv 1}\,$ by little Fermat.

Or, directly $\,\color{#c00}{n\equiv 0}\ $ or $\ n\equiv \pm1,\pm2\,\Rightarrow\, n^2\equiv \pm1\,\Rightarrow\, \color{#0a0}{n^4\equiv 1}$

$\endgroup$
3
$\begingroup$

Notice that $(n^2 - 1)(n^2 + 1) = n^4 - 1$. Fermat's little theorem tells us that $n^4 \equiv 1 \pmod 5$. This means that $n^4 - 1$ is a multiple of $5$ if $n$ is not, and therefore $n^2 (n^4 - 1)$ is also a multiple of $5$. For example, if $n = 2$, then $n^4 - 1 = 15$ and $n^2 (n^2 - 1)(n^2 + 1) = 60$.

This leaves us the case where $n$ is a multiple of $5$ to consider. Obviously $n^4 - 1$ is not a multiple of $5$. But $n^2$ is. For example, $n = 5$ gives us $15600$.

$\endgroup$
2
$\begingroup$

$n^2(n^2+1)(n^2-1)=n^2(n^4-1)$ and $n^4\equiv1\mod5$ by FLT for $n\in\{1,2,3,4\}$

Or, as FLT also states that $a^{p-1+k}\equiv a^k \mod p$, and as the equation is $n^6-n^2$, the fact is immediate.

$\endgroup$
2
$\begingroup$

If one wishes to use induction:

The statement holds for $n=0$, so let us assume it's true for $n=k$: $$k^2(k^2+1)(k^2-1)=(k-1)k^2(k+1)(k^2+1)=5m $$ and consider it for $n=k+1$. We have $$(k+1)^2((k+1)^2+1)((k+1)^2-1)=\\ (k+1)^2(k^2+2k+2)(k^2+2k)=\\ k(k+1)^2(k+2)(k^2+2k+2).$$ Suppose this isn't a multiple of $5$. Then none of its factor is, so our inductive hypothesis yields that for some integer $a,b$ either $k-1=5a$ or $k^2+1=5b$, or both:

  • if both, then $$(k-1)+(k^2+1)=k(k+1)=5(a+b),$$ contradiction;
  • if only the former, we have $$k+4=5(a+1),$$ whence $$ k^2+2k+2=25(a+1)^2-6k-14=25(a+1)^2-2(3k+7)=\\25(a+1)^2-2(3(k-1)+10)=5\left(5(a+1)^2-2\left(\frac{3(k-1)}{5}+2\right)\right),$$ contradiction;
  • if only the latter, we also have for some integer $c$ $$k+3=5c,$$ whence $$k^2+2k+2=k^2+2k+7-5=(k^2+1)+2(k+3)-5=5(b+2c)-5=5(b+2c-1),$$ contradiction.
$\endgroup$
6
  • $\begingroup$ @rank Oops, of course, thanks. $\endgroup$ – Vincenzo Oliva Apr 29 '15 at 17:01
  • 2
    $\begingroup$ I don't see where you've used the inductive hypothesis -- the substitution of $5m$ for $k^2(k^2+1)(k^2-1)$ is never used in the block of equations for the next case! $\endgroup$ – Barry Cipra Apr 29 '15 at 17:20
  • $\begingroup$ @Joffan, is it really a proof by induction if the proof doesn't make use of the inductive hypothesis? $\endgroup$ – Barry Cipra Apr 29 '15 at 17:23
  • $\begingroup$ @BarryCipra, Joffan Agreed, I did feel it was similar to what another answer had done, but didn't realize I wasn't doing induction. How about now? I dodn't make the substitution you refer to, but I do use that equation, right? $\endgroup$ – Vincenzo Oliva Apr 29 '15 at 22:51
  • $\begingroup$ @Joffan How about now? $\endgroup$ – Vincenzo Oliva Apr 29 '15 at 22:52
1
$\begingroup$

In case $n$ is a multiple of $5$ the $n^2$ on the rhs is also.

If $n=2,3\pmod 5$ then $n^2\equiv4\pmod5$ , hence $n^2+1$ would be a multiple of $5$.

In the remaining cases, i.e.,$n=1,4\pmod 5$ then in $n^2-1= (n+1)(n-1)$ one of the term on the right will be a multiple of $5$.

So $n^2(n^2+1)(n^2-1)$ is always a multiple of $5$.

$\endgroup$
1
$\begingroup$

Fermat's Little Theorem: $p$ prime $\,\Rightarrow\, a^p\equiv a\pmod {p}$.

Proof: Clearly $0^p\equiv 0$. Assume $a^{p}\equiv a$. Then $$(a+1)^p\,\stackrel{\text{BT}}\equiv \,a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots+\binom{p}{p-1}a+1\equiv a^p+1\stackrel{\text{ind. hyp.}}\equiv a+1$$

$\text{BT}$ refers to binomial theorem. I used $\binom{p}{i}\equiv 0,\,\forall i\in\{1,2,\ldots,p-1\}$.

It follows from $\binom{p}{i}=\frac{p!}{(p-i)!i!}$ and $p\mid p!,\ \ p\nmid (p-i)!i!$.

$5$ prime $\,\Rightarrow\, n^2(n^2+1)(n^2-1)\equiv n^2(n^4-1)\equiv n(n^5-n)\equiv n\cdot 0\equiv 0\pmod {5}$.

$\endgroup$
0
1
$\begingroup$

Here's a proof based on the fact that among any five consecutive numbers, one of them must be divisible by $5$.

Suppose that $n^2(n^2+1)(n^2-1)$ is not divisible by $5$. Then either $n^2+2$ or $n^2-2$ is divisible by $5$. Let's write this as $n^2+2\sigma=5k$, where $|\sigma|=1$.

But if $n^2(n^2+1)(n^2-1)$ is not divisible by $5$, then neither is $n(n^2-1)=n(n+1)(n-1)$, and therefore $5$ divides either $n-2$ or $n+2$. Let's write this as $n+2\tau=5h$ with $|\tau|=1$.

Combining these cleverly, we can conclude $n^2-\sigma\tau n=5(k-\sigma\tau h)$, which implies $5$ divides $n(n-\sigma\tau)$, where $|\sigma\tau|=1$. But that implies $5$ divides $n(n-1)(n+1)$, which is a contradiction. Therefore $5$ must divide $n^2(n^2+1)(n^2-1)$.

$\endgroup$
1
  • $\begingroup$ I was liking where this was going in the first paragraph. If there was a way to do a half-upvote, I would. $\endgroup$ – user155234 Apr 30 '15 at 21:29
0
$\begingroup$

If $n$ is divisible by five, then $n^2(n^2+1)(n^2-1)$ is divisible by $5$, since $n^2$ is a factor.

Now suppose that $n$ is not divisble by $5$. Then $n=5m+r$ for some $r=1,2,3,4$. Note that $(n^2 + 1)(n^2-1) = n^4-1$.

$$n^4 = (5m+r)^4 = (5m)^4 + 4 (5m)^3r + 6 (5m)^2 r^2 + 4 (5m) r^3 + r^4$$ by the binomial theorem. We see then that $n^4 = 5\cdot M + r^4$ for some $M$. Now we just need to show that $r^4-1$ is divisible by $5$ to establish that $n^4-1$ is divisible by $5$.

This does follow by Fermat's little theorem. If that sounds foreign to you, it's easy enough to check by hand. $r$ can take four different values, $1,2,3,4$ (remember we already assumed that $r\neq 0$ since we are assuming $n$ is not divisble by $5$).

$$1^4 -1 = 0$$ $$2^4 -1= 15$$ $$3^4 - 1 = 80$$ $$4^4 - 1 = 255$$

Thus we see that, if $n$ is not divisible by $5$, then $$n^4 -1 = 5 M + r^4 - 1$$ and both $5M$ and $r^4 - 1$ are divisible by five. Therefore, $n^4-1$ is divisible by five, and $$n^2(n^2+1)(n^2-1) = n^2(n^4-1)$$ is divisible by $5$.

$\endgroup$
-1
$\begingroup$

Lemma:

For any polynomial of integer coefficients $P(n)$, $n=0,1,2,3,4$ exhaust the possible values of $P(n)\bmod 5$.

Indeed for any $a$, $(n+a)\bmod 5=(n\bmod5+a)\bmod5$, and $(na)\bmod5=((n\bmod5)a)\bmod5$, so that $P(n)\bmod5=P(n\bmod 5)\bmod5$. QED.

Now, $$0^2(0^4-1)\bmod5=0\\ 1^2(1^4-1)\bmod5=1\cdot0\bmod5=0\\ 2^2(2^4-1)\bmod5=4\cdot15\bmod5=0\\ 3^2(3^4-1)\bmod5=9\cdot80\bmod5=0\\ 4^2(4^4-1)\bmod5=16\cdot255\bmod5=0\\$$

$\endgroup$
5
  • $\begingroup$ The Lemma in congruence form in known as the Polynomial Congruence Rule.. You can cut your work in half by noticing that $\,\, 3\equiv -2,\,$ so $\,3^4\equiv (-2)^4\equiv 2^4\,$ and similarly for $\,4\equiv -1.\ \ $ $\endgroup$ – Bill Dubuque Apr 29 '15 at 17:29
  • $\begingroup$ @BillDubuque: thanks for the pointer. Now we can introduce the "Even Polynomial Congruence Rule". $\endgroup$ – Yves Daoust Apr 29 '15 at 18:31
  • $\begingroup$ Not needed. If $\,P(-n) = P(n)\,$ then $\,{\rm mod}\ m\!:\ m\!-\!n\equiv -n\,\Rightarrow\,P(m\!-\!n)\equiv P(-n) = P(n).\,$ But maybe your remark was in jest? $\endgroup$ – Bill Dubuque Apr 29 '15 at 19:25
  • $\begingroup$ @BillDubuque: I am afraid so :) $\endgroup$ – Yves Daoust Apr 29 '15 at 19:29
  • $\begingroup$ In case you might not know, the reason to explicitly introduce these Congruence Rules is that it makes precise the scope of the rules. Without such, students may try to apply analogous rules to other operations (e.g. exponents in powers) where they are no longer valid. It's difficult to do much better before students learn the appropriate abstract algebraic equivalents (quotient rings), $\endgroup$ – Bill Dubuque Apr 29 '15 at 19:35

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