Which of the following numbers does not divide $2^{1650}-1$?

Question

I'm practicing for a math competition that is coming up, and I got stuck on this question: Which of the following numbers does not divide $2^{1650}-1$?

$3$, $7$, $31$, $127$, $2047$

I've seen a link on Yahoo Answers that says this:

---

Note that $3 = 2^2 - 1$, $7 = 2^3 - 1$, $31 = 2^5 - 1$, $127 = 2^7 - 1$ and $2047 = 2^{11} - 1$.

Let's consider $2^n - 1$. If $n = ab$ (i.e. $n$ is divisible by $a$) then we have

$2^{ab} - 1$.

Now in the case of $n = 1650$ is a number that is divisible by $2$, but not by $4$, which means that exactly one of $a$ or $b$ must be even (since when you multiply two odd numbers you get an odd number, and when you multiply two even numbers you get a number divisible by $4$). So let's say, without loss of generality, that the even one is $a$. Since it's even, we can say that $a = 2k$ for some integer $k$.

So we have $2^{1650} - 1$ = $2^{2kb} - 1$. We can employ the laws of exponents on the right hand side to get $(2^{kb})^2 - 1$, a difference of two squares which can be written as $(2^{kb} + 1)(2^{kb} - 1)$.

Now $2^{1650} - 1 = (2^{kb} + 1)(2^{kb} - 1)$.

We can now conclude that if $k$ divides $1650$, then $2^k - 1$ divides $2^{1650} - 1$.

---

But I don't understand the conclusion. I see how $2^{1650} - 1$ is divisible by $(2^{kb} - 1)$ and $(2^{kb} + 1)$, but not $(2^k - 1)$.

Answer 1

Here is an easier way of understanding that theorem.

For any positive integer $m$ we have: $x^m-1 = (x-1)(x^{m-1}+x^{m-2}+\cdots+x+1)$.

Now set $m = b$ and $x = 2^a$, to get $(2^a)^b - 1 = (2^a-1)[(2^a)^{b-1}+(2^a)^{b-1}+\cdots+(2^a)+1]$.

This simplifies as $2^{ab}-1 = (2^a-1)[\text{some integer}]$.

Hence, $2^{ab}-1$ is divisible by $2^a-1$ for any choice of positive integers $a$ and $b$.

---

Now, to solve this question, use the above statement for different values of $a$ and $b$.

For instance, pick $a = 2$ and $b = 825$ to get that $2^{1650}-1$ is divisible by $2^2-1 = 3$.

Also, pick $a = 3$ and $b = 550$ to get that $2^{1650}-1$ is divisible by $2^3-1 = 7$.

Can you continue from here? Knowing which small numbers divide $1650$ will be useful.

Answer 2

For $x,y \in \mathbb{R}$, we can factor $x^2-y^2$ as $$x^2-y^2=(x-y)(x+y)$$

This called a difference of squares. There are similar identities for differences of cubes, sums of cubes, and for higher powers.

Consider positive integers $m,n \in \mathbb{N}$. We can apply the identity above to $m^{2n}-1$ as follows:

$$m^{2n}-1=\left(m^n\right)^2-1=(m^n-1)(m^n+1)$$

---

With $m=2$ and $2n=1650$ (or $n=825$), we have $$2^{1650}-1 = (2^{825}-1)(2^{825}+1)$$

Notice that $825$ is a multiple of $3$. This means that $2^{825}$ is a perfect cube, so $2^{825}-1$ is a difference of cubes, and $2^{825}+1$ is a sum of cubes. In particular, $2^{275}-1$ is a factor of $2^{825}-1$.

---

I won't answer the entire question for you, but you can use the many identities about sums and differences of powers to repeatedly factor $2^{1650}-1$ like I've started to do above. You'll have some fifth powers as well, since $5$ divides $825$.

Good luck :)