Difference between revisions of "2003 Indonesia MO Problems/Problem 1"
Rockmanex3 (talk | contribs) (Solution to Problem 1 -- Fermat makes it faster) |
Rockmanex3 (talk | contribs) m (→Solution 2) |
||
Line 14: | Line 14: | ||
<br> | <br> | ||
− | '''Lemma 1: <math>a</math> is divisible by <math>2</math>'''<br> | + | '''Lemma 1: <math>a^9 - a</math> is divisible by <math>2</math>'''<br> |
Obviously if <math>a \equiv 0 \pmod{2},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>2.</math> If <math>a \equiv 1 \pmod{2},</math> then <math>a-1 \equiv 0 \pmod{2},</math> making <math>a^9 - a</math> divisible by <math>2.</math> | Obviously if <math>a \equiv 0 \pmod{2},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>2.</math> If <math>a \equiv 1 \pmod{2},</math> then <math>a-1 \equiv 0 \pmod{2},</math> making <math>a^9 - a</math> divisible by <math>2.</math> | ||
<br> | <br> | ||
− | '''Lemma 2: <math>a</math> is divisible by <math>3</math>'''<br> | + | '''Lemma 2: <math>a^9 - a</math> is divisible by <math>3</math>'''<br> |
Obviously if <math>a \equiv 0 \pmod{3},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>3.</math> If <math>a \equiv 1 \pmod{3},</math> then <math>a-1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>. Also, if <math>a \equiv 2 \pmod{3},</math> then <math>a+1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>. | Obviously if <math>a \equiv 0 \pmod{3},</math> since <math>a</math> is a factor of <math>a^9 - a,</math> the expression is divisible by <math>3.</math> If <math>a \equiv 1 \pmod{3},</math> then <math>a-1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>. Also, if <math>a \equiv 2 \pmod{3},</math> then <math>a+1 \equiv 0 \pmod{3},</math> making <math>a^9 - a</math> divisible by <math>3</math>. | ||
Latest revision as of 20:10, 7 August 2018
Contents
[hide]Problem
Prove that is divisible by
for every integers
.
Solutions
Solution 1
By Fermat's Little Theorem, so
Also,
so
That means
is divisible by
and
so
is divisible by
for every integer
Solution 2
The expression can be factored into
In order to show that
is divisible by
we need to show that
is divisible by
and
Lemma 1: is divisible by
Obviously if since
is a factor of
the expression is divisible by
If
then
making
divisible by
Lemma 2: is divisible by
Obviously if since
is a factor of
the expression is divisible by
If
then
making
divisible by
. Also, if
then
making
divisible by
.
Since we've shown that is divisible by
and
for all
the value
is divisible by
See Also
2003 Indonesia MO (Problems) | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 2 |
All Indonesia MO Problems and Solutions |