Difference between revisions of "2002 Indonesia MO Problems/Problem 1"
Rockmanex3 (talk | contribs) (→See Also) |
Rockmanex3 (talk | contribs) (→Solution) |
||
Line 5: | Line 5: | ||
==Solution== | ==Solution== | ||
− | In order for <math>n^4 - n^2</math> to be divisible by <math>12</math>, | + | In order for <math>n^4 - n^2</math> to be divisible by <math>12</math>, <math>n^2 (n+1)(n-1)</math> must be divisible by <math>4</math> and <math>3</math>. |
− | If <math>n</math> is even, then <math>n^2 \equiv 0 \pmod{4}</math>. If <math>n \equiv 1 \pmod{4}</math>, then <math>n-1 \equiv 0 \pmod{4}</math>, and if <math>n \equiv 3 \pmod{4}</math>, then <math>n+1 \equiv 0 \pmod{4}</math>. That means for all positive <math>n</math>, <math>n^ | + | <br> |
+ | '''Lemma 1:''' <math>n^2 (n+1)(n-1)</math> is divisible by 4<br> | ||
+ | Note that <math>n^4 - n^2</math> can be factored into <math>n^2 (n+1)(n-1)</math>. If <math>n</math> is even, then <math>n^2 \equiv 0 \pmod{4}</math>. If <math>n \equiv 1 \pmod{4}</math>, then <math>n-1 \equiv 0 \pmod{4}</math>, and if <math>n \equiv 3 \pmod{4}</math>, then <math>n+1 \equiv 0 \pmod{4}</math>. That means for all positive <math>n</math>, <math>n^2 (n+1)(n-1)</math> is divisible by <math>4</math>. | ||
− | If <math>n \equiv 0 \pmod{3}</math>, then <math>n^2 \equiv 0 \pmod{3}</math>. If <math>n \equiv 1 \pmod{3}</math>, then <math>n-1 \equiv 0 \pmod{3}</math>. If <math>n \equiv 2 \pmod{3}</math>, then <math>n+1 \equiv 0 \pmod{3}</math>. That means for all positive <math>n</math>, <math>n^ | + | <br> |
+ | '''Lemma 2:''' <math>n^2 (n+1)(n-1)</math> is divisible by 3<br> | ||
+ | Again, note that <math>n^4 - n^2</math> can be factored into <math>n^2 (n+1)(n-1)</math>. If <math>n \equiv 0 \pmod{3}</math>, then <math>n^2 \equiv 0 \pmod{3}</math>. If <math>n \equiv 1 \pmod{3}</math>, then <math>n-1 \equiv 0 \pmod{3}</math>. If <math>n \equiv 2 \pmod{3}</math>, then <math>n+1 \equiv 0 \pmod{3}</math>. That means for all positive <math>n</math>, <math>n^2 (n+1)(n-1)</math> is divisible by <math>3</math>. | ||
− | Because <math>n^4 - n^2</math> is divisible by <math>4</math> and <math>3</math>, | + | <br> |
+ | Because <math>n^4 - n^2</math> is divisible by <math>4</math> and <math>3</math>, <math>n^4 - n^2</math> must be divisible by <math>12</math>. | ||
==See Also== | ==See Also== |
Revision as of 13:20, 14 July 2018
Problem
Show that is divisible by
for any integers
.
Solution
In order for to be divisible by
,
must be divisible by
and
.
Lemma 1: is divisible by 4
Note that can be factored into
. If
is even, then
. If
, then
, and if
, then
. That means for all positive
,
is divisible by
.
Lemma 2: is divisible by 3
Again, note that can be factored into
. If
, then
. If
, then
. If
, then
. That means for all positive
,
is divisible by
.
Because is divisible by
and
,
must be divisible by
.