Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)$.

Edit: Here I have added some explanation about order.

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

share|cite|improve this answer
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
@user143863 I have added some explanation about this. – Ivan Loh Apr 20 '14 at 16:43
Really nice solution.+1. – rah4927 Apr 20 '14 at 16:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.