I need to know how could I prove that $2^{33} + 1$ is composite.
Thanks!
Asked
Active
Viewed 112 times
0
-
Start by drawing a circle. No really, what have you done so far? – Shahar Aug 24 '14 at 17:53
-
Well I know that this number has to be higher than 1. I have no problem proving if a number is composite for something more simple than this, but that + 1 is confusing me. Sorry, its my first post here and thanks for your interest. – Ben Aug 24 '14 at 17:55
-
3Hint: $2^{33} + 1 = 2^{33} - (-1)^{33}$. Do you remember any formula that factors $a^n - b^n$? – Sangchul Lee Aug 24 '14 at 17:56
-
Is it (a^1/2n - b^1/2n)(a^1/2n + b^1/2n) ? – Ben Aug 24 '14 at 18:03
-
$2^{33}+1=3×2049×1397419$ – Bumblebee Aug 24 '14 at 18:08
-
Well this is not really accepted by my teacher as a proof:/ – Ben Aug 24 '14 at 18:09
3 Answers
1
Hint: Show that $2^{33}+1$ is divisible by $3$. If you are familiar with congruences, note that $2$ to an even power is congruent to $1$ modulo $3$.
I can make no useful comments about the general problem of the title. For large numbers, it is very difficult.
Remark: One first step in approaching the problem is to look at $2^1+1$, $2^2+1$, $2^3+1$, and so on for a while to see whether one can detect a pattern. Maybe one notices that for small odd $n$ the number $2^n+1$ is divisible by $3$. Then one can use a calculator to verify that $2^{33}+1$ is divisible by $3$. And then maybe (though this is not asked for) one can show that $2^n+1$ is divisible by $3$ for all odd $n$.
André Nicolas
- 507,029
-
I see. And maybe you could link something I could hold on to? I've been googling for a solid amount of time today just for this problem, and everything I found was a lot easier :( Thanks for your interest! – Ben Aug 24 '14 at 17:57
-
At what stage are you in mathematics? The answer would very much depend on that. – André Nicolas Aug 24 '14 at 18:04
-
I'm 16 years old, about to start the 12th grade. In Europe, if that matters. – Ben Aug 24 '14 at 18:05
-
1Maybe you are just expected to note that the remainders when $2^n$ is divided by $3$ alternate between $1$ and $2$. Or else you can use the fact that if $n$ is odd then $x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+\cdots +y^{n-1}$. Let $x=2$, $y=1$, $n=33$. Then $x+y$, that is, $3$, divides $x^n+y^n$. – André Nicolas Aug 24 '14 at 18:16
1
The sum of cubes factorization is $a^3+b^3 = (a+b)(a^2-ab+b^2)$.
Setting $a = 2^{11}$ and $b = 1$ yields $2^{33}+1 = (2^{11}+1)(2^{22}-2^{11}+1)$.
Both factors are clearly greater than $1$.
JimmyK4542
- 54,331