Teoria dos Números e Algoritmo de Euclides

Prévia do material em texto

UNIVERSIDADE FEDERAL DA BAHIA- UFBA 
DISCIPLINA: Matemática Discreta II – MAT A97 
Michele Novais 
 
 
2. TEORIA DOSNÚMEROS 
2.1 DIVISIBILIDADE 
 Se ,dizemos que , denotado por se 
existe um tal que 
 
 Se , então . 
 
 
 
 
 
 Se 
 
 
 
Teorema 2.1.4. A divisão tem as seguintes propriedades: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
(Teorema de Eudoxios) Dados então ou 
se encontra entre dois múltiplos consecutivos de Isto é, para cada par 
de inteiros, tal que 
Para 
 
Para 
 
 
 . tal que 
 
 
 Dados existe um único par de inteiros 
 tais que 
 com 0 
q é chamado de quociente e r de resto da divisão de . 
 
 
 
 
 
 
 
 
 
 
2.2. MÁXIMO DIVISOR COMUM 
O máximo divisor comum de dois inteiros 
( denotado por é o maior inteiro que 
divide . 
 Seja o máximo divisor comum de então 
 tais que 
 
 
 
 
 
 
 
 Se . 
 
 
 
 
 
 
 
 
Teorema 2.2.3. e onde então 
 
 
 
 
 
 
 
 
 
 
3. ALGORITMO DE EUCLIDES 
 
 Calcular o 
 
 
 
 
 
 
 
Calcular o 
 
 Sejam com Se o 
algoritmo da divisão for aplicado sucessivamente para obter 
 , então o 
 o ultimo resto não nulo.