1. ## Divisors

Prove, that a composite number 2^p - 1 (where p is a prime) has at least 2 different prime factors.

How I tried to solve this problem:
I tried to write 2^p -1 as x^n (x, n are integers, n>1, just to prove that it can't be this way). I know that the only prime factors of 2^p - 1 can be numbers like 2kp+1 and I also tried this way. What is more, I tried with two cases- n odd and n even, separately. But I didn't manage to prove anything. Please, help. Thank you in advance.

2. x^n-1=(x-1)*(x^{n-1}+x^{n-2}+...+x+1)

EDIT: NOT HELPING TOO MUCH.

2^31 - 1 is prime.

3. Yes, but in my question if you have an equation x^n-1=(x-1)*(x^{n-1}+x^{n-2}+...+x+1) then x=2 and we have to prove that (x^{n-1}+x^{n-2}+...+x+1) has at least 2 prime factors. How?

4. Originally Posted by conrad
Prove, that a composite number 2^p - 1 (where p is a prime) has at least 2 different prime factors.

How I tried to solve this problem:
I tried to write 2^p -1 as x^n (x, n are integers, n>1, just to prove that it can't be this way). I know that the only prime factors of 2^p - 1 can be numbers like 2kp+1 and I also tried this way. What is more, I tried with two cases- n odd and n even, separately. But I didn't manage to prove anything. Please, help. Thank you in advance.
I'll try to show a more general result: Let $\displaystyle n, a$ and $\displaystyle m$ be positive integers. If $\displaystyle 2^n-1=a^m$, then $\displaystyle 2^n-1=a$. To put it differently, $\displaystyle m$ must equal 1. (execpt for the case $\displaystyle n=1$, where $\displaystyle 2^1-1=1^m$)

We suppose that $\displaystyle n\geq2$. It's clear that $\displaystyle a$ is odd.
If $\displaystyle m$ is even, then $\displaystyle a^m$ would be of the form $\displaystyle 4k+1$. But $\displaystyle 2^n-1$ has the form $\displaystyle 4q+3$; therefore $\displaystyle m$ is odd.*

The following identity holds, since $\displaystyle m$ is odd: $\displaystyle a^m+1=(a+1)(a^{m-1}-a^{m-2}+\cdots+a^2-a+1)=2^n$. Note that the term $\displaystyle a^{m-1}-a^{m-2}+\cdots+a^2-a+1$ is odd and thus relatively prime to $\displaystyle 2^n$. So $\displaystyle 2^n$ must be equal to $\displaystyle a+1$, namely $\displaystyle a=2^n-1$.

Back to the original problem... Assume to the contrary that $\displaystyle 2^p-1$ has only one prime factor, that is $\displaystyle 2^p-1=q^m$, where $\displaystyle q$ is prime. But the result implies that $\displaystyle 2^p-1=q$, contradiction.

* To see why: For any odd $\displaystyle a$ we have $\displaystyle a\equiv\pm1\pmod4$. Then $\displaystyle a^m\equiv1\pmod4$ if $\displaystyle m$ is even. But $\displaystyle 2^n-1\equiv-1\pmod4$, so $\displaystyle 1\equiv-1\pmod4$, contradiction. Sorry if this part is tedious...

5. Thank you! You helped me so much. I'm very grateful!

6. @melese, maybe you have and idea how to solve this one:
We have:
z = (2^(mn) - 1)/[(2^m - 1)(2^n - 1)], where (2^m - 1) and (2^n - 1) are prime numbers.
Prove that (2^m - 1) and (2^n - 1) are not the only prime factors of z.

I tried to solve it writing z = (2^m - 1)^a * (2^n - 1)^b and proving that it is not correct. But I don't know how. I also noticed that it would be sufficient to prove that 2^(mn) - 1 can't be written as ((2^m - 1)^x * (2^n - 1)^y but I also have no idea how to prove it. I tried with comparing highest exponents, but nothing..

Thank you very much in advance!