# Number theory; primes dividing proof

1. Sep 29, 2012

### amalak

1. The problem statement, all variables and given/known data

Show there exist infinitely many (p, q) pairs, (p ≠ q), s.t.
p | 2$^{q - 1}$ - 1 and q | 2$^{p - 1}$ - 1

2. Relevant equations

We are allowed to assume that 2$^{β}$ - 1 is not a prime number or the power of a prime if β is prime.

3. The attempt at a solution

Using fermat's little theorem and the Chinese Remainder Theorem; we get

pq | 2$^{q - 1}$ - 1 and pq | 2$^{p - 1}$ - 1,

which together yield:

pq | gcd(2$^{q - 1}$ - 1, 2$^{p - 1}$ - 1)

which yields

pq | 2$^{gcd(q - 1, p - 1)}$ - 1

My strategy from here is to find some

2$^{α}$ - 1 such that 2$^{α}$ - 1 | 2$^{gcd(q - 1, p - 1)}$ - 1

and that pq | 2$^{α}$ - 1.

However, this doesn't seem to be fruitful for me; I suspect I'm missing something very easy.

Any hints would be greatly appreciated!

Thanks!

Last edited: Sep 29, 2012