Difference between revisions of "2000 IMO Problems/Problem 5"
(Created page with "Does there exist a positive integer <math> n</math> such that <math> n</math> has exactly 2000 prime divisors and <math> n</math> divides <math> 2^n + 1</math>? ==Solution==...") |
(No difference)
|
Revision as of 22:45, 9 April 2021
Does there exist a positive integer such that
has exactly 2000 prime divisors and
divides
?
Solution
Let . We will assume for the sake of contradiction that
.
(mod
)
(mod
). So 2 does not divide
, and so
is odd.
Select an arbitrary prime factor of and call it
. Let's represent
in the form
, where
is not divisible by
.
Note that and
are both odd since
is odd. By repeated applications of Fermat's Little Theorem:
(mod
)
Continuing in this manner, and inducting on k from 1 to ,
(mod
)
(mod
)
So we have (mod
)
Since is relatively prime to
,
(mod
)
(mod
)
Since is odd,
is not divisible by
. Hence
is not divisible by
. So we have a contradiction, and our original assumption was false, and therefore
is still not divisible by
.