Prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$?

Question

I have to prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$. I have proven using congruencies that $2^{15}-1$ is divided by $31$. However we have

$$2^5\equiv 10 \mod{11}$$ $$2^{15}\equiv 10^3=1000\equiv 10 \pmod {11}$$ Therefore $$2^{15}-1\equiv 9 \pmod{11}.$$ So it is impossible to prove!!

By the way, the smallest number of the form $2^n-1$ which is divisible by $11,31,61$ is $2^{60}-1$. — pre-kidney, Jun 27 '15 at 21:36
The given number is not divisible by 11, or am I missing something? — imranfat, Jun 27 '15 at 21:37
$2^{15}\equiv \left(\frac{2}{31}\right)\equiv 1\pmod{! 31}$ using Euler's criterion and Quadratic reciprocity. — user26486, Jun 27 '15 at 21:45
Shorter: $2^5\equiv −1\mod11$, hence $2^{15}\equiv (−1)^3\equiv−1\mod11$. — Bernard, Jun 27 '15 at 21:49
How do you prove using congruencies that $2^{60}-1$ is divided by 61? — parkhyeyoo, Jun 27 '15 at 21:52
I did it, still my opinion is it's more accurate to write = when there is no reduction . — Bernard, Jun 27 '15 at 21:53
@parkhyeyoo Fermat's little theorem: $\gcd(a,p)=1,\Rightarrow, a^{p-1}\equiv 1\pmod{! p}$. — user26486, Jun 27 '15 at 21:54
I am not allowed to use Fermat's theorem. Only congruencies. — parkhyeyoo, Jun 27 '15 at 21:55
$2^6\equiv -3,\Rightarrow, 2^{60}\equiv (-3)^{10}\equiv 3^{10}\equiv \left(3^{5}\right)^2 \equiv (-1)^2\equiv 1\pmod{! 61}$ — user26486, Jun 27 '15 at 22:00

score 2 · Answer 1 · answered Jun 27 '15 at 21:34

2

You are correct, there is a mistake in the problem. Here are two useful prime factorizations: $$ \begin{align*} 2^{15}-1&=32767=7\cdot 31\cdot 151\\ 2^{15}+1&=32769=3^2\cdot 11\cdot 331 \end{align*} $$

answered Jun 27 '15 at 21:34

pre-kidney

30,223

score 1 · Answer 2 · answered Jun 27 '15 at 21:34

You are correct: the factorization you are given is wrong.

Since $N=2^{15}-1=(2^5)^3-1=(2^5-1)((2^5)^2+2^5+1)$ you get $$ 2^{15}-1=31\cdot(1024+32+1)=31\cdot 1057 $$ However, you can also use $$ 2^{15}-1=(2^3)^5-1=(2^3-1)((2^3)^4+(2^3)^2+2^3+1) $$ so $N$ is also divisible by $7$. Divide $1057$ by $7$ to get $$ N=31\cdot 7\cdot 151 $$ (and $151$ is prime).

Prove that $2^{15}-1$ is divided by $11\cdot31\cdot61$?

2 Answers2