# Congruences and prime powers

I have just a small question that probably is not hard to answer, but I could not find and elegant solution to this question.

Let $p$ and $q$ be prime numbers.

$$5^q\equiv 2^q \pmod p$$ $$5^p\equiv 2^p \pmod q$$

Find all solutions to this modular equation.

I know solutions are $p=q=3$ and $p=3; q=13$ (and the other way around)

But I do not find a way to prove these are the only ones (or find other solutions).

-
Solutions to both equations separately or? – kingW3 Apr 20 '14 at 16:08
Solutions to both equations together. – user143863 Apr 20 '14 at 16:11
I have got the solution but i don't know how to write in mathematical form. – Satvik Mashkaria Apr 20 '14 at 16:14
For all primes q and p=3 also holds – Satvik Mashkaria Apr 20 '14 at 16:15
@SatvikMashkaria No it doesn't,simple example q=113 – kingW3 Apr 20 '14 at 16:17

If $p=q$, we have $5^p \equiv 2^p \pmod{p}$ so by Fermat's little theorem, $5 \equiv 2 \pmod{p}$ so $p=3$. This gives the solution $(p, q)=(3, 3)$.

Otherwise $p \not =q$, so we may WLOG assume $p>q$.

Clearly $q \not =2, 5$, so $(2, q)=(5, q)=1$. Let $d$ be the order of $5 \cdot 2^{-1} \pmod{q}$. Then $(5 \cdot 2^{-1})^p \equiv 1 \pmod{q}$ implies $d \mid p$, and $d \mid q-1$ by Fermat's little theorem. Since $p>q$, we have $(p, q-1)=1$, so $d=1$. Thus $5 \cdot 2^{-1} \equiv 1 \pmod{q}$, so $q=3$.

Now $5^3 \equiv 2^3 \pmod{p}$ and $p>q=3$ so $p=13$. This gives $(p, q)=(13, 3)$.

In conclusion, the solutions are $(p, q)=(3, 3), (3, 13), (13, 3)$.

The order of $x \pmod{q}$ is the smallest positive integer $d$ such that $x^d \equiv 1 \pmod{q}$. The following useful result is not too hard to prove:

Result: If $d$ is the order of $x \pmod{q}$ and $x^n \equiv 1 \pmod{q}$ then $d \mid n$.

Proof: Write $n=ad+b$, where $a, b \in \mathbb{Z}$ and $0 \leq b<d$. Then $$1 \equiv x^n \equiv (x^d)^ax^b \equiv x^b \pmod{q}$$ (Note $x^d \equiv 1 \pmod{q}$ by definition)

If $b>0$, then $b<d$ is a positive integer and $x^b \equiv 1 \pmod{q}$, contradicting minimality of $d$. Thus $b=0$ so $d \mid n$.

Note: In my solution of the question above, I have used $x \equiv 5 \cdot 2^{-1} \pmod{q}$ and $n=p, q-1$ to conclude using this result that $d \mid p, d\mid q-1$.

-
I don't really understand the whole concept of order. Do I have to use it in this case? I will try to find a good explanation to help me work it out in my head. – user143863 Apr 20 '14 at 16:27