Slide - Aula 9 Teorema Fundamental da Aritmética - Matemática Discreta 2021-2

Matematica Discreta — Aula 09 — ms Divisibilidade, MDC, teorema fundamental da aritmética Jamil Abreu UFLA/ICET/DMM Lavras/MG Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 1/26 Seja a um inteiro, a ̸= 0. Seja b um inteiro arbitr´ario. Dizemos que a divide b, ou que a ´e um divisor de b, se existe um inteiro c tal que a = bc. Escrevemos a|b para denotar que a divide b. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 2 / 26 Exemplo ( √ 2 ´e irracional) Pelo algoritmo da divis˜ao, todo inteiro ´e da forma 2m (par) ou 2m + 1 (´ımpar). Suponha √ 2 = a b (∗) para certos inteiros a e b. Elevando ao quadrado, temos a2 = 2b2. (∗∗) Observamos o seguinte: para qualquer inteiro x, x ´e par/´ımpar se e somente se x2 ´e par/´ımpar. Por (∗∗), a2 ´e par, logo a ´e par, digamos a = 2a1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 3 / 26 Continua¸c˜ao Substituindo em (∗∗), deduzimos que b2 = 2a2 1. Logo, tamb´em b2 ´e par, portanto b ´e par, digamos b = 2b1. Substituindo novamente na identidade acima, obtemos a2 1 = 2b2 1. (∗ ∗ ∗) Claramente, (∗ ∗ ∗) ´e da forma (∗∗), com novos inteiros a1 < a e b1 < b. A repeti¸c˜ao ad infinitum deste argumento forneceria sequˆencias decrescentes infinitas de inteiros positivos a > a1 > a2 > · · · e b > b1 > b2 > · · · , o que ´e um absurdo. Assim, (∗) ´e imposs´ıvel, portanto √ 2 ´e irracional. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 4 / 26 As seguintes afirma¸c˜oes s˜ao consequˆencias diretas da defini¸c˜ao de divisibilidade: 1 para todo a ̸= 0, a|0 e a|a; para todo b, ±1|b; 2 se a|b e b|c ent˜ao a|c; 3 se a|b e a|c ent˜ao a|bx + cy para quaisquer x e y; 4 se a|b e b ̸= 0 ent˜ao |a| ⩽ |b|. Quando a|b e a|c, dizemos que a ´e um divisor comum de b e c. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 5 / 26 Teorema | Dados dois inteiros a e b, nao ambos iguais a 0, existe um Unico inteiro d | tal que . | (i) d>0; | (ii) dla edb; | (iii) se dy é um inteiro tal que dy|\a e dy|b entao did. OBSERVACOES: r= A propriedade (iii) diz que todo divisor comum de ae b divide d. r= Segue de (4) que d é numericamente o maior dentre todos os divisores comuns de ae b. sr Logo, d é maximal em dois sentidos diferentes; por isso, d é denominado o maior divisor comum de ae b. r= Dizemos que d € 0 MDC de ae 5b; notacao d = (a, b). Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 6 / 26 Demonstra¸c˜ao Suponha 0 < b < a. Pelo algoritmo da divis˜ao existem q1 e r1 tais que a = bq1 + r1, onde 0 ⩽ r1 < b. Se r1 = 0 ent˜ao b|a e podemos tomar d = b, no que tange (i), (ii) e (iii). Se r1 ̸= 0 ent˜ao aplica¸c˜ao repetida do algoritmo da divis˜ao fornece pares ´unicos (q2, r2), (q3, r3), . . . tais que a = bq1 + r1, onde 0 < r1 < b, b = r1q2 + r2, onde 0 < r2 < r1, r1 = r2q3 + r3, onde 0 < r3 < r2, ... rk−2 = rk−1qk + rk, onde 0 < rk < rk−1, rk−1 = rkqk+1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 7 / 26 Como os sucessivos restos constituem uma sequˆencia decrescente de inteiros positivos, ´e claro que um resto igual a 0 deve ser obtido em algum momento. Afirmamos que d = rk cumpre as condi¸c˜oes (i), (ii) e (iii), o que deixamos para vocˆe verificar. Quanto aos casos excepcionais: ▶ se a < b, basta inverter os pap´eis de a e b acima; ▶ se a ou b s˜ao negativos, aplique o que foi feito acima a |a| ou |b|, conforme o caso; ▶ se a = 0, tome d = |b|. Quanto `a unicidade, sejam d1 e d2 satisfazendo (i), (ii) e (iii). Como d1 ´e divisor comum e d2 ´e MDC, ent˜ao d1|d2. Analogamente, d2|d1. Claramente, d1|d2 e d2|d1 implica d1 = d2. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 8 / 26 Exemplo Achar o MDC de 4147 e 10672. Dividindo 10672 por 4147 temos 10672 4147 2378 2 Logo, 10672 = 4147 × 2 + 2378. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 9 / 26 Continuando: 4147 = 2378 × 1 + 1769, 2378 = 1769 × 1 + 609, 1769 = 609 × 2 + 551, 609 = 551 × 1 + 58, 551 = 58 × 9 + 29, 58 = 29 × 2. Logo, (4147, 10672) = 29. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 10 / 26 Se a e b n˜ao tˆem fatores comuns maiores do que 1 ent˜ao (a, b) = 1. Nesse caso, dizemos que a e b s˜ao relativamente primos. As seguintes propriedades s˜ao dedut´ıveis da defini¸c˜ao ou do algoritmo da divis˜ao: (a) O MDC de n n´umeros a1, a2, . . . , an, definido como o divisor comum de todos estes n´umeros que ´e divis´ıvel por qualquer de seus divisores comuns, existe e pode ser encontrado da seguinte maneira: defina D1 = (a1, a2), D2 = (D1, a3), D3 = (D2, a4), ... Dn−1 = (Dn−2, an). Resulta que (a1, . . . , an) = Dn−1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 11 / 26 (b) (ma, mb) = m(a, b) para todo m > 0. (c) Se mla e m|b entao ( a >.) (a, b) m>m m- (d) Se (a, b) = d entdo existem x e y tais que ax + by = d. Logo, se a e b sao relativamente primos entao existem x e y tais que ax + by = 1. Reciprocamente, se a equacdo acima é possivel entdo (a, b) = 1. (e) Se um numero é relativamente primo com varios outros numeros entao ele é relativamente primo com o produto desses nimeros. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 12/26 Como exemplo da afirma¸c˜ao (e), se (a, b) = 1 e (a, c) = 1 ent˜ao existem x, y, t e u tais que ax + by = 1 e at + cu = 1. Logo, 1 = ax + by = ax + by(at + cu) = a(x + byt) + bc(yu) Portanto, (a, bc) = 1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 13 / 26 O algoritmo da divis˜ao pode ser usado para encontrar os n´umeros x e y na propriedade (d). Por exemplo: 29 = 551 − 9 × 58 = 551 − 9 × (609 − 1 × 551) = 10 × 551 − 9 × 609 = 10 × (1769 − 2 × 609) − 9 × 609 = 10 × 1769 − 29 × 609 = 10 × 1769 − 29 × (2378 − 1 × 1769) = 39 × 1769 − 29 × 2378 = 39 × (4147 − 1 × 2378) − 29 × 2378 = 39 × 4174 − 68 × 2378 = 39 × 4174 − 68 × (10672 − 2 × 4174) = 175 × 4174 − 68 × 10672. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 14 / 26 Teorema Todo inteiro a > 1 pode ser escrito como produto de um ou mais primos. | a DEMONSTRACAO O teorema é obviamente vdlido para a = 2. Suponha que ele seja valido para 2, 3, 4,..., a—1. Se a é primo, nada mais ha que se provar. Caso contrario, a tem um divisor b > 1, logo a= bc, onde l<b<ael<c<a. A hipdtese indutiva implica que s t b=|[r e c=][P’ i=1 j=l onde os p} e pi’ sdo primos. Logo, a= pi--- pypy--: Pr. QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 15 / 26 Teorema Se a|bc e (a, b) = 1 ent˜ao a|c. DEMONSTRAC¸ ˜AO Se (a, b) = 1 ent˜ao existem inteiros x e y tais que ax + by = 1. Logo, acx + bcy = c. Como a|ac (´obvio) e a|bc (hip´otese), resulta da igualdade acima que a|c. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 16 / 26 Exemplo Uma fracao reduzida a/b nao pode ser 0 cubo de um numero racional, a menos que ae b ja sejam cubos perfeitos. Suponha a (2) x3 bo \y} y® Logo, ay? = bx?. Obviamente, alay?, logo a|bx°. Como (a, b) = 1, segue do teorema anterior que a|x?, portanto a = mx? para algum inteiro m. Analogamente, b = ny?. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 17/26 Continua¸c˜ao Claramente, m = n: logo a = mx3 e b = my3. Para concluir, basta mostrar que m = ±1. Como (a, b) = 1, existem inteiros r e s tais que ar + bs = 1. Logo, mx3r + my3s = 1, m(rx3 + sy3) = 1. Esta ´ultima s´o ´e poss´ıvel se m = ±1 e rx3 + sy3 = ±1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 18 / 26 Teorema Se p| |] 1 Pm entao p = Pm para algum m. DEMONSTRACAO Se p # P1,---, Pn—1 entdo p é relativamente primo com todos esses p;’s. Pela propriedade (e), p é relativamente primo com o produto py --+ Pp—1, logo (P, Pi-** Pn—-1) = 1. Pelo teorema anterior, p|pp. Portanto p = pp. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 19 / 26 Teorema (teorema da fatoracao Unica) | A representacdo de a > 1 como produto de primos é Unica, a nao ser pela | ordem dos fatores. J DEMONSTRACAO Devemos mostrar o seguinte: se ny n2 / 2=TLen= I] Ph m=1 m=1 onde / / / Pl < P2 S++ S Pm & Pp S P2L+*+ S Pry entao my = m2 € Pm = p,, paral<m<m. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 20 / 26 A afirmacao é valida para a = 2, pois nesse caso, nj} = m2 =1le _—p— Pi = Py = 2. Suponha que a afirmacao seja valida para 2, 3, 4,..., a—1. Podemos supor sem perda de generalidade que a é composto, isto é, nao é primo. / m1 : a Como p}| [ [ir—1 Pm, Segue do teorema anterior que p| = p, para algum r. Analogamente, pi = p, para algum s. Como / / Pt < Pr = Pt S Ps = P11; vemos que pi = Pj. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 21/26 Agora, como 1 < p; < ae pi|a, temos ny n2 a / 1< TL pn=[Lon<e Pl m=2 m=2 away iT (*) (**) Os produtos (x) e (**) sdo decomposicdes em fatores primos do mesmo numero, nimero esse que esta ao alcance da hipdtese indutiva. Logo, my = no e também pp = ph, p3 = Pp, etc. QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 09 22 / 26 A demonstra¸c˜ao anterior claramente se baseia no conceito de MDC. (Por quˆe?) Dado seu papel fundamental na teoria dos n´umeros ´e razo´avel questionar se seria poss´ıvel uma demonstra¸c˜ao independente do conceito de MDC. Vamos mostrar como isto ´e poss´ıvel. Um primeiro passo ´e observar o seguinte: se um inteiro n tem fatora¸c˜ao ´unica e um primo p divide n ent˜ao p ocorre na fatora¸c˜ao em primos de n. Caso contr´ario, n/p seria um produto de primos q1 · · · qm (n˜ao necessariamente ´unicos), logo n = pq1 · · · qm seria uma segunda representa¸c˜ao de n (agora contendo p), o que contradiz a unicidade da fatora¸c˜ao de n. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 23 / 26 Voltemos ao passo indutivo da demonstra¸c˜ao do teorema anterior. Seja n > 1 um n´umero composto e suponha que todo inteiro a com 1 < a < n tem fatora¸c˜ao ´unica. Suponha que n n˜ao tenha fatora¸c˜ao ´unica e sejam n = p1p2 · · · = p′ 1p′ 2 · · · duas representa¸c˜oes, onde onde p1 ⩽ p2 ⩽ · · · e p′ 1 ⩽ p′ 2 ⩽ · · · . Podemos supor que cada pi ´e diferente de qualquer pj pois, caso contr´ario, poder´ıamos cancelar este fator em ambos os lados e a hip´otese indutiva se aplicaria. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 24 / 26 Como h´a pelo menos dois fatores em cada lado, temos n ⩾ p1p2 ⩾ p2 1, ou p1 ⩽ √n. Analogamente, p′ 1 ⩽ √n. Logo, a = n − p1p′ 1 ⩾ 0. Se a = 0 ent˜ao ter´ıamos n = p1p′ 1 = p1p2 · · · , p′ 1 = p2 · · · , logo p′ 1 = pm para algum m ⩾ 2, contrariamente `a hip´otese. Logo, a ⩾ 1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 25 / 26 Se a = 1 ent˜ao ter´ıamos n = p1p′ 1 + 1, um n´umero n˜ao divis´ıvel por p1; absurdo! Logo, 1 < a < n. Pela hip´otese indutiva, a tem fatora¸c˜ao ´unica. Como p1 e p′ 1 dividem a, decorre que ambos p1 e p′ 1 ocorrem na fatora¸c˜ao de a. Logo, a = p1p′ 1b para algum inteiro b. Consequentemente, n = p1p′ 1(b + 1) = p1p2 · · · , isto ´e p′ 1(b + 1) = p2 · · · . Assim, p2 · · · tem fatora¸c˜ao ´unica e ´e divis´ıvel por p′ 1. Logo, p′ 1 = pm para algum m ⩾ 2, o que ´e uma contradi¸c˜ao. Logo, n deve ter fatora¸c˜ao ´unica, como quer´ıamos mostrar. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 09 26 / 26