Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.