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 21:10, 7 August 2018
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 |