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 "1982 USAMO Problems/Problem 4"

(→‎Solution: Essentially chooses Fermat Numbers until We get to a composite one, 1+1/2+...+1/32+1/64+1/64=1, will write motivation soon)
m (→‎Solution 2: just removes some random $ signs)
Line 22: Line 22:
 
Consider some cases:
 
Consider some cases:
  
−
When <math>n\equiv1\text{ (mod }2)\iff n=m\ </math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }3)</math>
+
When <math>n\equiv1\text{ (mod }2)\iff n=m</math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }3)</math>
  
−
When <math>n\equiv2\text{ (mod }4)\iff n=2m\ </math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }5)</math>
+
When <math>n\equiv2\text{ (mod }4)\iff n=2m</math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }5)</math>
  
−
When <math>n\equiv4\text{ (mod }8)\iff n=4m\ </math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }17)</math>
+
When <math>n\equiv4\text{ (mod }8)\iff n=4m</math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }17)</math>
  
−
When <math>n\equiv8\text{ (mod }16)\iff n=8m\ </math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }257)</math>
+
When <math>n\equiv8\text{ (mod }16)\iff n=8m</math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }257)</math>
  
−
When <math>n\equiv16\text{ (mod }32)\iff n=16m\ </math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }65537)</math>
+
When <math>n\equiv16\text{ (mod }32)\iff n=16m</math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }65537)</math>
  
−
When <math>n\equiv32\text{ (mod }64)\iff n=32m\ </math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }6700417)</math>
+
When <math>n\equiv32\text{ (mod }64)\iff n=32m</math> we have <math>2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }6700417)</math>
  
−
When <math>n\equiv0\text{ (mod }64)\iff64\mid n\ </math> we have <math>2^n\cdot k+1\equiv k+1\equiv 0 \text{ (mod }641)</math>, since <math>2^{64}\equiv 1  \text{ (mod }641)</math>
+
When <math>n\equiv0\text{ (mod }64)\iff64\mid n</math> we have <math>2^n\cdot k+1\equiv k+1\equiv 0 \text{ (mod }641)</math>, since <math>2^{64}\equiv 1  \text{ (mod }641)</math>
  
 
And furthermore, <math>k>>3,5,17,257,65537,6700417,641</math> so these numbers need be composite.
 
And furthermore, <math>k>>3,5,17,257,65537,6700417,641</math> so these numbers need be composite.

Revision as of 22:03, 21 September 2016

Problem

Prove that there exists a positive integer $k$ such that $k\cdot2^n+1$ is composite for every integer $n$.

Solution 1

Let $p$ be a prime number that divides $2^y-1$ and $x$ be a whole number less than $y$ such that \[k\equiv -1\cdot2^{y-x}\pmod{p}\] If $n-x$ is a multiple of $y$, then, for some integer $r$, \[k\cdot2^{n}\equiv-1\cdot2^{y-x}\cdot2^{x+ry}\pmod{p}\] This simplifies to \[k\cdot2^{n} \equiv -1\pmod{p}\] This implies that $k\cdot2^{n}+1\equiv 0 \pmod{p}$. Thus we conclude that there exists an integer $k$ such that $k\cdot2^{n}+1$ is composite for all integral $n$.

Solution 2

I claim that $\boxed{k=2935363331541925531}$ works

Consider the primes $3,5,7,17,257,65537,6700417,641$

Note that \[k\equiv 1\text{ (mod }3,5,7,17,257,65537,6700417)\] and that \[k\equiv 1\text{ (mod }641)\]

Also, \[\text{ord}_3(2)=2\]\[\text{ord}_5(2)=4\]\[\text{ord}_{17}(2)=8\]\[\text{ord}_{257}(2)=16\]\[\text{ord}_{65537}(2)=32\]\[\text{ord}_{6700417}(2)=2=\text{ord}_{641}(2)=64\]


Take $m$ to be an odd integer.

It is well known (and not hard to prove) that $2^{\frac{\text{ord}_p(2)}{2}\cdot m}\equiv \left(2^{\frac{\text{ord}_p(2)}{2}}\right)^m\equiv -1^m\equiv -1\text{ (mod }p)$

Consider some cases:

When $n\equiv1\text{ (mod }2)\iff n=m$ we have $2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }3)$

When $n\equiv2\text{ (mod }4)\iff n=2m$ we have $2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }5)$

When $n\equiv4\text{ (mod }8)\iff n=4m$ we have $2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }17)$

When $n\equiv8\text{ (mod }16)\iff n=8m$ we have $2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }257)$

When $n\equiv16\text{ (mod }32)\iff n=16m$ we have $2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }65537)$

When $n\equiv32\text{ (mod }64)\iff n=32m$ we have $2^n\cdot k+1\equiv -k+1\equiv 0 \text{ (mod }6700417)$

When $n\equiv0\text{ (mod }64)\iff64\mid n$ we have $2^n\cdot k+1\equiv k+1\equiv 0 \text{ (mod }641)$, since $2^{64}\equiv 1 \text{ (mod }641)$

And furthermore, $k>>3,5,17,257,65537,6700417,641$ so these numbers need be composite.

But this covers all cases; we are done $\Box$

See Also

1982 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1982_USAMO_Problems/Problem_4&oldid=80350"