Which of the following numbers does not divide $2^{1650}-1$? 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)$. 
 A: 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. 
A: 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 :)
