Fermat converso (en general, espurio)

Tenemos que

$a^p \equiv a \pmod{q}$ ... (1)

$a^q \equiv a \pmod{p}$ ... (2)

y 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 fácilmente que

$2^{341} \equiv 2 \pmod{341}$

podemos utilizar la operación de "eliminación" en congruencias por ser 2 y 341 primos relativos, así que

$2^{340} \equiv 1 \pmod{341}$

lo cual demuestra que el PTF no siempre es verdadero al revés.

(Solución enviada por Zzq --las gracias le sean dadas)