A condição \(a^{n-1}\equiv a (mod n)\) é equivalente a dizer que \(a^{n-1}-a\) é múltiplo de \(n\). Como \(n=2p\), temos que \(a^{n-1}-a=a(a^{2p-2}-1)=a(a^{p-1}+1)(a^{p-1}-1)\). Para qualquer inteiro \(a\), \(a(a^{p-1}+1)\) é múltiplo de 2. Se \(a\) for múltiplo de \(p\) então \(a(a^{p-1}+1)\) é múltiplo de \(n=2p\). Se \(a\) não for múltiplo de \(p\) então \(a^{p-1}-1\) é múltiplo de \(p\) (pelo
pequeno teorema de Fermat). Logo \(a(a^{p-1}+1)(a^{p-1}-1)\) é múltiplo de \(n=2p\).