Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I thought I proved the following two divisibility statements but later I found out I was wrong. Could someone explain them?

1) For primes $q\geq 2$, $2^q-1$ is divisible by some prime $p$ such that $p\equiv 3(mod\, 4)$

2) If $r$ and $s$ are distinct primes, then $gcd(2^s-1, 2^r-1)=1$

share|improve this question
add comment

2 Answers 2

If $q\ge 2$, then $2^q-1\equiv -1\pmod{4}$.

Any product of primes (distinct or not) which are congruent to $1$ modulo $4$ is itself congruent to $1$ modulo $4$.

Since $2^q\equiv -1\pmod{4}$, it follows that not all the prime divisors of $2^q-1$ can be congruent to $1$ modulo $4$.

Similarly, any positive integer of the form $3k-1$ has a prime divisor of the form $3k-1$.

As to the $\gcd$ question, it has been asked and answered many times, and in many ways. In general, $$\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1.$$ And the $2$ is not important. A quick search gave this MSE link.

One way is to do it by induction on the maximum of $a$ and $b$. Say it is $b$, and that $a\lt b$. Note that $2^b-1=(2^a-1)2^{b-a}+(2^{b-a}-1)$. From this we can conclude that $\gcd(2^a-1,2^b-1)=\gcd(2^a-1,2^{b-a}-1)$. But $\gcd(a,b-a)=\gcd(a,b)$.

share|improve this answer
add comment

For 1), you can notice that $$2^q-1 = 2^q - 1^q = (2-1) \times \sum_{i=0}^{q-1} 2^i = 3 + \sum_{i=2}^{q-1} 2^i = 3 + 4 \times \sum_{i = 0}^{q-3} 2^i = 3 + 4 \times (2^{q-2} - 1).$$ So if $2^q-1$ is prime, then it is fine. Otherwise, it is a product of primes, and since $2$ does not divide $2^q-1$, if prime $p$ is such that $p | 2^q-1$ then $ p = 1 \mod 4$ or $p = 3 \mod 4$. If all the divisors of $2^q-1$ are equal to $1 \mod 4$ you get a contradiction (because their product is equal to $1 \mod 4$).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.