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==...")
 
(→‎Solution)
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}}

Revision as of 00:06, 19 November 2023

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$ (mod $n$) $\Rightarrow 2^n \equiv -1$ (mod $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=204477"