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?
Solving a pair of congruences
3
$\begingroup$
number-theory
prime-numbers
-
0Alternatively, 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
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$.