# Divisors again

• Nov 20th 2010, 09:18 AM
Divisors again
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..
It will be fantastic if you help me with proving this fact.
• Nov 20th 2010, 10:57 AM
Opalg
Quote:

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..
It will be fantastic if you help me with proving this fact.

Hint: See melese's comment #4 in this thread, and think what happens mod 4.
• Nov 20th 2010, 01:55 PM
Well, I don't really know what you mean.. I guess we can prove that one of those numbers: x and y is odd and another is even. But, what next?
• Nov 21st 2010, 01:18 AM
Opalg
My previous comment was based on a misreading of the question. Ignore it.

However, the question as stated is plain wrong (unless I'm still misreading it):
Quote:

We have: $\displaystyle z = (2^{mn} - 1)/[(2^m - 1)(2^n - 1)]$, where $\displaystyle (2^m - 1)$ and $\displaystyle (2^n - 1)$ are prime numbers. Prove that $\displaystyle (2^m - 1)$ and $\displaystyle (2^n - 1)$ are not the only prime factors of z.
Try taking m=2 and n=3. Then $\displaystyle z = \frac{2^6 - 1}{(2^2 - 1)(2^3 - 1)} = \frac{63}{3\times7} = 3$. The only prime factor of z is 3, which is $\displaystyle 2^m-1$.
• Nov 21st 2010, 02:48 AM
mistake
Oh, I'm sorry. Now I realised that I should have written: (2^m -1) and (2^n -1) are two different ODD primes.
But my question still remains the same.
• Nov 21st 2010, 07:56 AM
Opalg
Here's an approach that seems to work. Look at the polynomial $\displaystyle x^{2k+1}-1$, and let $\displaystyle p(x^2)$ be a nonconstant polynomial in $\displaystyle x^2$. Let $\displaystyle q(x)$ be the quotient, and $\displaystyle r(x)$ the remainder, when $\displaystyle x^{2k+1}-1$ is divided by $\displaystyle p(x^2)$. I claim that if $\displaystyle q(x)$ is nonzero then it consists entirely of odd powers of x. Reason: suppose not, let 2s be the highest even degree of a nonzero term in $\displaystyle q(x)$, and let 2t be the degree of $\displaystyle p(x^2)$. Then there is a nonzero term of degree 2(s+t) in their product (and there is no term of that degree in $\displaystyle r(x)$). But there is no term of that degree in $\displaystyle x^{2k+1}-1$, so we have a contradiction.

Therefore $\displaystyle p(x)q(x)$ consists entirely of terms of odd degree, and it follows that the constant term in r(x) must be –1.

Now let m, n be odd numbers, and suppose that $\displaystyle 2^m-1$ is a repeated factor of $\displaystyle 2^{mn}-1$. Notice that $\displaystyle (2^m-1)^2 = 2^{2m}- 2^{m+1}+1$. Since both those powers of 2 are even, that is a polynomial in $\displaystyle 2^2$. So let $\displaystyle p(x) = x^m-x^{(m+1)/2}+1$, divide $\displaystyle x^{mn}-1$ by $\displaystyle p(x^2)$ and then put x=2. The above result says that the remainder will be r(2), and r(2) must be an odd number (since the constant term in r(x) will be the only odd term). In particular r(2) can never be 0.

Conclusion: $\displaystyle 2^m-1$, and similarly $\displaystyle 2^n-1$, can never be repeated factors of $\displaystyle 2^{mn}-1$. And since their product can never be equal to $\displaystyle 2^{mn}-1$, there must always be a third factor.
• Nov 21st 2010, 08:57 AM
Quote:

Originally Posted by Opalg
Conclusion: $\displaystyle 2^m-1$, and similarly $\displaystyle 2^n-1$, can never be repeated factors of $\displaystyle 2^{mn}-1$. And since their product can never be equal to $\displaystyle 2^{mn}-1$, there must always be a third factor.

But, well, if we try with m=3, n=7, then 2^m -1 = 7 and 2^mn -1 = 2^21 -1 = 2 097 151 = 49 * 42799. So 2^m - 1 is a double factor. I think it would be enough to prove that 2^m - 1 can't be a triple factor. How?
• Nov 21st 2010, 09:51 AM
Opalg
Quote: