aritmética - aula 5 - algoritmo de euclides
TRANSCRIPT
![Page 1: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/1.jpg)
Sumário
ALGORITMO DE EUCLIDES
Luciana Santos da Silva Martinolulismartino.blogspot.com.br
PROFMAT - Colégio Pedro II
07 de outubro de 2016
![Page 2: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/2.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Sumário
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 3: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/3.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Outline
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 4: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/4.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Máximo Divisor Comum
Definição: Sejam dados dois inteiros a e b, distintos ou não. Umnúmero inteiro d será dito um divisor comum de a e b se d | a e d | b
Definição: Diremos que um número inteiro d ≥ 0 é um máximodivisor comum (mdc) de a e b, se possuir as seguintes propriedades:
i) d é um divisor comum de a e bii) d é divisível por todo divisor comum de a e bii’) Se c é divisor comum de a e b então c | d
Resultado: O mdc de dois números, quando existe, é único
![Page 5: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/5.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Máximo Divisor Comum
O mdc de dois números inteiros, que demonstraremos maistarde sempre existir, é denotado por (a,b), sendo(a,b) = (b,a)
Em alguns casos particulares, é fácil verificar a existência domdc
. Se a ∈ Z então (0,a) = |a|, (1,a) = 1 e (a,a) = |a|
. ∀b ∈ Z temos quea | b ⇔ (a,b) = |a|(a,b) = 0⇔ a = b = 0
![Page 6: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/6.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Máximo Divisor Comum
Resultado: O máximo divisor comum de dois números, nãoambos nulos, quando existe, é efetivamente o maior dentretodos os divisores comuns desses números
. Dados a,b ∈ Z, se existir (a,b) então(a,b) = (−a,b) = (a,−b) = (−a,−b)
Lema 5.2: Sejam a,b,n ∈ Z. Se existe (a,b − na), então,(a,b) = (a,b − na)
![Page 7: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/7.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Máximo Divisor Comum
Exemplo 5.3: Dados a ∈ Z com a 6= 1 e m ∈ N, temos que(am−1a−1 ,a− 1
)= (a− 1,m)
Exemplo 5.4: Sejam a ∈ Z e n ∈ N, vamos determinar(a + 1,a2n + 1)
Exemplo 5.5: Sejam a ∈ Z e n ∈ N, vamos determinar(a + 1,a2n+1 − 1)
![Page 8: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/8.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Outline
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 9: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/9.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Algoritmo de Euclides
Prova construtiva da existência do mdc dada por Euclides
Dados a,b ∈ N, podemos supor b ≤ a. Se b = 1 ou b = a, ou aindab | a, já vimos que (a,b) = a
Suponhamos então que 1 < b < a e que b - a
q1 q2 q3 ... qn−1 qn qn+1
a b r1 r2 ... rn−2 rn−1 rn = (a,b)r1 r2 r3 r4 ... rn
Exemplo 5.6: (372,162)
![Page 10: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/10.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Outline
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 11: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/11.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Propriedades do mdc
Sejam a,b ∈ Z. Definimos o conjunto
I (a,b) = {xa + yb; x , y ∈ Z}
Note que se a e b não são simultaneamente nulos entãoI (a,b) ∩ N 6= ∅
A seguir utilizaremos a notação
dZ = {ld , l ∈ Z}
![Page 12: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/12.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Propriedades do mdc
Teorema 5.7: Sejam a,b ∈ Z, não ambos nulos. Sed = minI (a,b) ∩ N, então
i) d é o mdc de a e b eii) I (a,b) = dZ
Esse Teorema nos dá uma outra demonstração da existência do mdcde dois números a e b e da existência dos inteiros m e n tais que(a,b) = ma + nb, mas não é uma demonstração construtiva
Corolário 5.8: Quaisquer que sejam a,b ∈ Z, não ambos nulos, en ∈ N tem-se que (na,nb) = n(a,b)
Corolário 5.9: Dados a,b ∈ Z, não ambos nulos, tem-se que(a
(a,b) ,b
(a,b)
)= 1
![Page 13: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/13.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Propriedades do mdc
Definição: Dois números inteiros a e b serão ditos primosentre si, ou coprimos, se (a,b) = 1, ou seja, se o único divisorpositivo de ambos é 1
Proposição 5.10: Dois números inteiros a e b são primosentre si se, e somente se, existem números inteiros m e n taisque ma + nb = 1
![Page 14: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/14.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Propriedades do mdc
Lema de GaussTeorema 5.11: Sejam a, b e c números inteiros. Se a | bc e
(a,b) = 1, então a | c
Corolário 5.12: Dados a, b e c números inteiros, com b e cnão ambos nulos, temos que
b | a e c | a⇔ bc(b, c)
| a
![Page 15: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/15.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
MDC: generalização
Definição: um número natural d será dito mdc de dados númerosinteiros a1, ...,an, não todos nulos, se possuir as seguintespropriedades:
i) d é um divisor comum de a1, ...,an
ii) Se c é um divisor comum de a1, ...,an então c | d
O mdc, quando existe, é certamente único e será representado por(a1, ...,an)
Proposição 5.13: Dados números inteiros a1, ...,an, não todos nulos,existe o seu mdc e (a1, ...,an) = (a1, ..., (an−1,an))
Essa Proposição nos fornece um método indutivo para o cálculo domdc de n inteiros
![Page 16: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/16.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Definição: Os inteiros a1, ...,an serão ditos primos entre si, oucoprimos, quando (a1, ...,an) = 1
. Dado um subconjunto finito A = {a1,a2, ...,an} de Z podemosdefinir o mdc de A como sendo mdc A = (a1,a2, ...,an)
. No caso em que A = {a1,a2, ...} é um subconjunto infinito deZ, ainda existe d = mdc A (Problema 5.2.13 p.100)
![Page 17: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/17.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Outline
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 18: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/18.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Algoritmo de Euclides Estendido
Suponhamos a ≥ b. Para calcular o mdc de a e b montamos a matriz
A =
[b 1 0a 0 1
]
. l2 = l2 − q1l1, sendo q1 =[
ab
]A1 =
[b 1 0
a− bq1 −q1 1
]=
[b 1 0r1 −q1 1
]onde r1 é o resto da divisão de a por b
. l1 = l1 − q2l2, sendo q2 =[
br1
]A2 =
[b − q2r1 1 + q1q2 −q2
r1 −q1 1
]=
[r2 1 + q1q2 −q2
r1 −q1 1
]onde r2 é o resto da divisão de b por r1
![Page 19: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/19.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Algoritmo de Euclides Estendido
. A linha (d ,m,n) da matriz B, obtida no final do processo, quecontém o elemento não nulo da primeira coluna será tal qued = (a,b)
. Os inteiros m e n assim obtidos são tais que (a,b) = ma + nb
Exemplo 5.14: (162,372)
![Page 20: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/20.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Outline
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 21: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/21.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Mínimo Múltiplo Comum
Definição: Diremos que um número inteiro é um múltiplo comum dedois números inteiros dados se ele é simultaneamente múltiplo deambos os números
Em qualquer caso os números ab e 0 são sempre múltiplos comunsde a e b
Definição: Diremos que um número inteiro m ≥ 0 é um mínimomúltiplo comum (mmc) dos números inteiros a e b, se possuir asseguintes propriedades:
i) m é um múltiplo comum de a e b, eii) se c é um múltiplo comum de a e b, então m | c
Resultado: O mmc, se existe, é único e é o menor dos múltiploscomuns positivos de a e b
![Page 22: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/22.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Mínimo Múltiplo Comum
. O mínimo múltiplo comum de a e b, se existe, é denotado por[a,b]
. Caso exista [a,b] = [−a,b] = [a,−b] = [−a,−b]
Resultado: [a,b] = 0⇔ a = 0 ou b = 0
Proposição 5.15: Dados dois números inteiros a e b, temosque [a,b] existe e [a,b](a,b) = |ab|
![Page 23: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/23.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Mínimo Múltiplo Comum
Corolário 5.16: Se a e b são números inteiros primos entre si,então [a,b] = |ab|
Exemplo 5.17: Sejam b e m dois números naturais. Vamosmostrar que, na sequência de números b,2b,3b, ...,mb,existem exatamente (b,m) números divisíveis por m
![Page 24: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/24.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Mínimo Múltiplo Comum
Definição: Diremos que um número natural m é um mmc dosinteiros não nulos a1, ...,an se m é múltiplo comum de a1, ...,an,e, se para todo múltiplo comum m′ desses números tem-seque m | m′
O mmc, se existe, é único, sendo denotado por [a1, ...,an]
Proposição 5.18: Sejam a1, ...,an números inteiros não nulos.Então existe o número [a1, ...,an] e[a1, ...,an−1,an] = [a1, ..., [an−1,an]]
![Page 25: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/25.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
Outline
1 Máximo Divisor Comum
2 Algoritmo de Euclides
3 Propriedades do mdc
4 Algoritmo de Euclides Estendido
5 Mínimo Múltiplo Comum
6 A Equação Pitagórica
![Page 26: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/26.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
A Equação Pitagórica
Vamos resolver em Z a equação pitagórica
X 2 + Y 2 = Z 2
Pitágoras: conjunto de soluções expressas por
x =n2 − 1
2, y = n , z =
n2 + 12
onde n > 1 é um inteiro ímpar
. Note que as soluções de Pitágoras não fornecem todas assoluções, já que a solução (8,15,17) não pode ser obtidadessa forma
. Quando os lados de um triângulo retângulo, solução daequação pitagórica, forem números naturais, ele será chamadode triângulo pitagórico
![Page 27: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/27.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
A Equação Pitagórica
Vamos determinar todas as soluções inteiras da equaçãopitagórica
. As únicas soluções com uma das coordenadas não nula são(0,b,±b), (a,0,±a), onde a,b ∈ Z: são chamadas de soluçõestriviais
. Como os expoentes a que estão elevadas as incógnitas sãotodos pares basta encontrar as soluções em números naturais
![Page 28: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/28.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
A Equação Pitagórica
Lema 5.20: Dados dois números naturais a e b primos entre si,se ab é um quadrado, então tanto a quanto b são quadrados
Resultado: Se ab = cn, onde a, b e c são números naturais,com (a,b) = 1, então a e b são potências n-ésimas(Problema 5.5.1, p.113) (Problema 7.1.3, p.149)
![Page 29: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/29.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
A Equação Pitagórica
. Um terno (a,b, c) de números naturais será dito um ternopitagórico quando for solução da equação pitagórica, ou seja,quando a2 + b2 = c2
. Chamaremos de triângulo pitagórico primitivo a um triânguloretângulo cujos lados são números naturais coprimos. Umterno que representa os lados de um triângulo pitagóricoprimitivo será chamado de terno pitagórico primitivo
. Os ternos pitagóricos primitivos (a,b, c) dão origem a todosos ternos pitagóricos. Podemos portanto concentrar nossaatenção nos ternos primitivos
![Page 30: Aritmética - Aula 5 - Algoritmo de Euclides](https://reader034.vdocumento.com/reader034/viewer/2022042619/587822e11a28aba12d8b6de5/html5/thumbnails/30.jpg)
Máximo Divisor Comum Algoritmo de Euclides Propriedades do mdc Algoritmo de Euclides Estendido Mínimo Múltiplo Comum A Equação Pitagórica
A Equação Pitagórica
. As soluções primitivas
a = n2 −m2 , b = 2nm , c = n2 + m2
são devidas a Euclides, e toda solução primitiva é representada de modoúnico nessa forma
Teorema 5.21: As soluções em N da equação pitagórica X 2 + Y 2 = Z 2
expressam-se de modo único, a menos da ordem de x e y , como
x = l(n2 −m2) , y = 2lnm e z = l(n2 + m2)
onde l, n,m ∈ N, n > m, com m e n coprimos e com paridades distintas.Reciprocamente, todo terno (x , y , z) como acima, é um terno pitagórico
Resultado: Dado um número natural existe sempre um triângulo pitagóricocom um dos catetos igual a esse número natural. Entretanto, nem todonúmero natural c ímpar pode ser a hipotenusa de um triângulo pitagórico