Demostrar que $a^{q-1} \equiv 1 \pmod{pq}$

Question

Supongamos que $p$ y $q$ son números primos distintos que se suman y son tales que $p-1\mid q-1$ . Si $\gcd(a,pq)=1$ demuestran que..: $$a^{q-1} \equiv 1 \pmod{pq}$$

He intentado lo siguiente: $$a^{q-1} \equiv 1 \pmod{q} \quad \text{and} \quad a^{p-1} \equiv 1 \pmod{p}$$ $$\implies a^{(q-1)(p-1)} \equiv 1 \pmod{q} \quad \text{and} \quad a^{(q-1)(p-1)} \equiv 1 \pmod{p}$$ $$\implies a^{(q-1)(p-1)} \equiv 1 \pmod{pq}$$
Pero entonces estoy atascado - por favor, ayuda.

Answer 1

Recuerde que se le dice que $p-1$ divide $q-1$ . Tenga en cuenta que aún no ha utilizado esta hipótesis. Eso sugiere que debería realmente intentar usarla de alguna manera.

Desde $p-1$ divide $q-1$ entonces existe $k$ tal que $q-1 = k(p-1)$ . Eso significa que, como $a^{p-1}\equiv 1\pmod{p}$ entonces $$1 \equiv 1^k \equiv (a^{p-1})^k \equiv a^{(p-1)k} = a^{q-1}\pmod{p}.$$

Así que ahora tienes $a^{q-1}\equiv 1\pmod{q}$ y $a^{q-1}\equiv 1\pmod{p}.$

Answer 2

Tenga en cuenta que $p-1\mid q-1$ significa que $q-1=k(p-1)$ para algunos $k$ . Así, $$a^{p-1}\equiv 1\bmod p$$ implica que $$a^{q-1} = a^{k(p-1)} = (a^{p-1})^k\equiv 1^k= 1\bmod p.$$ Ahora usa el Teorema Chino del Resto.

Answer 3

Ya lo sabes:

$a^{p-1} \equiv 1$ mod $p$

pero $(p-1)|(q-1)$ por lo que esto significa que

$a^{q-1} \equiv 1$ mod $p$ .

Ahora puedes usar el teorema del rema chino con tu primera congruencia para decirte que

$a^{q-1} \equiv 1$ mod $pq$