Question

Teoria dos números.


Prove que se n é um inteiro positivo e n | (n - 1)! + 1, então n é primo.


______________


Por favor responder de forma detalhada.

Answer 1

Se $n~|~(n-1)!+1$, podemos afirmar que $(n-1)!\equiv-1\pmod{n}$.

Vamos supor que $n$ não é primo. Então, $n$ é um composto maior que $4$

Se $n$ não é um quadrado perfeito, temos que $n=ab$, com $a,b\in\mathbb{N},~a,b<n$

Note que $(n-1)!$ contém os fatores $a$ e $b$, por consequência, $n~|~(n-1)!$, que é um absurdo, pois $(n-1)!\equiv-1\pmod{n}$

Se $n$ é um quadrado perfeito, podemos escrever $n=c^2$, com $c\in\mathbb{N},~2<c<n$

Analogamente, $(n-1)!$ contém os fatores $c$ e $2c$, pois $c^2>2c>c,~\forall~c>2$. Com isso, $n~|~(n-1)!$, absurdo.

Portanto, $n$ é primo.


Outra solução:

Lema: se $\text{mdc}(a,m)=1$, então existe um inteiro $x$ tal que $ax\equiv1\pmod{m}$. Tal $x$ é único módulo $m$

Temos que $(n-1)!=1\cdot2\cdot3\dots(n-1)$. Pelo lema acima, podemos dividir os fatores do produto $(n-1)!$ em pares $(a,b)$, tais que $ab\equiv1\pmod{n}$, pois todos são primos com $n$

Por outro lado, se $a=b$, teríamos $a^2\equiv1\pmod{n}$, isto é, $a^2-1=(a-1)\cdot(a+1)\equiv0\pmod{n}$.

Assim, $a\equiv1\pmod{n}~\hookrightarrow~a=1$ ou $a\equiv-1\pmod{n}~\hookrightarrow~a=n-1$.

Desse modo, $1$ e $n-1$ são únicos fatores do produto $(n-1)!$ que têm o inverso igual a ele próprio.

Logo, $(n-1)!\equiv1\cdot(n-1)\equiv-1\pmod{n}$ e, portanto, $n~|~(n-1)!+1$