aula05_2010

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

A´lgebra A – Aula 05
Induc¸a˜o e Fermat
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Induc¸a˜o finita
Seja P(n) uma proposic¸a˜o que afirma que uma determinada
propriedade vale para cada nu´mero natural n. Por exemplo:
I Se p e´ um nu´mero primo, enta˜o np − n e´ divis´ıvel por p para
todo natural n.
I A soma de 1 ate´ n e´ n(n+1)2
Induc¸a˜o finita
Princ´ıpio da induc¸a˜o finita. Para que uma proposic¸a˜o P(n)
seja verdadeira para todo n natural, basta que:
1. P(1) seja verdadeira.
2. Se P(k) for verdadeira para algum nu´mero natural k,
enta˜o P(k + 1) tambe´m e´ verdadeira.
Pequeno teorema de Fermat
Lema. Seja p um nu´mero primo e a, b inteiros. Enta˜o,
(a + b)p ≡ ap + bp (mod p)
Teorema de Fermat. Seja p um nu´mero primo e a um
nu´mero inteiro. Enta˜o
ap ≡ a (mod p).
Pequeno teorema de Fermat
Prova.
I Se n = 1, enta˜o 1p ≡ 1 (mod p) trivialmente.
I Suponhamos que np ≡ n (mod p) para algum n inteiro
positivo. Usando o lema anterior,
(n + 1)p ≡ np + 1p ≡ np + 1 (mod p)
Como pela hipo´tese de induc¸a˜o temos np ≡ n (mod p),
(n + 1)p ≡ np + 1 ≡ n + 1 (mod p)
Teorema de Fermat II
Teorema de Fermat II. Seja p um nu´mero primo e a um
inteiro que na˜o e´ divis´ıvel por p. Enta˜o,
ap−1 ≡ 1 (mod p).
Prova. Como mdc(a, p) = 1, existe a′ tal que
aa′ ≡ 1 (mod p)
Multiplicando ambos os membros de ap ≡ a (mod p). por a′,
obtemos:
a′.a.ap−1 ≡ a′.a (mod p).
Logo,
ap−1 ≡ 1 (mod p).
Teorema de Fermat
Podemos simplificar algumas contas usando o Teorema de Fermat.
De fato, sejam p primo, a inteiro tal que mdc(a, p) = 1 e k um
nu´mero inteiro tal que k ≥ p − 1. Dividindo k por p − 1,
k = (p − 1).q + r 0 ≤ r < (p − 1)
Logo,
ak ≡ a(p−1).q+r ≡ (ap−1)q.ar (mod p).
Mas (ap−1) ≡ 1 (mod p) e portanto
ak ≡ ar (mod p).
Exerc´ıcios propostos - Cap´ıtulo 5
1, 3, 4, 6, 7, 8, 12