Divisors

**conrad** · November 20th 2010, 05:03 AM

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.

**Also sprach Zarathustra** · November 20th 2010, 05:19 AM

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

EDIT: NOT HELPING TOO MUCH.

What about p=31?

2^31 - 1 is prime.

**conrad** · November 20th 2010, 05:26 AM

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?

**melese** · November 20th 2010, 08:07 AM

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 $n, a$ and $m$ be positive integers. If $2^n-1=a^m$ , then $2^n-1=a$ . To put it differently, $m$ must equal 1. (execpt for the case $n=1$ , where $2^1-1=1^m$ )

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

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

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

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

**conrad** · November 20th 2010, 09:06 AM

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

**conrad** · November 20th 2010, 09:32 AM

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

Thread: Divisors

LinkBack

Thread Tools

Display

Divisors

Similar Math Help Forum Discussions

Relitivly prime, unique divisors of divisors

divisors

Zero divisors and such

Divisors of N

divisors

Search Tags