- #1
amalak
- 7
- 0
Homework Statement
Show there exist infinitely many (p, q) pairs, (p ≠ q), s.t.
p | 2[itex]^{q - 1}[/itex] - 1 and q | 2[itex]^{p - 1}[/itex] - 1
Homework Equations
We are allowed to assume that 2[itex]^{β}[/itex] - 1 is not a prime number or the power of a prime if β is prime.
The Attempt at a Solution
Using fermat's little theorem and the Chinese Remainder Theorem; we get
pq | 2[itex]^{q - 1}[/itex] - 1 and pq | 2[itex]^{p - 1}[/itex] - 1,
which together yield:
pq | gcd(2[itex]^{q - 1}[/itex] - 1, 2[itex]^{p - 1}[/itex] - 1)
which yields
pq | 2[itex]^{gcd(q - 1, p - 1)}[/itex] - 1
My strategy from here is to find some
2[itex]^{α}[/itex] - 1 such that 2[itex]^{α}[/itex] - 1 | 2[itex]^{gcd(q - 1, p - 1)}[/itex] - 1
and that pq | 2[itex]^{α}[/itex] - 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: