# Thread:

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

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!
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 32, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9648839235305786, "perplexity_flag": "head"}