# Solving a pair of congruences

Any ideas on how to solve the congruences \begin{eqnarray*} p^k &\equiv& 1 \mod q \\ q &\equiv& 1 \mod p \end{eqnarray*} where $p$ and $q$ are primes and $k$ is a positive integer?

-
$(p,q,k)=(2,7,3)$ is one solution. What do you want - all solutions? There might be quite a few.... – Gerry Myerson Aug 15 '12 at 4:53
Indeed, every Mersenne prime $q=2^k-1$ will give a solution with $p=2$, and it's conjectured there are infinitely many. That gives you at least 47 solutions, anyway. – Kevin Carlson Aug 15 '12 at 5:25
Alternatively, for every pair of primes $p,q$ such that $p$ divides $q-1$, we can take $k$ to be $q-1.$ This gives a ton of solutions... – only Aug 15 '12 at 5:31

Given any prime $p$, by Dirichlet's theorem on primes in arithmetic progressions there are infinitely many primes $q$ such that $q \equiv 1 \mod p$. Now you just need $k$ to be any multiple of the order $\text{ord}_q(p)$ of $p \mod q$. By Fermat's "little" theorem, $\text{ord}_q(p)$ divides $q-1$.

-