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!!

Answer 1

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).

Answer 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*} $$