Demostrar que si $p, q$ son dos primos distintos para los cuales $a^p\equiv a \pmod{q}$ y $a^q\equiv{a} \pmod{p}$, entonces $a^{pq} \equiv a \pmod{pq}$. }
Demostrar, con este resultado, el siguiente contraejemplo para la conversa del pequeño teorema de Fermat: $2^{340} \equiv 1 \pmod{341}$ --¡pero 341 es compuesto!
Ver también:
Pequeño teorema de Fermat
Ver también:
Recíproca (de una proposición condicional)
Tenemos ... (1) ...
Tenemos
$a^p \equiv a \pmod{q}$ ... (1)
$a^q \equiv a \pmod{p}$ ... (2)
sabemos que p y q son primos, asi que por el PTF vemos que
$a^q \equiv a \pmod{q}$ ... (3)
$a^p \equiv a \pmod{p}$ ... (4)
por (1) y (3) tenemos
$(a^p)^q=a^{pq}\equiv a \pmod{q}$ ... (5)
y por (2) y (4) tenemos
$(a^q)^p=a^{pq}\equiv a \pmod{p}$ ... (6)
por (5) y (6) vemos que
$q | a^{pq}- a$
$p | a^{pq}- a$
pero p y q son primos, lo cual implica que
$pq | a^{pq}- a$
que es equivalente a
$a^{pq} \equiv a \pmod{pq}$.
Para el contraejemplo, ponemos a p=11 y q=31, y se ve facilmente que
$2^{341} \equiv 2 \pmod{341}$
podemos utilizar la operacion de "eliminacion" en congruencias por ser 2 y 341 primos relativos, asi que
$2^{340} \equiv 1 \pmod{341}$
lo cual demuestra que el PTF no siempre es verdadero al reves.