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)
(Removed Solution 1 (nonsense); revised the structure and presentation of Solution 2 (own))
 
(3 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
Prove that there exists a positive integer <math>k</math> such that <math>k\cdot2^n+1</math> is composite for every integer <math>n</math>.
 
Prove that there exists a positive integer <math>k</math> such that <math>k\cdot2^n+1</math> is composite for every integer <math>n</math>.
  
−
== Solution 1 ==
+
== Solution ==
 +
Indeed, <math>\boxed{k=2935363331541925531}</math> has the requisite property.
  
−
Let <math>p</math> be a prime number that divides <math>2^y-1</math> and <math>x</math> be a whole number less than <math>y</math> such that <cmath>k\equiv -1\cdot2^{y-x}\pmod{p}</cmath> If <math>n-x</math> is a multiple of <math>y</math>, then, for some integer <math>r</math>, <cmath>k\cdot2^{n}\equiv-1\cdot2^{y-x}\cdot2^{x+ry}\pmod{p}</cmath> This simplifies to <cmath>k\cdot2^{n} \equiv -1\pmod{p}</cmath> This implies that <math>k\cdot2^{n}+1\equiv 0 \pmod{p}</math>. Thus we conclude that there exists an integer <math>k</math> such that <math>k\cdot2^{n}+1</math> is composite for all integral <math>n</math>.
+
To see why, consider the primes <math>3,\ 5,\ 17,\ 257,\ 65537,\ 6700417,\ 641</math>, and observe that <cmath>\begin{align*}k&\equiv 1\pmod{3}\\ k&\equiv 1\pmod{5}\\ k&\equiv 1\pmod{17}\\ k&\equiv 1\pmod{257}\\ k&\equiv 1\pmod{65537}\\ k&\equiv 1\pmod{6700417}\\ k&\equiv -1\pmod{641}\end{align*}</cmath>
  
−
== Solution 2==
+
Moreover, <cmath>\begin{align*}\text{ord}_{3}\left(2\right)&=2\\ \text{ord}_{5}\left(2\right)&=4\\ \text{ord}_{17}\left(2\right)&=8\\ \text{ord}_{257}\left(2\right)&=16\\ \text{ord}_{65537}\left(2\right)&=32\\ \text{ord}_{6700417}\left(2\right)&=64\\ \text{ord}_{641}\left(2\right)&=64\end{align*}</cmath>
−
I claim that <math>\boxed{k=2935363331541925531}</math> works
 
  
−
Consider the primes <math>3,5,7,17,257,65537,6700417,641</math>
+
We conclude that <cmath>\begin{align*}n\equiv 1\pmod{2}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{3}\\ n\equiv 2\pmod{4}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{5}\\ n\equiv 4\pmod{8}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{17}\\ n\equiv 8\pmod{16}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{257}\\ n\equiv 16\pmod{32}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{65537}\\ n\equiv 32\pmod{64}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{6700417}\\ n\equiv 0\pmod{64}&\implies k\cdot 2^{n}-1\equiv k\cdot1+1\equiv 0\pmod{641}\end{align*}</cmath>
  
−
Note that <cmath>k\equiv 1\text{ (mod }3,5,7,17,257,65537,6700417)</cmath> and that <cmath>k\equiv 1\text{ (mod }641)</cmath>
+
And <math>k>>3,5,17,257,65537,6700417,641</math> so the relevant values will, in fact, always be composite. <math>\blacksquare</math>
−
 
 
−
Also, <cmath>\text{ord}_3(2)=2</cmath><cmath>\text{ord}_5(2)=4</cmath><cmath>\text{ord}_{17}(2)=8</cmath><cmath>\text{ord}_{257}(2)=16</cmath><cmath>\text{ord}_{65537}(2)=32</cmath><cmath>\text{ord}_{6700417}(2)=2=\text{ord}_{641}(2)=64</cmath>
 
−
 
 
−
 
 
−
Take <math>m</math> to be an odd integer.
 
−
 
 
−
It is well known (and not hard to prove) that <math>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)</math>
 
−
 
 
−
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\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\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\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>
 
−
 
 
−
And furthermore, <math>k>>3,5,17,257,65537,6700417,641</math> so these numbers need be composite.
 
−
 
 
−
But this covers all cases; we are done <math>\Box</math>
 
  
 
== See Also ==
 
== See Also ==

Latest revision as of 00:15, 4 June 2021

Problem

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

Solution

Indeed, $\boxed{k=2935363331541925531}$ has the requisite property.

To see why, consider the primes $3,\ 5,\ 17,\ 257,\ 65537,\ 6700417,\ 641$, and observe that \begin{align*}k&\equiv 1\pmod{3}\\ k&\equiv 1\pmod{5}\\ k&\equiv 1\pmod{17}\\ k&\equiv 1\pmod{257}\\ k&\equiv 1\pmod{65537}\\ k&\equiv 1\pmod{6700417}\\ k&\equiv -1\pmod{641}\end{align*}

Moreover, \begin{align*}\text{ord}_{3}\left(2\right)&=2\\ \text{ord}_{5}\left(2\right)&=4\\ \text{ord}_{17}\left(2\right)&=8\\ \text{ord}_{257}\left(2\right)&=16\\ \text{ord}_{65537}\left(2\right)&=32\\ \text{ord}_{6700417}\left(2\right)&=64\\ \text{ord}_{641}\left(2\right)&=64\end{align*}

We conclude that \begin{align*}n\equiv 1\pmod{2}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{3}\\ n\equiv 2\pmod{4}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{5}\\ n\equiv 4\pmod{8}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{17}\\ n\equiv 8\pmod{16}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{257}\\ n\equiv 16\pmod{32}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{65537}\\ n\equiv 32\pmod{64}&\implies k\cdot 2^{n}-1\equiv k\cdot\left(-1\right)+1\equiv 0\pmod{6700417}\\ n\equiv 0\pmod{64}&\implies k\cdot 2^{n}-1\equiv k\cdot1+1\equiv 0\pmod{641}\end{align*}

And $k>>3,5,17,257,65537,6700417,641$ so the relevant values will, in fact, always be composite. $\blacksquare$

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=155088"