Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Números Inteiros

Prof. Eanes Torres Pereira

FMCC2

Prof. Eanes Torres Pereira 1 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Roteiro

1. O Algoritmo da Divisão

2. Divisibilidade

3. O Algoritmo de Euclides

3. Números Primos

Prof. Eanes Torres Pereira 2 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

O Algoritmo da Divisão

I Consideramos Z = {0, ± 1, ± 2, . . .}
I Princípio da Boa Ordenação - PBO. Todo subconjunto
não-vazio do conjunto dos inteiros não-negativos contém um
menor elemento.
I O PBO não é válido para o conjunto de todos os inteiros.
I Divisão Inteira. dividendo = (divisor)(quociente) + (resto)
I Teorema 1.1 (O algoritmo da divisão). Sejam a, b inteiros
com b > 0. Então, existem inteiros únicos q e r tais que:
a = bq + r e 0 ≤ r < b.

Prof. Eanes Torres Pereira 2 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

O Algoritmo da Divisão

I Observações sobre o Algoritmo da Divisão:

1. Esse teorema permite a possibilidade de que o dividendo, a,
seja negativo.
2. Por isso, há uma afirmação adicional indicando que o
quociente, q, e o resto, r , são únicos e r é não-negativo.
3. A ideia fundamental para a prova do Teorema 1.1 é que a
divisão é apenas a repetição de subtrações.

Prof. Eanes Torres Pereira 3 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Exercícios

Determine o quociente e o resto quando a é dividido por b:

1. a = 302, b = 19
2. a = 0, b = 19
3. a = 2001, b = 17

Prof. Eanes Torres Pereira 4 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Respostas do Exercícios

1. quociente 15; resto 17;

2. quociente 0; resto 0;
3. quociente 117; resto 12

Prof. Eanes Torres Pereira 5 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

O Algoritmo da Divisão

I Corolário 1.2. Sejam a e c inteiros, com c 6= 0. Então,

existem inteiros únicos q e r , tal que: a = cq + r e 0 ≤ r < |c|.
I Como Exercício, prove o Corolário 1.2.

Prof. Eanes Torres Pereira 6 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Roteiro

1. O Algoritmo da Divisão

2. Divisibilidade

3. O Algoritmo de Euclides

3. Números Primos

Prof. Eanes Torres Pereira 7 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Divisibilidade

I Definição. Sejam a e b inteiros com b 6= 0. Dizemos que b

divide a (ou que b é divisor de a ou que b é um fator de a) se
a = bc para algum inteiro c. Em símbolos, "b divide
a" escrito b | a e "b não divide a" é escrito b - a.
I Exemplo 1. 3|24 por que 24 = 3 · 8. Mas 3 - 7. Divisores
negativos são permitidos: −6|54 por que 54 = (−6)(−9), mas
−6 - (−13).
I Exemplo 2. Todo inteiro b diferente de zero divide zero, por
que 0 = b · 0. Para todo inteiro a, temos 1|a, por que
a = 1 · a.

Prof. Eanes Torres Pereira 7 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Máximo Divisor Comum

I Definição. Sejam a e b inteiros, diferentes de zero. O maior

divisor comum (mdc) de a e de b é o maior inteiro d que
divide ambos, a e b. Em outras palavras, d é o mdc de a e de
b desde que:
(i) d|a e d|b;
(ii) se c|a e c|b, então c ≤ d.
I Vamos denotar o mdc de a e de b como mdc(a, b).
I Exemplo. mdc(12, 30) = 6. Os únicos divisores comuns de 10
e de 21 são 1 e -1. Portanto, mdc(10, 21) = 1. Dois inteiros
cujo mdc é 1, são chamados de primos entre si ou primos
relativos.

Prof. Eanes Torres Pereira 8 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Máximo Divisor Comum

I Teorema 1.3 Sejam a e b inteiros, ambos não são zero

simultaneamente, e seja d seu mdc. Então, existem inteiros u
e v , não necessariamente únicos, tais que d = au + bv .
I Exercício. Para cada par de números a seguir, determine o
mdc.
1. 56 e 72
2. 24 e 138
I Respostas:

Prof. Eanes Torres Pereira 9 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Máximo Divisor Comum

I Teorema 1.3 Sejam a e b inteiros, ambos não são zero

simultaneamente, e seja d seu mdc. Então, existem inteiros u
e v , não necessariamente únicos, tais que d = au + bv .
I Exercício. Para cada par de números a seguir, determine o
mdc.
1. 56 e 72
2. 24 e 138
I Respostas:
1. mdc(56,72) = 8

Prof. Eanes Torres Pereira 9 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Máximo Divisor Comum

I Teorema 1.3 Sejam a e b inteiros, ambos não são zero

simultaneamente, e seja d seu mdc. Então, existem inteiros u
e v , não necessariamente únicos, tais que d = au + bv .
I Exercício. Para cada par de números a seguir, determine o
mdc.
1. 56 e 72
2. 24 e 138
I Respostas:
1. mdc(56,72) = 8
2. mdc(24, 138) = 6

