Técnica olímpica - Teorema de Wilson estendido
Enviado: Qui 03 Set, 2020 20:19
É um fato bem conhecido que se p é primo então: [tex3](p-1)! \equiv -1 \mod(p) [/tex3]
, mas algo pouco comentado é que se n é composto e diferente de 4, então [tex3](n-1)! \equiv 0 \mod(n) [/tex3]
. Primeiro vamos a conceitos básicos:
"a" é dito inverso de "b" módulo k, se [tex3]ab \equiv 1 \mod(k) [/tex3].
"a" tem inverso módulo "k", se e somente se [tex3]mdc(a,k) = 1 [/tex3]
Demonstração:
Primeiro a volta: [tex3]mdc(a,k) = 1 [/tex3] , então pelo teorema de Bezout existem inteiros x e y tais que: [tex3]ax+ky = 1 [/tex3]
Olhando essa expressão módulo k, temos que: [tex3]ax \equiv 1 \mod(k) [/tex3] e está feito.
Agora a ida: Existe b tal que: [tex3]ab \equiv 1 \mod(k) [/tex3] , ou seja, existe x inteiro tal que: [tex3]ab -1=kx [/tex3]
Seja [tex3]d = mdc(a,k) [/tex3] , então [tex3]d|ab [/tex3] , [tex3]d|kx [/tex3] e portanto [tex3]d|1\rightarrow \boxed{d = 1} [/tex3]
Os inversos são únicos módulo p primo
Demonstração:
Sejam a,b,c<p tais que: [tex3]\begin{cases}
ab\equiv 1 \mod(p) \\
ac \equiv 1 \mod(p)
\end{cases}[/tex3] , então [tex3]a\cdot (b-c) \equiv 0 \mod(p) [/tex3] , ou seja: [tex3]b\equiv c \mod(p) [/tex3]
Nas classes de congruência módulo p, apenas [tex3]1 [/tex3] e [tex3]p-1 [/tex3] são inversos de si mesmos:
Demonstração:
Se a<p tal que [tex3]a^2 \equiv 1 \mod(p)\rightarrow (a-1)\cdot (a+1)\equiv 0 \mod(p) [/tex3] , portanto ou [tex3]a\equiv 1 \mod(p) [/tex3] ou [tex3]a\equiv p-1 \mod(p) [/tex3]
Teorema de Wilson diz que se p é primo, então: [tex3](p-1)! \equiv -1 \mod(p) [/tex3]
Demonstração:
[tex3](p-1)! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot .... (p-1) \equiv 1 \cdot (p-1) \equiv -1 \mod(p)[/tex3]
Teorema de Wilson estendido diz que se n é composto e diferente de 4, então [tex3](n-1)! \equiv 0 \mod(n) [/tex3]
Demonstração:
Primeiro caso, se n=ab, onde [tex3]2\leq a < b \leq n-2 [/tex3] , então a e b aparecem no produto [tex3](n-1)! [/tex3] e está provado. Segundo caso, se n não pode ser fatorado dessa forma, então [tex3]n = p^2 [/tex3] para algum primo p>2. Mas sendo assim, então: [tex3]2p<p^2=n [/tex3] , ou seja, p e 2p aparecem no produto [tex3](n-1)![/tex3] e está provado.
"a" é dito inverso de "b" módulo k, se [tex3]ab \equiv 1 \mod(k) [/tex3].
"a" tem inverso módulo "k", se e somente se [tex3]mdc(a,k) = 1 [/tex3]
Demonstração:
Resposta
Primeiro a volta: [tex3]mdc(a,k) = 1 [/tex3] , então pelo teorema de Bezout existem inteiros x e y tais que: [tex3]ax+ky = 1 [/tex3]
Olhando essa expressão módulo k, temos que: [tex3]ax \equiv 1 \mod(k) [/tex3] e está feito.
Agora a ida: Existe b tal que: [tex3]ab \equiv 1 \mod(k) [/tex3] , ou seja, existe x inteiro tal que: [tex3]ab -1=kx [/tex3]
Seja [tex3]d = mdc(a,k) [/tex3] , então [tex3]d|ab [/tex3] , [tex3]d|kx [/tex3] e portanto [tex3]d|1\rightarrow \boxed{d = 1} [/tex3]
Demonstração:
Resposta
Sejam a,b,c<p tais que: [tex3]\begin{cases}
ab\equiv 1 \mod(p) \\
ac \equiv 1 \mod(p)
\end{cases}[/tex3] , então [tex3]a\cdot (b-c) \equiv 0 \mod(p) [/tex3] , ou seja: [tex3]b\equiv c \mod(p) [/tex3]
Demonstração:
Resposta
Se a<p tal que [tex3]a^2 \equiv 1 \mod(p)\rightarrow (a-1)\cdot (a+1)\equiv 0 \mod(p) [/tex3] , portanto ou [tex3]a\equiv 1 \mod(p) [/tex3] ou [tex3]a\equiv p-1 \mod(p) [/tex3]
Demonstração:
Resposta
[tex3](p-1)! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot .... (p-1) \equiv 1 \cdot (p-1) \equiv -1 \mod(p)[/tex3]
Demonstração:
Resposta
Primeiro caso, se n=ab, onde [tex3]2\leq a < b \leq n-2 [/tex3] , então a e b aparecem no produto [tex3](n-1)! [/tex3] e está provado. Segundo caso, se n não pode ser fatorado dessa forma, então [tex3]n = p^2 [/tex3] para algum primo p>2. Mas sendo assim, então: [tex3]2p<p^2=n [/tex3] , ou seja, p e 2p aparecem no produto [tex3](n-1)![/tex3] e está provado.