Congruencias y potencias primarias

Question

Tengo una pequeña pregunta que probablemente no sea difícil de responder, pero no he podido encontrar una solución elegante a esta cuestión.

Dejemos que $p$ y $q$ sean números primos.

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

Encuentra todas las soluciones de esta ecuación modular.

Sé que las soluciones son $p=q=3$ y $p=3; q=13$ (y al revés)

Pero no encuentro la manera de demostrar que estos son los únicos (o encontrar otras soluciones).

Answer 1

Si $p=q$ tenemos $5^p \equiv 2^p \pmod{p}$ así que por el pequeño teorema de Fermat, $5 \equiv 2 \pmod{p}$ así que $p=3$ . Esto da la solución $(p, q)=(3, 3)$ .

De lo contrario, $p \not =q$ por lo que podemos suponer que WLOG $p>q$ .

Claramente $q \not =2, 5$ Así que $(2, q)=(5, q)=1$ . Dejemos que $d$ sea el orden de $5 \cdot 2^{-1} \pmod{q}$ . Entonces $(5 \cdot 2^{-1})^p \equiv 1 \pmod{q}$ implica $d \mid p$ y $d \mid q-1$ por el pequeño teorema de Fermat. Como $p>q$ tenemos $(p, q-1)=1$ Así que $d=1$ . Así, $5 \cdot 2^{-1} \equiv 1 \pmod{q}$ Así que $q=3$ .

Ahora $5^3 \equiv 2^3 \pmod{p}$ y $p>q=3$ así que $p=13$ . Esto da $(p, q)=(13, 3)$ .

En conclusión, las soluciones son $(p, q)=(3, 3), (3, 13), (13, 3)$ .

---

Editar: Aquí he añadido alguna explicación sobre pedir .

El orden de $x \pmod{q}$ es el menor número entero positivo $d$ tal que $x^d \equiv 1 \pmod{q}$ . El siguiente resultado útil no es demasiado difícil de demostrar:

Resultado: Si $d$ es el orden de $x \pmod{q}$ y $x^n \equiv 1 \pmod{q}$ entonces $d \mid n$ .

Prueba: Escriba $n=ad+b$ , donde $a, b \in \mathbb{Z}$ y $0 \leq b<d$ . Entonces $$1 \equiv x^n \equiv (x^d)^ax^b \equiv x^b \pmod{q}$$ (Nota $x^d \equiv 1 \pmod{q}$ por definición)

Si $b>0$ entonces $b<d$ es un número entero positivo y $x^b \equiv 1 \pmod{q}$ contradiciendo la minimidad de $d$ . Así, $b=0$ así que $d \mid n$ .

Nota: En mi solución de la pregunta anterior, he utilizado $x \equiv 5 \cdot 2^{-1} \pmod{q}$ y $n=p, q-1$ para concluir utilizando este resultado que $d \mid p, d\mid q-1$ .