Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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==...")
 
m
 
(One intermediate revision by one other user not shown)
Line 4: Line 4:
 
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> (mod <math>n</math>) <math>\Rightarrow 2^n \equiv -1</math> (mod <math>n</math>). So 2 does not divide <math>n</math>, and so <math>n</math> is odd.
+
<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 21:
  
 
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 01:04, 8 March 2024

Does there exist a positive integer $n$ such that $n$ has exactly 2000 prime divisors and $n$ divides $2^n + 1$?

Solution

Let $N=2^n+1$. We will assume for the sake of contradiction that $n|N$.

$2^n+1 \equiv 0 \pmod{n} \Rightarrow 2^n \equiv -1 \pmod{n}$. So 2 does not divide $n$, and so $n$ is odd.

Select an arbitrary prime factor of $n$ and call it $p$. Let's represent $n$ in the form $p^am$, where $m$ is not divisible by $p$.

Note that $p$ and $m$ are both odd since $n$ is odd. By repeated applications of Fermat's Little Theorem:

$N = 2^n+1 = 2^{p^am} + 1 = (2^{p^{a-1}m})^p + 1 \equiv 2^{p^{a-1}m} + 1$ (mod $p$)

Continuing in this manner, and inducting on k from 1 to $a$,

$2^{p^{a-k}m}+1 \equiv (2^{p^{a-k-1}m})^p + 1$ (mod $p$) $\equiv 2^{p^{a-k-1}m} + 1$ (mod $p$)

So we have $N \equiv 2^m+1$ (mod $p$)

Since $p$ is relatively prime to $m$, $N \equiv 1+1$ (mod $p$) $\equiv 2$ (mod $p$)

Since $p$ is odd, $N$ is not divisible by $p$. Hence $N$ is not divisible by $n$. So we have a contradiction, and our original assumption was false, and therefore $N$ is still not divisible by $n$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_5&oldid=216598"