Congruência (aritmética modular)

Para um inteiro ímpar n > 1, seja S o conjunto de inteiros x,1 ≤ x ≤ n, tal que ambos x e x + 1 são relativamente primos com n. Mostre que o produto de todos os elementos de S deixa resto 1 na divisão por n.

Consegui provar apenas para n primo através do teorema de Wilson (talvez ele seja útil para p caso geral).

Provar pelo teorema de Wilson torna o problema fácil, pois você terá as soluções apenas para  

Se n é par, S é vazio e



Suponha que n seja ímpar. Temos que provar que

 

para cada p primo e  tal que  


Seja 



a fatoração de primos de n. Pelo Teorema do Restante Chinês, existem exatamente



números 



que são congruentes com

  ou  

módulo  para todo    e    e congruente com algum módulo inteiro  

Esse  é um número ímpar, pois todos os fatores primos de n são ímpares. Portanto





     

Os inversos de  

 módulo   são  

em alguma ordem, porque o produto deve ser



Então 



Temos 



Os dois fatores diferem 2, então eles não podem ser divisíveis por 



Portanto



ou





E portanto



Então