3
$\begingroup$

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?

  • 0
    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...2012-08-15

1 Answers 1

1

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$.