# Difference between revisions of "2002 Indonesia MO Problems/Problem 1"

Rockmanex3 (talk | contribs) m (→Solution) |
Rockmanex3 (talk | contribs) m (→Solution) |
||

Line 5: | Line 5: | ||

==Solution== | ==Solution== | ||

− | In order for <math>n^4 - n^2</math> to be divisible by <math>12</math>, <math>n^2 | + | In order for <math>n^4 - n^2</math> to be divisible by <math>12</math>, <math>n^4 - n^2</math> must be divisible by <math>4</math> and <math>3</math>. |

<br> | <br> | ||

− | '''Lemma 1: <math>n^2 | + | '''Lemma 1: <math>n^4 - n^2</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>. | 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>. | ||

<br> | <br> | ||

− | '''Lemma 2: <math>n^2 | + | '''Lemma 2: <math>n^4 - n^2</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>. | 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>. | ||

## Revision as of 17:44, 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 .