Bezout e algoritmo de Euclides
O algoritmo de Euclides calcula o MDC repetindo divisoes. A identidade de Bezout diz que esse MDC pode ser escrito como combinacao linear dos dois numeros.
Identidade de Bezout
Se d = mdc(a,b), entao existem inteiros x e y tais que ax + by = d
Essa identidade e a ponte entre divisibilidade, diofantinas e inverso modular.
Exemplo
Use Euclides para calcular mdc(84,30).
1
84 = 30.2 + 24.
2
30 = 24.1 + 6.
3
24 = 6.4 + 0.
Logo, mdc(84,30)=6.
Funcao phi de Euler
A funcao φ(n) conta quantos inteiros de 1 ate n sao coprimos com n.
Formula por fatoracao
Se n = p1a...pkm, entao φ(n) = n(1-1/p1)...(1-1/pk)
Exemplo
Calcule φ(12).
1
12 = 22.3.
2
φ(12)=12(1-1/2)(1-1/3).
φ(12)=4.
Teorema de Euler
O teorema de Euler amplia a ideia de Fermat. Se a e coprimo com n, entao elevar a a φ(n) produz resto 1 modulo n.
Forma classica
Se mdc(a,n)=1, entao aφ(n) ≡ 1 (mod n)
Quando n e primo, temos φ(n)=n-1, e Euler vira exatamente o pequeno teorema de Fermat.
Pequeno teorema de Fermat
Se p e primo e a nao e multiplo de p, entao ap-1 ≡ 1 (mod p). Ele e muito util para reduzir potencias grandes modulo primo.
Forma classica
Se p primo e p nao divide a, entao ap-1 ≡ 1 (mod p)
Exemplo
Reduza 3100 (mod 7).
1
Como 7 e primo, 36 ≡ 1 (mod 7).
2
100 = 6.16 + 4, entao 3100 ≡ (36)16.34 ≡ 34.
3
32=9 ≡ 2, logo 34 ≡ 4.
3100 ≡ 4 (mod 7).
Como usar esses teoremas
| Ferramenta | Quando ela entra |
|---|---|
| Euclides | calcular MDC rapido |
| Bezout | provar existencia de combinacao linear e diofantinas |
| Phi de Euler | contar coprimos e preparar o teorema de Euler |
| Teorema de Euler | reduzir expoentes quando a e n sao coprimos |
| Fermat | trabalhar potencias modulo primo |
O ponto importante e escolher a ferramenta certa pelo formato do problema, nao decorar nomes isolados.
Exercicio rapido
Cheque rapido
Quando mdc(a,n)=1, qual teorema reduz expoentes usando φ(n)?