2003 Indonesia MO Problems/Problem 1
Revision as of 18:53, 7 August 2018 by Rockmanex3 (talk | contribs) (Solution to Problem 1 -- Fermat makes it faster)
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 |