Prof. Eanes Torres Pereira 9 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Máximo Divisor Comum

I Teorema 1.3 Sejam a e b inteiros, ambos não são zero

simultaneamente, e seja d seu mdc. Então, existem inteiros u
e v , não necessariamente únicos, tais que d = au + bv .
I Exercício. Para cada par de números a seguir, determine o
mdc.
1. 56 e 72
2. 24 e 138
I Respostas:
1. mdc(56,72) = 8
2. mdc(24, 138) = 6

Prof. Eanes Torres Pereira 9 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Máximo Divisor Comum

I Corolário 1.4. Sejam a e b inteiros, não zero

simultaneamente, e seja d um inteiro positivo. Então, d é o
mdc de a e de b se, e somente se, d satisfaz estas condições:
(i) d|a e d|b;
(ii) se c|a e c|b, então c|d.
I Teorema 1.5. Se a|bc e mdc(a,b)=1, então a|c.

Prof. Eanes Torres Pereira 10 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Roteiro

1. O Algoritmo da Divisão

2. Divisibilidade

3. O Algoritmo de Euclides

3. Números Primos

Prof. Eanes Torres Pereira 11 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

O Algoritmo de Euclides

I Teorema 1.6. Sejam a e b inteiros positivos com a ≥ b. Se

b|a, então mdc(a, b) = b. Se b - a, então aplique o algoritmo
da divisão repetidamente como segue:
a = bq0 + r0 , 0 < r0 < b
b = r0 q1 + r1 , 0 ≤ r1 < r0
r0 = r1 q2 + r2 , 0 ≤ r2 < r1
r1 = r2 q3 + r3 , 0 ≤ r3 < r2
···
···
···
I Esse processo para quando um resto igual a zero for obtido. O
último resto não-zero é o mdc de a e de b.

Prof. Eanes Torres Pereira 11 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Exemplo

I Use o algoritmo de Euclides para calcular mdc(324, 148).

Solução:
324 = 148·2 + 28
148 = 28·5 + 8
28 = 8·3 + 4
8 = 4·2 + 0
I Use substituição retroativa para escrever 4 como uma
combinação linear de 324 e 148.
I Resposta:

Prof. Eanes Torres Pereira 12 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Exemplo

I Use o algoritmo de Euclides para calcular mdc(324, 148).

Solução:
324 = 148·2 + 28
148 = 28·5 + 8
28 = 8·3 + 4
8 = 4·2 + 0
I Use substituição retroativa para escrever 4 como uma
combinação linear de 324 e 148.
I Resposta:
mdc(324,148) = 4; 4 = 16 · 324 − 35 · 148.

Prof. Eanes Torres Pereira 12 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

O Algoritmo de Euclides

I Lema 1.7. Se a, b, q, r ∈ Z e a = bq + r , então mdc(a,b) =

mdc(b,r).
I Exercício. Expresse cada um dos mdc(a,b) a seguir como
uma combinação linear de a e de b:
I mdc(56, 72)
I mdc(24,138)
I mdc(143, 227)
I mdc(314, 159)

Prof. Eanes Torres Pereira 13 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Roteiro

1. O Algoritmo da Divisão

2. Divisibilidade

3. O Algoritmo de Euclides

3. Números Primos

Prof. Eanes Torres Pereira 14 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Números Primos

I Definição. Um inteiro p é chamado de primo se p 6= 0,

p 6= ±1 e os únicos divisores de p são ±1 e ±p.
I Exemplo. 3, -5, 7, -11, 13 e -17 são primos, mas 15 não é. O
inteiro 4567 é primo
I Teorema 1.8. Seja p um inteiro com p 6= 0, p 6= ±1. Então p
é primo se, e somente se, p tem esta propriedade: sempre que
p|bc, então p|b ou p|c.
I Corolário 1.9. Se p é primo e p|a1 a2 . . . an , então p divide
pelo menos um dos ai .

Prof. Eanes Torres Pereira 14 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

O Teorema Fundamental da Aritmética

I Teorema 1.10. Todo inteiro n exceto 0, ±1 é o produto de

primos.
I Teorema 1.11. A fatoração de um inteiro em números primos
é única.
I Corolário 1.12. Todo inteiro n > 1 pode ser escrito apenas
na forma n = p1 p2 p3 . . . pr , em que os pi são primos positivos
tais que p1 ≤ p2 ≤ p3 ≤ . . . ≤ pr .

Prof. Eanes Torres Pereira 15 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Exercício

I Busque em livros texto de Álgebra Abstrata demonstrações

para os teoremas, corolários e lemas vistos neste slide e
estude-os.

Prof. Eanes Torres Pereira 16 / 17 UFCG CEEI

Aritmética em Z Divisibilidade O Algoritmo de Euclides Números Primos

Referência

I Abstract Algebra an Introduction. Thomas W. Hungerford.

Prof. Eanes Torres Pereira 17 / 17 UFCG CEEI