Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

Your Answer

 
discard

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.