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==...") |
(→Solution) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 2: | Line 2: | ||
==Solution== | ==Solution== | ||
+ | THIS SOLUTION IS WRONG.. ANOTHER SOLUTION IS NEEDED.. | ||
+ | |||
Let <math>N=2^n+1</math>. We will assume for the sake of contradiction that <math>n|N</math>. | Let <math>N=2^n+1</math>. We will assume for the sake of contradiction that <math>n|N</math>. | ||
− | <math>2^n+1 \equiv 0 | + | <math>2^n+1 \equiv 0 \pmod{n} \Rightarrow 2^n \equiv -1 \pmod{n}</math>. So 2 does not divide <math>n</math>, and so <math>n</math> is odd. |
Select an arbitrary prime factor of <math>n</math> and call it <math>p</math>. Let's represent <math>n</math> in the form <math>p^am</math>, where <math>m</math> is not divisible by <math>p</math>. | Select an arbitrary prime factor of <math>n</math> and call it <math>p</math>. Let's represent <math>n</math> in the form <math>p^am</math>, where <math>m</math> is not divisible by <math>p</math>. | ||
Line 21: | Line 23: | ||
Since <math>p</math> is odd, <math>N</math> is not divisible by <math>p</math>. Hence <math>N</math> is not divisible by <math>n</math>. So we have a contradiction, and our original assumption was false, and therefore <math>N</math> is still not divisible by <math>n</math>. | Since <math>p</math> is odd, <math>N</math> is not divisible by <math>p</math>. Hence <math>N</math> is not divisible by <math>n</math>. So we have a contradiction, and our original assumption was false, and therefore <math>N</math> is still not divisible by <math>n</math>. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2000|num-b=4|num-a=6}} |
Latest revision as of 15:39, 5 August 2024
Does there exist a positive integer such that
has exactly 2000 prime divisors and
divides
?
Solution
THIS SOLUTION IS WRONG.. ANOTHER SOLUTION IS NEEDED..
Let . We will assume for the sake of contradiction that
.
. 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
.
See Also
2000 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |