"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.