Teoria dos números

Prévia do material em texto

- -1
TEORIA DOS NÚMEROS
MÁXIMO DIVISOR COMUM (MDC) E MÍNIMO 
MÚLTIPLO COMUM (MMC)
- -2
Olá!
Os conceitos de Máximo Divisor Comum e Mínimo Múltiplo Comum são fundamentais para o bom entendimento
de um curso de Matemática Superior como ferramenta na resolução de diversos tipos de problemas.
Nesta aula, você irá:
1- Identificar o Máximo Divisor Comum e o Mínimo Múltiplo Comum entre números inteiros;
2- Relacionar o Máximo Divisor Comum com o Mínimo Múltiplo Comum entre números inteiros.
1 Definição de Máximo Divisor Comum
Dados a, b ∈ Z não conjuntamente nulos (a≠0 ou b≠0), dizemos que o inteiro positivo d (d > 0) é o máximo
divisor comum de a e b quando este satisfizer as seguintes condições:
d|a e d|b
se c|a e se c|b, então c≤ d
Notação: mdc (a,b) ou simplesmente (a,b).
Fique ligado
Notemos que:
A condição (a) nos assegura que é um divisor comum de e .d a b
A condição (b) nos assegura que é o maior dentre todos os divisores de e .d a b
- -3
2 Inteiros primos entre si
Propriedades:
mdc (a,b) = mdc (b,a)
mdc (0,0) não existe
mdc (a,1) = 1
Se a ≠ 0, então o mdc (a, 0) =|a|
Se a|b então o mdc (a,b) = |a|
Exemplos
mdc (12,30) = 6
mdc (-3,0) = |-3| = 3
mdc (-7,28) = 7
mdc (0,-15) = 15
mdc (-16,24) = mdc (16,-24) = mdc (-16,-24) = 8
Teorema: Se a e b são dois inteiros não conjuntamente nulos , então existe e é único o mdc (a,b). Além disto,
existem inteiros x e y tais que o mdc (a,b) é uma combinação linear de a e b, ou seja:
mdc (a,b) = ax + by
Observação: Os exemplos que aparecem ao lado das propriedades sugerem ao leitor que são correspondentes
as propriedades , e não são.
Definição: Sejam a e b inteiros não conjuntamente nulos. Dizemos que a e b são se e somente seprimos entre si
o mdc (a,b) = 1
Exemplos: mdc (2,5) = 1 mdc (-9,16) = 1 mdc (-27,-35) = 1
Saiba mais
Definição
Dados dois inteiros com, denomina-se MDC entre a e b o que dividamaior inteiro positivo
simultaneamente a e b.
- -4
Teorema: Dois inteiros a e b, não conjuntamente nulos, são primos entre si se e somente se existem inteiros x e
y tais que ax+by=1.
Corolário: mdc (a,b) = d → mdc (a/d,b/d) = 1
Exemplo: mdc (-12,30) = 6 → mdc (-12/6,30/6) = 1
3 Crivo de Erastótenes
Crivo de Erastótenes é um processo que consiste na construção de uma tabela de primos que não excedam um
dado inteiro n.
Procedimento: Escrevem-se na ordem natural todos os inteiros desde 2 até n.
Eliminam-se todos os compostos que são múltiplos dos primos, isto é, 2p, 3p, 4p,...
Exemplo: Deseja escrever todos os primos menores n = 100.
O consiste em escrever todos os inteiros desde 2 até n.crivo de Eratóstenes
Em seguida, eliminar todos os compostos múltiplos de todos os primos menores ou iguais à √n. Então devemos
eliminar os múltiplos de 2, 3, 5 e 7. Eliminaremos o 2, 2.2, 2.3, 2.4 ...ou seja, todos os pares. A seguir o 3, o 3.2, 3.3
..., e todos os múltiplos de 3. A seguir, os múltiplos de 5 e finalmente, os múltiplos de 7.
Quadro:
Os inteiros positivos não eliminados – destacados na tabela - são todos os primos menores que 100.
Seja n ≥ 2.
√313 17,69≅
P= {2,3,5,11,13,17}
Nenhum desses valores pertencentes ao conjunto P divide 313, portanto 313 é primo.
- -5
4 Definição de Máximo Divisor Comum
Definição: Dados a não conjuntamente nulos ( ou ). Dizemos que o inteiro positivo (, b, c є Z a ≠ 0 ou b ≠ 0 c ≠ 0 d d
) é o de a, b e c quando este satisfizer as condições:> 0 máximo divisor comum
d|a, d|b e d|c
se e|a , e|b e e|c então e ≤ d
Exemplo: mdc (49, 210, 350) = mdc ((49, 210), 350) = 7
Exemplo: mdc (39, 42, 54) = mdc ((39, 42), 54) = 3
5 Algoritmo de Euclides (para o cálculo do MDC)
Dados a, b, c є Z como determinar mdc (a, b)?
Dados a, b, c є Z como determinar mdc (a, b)?
Dividindo por : a b a = bq + r 0 ≤ r <|b|
Se r = 0, então (a, b) = (b, r)= (b,0) = b
Se r ≠ 0 dividimos b por r : b = q1r. + r1 0 ≤ r1 < |r|
Se r1 = 0, então, (a, b) = (b, r)= (r,r1) = (r,0) = r
Se r1 ≠ 0 dividimos r por r1: r = q2r1 + r2 0 ≤ r2 < |r2I
Assim,
r = q2r1 + r2
r2 = q3r2 + r3
r2 = q4r3 + r4
Exemplo: Represente (1238, 325) como soma de múltiplos desses inteiros:
Fique ligado
Trabalhamos com números finitos, portanto o resto fica cada vez menor até chegar a zero.
r = q r + r 0 ≤ r < |r |
n-2 n n-1 n n n-1
r = q r
n-1 n-1 n
- -6
Exemplo:
Segundo exemplo: O mdc de dois a e b números inteiros e positivos é 74 e na sua determinação pelo algoritmo
de Euclides foram obtidos os quocientes: 1, 2, 2, 5, 1 e 3. Calcule a e b.
- -7
6 MMC de dois inteiros
Definição:
Sejam a, b Є Z, a ≠ 0, b ≠ 0. Chamamos de mínimo múltiplo comum de a e b o inteiro m (m > 0) que satisfaz a:
a|m e b|m
se a|c e se b|c com c > 0, então m ≤ c
Observações:
A condição (a) nos assegura que m é um múltiplo comum de a e b.
A condição (b) nos assegura que m é o menor dentre todos os múltiplos comuns positivos de a e b.
Notação: mmc(a, b)
Observação:
Pelo princípio da Boa Ordenação (PBO) o conjunto dos múltiplos comuns de a e b possui elemento mínimo.
Assim, temos que o mmc (a,b) existe sempre e é único.
Como ab é múltiplo comum de a e b, mmc (a, b) ≤ ab|
Particularmente: a|b mmc(a, b) = |b|⇒
Exemplo:
a = - 12 e b = 30.
Múltiplos comuns positivos: 60, 120, 180, ...,
mmc (a, b) ≤|ab|
- -8
Como o menor deles é 60 mmc (-12,30) = 60⇒
7 Relação entre MDC e MMC
Teorema: temos: mdc (a, b) mmc (a, b) = a . ba,b Є Z
Exemplo: Determinar o mmc (963,657), sabendo que
mdc (963,657) = 9. 9 . mmc (963,657) = 963. 657
mmc (963,657) = 963. 657/ 9
mmc (963,657) = 70299
Corolário: mmc (a,b) = ab ↔ mdc (a,b) = 1a,b Є Z
8 MMC de vários inteiros
Definição: Dados a, b, c Є Z diferentes de zero (a ≠ 0 e b ≠ 0 e c ≠ 0). Dizemos que o inteiro positivo m (m > 0) é o
mínimo múltiplo comum (mmc) de a, b e c quando este satisfizer as condições:
a|m, b|m e c|m
se a|e, b|e e c|e com e > 0, então m ≤ e
Exemplo: mmc (39, 102, 75) = 33150
O que vem na próxima aula
Na próxima aula, você vai estudar:
• Conceito de números primos.
CONCLUSÃO
Nesta aula, você:
• Identificou o Máximo Divisor Comum e o Mínimo Múltiplo Comum entre números inteiros;
• Relacionou o Máximo Divisor Comum com o Mínimo Múltiplo Comum entre números inteiros.
•
•
•
	Olá!
	1 Definição de Máximo Divisor Comum
	2 Inteiros primos entre si
	3 Crivo de Erastótenes
	4 Definição de Máximo Divisor Comum
	5 Algoritmo de Euclides (para o cálculo do MDC)
	6 MMC de dois inteiros
	7 Relação entre MDC e MMC
	8 MMC de vários inteiros
	O que vem na próxima aula
	CONCLUSÃO