MDC, MMC e números primos

Prévia do material em texto

<p>MDC, MMC e números primos</p><p>Profa. Denise Candal</p><p>Descrição</p><p>Você vai acompanhar o cálculo e resultados relativos ao MDC de dois</p><p>números inteiros e ao MMC de dois números inteiros, a classificação</p><p>dos números em primos e compostos, o teorema fundamental da</p><p>aritmética, o crivo de Erastóstenes, os primos gêmeos e a conjectura de</p><p>Goldbach.</p><p>Propósito</p><p>Trabalhar com a conceituação e o cálculo do máximo divisor comum de</p><p>dois números inteiros e do mínimo múltiplo comum de dois números</p><p>inteiros é importante para a compreensão das leis naturais que regem o</p><p>mundo ao nosso redor.</p><p>Preparação</p><p>Antes de iniciar o conteúdo, faça o download do Solucionário. Nele, você</p><p>encontrará o feedback das atividades.</p><p>Objetivos</p><p>Módulo 1</p><p>Máximo divisor comum de dois</p><p>números inteiros</p><p>Analisar o máximo divisor comum que consegue simultaneamente</p><p>dividir dois números inteiros.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 1/72</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/doc/solucionario.pdf</p><p>Módulo 2</p><p>Mínimo múltiplo comum de dois</p><p>números inteiros</p><p>Analisar o menor número primo capaz de dividir dois números</p><p>inteiros distintos.</p><p>Módulo 3</p><p>Números primos, teorema</p><p>fundamental da aritmética</p><p>Identificar números primos, números compostos e a importância do</p><p>teorema fundamental da aritmética.</p><p>Módulo 4</p><p>Crivo de Erastóstenes, primos</p><p>gêmeos, conjectura de Goldbach</p><p>Analisar o crivo de Erastóstenes, identificando os primos gêmeos.</p><p>Introdução</p><p>Olá! Antes de começarmos, assista ao vídeo e compreenda os</p><p>conceitos de MMC e MDC, cujos cálculos estão relacionados a</p><p>múltiplos e divisores de um número.</p><p></p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 2/72</p><p>Material para download</p><p>Clique no botão abaixo para fazer o download do</p><p>conteúdo completo em formato PDF.</p><p>Download material</p><p>1 - Máximo divisor comum de dois números</p><p>inteiros</p><p>Ao �nal deste módulo, você será capaz de analisar o máximo divisor</p><p>comum que consegue simultaneamente dividir dois números</p><p>inteiros.</p><p>MDC e inteiros primos</p><p>entre si</p><p>Neste vídeo você vai compreender a concepção do MDC e dos inteiros</p><p>primos, que se relacionam entre si. Assista!</p><p>Máximo divisor comum</p><p>(MDC)</p><p>Conceituação</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 3/72</p><p>javascript:CriaPDF()</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou . Chamamos de máximo divisor comum (MDC) de e</p><p>o inteiro positivo de modo que satisfaça estas condições:</p><p>e , ou seja, é um divisor comum de e .</p><p>se e se então , ou seja, é o maior dentre todos os</p><p>divisores comuns de e</p><p>Notação:</p><p>Considere os inteiros e . Determinaremos o MDC entre</p><p>esses dois números.</p><p>Vamos determinar o conjunto dos divisores positivos!</p><p>Determinamos da seguinte forma:</p><p>Temos:</p><p>D(20)={1,2,4,5,10,20}.</p><p>Determinamos da seguinte forma:</p><p>Temos:</p><p>D(12)={1,2,3,4,6,12}</p><p>Com isso, podemos concluir que:</p><p>O conjunto dos divisores positivos .</p><p>O maior divisor comum será: .</p><p>Agora, considere os inteiros e . Determinaremos o</p><p>MDC entre esses dois números. Vamos então determinar o conjunto dos</p><p>divisores positivos!</p><p>a b</p><p>a ≠ 0 b ≠ 0 a b</p><p>d > 0</p><p>d|a d|b d a b</p><p>c|a c|b c ≤ d d</p><p>a b.</p><p>mdc(a, b) = d</p><p>a = 12 b = 20</p><p>a = 12</p><p>b = 20</p><p>D(12, 20) = {1, 2, 4}</p><p>mdc(20, 12) = 4</p><p>a = −24 b = 60</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 4/72</p><p>24</p><p>Determinamos da seguinte forma:</p><p>60</p><p>Determinamos da seguinte forma:</p><p>Com isso, podemos concluir que o conjunto dos divisores positivos é:</p><p>E o conjunto dos divisores comuns positivos é:</p><p>O maior divisor comum será:</p><p>Temos alguns resultados mais imediatos com relação ao MDC, veja!</p><p>não existe.</p><p>se , então .</p><p>se , então .</p><p>Exemplos</p><p>D(60) = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}</p><p>D(−24) = D(24) = {1, 2, 3, 4, 6, 8, 12, 24}</p><p>D(60, −24) = {1, 2, 3, 4, 6, 12}</p><p>mdc(60, −24) = 12</p><p>mdc(a, b) = mdc(b, a)</p><p>mdc(0, 0)</p><p>mdc(a, 1) = 1</p><p>a ≠ 0 mdc(a, 0) = |a|</p><p>a|b mdc(a, b) = |a|</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 5/72</p><p>Teorema da existência e da unicidade do MDC</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou . Então, existe e é único o .</p><p>Existem, ainda, os inteiros e tais que o é uma</p><p>combinação linear de e , ou seja, .</p><p>Considere um conjunto de todos os números inteiros positivos da</p><p>forma , ou seja:</p><p>Temos que o conjunto não é vazio. De fato, se , um dos dois</p><p>inteiros ou é positivo e</p><p>pertence a .</p><p>Assim, pelo princípio da boa ordenação, o elemento mínimo do</p><p>conjunto existe e é único.</p><p>Pela definição do conjunto , temos que existem e inteiros, de modo</p><p>que .</p><p>Precisamos agora mostrar que . Utilizando o algoritmo</p><p>da divisão, ficamos com:</p><p>Queremos mostrar que é zero e que, assim, , ou seja, . De</p><p>fato:</p><p>Chegamos ao fato de que é uma combinação linear de e .</p><p>Sabemos que e e, portanto, ,</p><p>ou seja, que . De forma análoga, mostramos que . Dessa forma,</p><p>mdc(6, 1) = 1</p><p>mdc(−3, 0) = | − 3| = 3</p><p>mdc(−6, 12) = | − 6| = 6</p><p>a b</p><p>a ≠ 0 b ≠ 0 mdc(a, b)</p><p>x y mdc(a, b)</p><p>a b mdc(a, b) = ax + by</p><p>S</p><p>au + bv, comu, v ∈ Z</p><p>S = {au + bv|au + bv > 0 e u, v ∈ Z}</p><p>S a ≠ 0</p><p>a = a ⋅ 1 + b ⋅ 0 −a = a ⋅ (−1) + b ⋅ 0</p><p>S</p><p>d</p><p>S</p><p>minS = d > 0</p><p>S x y</p><p>d = ax + by</p><p>d = mdc(a, b)</p><p>a = dq + r</p><p>0 ≤ r < d</p><p>r a = dq d|a</p><p>a = dq + r</p><p>r = a − dq = a − (ax + by)q = a − axq − byq = a(1 − ax) +</p><p>r a b</p><p>0 ≤ r < d minS = d > 0, r = 0 a = dq</p><p>d|a d|b</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 6/72</p><p>temos que é divisor positivo de e .</p><p>Ainda, se é um divisor comum positivo de e , ficamos com</p><p>e . Então:</p><p>Dessa forma, é o maior divisor comum positivo de e .</p><p>Observe que é o menor inteiro que pode ser escrito sob</p><p>a forma de combinação linear de e . Convém ressaltar, no</p><p>entanto, que essa combinação linear que representa o</p><p>não é única. Qualquer que seja inteiro:</p><p>Ainda, se, para inteiros e , então não é</p><p>necessariamente o .</p><p>Veja um exemplo:</p><p>Veja outro exemplo. Consideremos dois inteiros e .</p><p>Determinamos da seguinte forma:</p><p>d a b</p><p>c a b c|a, c|b</p><p>c > 0</p><p>c ∣ (ax + by)</p><p>c|d</p><p>c ≤ d</p><p>d a b</p><p>mdc(a, b) = d = ax + by</p><p>x, y ∈ Z</p><p>mdc(a, b) = d</p><p>ax + by a b</p><p>mdc(a, b) = d</p><p>t</p><p>mdc(a, b) = d = ax + by + abt − abt = a(x + bt) + b(y − at</p><p>r s, d = ar + bs d</p><p>mdc(a, b)</p><p>mdc(a, b) = ax + by</p><p>t ⋅ mdc(a, b) = atx + bty, ∀t ∈ Z</p><p>d = ar + bs</p><p>d = t ⋅ mdc(a, b)</p><p>r = tx</p><p>s = ty</p><p>a = 6 b = 27</p><p>a = 6</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 7/72</p><p>Determinamos da seguinte forma:</p><p>O cálculo será:</p><p>Teorema dos inteiros não nulos</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou . Então, o conjunto dos múltiplos do é</p><p>dado por .</p><p>Uma vez que sabemos que sendo e , temos que</p><p>. Dessa forma, todo elemento do conjunto</p><p>é um múltiplo de .</p><p>Existem ainda inteiros e , cujos múltiplos</p><p>são combinaç��es lineares de e .</p><p>Assim, é elemento do conjunto .</p><p>b = 27</p><p>mdc(6, 27) = 3 = 6(x) + 27(y) = 6(−4) + 27(1) = 6(−4 + 2</p><p>a b</p><p>a ≠ 0 b ≠ 0 d = mdc(a, b)</p><p>T = {ax + by|x, y ∈ Z}</p><p>d = mdc(a, b), d|a d|b</p><p>d ∣ (ax + by), ∀x, y ∈ Z</p><p>T = {ax + by|x, y ∈ Z} d</p><p>x0 y0 com d = ax0 + by0 kd</p><p>a b</p><p>kd = k (ax0 + by0) = a (kx0) + b (ky0)</p><p>kd T</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 8/72</p><p>Caracterização do MDC de dois inteiros</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou .</p><p>Um inteiro positivo é o se e somente se satisfaz estas</p><p>condições:</p><p>e .</p><p>Se e se , então .</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou .</p><p>(ida)</p><p>Consideremos . Temos então que e . Assim,</p><p>a condição</p><p>gêmeos.</p><p>II. São pares primos.</p><p>III. São primos.</p><p>É correto o que se afirma</p><p>Parabéns! A alternativa E está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Considerações �nais</p><p>Mergulhamos nas profundezas de conceitos e resultados relacionados</p><p>ao máximo divisor comum de dois números inteiros e ao mínimo</p><p>múltiplo comum de dois números inteiros. Exploramos a rica tapeçaria</p><p>dos números, categorizando-os meticulosamente em primos e</p><p>D nas alternativas I e II.</p><p>E nas alternativas I e III.</p><p>A somente na alternativa I.</p><p>B somente na alternativa II.</p><p>C somente na alternativa III.</p><p>D nas alternativas I e II.</p><p>E nas alternativas I e III.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 70/72</p><p>compostos. Além disso, imergimos na essência do teorema</p><p>fundamental da aritmética, desvendando suas implicações e aplicações.</p><p>Nosso percurso matemático nos conduziu à construção do crivo de</p><p>Erastóstenes, uma ferramenta poderosa para identificar números primos</p><p>de maneira eficiente. Profundamente imersos no mundo dos números</p><p>primos, desvendamos o intrigante mistério dos primos gêmeos,</p><p>compreendendo a peculiaridade desses pares fascinantes.</p><p>Por fim, nos deparamos com a conjectura de Goldbach, um enigma que</p><p>há séculos instiga mentes brilhantes. Ao explorar essa conjectura,</p><p>expandimos nossa compreensão dos números inteiros e suas relações,</p><p>iluminando mais um canto do vasto universo matemático.</p><p>Explore +</p><p>Para entender mais sobre os primos gêmeos, leia o artigo Duas notícias</p><p>espetaculares, no site da Revista do Professor de Matemática.</p><p>Referências</p><p>AIRES, F. C. Introdução à teoria dos números. Fortaleza: EdUECE, 2015.</p><p>ALENCAR FILHO, E. de. Teoria elementar dos números. São Paulo:</p><p>Nobel, 1981.</p><p>HEFEZ, A. Elementos de aritmética. Rio de Janeiro: SBM, 2006.</p><p>SANTOS, J. P. de O. Introdução à teoria dos números. Rio de Janeiro:</p><p>IMPA, 2020.</p><p>VIEIRA, V. L. Um curso básico em teoria dos números. São Paulo:</p><p>Livraria da Física, 2020.</p><p>Material para download</p><p>Clique no botão abaixo para fazer o download do</p><p>conteúdo completo em formato PDF.</p><p>Download material</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 71/72</p><p>javascript:CriaPDF()</p><p>O que você achou do conteúdo?</p><p>Relatar problema</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 72/72</p><p>(I) está satisfeita. Ainda, existem inteiros e tais que o</p><p>é uma combinação linear de e , ou seja,</p><p>.</p><p>Dessa forma, se e se , temos que ou ainda, . Assim,</p><p>a condição (II) está satisfeita.</p><p>(volta)</p><p>Agora, considere um inteiro positivo que satisfaz as condições:</p><p>e</p><p>Se e se , então .</p><p>Utilizando a condição (2), temos que todo divisor comum de e é</p><p>também divisor de , ou seja, . Assim, sabemos que . Dessa</p><p>forma, .</p><p>MDC de vários inteiros</p><p>Definimos máximo divisor comum para dois inteiros e . Podemos</p><p>estender esse conceito de máximo divisor comum para mais de dois</p><p>inteiros.</p><p>Considerando três inteiros e não todos nulos, dizemos que o</p><p>inteiro positivo quando satisfaz as condições:</p><p>e</p><p>Se , se e se , então .</p><p>Vamos determinar o . Obtendo os divisores dos três</p><p>números:</p><p>6</p><p>Determinamos da seguinte forma:</p><p>a b</p><p>a ≠ 0 b ≠ 0</p><p>d > 0 mdc(a, b)</p><p>d|a d|b</p><p>c|a c|b c|d</p><p>a b</p><p>a ≠ 0 b ≠ 0</p><p>mdc(a, b) = d > 0 d|a d|b</p><p>x y</p><p>md c(a, b) a b</p><p>mdc(a, b) = d = ax + by</p><p>c|a c|b c|ax + by c|d</p><p>d > 0</p><p>d|a d|b</p><p>c|a c|b c|d</p><p>c a b</p><p>d c|d c ≤ d</p><p>d = mdc(a, b)</p><p>a b</p><p>a, b c</p><p>mdc(a, b, c) = d, d</p><p>d|a, d|b d|c</p><p>e|a e|b e|c e ≤ d</p><p>mdc(6, 12, 15)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 9/72</p><p>Temos:</p><p>D(6)={-6,-3,-2,-1,1,2,3,6}</p><p>12</p><p>Determinamos da seguinte forma:</p><p>Temos:</p><p>D(12)={-12,-6,-4,-3,-2,-1,1,2,3,4,6,12}</p><p>15</p><p>Determinamos da seguinte forma:</p><p>Temos:</p><p>D(15)={-15,-5,-3,-1,1,3,5,15}</p><p>O maior divisor comum será .</p><p>Teorema do MDC</p><p>mdc(6, 12, 15) = 3</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 10/72</p><p>Vamos agora compreender o MDC entre dois números inteiros. Esse</p><p>máximo divisor é o maior número inteiro capaz de dividir dois outros</p><p>números inteiros simultaneamente.</p><p>Por exemplo, para obter:</p><p>Considere:</p><p>Temos então que e .</p><p>Existem inteiros e tais que . Assim, ou</p><p>. Dessa forma, temos que é um divisor comum de e de ou,</p><p>ainda, e .</p><p>Consideremos um divisor comum qualquer de e de ou, ainda, e</p><p>. Temos então que e . Assim, sabemos que .</p><p>Assim, ficamos com ou ainda:</p><p>Vejamos o próximo exemplo para compreender melhor. Vamos</p><p>determinar o utilizando o teorema que nos afirma que</p><p>.</p><p>Determinando o , temos:</p><p>15</p><p>Determinamos da seguinte forma:</p><p>mdc(a, b, c) = mdc(mdc(a, b), c)</p><p>mdc(a, b, c) = d</p><p>mdc(a, b) = e</p><p>d|a, d|b d|c</p><p>x y ax + by = e d ∣ (ax + by)</p><p>d|e d e c</p><p>d|e d|c</p><p>f e c f|e</p><p>f|c f|a, f|b f|c f ≤ d</p><p>mdc(e, c) = d</p><p>mdc(mdc(a, b), c) = mdc(a, b, c)</p><p>mdc(20, 15, 10)</p><p>mdc(a, b, c) = mdc(mdc(a, b), c)</p><p>mdc(20, 15, 10) = mdc(mdc(20, 15), 10)</p><p>mdc(20, 15)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 11/72</p><p>20</p><p>Determinamos da seguinte forma:</p><p>Assim, temos:</p><p>Agora determinamos:</p><p>Em que:</p><p>Assim, temos:</p><p>Inteiros primos entre si</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou . Dizemos que e são primos entre si se e somente se</p><p>.</p><p>Exemplo</p><p>3 e 5 são primos entre si, pois o .</p><p>mdc(20, 15) = 5</p><p>mdc(mdc(20, 15), 10) = mdc(5, 10)</p><p>D(5) = {−5, −1, 1, 5}</p><p>mdc(20, 15, 10) = mdc(mdc(20, 15), 10) = 5</p><p>a b</p><p>a ≠ 0 b ≠ 0 a b</p><p>mdc(a, b) = 1</p><p>md c(3, 5) = 1</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 12/72</p><p>3 e -10 são primos entre si, pois o .</p><p>Dois inteiros e que são primos entre si possuem somente dois</p><p>divisores comuns: 1 e -1 .</p><p>Teorema inteiros primos entre si</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou . Esses dois inteiros serão primos entre si se e somente</p><p>se existirem inteiros e tais que .</p><p>Vamos considerar dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou .</p><p>(ida)</p><p>Suponha esses dois inteiros primos entre si:</p><p>Existem inteiros e tais que o é uma combinação linear de</p><p>e , ou seja:</p><p>(volta)</p><p>Suponha que existam inteiros e tais que .</p><p>Sendo , temos que e .</p><p>Assim, sabemos que ou ainda .</p><p>Dessa forma, temos , ou seja, que e são primos</p><p>entre si.</p><p>Corolário – MDC entre dois inteiros</p><p>Se , então .</p><p>Demonstração</p><p>Suponha que</p><p>Uma vez que é divisor comum de e , temos que são</p><p>inteiros.</p><p>Como , existem inteiros e tais que .</p><p>Ainda, dividindo a equação por , ficamos com .</p><p>Assim, e são primos entre si e, portanto, .</p><p>Veja o exemplo:</p><p>mdc(3, 5) = 1</p><p>a b</p><p>a b</p><p>a ≠ 0 b ≠ 0</p><p>x y ax + by = 1</p><p>a b</p><p>a ≠ 0 b ≠ 0</p><p>mdc(a, b) = 1</p><p>x y mdc(a, b)</p><p>a b</p><p>mdc(a, b) = ax + by = 1</p><p>x y ax + by = 1</p><p>mdc(a, b) = d d|a d|b</p><p>d ∣ (ax + by) d|1</p><p>mdc(a, b) = d = 1 a b</p><p>mdc(a, b) = d mdc(a/d, b/d) = 1</p><p>mdc(a, b) = d</p><p>d a b a/deb/d</p><p>mdc(a, b) = d x y ax + by = d</p><p>d a/dx + b/dy = 1</p><p>a/d b/d mdc(a/d, b/d) = 1</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 13/72</p><p>Corolário - prova de que</p><p>Se e se o , então temos que .</p><p>Agora, suponha que e se o .</p><p>Como , temos que , sendo .</p><p>Como , sabemos que , sendo .</p><p>Corolário - prova de que</p><p>Se , então temos que .</p><p>Agora, suponha que .</p><p>Como , sabemos que , sendo .</p><p>Como , sabemos que , sendo .</p><p>O corolário a seguir é a recíproca do corolário anterior.</p><p>Corolário - prova de que</p><p>Se , então temos que .</p><p>Agora, suponha que</p><p>Como , sabemos que , sendo</p><p>.</p><p>mdc(24, 30) = 6</p><p>mdc(24/6, 30/6) = mdc(4, 5) = 1</p><p>mdc(a, c) = 1</p><p>a|b mdc(b, c) = 1 mdc(a, c) = 1</p><p>a|b mdc(b, c) = 1</p><p>a|b b = aq q ∈ Z</p><p>mdc(b, c) = 1 bx + cy = 1 x, y ∈ Z</p><p>(aq)x + cy = 1</p><p>a(qx) + cy = 1</p><p>mdc(a, c) = 1</p><p>mdc(a, bc) = 1</p><p>mdc(a, b) = mdc(a, c) = 1 mdc(a, bc) = 1</p><p>mdc(a, b) = mdc(a, c) = 1</p><p>mdc(a, b) = 1 ax + by = 1 x, y ∈ Z</p><p>mdc(a, c) = 1 av + cw = 1 v,w ∈ Z</p><p>ax + by = 1</p><p>ax + by(av + cw) = 1</p><p>ax + byav + bycw = 1</p><p>a(x + byv) + bc(yw) = 1</p><p>mdc(a, bc) = 1</p><p>mdc(a, c) = 1</p><p>mdc(a, bc) = 1 mdc(a, b) = mdc(a, c) = 1</p><p>mdc(a, bc) = 1</p><p>mdc(a, bc) = 1 ax + (bc)y = 1 x, y ∈ Z</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 14/72</p><p>Teorema de Euclides: primos entre si</p><p>Se e se o , então temos que .</p><p>Suponha que e que o .</p><p>Como , temos que , sendo .</p><p>Como , sabemos que , sendo .</p><p>Ainda:</p><p>Antes de continuar, entenda a seguinte informação.</p><p>Atenção!</p><p>Três inteiros podem ser primos entre si, ou seja, , no</p><p>entanto, sem ser primos entre si, dois a dois. Exemplo: 6, 10 e 15.</p><p>Corolário - prova de que</p><p>Se , se e se o , então temos que .</p><p>Agora, suponha que , se e se o .</p><p>Como , temos que , sendo .</p><p>Como , temos que , sendo .</p><p>Como , sabemos que , sendo .</p><p>Ainda:</p><p>ax + b(cy) = 1,  então  mdc(a, b) = 1.</p><p>ax + c(by) = 1,  então  mdc(a, c) = 1.</p><p>a|bc mdc(a, b) = 1 a|c</p><p>a|bc md c(a, b) = 1</p><p>a|bc bc = aq q ∈ Z</p><p>mdc(a, b) = 1 ax + by = 1 x, y ∈ Z</p><p>cax + cby = c</p><p>acx + bcy = c</p><p>acx + (aq)y = c</p><p>a(cx + qy) = c</p><p>a|c</p><p>md c(a, b, c) = 1</p><p>ab|c</p><p>a|c b|c mdc(a, b) = 1 ab|c</p><p>a|c b|c md c(a, b) = 1</p><p>a|c c = aq1 q1 ∈ Z</p><p>b|c c = bq2 q2 ∈ Z</p><p>mdc(a, b) = 1 ax + by = 1 x, y ∈ Z</p><p>cax + cby = c</p><p>a (bq2)x + b (aq1)y = c</p><p>ab (q2x + q1y) = c</p><p>ab|c</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 15/72</p><p>Teoria na prática</p><p>Determine o MDC dos dois inteiros e .</p><p>Mão na massa</p><p>Questão 1</p><p>Considere os inteiros e . Determinando o conjunto</p><p>dos divisores positivos de e e MDC entre esses dois</p><p>números, obtemos:</p><p>Parabéns! A alternativa E está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>_black</p><p>a = −30 b = −20</p><p>Mostrar solução</p><p></p><p>a = 16 b = 24</p><p>a = 12 b = 20</p><p>A e</p><p>D(16) = {2, 4, 8, 16},D(24) = {2, 3, 4, 6, 8, 12, 24}</p><p>mdc(16, 24) = 2</p><p>B e</p><p>D(16) = {1, 2, 4, 8, 16},D(24) = {1, 2, 3, 4, 6, 8, 12</p><p>mdc(16, 24) = 2</p><p>C</p><p>eD(16) = {2, 4, 8},D(24) = {2, 3, 4, 6, 8, 12}</p><p>mdc(16, 24) = 2</p><p>D</p><p>e</p><p>D(16) = {1, 2, 4, 8},D(24) = {1, 2, 3, 4, 6, 8, 12}</p><p>mdc(16, 24) = 8</p><p>E e</p><p>D(16) = {1, 2, 4, 8, 16},D(24)</p><p>= {1, 2, 3, 4, 6, 8, 12</p><p>mdc(16, 24) = 8</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 16/72</p><p>Questão 2</p><p>Calculando , sendo um inteiro par, obtemos</p><p>Parabéns! A alternativa B está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 3</p><p>Sendo um inteiro qualquer, ache os possíveis valores do MDC dos</p><p>inteiros e .</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>mdc(n,n + 2) n</p><p>A 1.</p><p>B 2.</p><p>C .n</p><p>D .n + 1</p><p>E .n + 2</p><p>n</p><p>n n + 10</p><p>A 1, 2, 5, 10</p><p>B 2, 5, 10</p><p>C 1, 2, 5</p><p>D 2, 5</p><p>E 1, 10</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 17/72</p><p>Questão 4</p><p>Considere o conjunto . Enumerando os</p><p>elementos do conjunto , obtemos</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 5</p><p>Ache o menor inteiro positivo , da forma , onde e</p><p>são dois inteiros.</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EAssista%20ao%20v%C3%ADdeo%20para%20conferir%20a%20resolu%C3%A7%C3%A3o%20da%</p><p>video-</p><p>player%20src%3D%22https%3A%2F%2Fplay.yduqs.videolib.live%2Findex.html%3Ftoken%3Dd72bfb4d469f49d5</p><p>A = {1, 2, 3, 4, 5, 6}</p><p>X = {x ∈ A ∣ mdc(x, 6) = 1}</p><p>A 1.</p><p>B 1, 2.</p><p>C 1, 5.</p><p>D 5.</p><p>E 1, 6.</p><p>c c = 22x + 55y x</p><p>y</p><p>A 1</p><p>B 22</p><p>C 11</p><p>D 55</p><p>E 77</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 18/72</p><p>5%22%20width%3D%22100%25%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2</p><p>video-</p><p>player%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20</p><p>Questão 6</p><p>Considere os dois inteiros e . Determinando o</p><p>MDC entre esses dois números, obtemos</p><p>Parabéns! A alternativa D está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Falta pouco para atingir seus objetivos.</p><p>Vamos praticar alguns conceitos?</p><p>Questão 1</p><p>Sabendo que o , achando todos os valores</p><p>possíveis do inteiro , obtemos</p><p>a = −21 b = 14</p><p>A 1.</p><p>B -1.</p><p>C -7.</p><p>D 7.</p><p>E -21.</p><p>mdc(a, 0) = 15</p><p>a</p><p>A 0.</p><p>B 1.</p><p>C 15.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 19/72</p><p>Parabéns! A alternativa E está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Considere os dois inteiros e . Determinando o</p><p>entre esses dois números, obtemos</p><p>Parabéns! A alternativa B está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>D -15.</p><p>E -15 ou 15.</p><p>a = 17 b = −18</p><p>mdc</p><p>A 0.</p><p>B 1.</p><p>C -1.</p><p>D 17.</p><p>E -18.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 20/72</p><p>2 - Mínimo múltiplo comum de dois números</p><p>inteiros</p><p>Ao �nal deste módulo, você será capaz de analisar o menor número</p><p>primo capaz de dividir dois números inteiros distintos.</p><p>Algoritmo de Euclides e</p><p>MMC</p><p>Neste vídeo, você vai compreender o algoritmo de Euclides e como ele</p><p>pode ser aplicado para calcular o mínimo múltiplo comum (MMC).</p><p>Confira!</p><p>Algoritmo de Euclides</p><p>Lema do algoritmo</p><p>O algoritmo de Euclides é determinado da seguinte maneira:</p><p>Para que possamos compreender por que isso ocorre, vamos à</p><p>demonstração. Consideremos e . Então</p><p>temos que e . Assim, ou . Dessa forma, temos</p><p>que é um divisor comum de e de , ou seja, e .</p><p>Se é um divisor comum qualquer de e de , ou seja, e , então</p><p>temos que ou . Assim, é um divisor comum de e e,</p><p>portanto, . Temos então que .</p><p>O algoritmo de Euclides ou processo das divisões sucessivas, que</p><p>veremos a seguir, é um processo prático que utilizamos para calcular o</p><p>MDC de dois inteiros positivos e .</p><p>Algoritmo de Euclides ou processo das</p><p>divisões sucessivas</p><p>Consideremos dois inteiros e não conjuntamente nulos, ou seja,</p><p>ou . Temos de modo mais imediato que:</p><p>Se , então .</p><p>Se , então .</p><p>Se a = bq + r, então temos que mdc(a, b) = mdc(b, r).</p><p>a = bq + r mdc(a, b) = d</p><p>d|a d|b d ∣ (a − bq) d|r</p><p>d b r d|b d|r</p><p>c b r c|b c|r</p><p>c ∣ (bq + r) c|a c a b</p><p>c ≤ d dc(b, r) = d</p><p>a b</p><p>a b</p><p>a ≠ 0 b ≠ 0</p><p>a ≠ 0 mdc(a, 0) = |a|</p><p>a ≠ 0 mdc(a, a) = |a|</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 21/72</p><p>Se , então .</p><p>Para determinarmos o MDC de e , como sabemos que</p><p>, basta trabalhar com e sendo inteiros</p><p>positivos distintos. Considerando e , utilizando o algoritmo</p><p>da divisão, ficamos com:</p><p>Os restos são positivos, sendo</p><p>. Há apenas inteiros positivos</p><p>menores que .</p><p>Chegaremos a uma divisão de modo que o resto , ou seja:</p><p>Utilizando o lema anterior, temos que:</p><p>O MDC de e será o último resto da sequência de divisões, ou</p><p>seja, .</p><p>Dispositivo prático para utilização do</p><p>algoritmo de Euclides</p><p>Agora que provamos o algoritmo, vamos entender como podemos</p><p>utilizá-lo. Para calcular nosso MMC, vamos ver os passos a seguir.</p><p>Passo 1</p><p>b|a mdc(a, b) = |b|</p><p>a b</p><p>mdc(a, b) = mdc(|a|, |b|) a b</p><p>a > b b ∤ a</p><p>a = bq1 + r1, 0 < r1 < b</p><p>b = r1q2 + r2, 0 < r2 < r1</p><p>r1 = r2q3 + r3, 0 < r3 < r2</p><p>r2 = r3q4 + r4, 0 < r4 < r3</p><p>r1, r2, r3, r4, ⋯</p><p>b > r1 > r2 > r3 > r4 > ⋯ b − 1</p><p>b</p><p>rn+1 = 0</p><p>rn−2 = rn−1qn + rn, 0 < rn < rn−1</p><p>rn−1 = rnqn+1 + rn+1, rn+1 = 0</p><p>mdc(a, b) = mdc (b, r1) = mdc (r1, r2) = mdc (r2, r3) = ⋯</p><p>= mdc (rn−1, rn) = rn</p><p>a b rn ≠ 0</p><p>md c(a, b) = rn</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 22/72</p><p>Fazemos a divisão de por .</p><p>Passo 2</p><p>O novo divisor será o resto obtido. Dividimos então o pelo</p><p>resto .</p><p>Passo 3</p><p>Repetimos esse procedimento até chegarmos ao resto zero.</p><p>O MDC que estamos buscando será o último resto não nulo. Podemos</p><p>ainda utilizar o algoritmo de Euclides para determinar a expressão</p><p>como combinação linear de e . Basta, para isso,</p><p>eliminar sucessivamente os restos</p><p>entre as primeiras igualdades anteriores.</p><p>Exemplo 1</p><p>Vamos determinar bem como a sua expressão como</p><p>combinação linear de 372 e 162. Veja!</p><p>Assim, temos:</p><p>a b</p><p>b</p><p>r1</p><p>mdc(a, b) = rn a b</p><p>rn−1, rn−2, rn−3, ⋯ , r3, r2, r1</p><p>n</p><p>mdc(372, 162),</p><p>372 = 162 ⋅ 2 + 48</p><p>162 = 48 ⋅ 3 + 18</p><p>48 = 18 ⋅ 2 + 12</p><p>18 = 12 ⋅ 1 + 6</p><p>12 = 6 ⋅ 2 + 0</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 23/72</p><p>Escreveremos agora o como combinação linear de</p><p>372 e 162. Basta substituirmos pelos valores dos restos das equações</p><p>anteriores.</p><p>Ficamos então com:</p><p>Dessa forma, temos que:</p><p>Exemplo 2</p><p>Sabe-se que o e que os quocientes obtidos pelo</p><p>algoritmo de Euclides são e 3 . Pede-se determinar os dois</p><p>inteiros positivos e . Veja!</p><p>Em que:</p><p>mdc(372, 162) = 6</p><p>372 = 162 ⋅ 2 + 48 ⇒ 372 − 162 ⋅ 2 = 48</p><p>162 = 48 ⋅ 3 + 18 ⇒ 162 − 48 ⋅ 3 = 18</p><p>48 = 18 ⋅ 2 + 12 ⇒ 48 − 18 ⋅ 2 = 12</p><p>18 = 12 ⋅ 1 + 6 ⇒ 18 − 12 ⋅ 1 = 6</p><p>12 = 6 ⋅ 2 + 0</p><p>6 = 18 − 12 =18 − (48 − 18 ⋅ 2) = 18 − 48 + 18 ⋅ 2 = 18 ⋅ 3</p><p>= (162 − 48 ⋅ 3) ⋅ 3 − 48 = 162 ⋅ 3 − 48 ⋅ 9 −</p><p>= 162 ⋅ 3 − (372 − 162 ⋅ 2) ⋅ 10 = 162 ⋅ 3 − 37</p><p>= 162 ⋅ 23 − 372 ⋅ 10</p><p>mdc(372, 162) = 6 = 162 ⋅ 23 − 372 ⋅ 10 = 162 ⋅ 23 + 372 ⋅ (</p><p>mdc(a, b) = 74</p><p>1, 2, 2, 5, 1</p><p>a b</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio#</p><p>24/72</p><p>Calculando, temos:</p><p>Determinando, temos:</p><p>Calculando, temos:</p><p>Para determinar, temos:</p><p>Calculando:</p><p>Determinando:</p><p>Calculando:</p><p>Para determinar, temos:</p><p>Para calcular, temos:</p><p>r4 = 74 ⋅ 3 + 0</p><p>r4 = 222</p><p>r3 = 222 ⋅ 1 + 74</p><p>r3 = 296</p><p>r2 = 296 ⋅ 5 + 222</p><p>r2 = 1.702</p><p>r1 = 1.702 ⋅ 2 + 296</p><p>r1 = 3.700</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 25/72</p><p>Determinando:</p><p>Calculando:</p><p>Exemplo 3</p><p>Usando o algoritmo de Euclides, vamos determinar inteiros que verifique</p><p>a igualdade</p><p>Determinando:</p><p>Escreveremos agora o como combinação</p><p>linear de 1.769 e 2.378. Basta substituir pelos valores dos restos das</p><p>equações anteriores.</p><p>Continuando o cálculo:</p><p>b = 3.700 ⋅ 2 + 1.702</p><p>b = 9.102</p><p>a = 9.102 ⋅ 1 + 3.700</p><p>b = 12.802</p><p>mdc(1.769, 2.378) = 1.769x + 2.378y</p><p>mdc(1.769, 2.378) = 1.769x + 2.378y</p><p>mdc(1769, 2378) = 29</p><p>2.378 = 1.769 ⋅ 1 + 609 ⇒ 2.378 − 1.769 ⋅ 1 = 609</p><p>1.769 = 609 ⋅ 2 + 551 ⇒ 1.769 − 609 ⋅ 2 = 551</p><p>609 = 551 ⋅ 1 + 58 ⇒ 609 − 551 ⋅ 1 = 58</p><p>551 = 58 ⋅ 9 + 29 ⇒ 551 − 58 ⋅ 9 = 29</p><p>58 = 29 ⋅ 2</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 26/72</p><p>Assim, ficamos com e .</p><p>Teorema - Demonstração de que</p><p>Se , então temos que .</p><p>Vamos multiplicar por cada uma das igualdades do algoritmo de</p><p>Euclides. Observe!</p><p>Note que essas igualdades representam o algoritmo de Euclides</p><p>aplicado aos inteiros e . Dessa forma, o será o</p><p>último resto , ou seja, .</p><p>Exemplos</p><p>No primeiro exemplo calculamos: .</p><p>No segundo exemplo calculamos: .</p><p>Corolário - mostrando que</p><p>Temos que</p><p>29 = 551 − 58 ⋅ 9 = 551 − (609 − 551 ⋅ 1) ⋅ 9 = 551 − 609 ⋅</p><p>= 551 ⋅ 10 − 609 ⋅ 9 = (1769 − 609 ⋅ 2) ⋅ 10 − 609 ⋅</p><p>= 1769 ⋅ 10 − 609 ⋅ 20 − 609 ⋅ 9 = 1769 ⋅ 10 − 609 ⋅</p><p>= 1769 ⋅ 10 − (2378 − 1769 ⋅ 1) ⋅ 29 = 1769 ⋅ 10 − 2378 ⋅ 29 +</p><p>= 1769 ⋅ 39 − 2378 ⋅ 29</p><p>29 = 1769 ⋅ (39) + 2378 ⋅ (−29)</p><p>mdc(1769, 2378) = 29 = 1769x + 2378y</p><p>x = 39 y = −29</p><p>mdc(ka, kb) = k ⋅ mdc(a, b)</p><p>k > 0 mdc(ka, kb) = k ⋅ mdc(a, b)</p><p>k > 0</p><p>n + 1</p><p>ak bk mdc(ak, bk)</p><p>rnk ≠ 0 mdc(ak, bk) = rnk = k ⋅ mdc(a, b)</p><p>mdc(15, 20)</p><p>mdc(15, 20) = mdc(3 ⋅ 5, 4 ⋅ 5) = 5 ⋅ mdc(3, 4) = 5 ⋅ 1 = 5</p><p>mdc(12, 30)</p><p>mdc(12, 30) = mdc(2 ⋅ 6, 5 ⋅ 6) = 6 ⋅ mdc(2, 5) = 6 ⋅ 1 = 6</p><p>mdc(ka, kb) = |k| ⋅ mdc(a, b)</p><p>∀k ≠ 0, mdc(ka, kb) = |k| ⋅ mdc(a, b)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 27/72</p><p>Para , o teorema anterior já foi provado.</p><p>Para , temos que .</p><p>Pelo teorema anterior ficamos com:</p><p>Mínimo múltiplo comum</p><p>(MMC)</p><p>Múltiplos comuns de dois Inteiros</p><p>Chamamos de conjunto dos múltiplos de um inteiro ao</p><p>conjunto:</p><p>Exemplos</p><p>No primeiro exemplo calculamos: .</p><p>No segundo exemplo calculamos: .</p><p>Antes de continuar, preste atenção na seguinte informação.</p><p>Atenção!</p><p>, temos que .</p><p>Múltiplo comum</p><p>Consideremos dois inteiros e diferentes de zero, ou seja, e</p><p>. Chamamos de múltiplo comum de e a todo inteiro de modo</p><p>que e .</p><p>Assim, o conjunto dos múltiplos comuns de e - são</p><p>todos os inteiros que pertençam simultaneamente aos conjuntos</p><p>e .</p><p>k > 0</p><p>k < 0 −k = |k| > 0</p><p>mdc(ka, kb) = mdc(−ka, −kb) = mdc(a ⋅ |k|, b ⋅ |k|) = |k| ⋅ m</p><p>M(a) a ≠ 0</p><p>M(a) = {x ∈ Z| a|x} = {aq|q ∈ Z}</p><p>M(6)</p><p>M(6) = {6q|q ∈ Z} = {0, ±6, ±12, ±18, ⋯}</p><p>M(5)</p><p>M(5) = {5q|q ∈ Z} = {0, ±5, ±10, ±15, ⋯}</p><p>∀a ≠ 0 M(a) = M(−a)</p><p>a b a ≠ 0</p><p>b ≠ 0 a b x</p><p>a|x b|x</p><p>a b − M(a, b)</p><p>M(a)</p><p>M(b)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 28/72</p><p>Antes de continuar, preste atenção na seguinte informação.</p><p>Atenção!</p><p>I)</p><p>II)</p><p>III) e -( são múltiplos de e de</p><p>Exemplo</p><p>Consideremos os inteiros e . Vamos esboçar o conjunto</p><p>dos múltiplos de cada um desses inteiros e o conjunto dos múltiplos</p><p>comuns.</p><p>Mínimo múltiplo comum de dois Inteiros</p><p>Consideremos dois inteiros e diferentes de zero, ou seja, e</p><p>.</p><p>Chamamos de mínimo múltiplo comum de e - ao</p><p>inteiro positivo de modo que satisfaça às duas condições:</p><p>é múltiplo comum de e , ou seja, e .</p><p>é o menor dos múltiplos comuns de e , ou seja, se e se</p><p>, sendo , temos então que .</p><p>O conjunto dos múltiplos comuns positivos de e possui elemento</p><p>mínimo, por conta do princípio da boa ordenação. Dessa forma, o</p><p>existe e é único. Como é múltiplo comum de e , temos</p><p>que . Ainda, se , então temos que</p><p>.</p><p>Exemplo 1</p><p>Considere dois inteiros e . Determine os múltiplos de</p><p>cada um deles:</p><p>M(a, b) = {x ∈ Z| a|x e b|x} = {x ∈ Z|x ∈ M(a) e x ∈ M(b</p><p>M(a, b) = M(b, a) = M(a) ∩ M(b) = M(b) ∩ M(a)</p><p>0 ∈ M(a, b)</p><p>ab ab) a b</p><p>a = −6 b = 20</p><p>M(−6) = M(6) = {−6q|q ∈ Z}</p><p>= {0, ±6, ±12, ±18, ±24, ±30, ±36, ±42 ± 48, ±54, ±60, ⋯</p><p>M(20) = {20q|q ∈ Z} = {0, ±20, ±40, ±60, ±80, ⋯}</p><p>M(−6, 20) = M(−6) ∩ M(20) = {0, ±60, ⋯}</p><p>a b a ≠ 0</p><p>b ≠ 0</p><p>a b − mmc(a, b)</p><p>m</p><p>m a b a|m b|m</p><p>m a b a|c b|c</p><p>c > 0 m ≤ c</p><p>a b</p><p>mmc(a, b) ab a b</p><p>mmc(a, b) ≤ |ab| a|b mmc(a, b) ≤</p><p>|b|</p><p>a = −12 b = −30</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 29/72</p><p>O menor dos múltiplos comuns positivos será</p><p>.</p><p>A comparação de múltiplos de dois números eventualmente é um</p><p>processo trabalhoso. Outra forma de se determinar o MMC é utilizar o</p><p>método das divisões sucessivas. A ideia é realizarmos divisões</p><p>sucessivas com os números dados, de modo simultâneo para encontrar</p><p>fatores. O produto desses fatores será o MMC.</p><p>Há ainda outra forma de determinar o MMD por intermédio da</p><p>decomposição em fatores primos e observação dos expoentes desses</p><p>fatores, que veremos mais adiante.</p><p>Exemplo 2</p><p>Agora, vamos calcular . A princípio, precisamos</p><p>determinar o menor número primo que divida pelo menos um dos</p><p>números dados.</p><p>M(−12) = M(12) = {−12q|q ∈ Z}</p><p>= {0, ±12, ±24, ±36, ±48, ±60 ± 72, ±84, ±96, ±108, ±1</p><p>M(−30) = M(30) = {−30q|q ∈ Z} = {0, ±30, ±60, ±90, ±</p><p>M(−12, −30) = M(−12) ∩ M(−30) = {0, ±60, ±120, ±18</p><p>60 : mmc(−12, −30) = 60</p><p>mmc(48, 84)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 30/72</p><p>Efetuamos então a divisão desses números por 2 e colocamos o</p><p>resultado na linha a seguir.</p><p>Repetimos o procedimento, buscando outro primo se não pudermos</p><p>dividir nenhum número pelo primo anterior. Se um dos números não for</p><p>divisível pelo primo em questão, repetimos esse número.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 31/72</p><p>Quando não pudermos mais dividir, o MMC é calculado multiplicando os</p><p>números encontrados.</p><p>Relação entre MDC e MMC</p><p>É válida, para todo par de inteiros positivos e , esta relação:</p><p>Demonstração</p><p>Vamos considerar:</p><p>a b</p><p>mdc(a, b) ⋅ mmc(a, b) = a ⋅ b</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 32/72</p><p>Uma vez que:</p><p>Temos, assim, que é um múltiplo comum de e . Dessa forma,</p><p>existe um inteiro positivo de modo que .</p><p>Assim:</p><p>Ou seja:</p><p>Isso significa que é um divisor comum dos inteiros e .</p><p>Corolário - mostrando que,</p><p>.</p><p>Se então , sabemos que e</p><p>são primos entre si, de forma que . Dessa forma, ficamos com:</p><p>Assim:</p><p>Exemplo</p><p>Vamos determinar o . Note que, para determinar esse</p><p>MMC, precisaríamos encontrar os múltiplos de cada um dos números,</p><p>mdc(a, b) = d</p><p>mmc(a, b) = m</p><p>a|a(b/d), ou ainda, a ∣ (ab/d)</p><p>e b|b(a/d), ou ainda, a ∣ (ab/d)</p><p>ab|d a b</p><p>k (ab/d) = mk, com k ∈ N</p><p>ab</p><p>d</p><p>= mk ou ainda</p><p>a</p><p>d</p><p>=</p><p>m</p><p>b</p><p>k</p><p>ab</p><p>d</p><p>= mk ou ainda</p><p>b</p><p>d</p><p>=</p><p>m</p><p>a</p><p>k</p><p>a/d = (m/b)k</p><p>b/d = (m/a)k</p><p>k a/d b/d</p><p>mdc(ka, kb) = |k| ⋅ mdc(a, b)</p><p>mdc(a, b) = d mdc(a/d, b/d) = 1 a/d b/d</p><p>k = 1</p><p>ab</p><p>d</p><p>= m  ou  ab = dm</p><p>a ⋅ b = mdc(a, b) ⋅ mmc(a, b)</p><p>mmc(963, 657)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 33/72</p><p>determinar a interseção e selecionar o menor número na interseção.</p><p>Esse procedimento</p><p>pode ser bem trabalhoso.</p><p>Dessa forma, utilizaremos o teorema que nos fornece a relação entre os</p><p>dois números. Utilizando o algoritmo de Euclides, achamos o</p><p>.</p><p>Corolário – par de inteiros positivos</p><p>É válida, para todo par de inteiros positivos e a relação</p><p>se e somente se .</p><p>Demonstração</p><p>(volta)</p><p>Consideremos . Pelo teorema que relaciona o MDC com</p><p>o MMC, temos:</p><p>(ida)</p><p>Consideremos . Ainda pelo teorema que relaciona o</p><p>MDC com o MMC, temos:</p><p>Mínimo múltiplo comum de vários inteiros</p><p>Definimos mínimo múltiplo comum para dois inteiros e . Podemos</p><p>estender esse conceito de MMC para mais de dois inteiros.</p><p>Considerando três inteiros e não todos nulos, dizemos que o</p><p>inteiro positivo, quando satisfaz as condições:</p><p>e</p><p>mdc(963, 657) = 9</p><p>a ⋅ b = mdc(a, b) ⋅ mmc(a, b)</p><p>963 ⋅ 657 = 9 ⋅ mmc(a, b)</p><p>mmc(a, b) =</p><p>963 ⋅ 657</p><p>9</p><p>mmc(a, b) = 70299</p><p>a b</p><p>mmc(a, b) = ab mdc(a, b) = 1</p><p>mdc(a, b) = 1</p><p>a ⋅ b = mdc(a, b) ⋅ mmc(a, b)</p><p>a ⋅ b = 1 ⋅ mmc(a, b)</p><p>a ⋅ b = mmc(a, b)</p><p>mmc(a, b) = ab</p><p>a ⋅ b = mdc(a, b) ⋅ mmc(a, b)</p><p>a ⋅ b = mdc(a, b) ⋅ ab</p><p>mdc(a, b) = 1</p><p>a b</p><p>a, b c</p><p>mmc(a, b, c) = m,m</p><p>a|m, b|m c|m</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 34/72</p><p>Se , se e se , com , então .</p><p>Exemplo</p><p>Começamos com:</p><p>Agora, vamos determinar o com o auxílio do algoritmo</p><p>de Euclides e achar a sua expressão como combinação linear de 963 e</p><p>657.</p><p>Em que:</p><p>O cálculo segue assim:</p><p>Dessa forma, temos que:</p><p>Convém observar que essa combinação linear do ,</p><p>em termos de , não é única. Se somarmos e subtrairmos o</p><p>produto no segundo membro da igualdade, temos:</p><p>a|e b|e c|e e > 0 m ≤ e</p><p>mmc(39, 102, 75) = 33.150</p><p>mdc(963, 657)</p><p>963 = 657 ⋅ 1 + 306 ⇒ 963 − 657 ⋅ 1 = 306</p><p>657 = 306 ⋅ 2 + 45 ⇒ 657 − 306 ⋅ 2 = 45</p><p>306 = 45 ⋅ 6 + 36 ⇒ 306 − 45 ⋅ 6 = 36</p><p>45 = 36 ⋅ 1 + 9 ⇒ 45 − 36 ⋅ 1 = 9</p><p>36 = 9 ⋅ 4 + 0</p><p>mdc(963, 657) = 9 = 45 − 36 ⋅ 1 = 45 − (306 − 45 ⋅ 6) = 45</p><p>= 45 ⋅ 7 − 306 = (657 − 306 ⋅ 2) ⋅ 7 − 306 = 6</p><p>= 657 ⋅ 7 − 306 ⋅ 15 = 657 ⋅ 7 − (963 − 657 ⋅</p><p>= 657 ⋅ 7 − 963 ⋅ 15 + 657 ⋅ 15 = 657 ⋅ 22 − 9</p><p>mdc(963, 657) = 9 = 657 ⋅ 22 − 963 ⋅ 15 = 657 ⋅ 22 + 963 ⋅ (</p><p>= 963 ⋅ (−15) + 657 ⋅ 22</p><p>mdc(963, 657) = 9</p><p>963e657</p><p>936 ⋅ 657</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 35/72</p><p>O foi escrito como uma outra combinação linear.</p><p>Teoria na prática</p><p>Sendo um inteiro qualquer, calcule o .</p><p>Mão na massa</p><p>Questão 1</p><p>Considere os inteiros e , sobre o conjunto dos</p><p>múltiplos de cada um desses inteiros e o conjunto dos múltiplos</p><p>comuns. Analise as afirmativas a seguir.</p><p>I)</p><p>II)</p><p>III)</p><p>É correto o que se afirma</p><p>mdc(936, 657) = 9</p><p>_black</p><p>n mdc (n − 1,n2 + n + 1)</p><p>Mostrar solução</p><p></p><p>a = 12 b = −18</p><p>M(12) = {12q ∣ q ∈ Z} = {0, ±12, ±24, ±36, ±48, ±60 ± 72, ⋯}</p><p>M(−18) = M(18) = {−18q ∣ q ∈ Z} = {0, ±18, ±36, ±54, ±72, ⋯}</p><p>M(12, −18) = M(12) ∪ M(−18) = {0, ±36, ±72, ⋯}</p><p>A nas alternativas II e III.</p><p>B nas alternativas I e III.</p><p>C nas alternativas I e II.</p><p>D somente na alternativa I.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 36/72</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Usando o algoritmo de Euclides, determinando inteiros que</p><p>verifiquem a igualdade , obtemos</p><p>Parabéns! A alternativa B está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 3</p><p>Determinando os inteiros positivos e , sabendo que</p><p>e que , obtemos</p><p>E somente na alternativa II.</p><p>mdc(119, 272) = 119x + 272y</p><p>A e .x = −7 y = −3</p><p>B e .x = 7 y = −3</p><p>C e .x = −7 y = 3</p><p>D e .x = 7 y = 3</p><p>E e .x = 119 y = 272</p><p>a b ab = 4.032</p><p>mmc(a, b) = 336</p><p>A 12 e 84 ou 336 e 84.</p><p>B 12 e 336 ou 48 e 84.</p><p>C 4.032 e 336.</p><p>D 336 e 2.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 37/72</p><p>Parabéns! A alternativa B está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EAssista%20ao%20v%C3%ADdeo%20para%20conferir%20a%20resolu%C3%A7%C3%A3o%20da%</p><p>video-</p><p>player%20src%3D%22https%3A%2F%2Fplay.yduqs.videolib.live%2Findex.html%3Ftoken%3D9e266c60b334455</p><p>3%22%20width%3D%22100%25%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2</p><p>video-</p><p>player%3E%20%20%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20</p><p>Questão 4</p><p>No alto de cada uma de duas torres de televisão, que se localizam</p><p>lado a lado, há luzes que piscam em frequências diferentes. A</p><p>primeira luz, localizada na primeira torre, pisca a cada 4 segundos,</p><p>enquanto na segunda torre a luz pisca a cada 6 segundos.</p><p>Se, em determinado instante, as luzes piscam simultaneamente,</p><p>após quantos segundos elas voltarão a piscar simultaneamente?</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 5</p><p>Usando o algoritmo de Euclides, determine inteiros que verifique a</p><p>igualdade .</p><p>E 4.032 e 336 ou 84 e 84.</p><p>A 12</p><p>B 10</p><p>C 20</p><p>D 15</p><p>E 30</p><p>mdc(56, 72) = 56x + 72y</p><p>A e .x = −4 y = −3</p><p>B e .x = 4 y = 3</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 38/72</p><p>Parabéns! A alternativa E está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 6</p><p>Determine o com o auxílio do algoritmo de</p><p>Euclides, bem como a sua expressão como combinação linear de</p><p>252 e -180.</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Falta pouco para atingir seus objetivos.</p><p>Vamos praticar alguns conceitos?</p><p>C e .x = −4 y = 3</p><p>D e .x = 56 y = 72</p><p>E e .x = 4 y = −3</p><p>mdc(252, −180)</p><p>A</p><p>e</p><p>.</p><p>mdc(252, −180) = 36</p><p>36 = (−180)(−3) + 252(−2)</p><p>B e .mdc(252, −180) = 1 1 = (−180)(1) + 252(1)</p><p>C</p><p>e</p><p>.</p><p>mdc(252, −180) = 36</p><p>36 = (180)(3) + 252(−2)</p><p>D</p><p>e</p><p>.</p><p>mdc(252, −180) = −36</p><p>−36 = (−180)(−3) + 252(2)</p><p>E</p><p>e</p><p>.</p><p>mdc(252, −180) = −36</p><p>−36 = (−180)(−3) + 252(−2)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 39/72</p><p>Questão 1</p><p>Calcule , sendo um inteiro ímpar.</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Usando o algoritmo de Euclides e determinando</p><p>, obtemos</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>mdc(n,n + 2) n</p><p>A 1</p><p>B 2</p><p>C n</p><p>D n + 1</p><p>E n + 2</p><p>mdc(−816, 7209)</p><p>A 1.</p><p>B 2.</p><p>C 3.</p><p>D 6.</p><p>E 9.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 40/72</p><p>3 - Números primos, teorema fundamental da</p><p>aritmética</p><p>Ao �nal deste módulo, você será capaz de identi�car números</p><p>primos, números compostos e a importância do teorema</p><p>fundamental da aritmética.</p><p>Números primos e</p><p>teoremas</p><p>Neste vídeo, você vai entender a importância dos números primos,</p><p>reconhecer os números compostos e entender o teorema fundamental</p><p>da aritmética. Assista!</p><p>Números primos,</p><p>compostos e teorema</p><p>fundamental da aritmética</p><p>Números primos e compostos</p><p>Dizemos que um número inteiro positivo é primo se</p><p>e somente se</p><p>seus únicos divisores positivos são 1 e .</p><p>Chamamos de número composto os números inteiros positivos maiores</p><p>que 1 que não são primos.</p><p>Exemplo</p><p>p > 1</p><p>p</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 41/72</p><p>Os primeiros números inteiros primos: 2, 3, 5 e 7.</p><p>Os primeiros números inteiros compostos: 4, 6, 8 e 10.</p><p>Atenção!</p><p>O número 2 é o único positivo par que é primo. O inteiro positivo 1 não é</p><p>primo, nem composto. Se é um inteiro positivo qualquer, temos então</p><p>que é primo, ou é composto, ou .</p><p>Teorema – primos entre si</p><p>Se um número primo não divide um inteiro , então temos que e</p><p>são primos entre si.</p><p>Demonstração</p><p>Considere um número primo que não divide um inteiro . Considere</p><p>também que . Sabemos, então, que e .</p><p>Como e é número primo, temos que ou . Mas como</p><p>não divide um inteiro a e , não podemos ter .</p><p>Dessa forma, temos que , ou seja, . Assim,</p><p>temos que e são primos entre si.</p><p>O corolário a seguir nos afirma que, se um primo divide um produto,</p><p>então divide um dos fatores.</p><p>Corolário – prova da razão por primos</p><p>Se é número primo de modo que , então temos que ou .</p><p>Demonstração</p><p>Suponha número primo de modo que . Se , o corolário está</p><p>demonstrado. Se , pelo teorema anterior, temos que e são</p><p>primos entre si e o .</p><p>Pelo teorema de Euclides: primos entre si (se e se o</p><p>, então temos que , temos que .</p><p>"Generalizando" o corolário anterior, temos que se é número primo de</p><p>modo que , então, para algum , temos que</p><p>.</p><p>Vamos provar utilizando indução.</p><p>P(1) é verdadeiro e P(2) também é verdadeiro pelo corolário</p><p>anterior.</p><p>Hipótese de indução.</p><p>Suponha que se é número primo de modo que divide o produto</p><p>com menos de fatores, então divide pelo menos um dos</p><p>fatores.</p><p>Etapa Indutiva</p><p>Utilizando o corolário anterior (se é número primo de modo que</p><p>, então temos que ou .), temos que se ,</p><p>a</p><p>a a a = 1</p><p>p a a p</p><p>p a</p><p>d = mdc(a, p) d|a d|p</p><p>d|p p d = 1 d = p p</p><p>d = mdc(a, p) d = p</p><p>d = 1 1 = d = mdc(a, p)</p><p>a p</p><p>p p|ab p|a p|b</p><p>p p|ab p|a</p><p>p ∤ a a p</p><p>md c(a, p) = 1</p><p>a|bc</p><p>mdc(a, b) = 1 a|c) p|b</p><p>p</p><p>p|a1a2a3 ⋯ an k, 1 ≤ k ≤ n</p><p>p|ak</p><p>p p</p><p>n p</p><p>p</p><p>p|ab p|a p|b p|a1a2a3 ⋯ an</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 42/72</p><p>então ou . Se , temos que a</p><p>proposição é válida.</p><p>Se , pela hipótese de indução, temos que divide</p><p>pelo menos um dos fatores, ou seja, , sendo .</p><p>Considerando ou , para algum ,</p><p>temos que .</p><p>Corolário todos primos</p><p>Se temos que os inteiros são todos primos e se</p><p>, então existe um índice , com , de modo que</p><p>.</p><p>Demonstração</p><p>Consideremos os inteiros todos primos e .</p><p>Pelo corolário anterior, existe um índice, , de modo que .</p><p>Mas, como é primo, os únicos divisores positivos de são 1 e .</p><p>Assim, temos que ou , mas, como é primo, . Dessa</p><p>forma, temos que .</p><p>Teorema – divisores primos</p><p>Todo inteiro composto possui um divisor primo.</p><p>Demonstração</p><p>Considere um número inteiro composto. Considere, ainda, o conjunto</p><p>de todos os divisores positivos de , exceto os divisores triviais 1 e .</p><p>Utilizando o princípio da boa ordenação, sabemos que existe elemento</p><p>mínimo de . Vamos então mostrar que esse elemento mínimo de</p><p>é primo.</p><p>Se fosse composto, admitiria pelo menos um divisor , com</p><p>, tal que . Mas como elemento mínimo de , temos que</p><p>e .</p><p>Assim, teríamos que . Isso significaria que não seria elemento</p><p>mínimo de e, por isso, é primo.</p><p>Teorema fundamental da aritmética</p><p>Todo inteiro positivo é igual a um produto de fatores primos.</p><p>Demonstração</p><p>Consideremos inteiro positivo. Se é primo, não há motivo para</p><p>demonstrações. Mas se é composto, pelo teorema (todo inteiro</p><p>composto possui um divisor primo) possui um divisor primo .</p><p>p|an p|a1a2a3 ⋯ an−1 p|an</p><p>p|a1a2a3 ⋯ an−1 p</p><p>p|ak 1 ≤ k ≤ n − 1</p><p>p|an p|a1a2a3 ⋯ an−1 k, 1 ≤ k ≤ n</p><p>p|ak</p><p>−p, q1, q2, ⋯ qn</p><p>p, q1, q2, ⋯ qn</p><p>p|q1q2 ⋯ qn k 1 ≤ k ≤ n</p><p>p = qk</p><p>p, q1, q2, ⋯ qn p|q1q2 ⋯ qn</p><p>1 ≤ k ≤ n p|qk</p><p>qk qk qk</p><p>p = 1 p = qk p p < 1</p><p>p = qk</p><p>a</p><p>A a a</p><p>A = {x|a|1 < x < a}</p><p>p</p><p>A p A</p><p>p d</p><p>1 < d < p d|p p A</p><p>p|a 1 < p < a</p><p>d|a p</p><p>A p</p><p>n > 1</p><p>n > 1 n</p><p>n</p><p>n p1</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 43/72</p><p>Se é primo, a igualdade já expressa como um produto</p><p>de fatores primos e . Se é composto, pelo teorema possui</p><p>um divisor primo .</p><p>Esse procedimento continua e obtemos esta sequência:</p><p>Como temos um número finito de inteiros entre 1 e , existe um que</p><p>é um primo . Dessa forma, ficamos com:</p><p>Escrevemos, portanto, inteiro positivo como um produto de</p><p>fatores primos.</p><p>Corolário – decomposição em fatores primos de um</p><p>inteiro positivo</p><p>A decomposição de um inteiro positivo como fatores primos é</p><p>única, a menos que mude a ordem dos fatores.</p><p>Demonstração</p><p>Sabemos, pelo teorema fundamental da aritmética, que todo inteiro</p><p>positivo é igual a um produto de fatores primos. Precisamos</p><p>mostrar que essa decomposição é única.</p><p>Para isso, vamos supor que o inteiro positivo admite duas</p><p>decomposições como produto de fatores primos:</p><p>Sendo e inteiros primos de modo que:</p><p>n = p1n1</p><p>1 < n1 < n</p><p>n1 n = p1n1 n</p><p>p1 n1 n1 n1</p><p>p2</p><p>n1 = p2n2 → 1 < n2 < n1</p><p>n = p1p2n2, → 1 < n2 < n1 < n</p><p>1 < ⋯ < n3 < n2 < n1 < n</p><p>n nk</p><p>pk : nk = pk</p><p>n = p1p2 ⋯ pk</p><p>n > 1</p><p>n > 1</p><p>n > 1</p><p>n > 1</p><p>n = p1p2p3 ⋯ pr = q1q2q3 ⋯ qs</p><p>r ≤ s</p><p>pi qj</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 44/72</p><p>Temos que ; assim, existe um índice , sendo</p><p>, de forma que , sendo .</p><p>De modo análogo, temos que , com sendo .</p><p>Assim, ficamos com e portanto:</p><p>Raciocinando da mesma forma, temos que e portanto:</p><p>E assim por diante.</p><p>Como , temos que . Chegamos a um absurdo,</p><p>pois cada .</p><p>Dessa forma, temos que e .</p><p>As duas decomposições do inteiro positivo como produto de</p><p>fatores primos são iguais ou, ainda, existe uma única decomposição de</p><p>como produto de fatores primos.</p><p>Corolário – decomposição primária</p><p>Para inteiro positivo e primo, , com</p><p>, temos que todo inteiro positivo</p><p>admite uma única decomposição da forma:</p><p>A decomposição é chamada decomposição</p><p>canônica do inteiro positivo .</p><p>Exemplo 1</p><p>Vamos escrever 2.700 como produto de fatores primos.</p><p>p1 ≤ p2 ≤ p3 ≤ ⋯ ≤ pr = q1 ≤ q2 ≤ q3 ≤ ⋯ ≤ qs</p><p>p1|q1q2q3 ⋯ qs k</p><p>1 ≤ k ≤ s p1 = qk p1 ≥ q1</p><p>q1 = ph 1 ≤ h ≤ r q1 ≥ p1</p><p>p1 = q1</p><p>p2p3 ⋯ pr = q2q3 ⋯ qs</p><p>p2 = q2</p><p>p3 ⋯ pr = q3 ⋯ qs</p><p>r < s 1 = qr+1qr+2 ⋯ qs</p><p>qj > 1</p><p>r = s p1 = q1, p2 = q2, ⋯ , pr = qr</p><p>n > 1</p><p>n</p><p>ki pi i = 1, 2, ⋯ , r</p><p>p1 < p2 < p3 < ⋯ < pr n > 1</p><p>n = pk1</p><p>1 pk2</p><p>2 ⋯ pkrr</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr</p><p>n > 1</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 45/72</p><p>Dessa forma, temos:</p><p>Antes de continuar, preste atenção na seguinte informação.</p><p>Atenção!</p><p>Os fatores primos podem aparecer repetidos.</p><p>A decomposição canônica de 2.700 é dada então por:</p><p>Exemplo 2</p><p>Determinando a decomposição canônica do inteiro positivo 1.500,</p><p>obtemos:</p><p>2.700 = 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 5 ⋅ 5</p><p>2700 = 22 ⋅ 33 ⋅ 52</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 46/72</p><p>Dessa forma, temos:</p><p>MMC e MDC a partir da decomposição</p><p>canônica</p><p>A partir do conhecimento da decomposição canônica de cada um de</p><p>dois inteiros positivos 1 e , podemos determinar o</p><p>e o . Entenda!</p><p>Mínimo múltiplo comum</p><p>O mínimo múltiplo comum de e será o produto dos</p><p>fatores primos comuns e não comuns das duas decomposições</p><p>canônicas com os maiores expoentes.</p><p>Maior divisor comum</p><p>O maior divisor comum será o produto dos fatores primos</p><p>comuns das duas decomposições canônicas com os menores</p><p>expoentes.</p><p>1.500 = 22 ⋅ 31 ⋅ 53</p><p>a > b > 1 mdc(a, b)</p><p>mmc(a, b)</p><p>a b,mmc(a, b)</p><p>mdc(a, b)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio#</p><p>47/72</p><p>Agora, vamos determinar o MDC e o MMC dos números 40 e 60, com o</p><p>auxílio da decomposição canônica de cada um dos dois inteiros</p><p>positivos. Veja!</p><p>40</p><p>Determinamos da seguinte forma:</p><p>60</p><p>Determinamos da seguinte forma:</p><p>Calculando, temos:</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 48/72</p><p>Teorema de Euclides e</p><p>fórmulas que dão primos</p><p>Teorema de Euclides</p><p>Há um número infinito de primos.</p><p>Demonstração</p><p>Considere que exista um número primo maior que todos os demais</p><p>primos</p><p>Considere ainda o inteiro positivo:</p><p>Utilizando o teorema fundamental da aritmética, como tem</p><p>pelo menos um divisor primo , que deve ser então um dos primos</p><p>.</p><p>Dessa forma, sabemos que:</p><p>Ou ainda:</p><p>Chegamos a um absurdo, pois , o único divisor positivo de 1, é o</p><p>próprio 1.</p><p>Assim, qualquer que seja o número primo, existe sempre um número</p><p>primo maior que ele.</p><p>O conjunto dos números primos é um conjunto infinito:</p><p>60 = 22 ⋅ 3 ⋅ 5</p><p>40 = 23 ⋅ 5</p><p>mmc(60, 40) = 23 ⋅ 3 ⋅ 5 = 120</p><p>pn</p><p>p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, ⋯</p><p>P = p1p2p3 ⋯ pn + 1</p><p>P > 1,P</p><p>p</p><p>p1, p2, p3, ⋯ , pn</p><p>p|P e p|p1p2p3 ⋯ pn</p><p>p|P − p1p2p3 ⋯ pn  ou  p|1</p><p>p > 1</p><p>{2, 3, 5, 7, 11, 13, ⋯}</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 49/72</p><p>O teorema a seguir vai nos auxiliar a reconhecer se um dado inteiro</p><p>é um número primo ou composto. Basta dividirmos a</p><p>sucessivamente pelos primos menores que .</p><p>Teorema – reconhecimento de números primos e</p><p>compostos</p><p>Se um número inteiro positivo é composto, então possui um</p><p>divisor primo .</p><p>Demonstração</p><p>Considere um número inteiro positivo é composto. Temos então</p><p>que:</p><p>Supondo que , ficamos com:</p><p>Como , utilizando o teorema fundamental da aritmética, tem pelo</p><p>menos um divisor primo , de forma que . Uma vez que</p><p>e , temos que , ou seja, o inteiro primo é um divisor de .</p><p>Esse teorema é logicamente equivalente a: "Se não é divisível por</p><p>nenhum primo então é primo."</p><p>Exemplo 1</p><p>Consideremos o número 223. Desejamos saber se é um número primo.</p><p>Os primos que não excedem a são e 13.</p><p>Podemos conferir se 223 não é divisível por nenhum desses números</p><p>primos.</p><p>Assim, temos que 223 é primo.</p><p>Esse procedimento pode ser bem trabalhoso, ainda mais para números</p><p>maiores.</p><p>Exemplo 2</p><p>a > 1</p><p>√a</p><p>a > 1 a</p><p>p ≤ √a</p><p>a > 0</p><p>a = bc</p><p>1 < b < a</p><p>1 < c < a</p><p>b ≤ c</p><p>b ⋅ b ≤ b ⋅ c</p><p>b2 ≤ b ⋅ c</p><p>b2 ≤ a</p><p>b ≤ √a</p><p>b > 1 b</p><p>p p ≤ b ≤ √a p|b</p><p>b|a p|a p ≤ √a a</p><p>a > 1</p><p>p ≤ √a a</p><p>√223 ≅14, 9 2, 3, 5, 7, 11</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 50/72</p><p>Considerando e inteiros positivos, demonstre que sempre</p><p>divide o .</p><p>Demonstração</p><p>Seja . Então existem inteiros primos e de modo que</p><p>e . Temos que</p><p>Mas sabemos que:</p><p>Assim, ficamos com:</p><p>Dessa forma, temos um inteiro de modo que o é um</p><p>múltiplo do . Dizemos, ainda, que divide o</p><p>.</p><p>Exemplo 3</p><p>Vamos mostrar que o único primo da forma é 7.</p><p>Demonstração</p><p>Sabemos que . Como queremos que</p><p>seja primo, temos então que são seus</p><p>fatores.</p><p>Exemplo 4</p><p>Mostre que a soma de dois inteiros positivos ímpares e consecutivos é</p><p>sempre um inteiro composto.</p><p>Demonstração</p><p>Consideremos dois inteiros ímpares consecutivos. Eles têm a forma</p><p>e . Somando os dois números, temos:</p><p>a b mdc(a, b)</p><p>mmc(a, b)</p><p>d = mdc(a, b) x y</p><p>a = dx b = dy</p><p>a ⋅ b = dx ⋅ dy = mdc(a, b) ⋅ x ⋅ mdc(a, b) ⋅ y = mdc(a, b) ⋅ mdc(a, b) ⋅ x ⋅ y.</p><p>mdc(a, b) ⋅ mmc(a, b) = a ⋅ b</p><p>mdc(a, b) ⋅ mdc(a, b) ⋅ x ⋅ y = mdc(a, b) ⋅ mmc(a, b)</p><p>mdc(a, b) ⋅ xy = mmc(a, b)</p><p>z = xy mmc(a, b)</p><p>mdc(a, b) mdc(a, b)</p><p>mmc(a, b)</p><p>n3 − 1</p><p>n3 − 1 = (n − 1) (n2 + n + 1)</p><p>n3 − 1 (n − 1) (n2 + n + 1)</p><p>n − 1 = 1</p><p>n = 2</p><p>n2 + n + 1 = 22 + 2 + 1 = 7</p><p>2k + 1 2k + 3</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 51/72</p><p>Assim, a soma é um múltiplo de 4, ou seja, um número composto.</p><p>Fórmulas que dão primos</p><p>A fórmula de Euler é uma das que nos fornecem números primos, por</p><p>exemplo, para .</p><p>Para e , a fórmula de Euler obtém números compostos.</p><p>São conhecidas outras fórmulas que fornecem números primos:</p><p>para</p><p>para</p><p>para</p><p>Agora, vamos demonstrar que se e são inteiros positivos tais que o</p><p>então .</p><p>Demonstração</p><p>Seja . Como , então</p><p>temos que e como , então temos que . Assim,</p><p>sabemos que .</p><p>Da mesma forma, como , então temos que e como</p><p>, então temos que . Assim, sabemos que e</p><p>temos .</p><p>Teoria na prática</p><p>Vamos demonstrar que, se o inteiro é composto, então também</p><p>é composto.</p><p>2k + 1 + 2k + 3 = 4k + 4 = 4(k + 1)</p><p>n = 1, 2, 3, ⋯ , 39</p><p>fn = n2 + n + 41</p><p>n = 40 n = 41</p><p>f40 = 402 + 40 + 41 = 40(40 + 1) + 41 = 40 ⋅ 41 + 41 = 41</p><p>f41 = 412 + 41 + 41 = 41(41 + 1) + 41 = 41 ⋅ 42 + 41 =</p><p>fn = 2n2 + 29 0 ≤ n ≤ 28</p><p>fn = n2 + n + 17 0 ≤ n ≤ 16</p><p>fn = 3n2 + 3n + 23 0 ≤ n ≤ 21</p><p>a b</p><p>mdc(a, b) = mmc(a, b) a = b</p><p>d = mdc(a, b) = mmc(a, b) d = mdc(a, b)</p><p>d|a d = mmc(a, b) a|d</p><p>a = d</p><p>d = mdc(a, b) d|b</p><p>d = mmc(a, b) b|d b = d</p><p>a = b</p><p>_black</p><p>n 2n−1</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 52/72</p><p>Mão na massa</p><p>Questão 1</p><p>Com o auxílio da decomposição canônica de cada um dos dois</p><p>inteiros positivos, determine o e o dos números 588 e</p><p>936.</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Determinando todos os pares de primos e , de modo que</p><p>, obtemos:</p><p>Mostrar solução</p><p></p><p>mdc mmc</p><p>A</p><p>e</p><p>.</p><p>mdc(588, 936) = 22 ⋅ 32</p><p>mmc(588, 936) = 23 ⋅ 33 ⋅ 72 ⋅ 13</p><p>B</p><p>e</p><p>.</p><p>mdc(588, 936) = 22 ⋅ 32</p><p>mmc(588, 936) = 23 ⋅ 32 ⋅ 72</p><p>C</p><p>e</p><p>.</p><p>mdc(588, 936) = 22 ⋅ 3</p><p>mmc(588, 936) = 23 ⋅ 32 ⋅ 72 ⋅ 13</p><p>D</p><p>e</p><p>.</p><p>mdc(588, 936) = 22</p><p>mmc(588, 936) = 23 ⋅ 32 ⋅ 72</p><p>E</p><p>e</p><p>.</p><p>mdc(588, 936) = 23 ⋅ 3</p><p>mmc(588, 936) = 22 ⋅ 33 ⋅ 72 ⋅ 13</p><p>p q</p><p>p − q = 3</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 53/72</p><p>Parabéns! A alternativa E está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 3</p><p>Determinando todos os primos que são iguais a um quadrado</p><p>perfeito menos 1, obtemos</p><p>Parabéns! A alternativa D está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 4</p><p>Com o auxílio da decomposição canônica dos inteiros 507 e 1.287,</p><p>determine o e o ,</p><p>respectivamente:</p><p>A e .p = 3 q = 1</p><p>B e .p = 7 q = 5</p><p>C e e .p = 9 q = 7; p = 7 q = 5</p><p>D e .p = 11 q = 9</p><p>E e .p = 5 q = 2</p><p>A 4.</p><p>B 9.</p><p>C 16.</p><p>D 3.</p><p>E 2.</p><p>mdc(507, 1.287) mmc(507, 1.287)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 54/72</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EAssista%20ao%20v%C3%ADdeo%20para%20conferir%20a%20resolu%C3%A7%C3%A3o%20da%</p><p>video-</p><p>player%20src%3D%22https%3A%2F%2Fplay.yduqs.videolib.live%2Findex.html%3Ftoken%3D54073913da80445</p><p>4%22%20width%3D%22100%25%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2</p><p>video-</p><p>player%3E%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20</p><p>Questão 5</p><p>Determine todos os primos tais que é um quadrado</p><p>perfeito.</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 6</p><p>A 39 e 16.731.</p><p>B 16.731 e 39.</p><p>C 507 e 1.287.</p><p>D 1.287 e 507.</p><p>E 429 e 1.287.</p><p>p 3p + 1</p><p>A 1</p><p>B 2</p><p>C 5</p><p>D 8</p><p>E 16</p><p>23/04/2024,</p><p>19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 55/72</p><p>Determinando a decomposição canônica do inteiro 5.040, obtemos:</p><p>Parabéns! A alternativa D está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Falta pouco para atingir seus objetivos.</p><p>Vamos praticar alguns conceitos?</p><p>Questão 1</p><p>Sabendo que e</p><p>, determine o e</p><p>, respectivamente:</p><p>A 22 ⋅ 32 ⋅ 52 ⋅ 7</p><p>B 24 ⋅ 34 ⋅ 52 ⋅ 7</p><p>C 23 ⋅ 34 ⋅ 5 ⋅ 7</p><p>D 24 ⋅ 32 ⋅ 5 ⋅ 7</p><p>E 22 ⋅ 32 ⋅ 5 ⋅ 7</p><p>a = 230 ⋅ 521 ⋅ 19 ⋅ 233</p><p>b = 26 ⋅ 3 ⋅ 74 ⋅ 112 ⋅ 195 ⋅ 237 mdc(a, b)</p><p>mmc(a, b)</p><p>A e .230 ⋅ 19 ⋅ 237 230 ⋅ 3 ⋅ 521 ⋅ 74 ⋅ 112 ⋅ 19 ⋅ 237</p><p>B e .230 ⋅ 3 ⋅ 521 ⋅ 74 ⋅ 112 ⋅ 195 ⋅ 237 26 ⋅ 19 ⋅ 233</p><p>C e .26 ⋅ 19 ⋅ 233 230 ⋅ 3 ⋅ 521 ⋅ 74 ⋅ 112 ⋅ 195 ⋅ 237</p><p>D e .26 ⋅ 521 ⋅ 19 ⋅ 233 230 ⋅ 3 ⋅ 521 ⋅ 74 ⋅ 195 ⋅ 237</p><p>E e .26 ⋅ 521 ⋅ 195 ⋅ 237 26 ⋅ 3 ⋅ 521 ⋅ 74 ⋅ 195 ⋅ 237</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 56/72</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Considerando os números inteiros 89 e 97 é correto afirmar que</p><p>Parabéns! A alternativa B está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>4 - Crivo de Erastóstenes, primos gêmeos,</p><p>conjectura de Goldbach</p><p>Ao �nal deste módulo, você será capaz de analisar o crivo de</p><p>Erastóstenes, identi�cando os primos gêmeos.</p><p>A ambos são números compostos.</p><p>B ambos são números primos.</p><p>C 89 é composto e 97 é primo.</p><p>D 89 é primo e 97 é composto.</p><p>E 89 e 97 não são compostos nem primos.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 57/72</p><p>Crivo de Erastóstenes e</p><p>primos gêmeos</p><p>Confira neste vídeo o crivo de Erastóstenes e os primos gêmeos, a</p><p>conjectura de Goldbach e o método de fatoração de Fermat.</p><p>Crivo de Erastóstenes e</p><p>primos gêmeos</p><p>Crivo de Erastóstenes</p><p>Algoritmo que relaciona os números primos menores que , levando-se</p><p>em consideração o fato de que os divisores precisam ser procurados</p><p>somente até . Para tanto, devemos seguir os passos a seguir.</p><p>Vamos observar agora como se dá, na prática, o procedimento do crivo</p><p>de Erastótenes para 60. Comecemos listando os números inteiros</p><p>positivos de 1 até 60. A princípio, vamos identificar até quando</p><p>n</p><p>√n</p><p> Primeiro passo</p><p>Relacionamos todos os inteiros entre 2 e .n − 1</p><p> Segundo passo</p><p>Para cada primo , eliminamos todos os</p><p>múltiplos de , para .</p><p>p ≤ √n</p><p>r ⋅ p p r ≥ 2</p><p> Terceiro passo</p><p>Os números que sobram são os primos menores</p><p>que .n</p><p>n =</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 58/72</p><p>precisamos procurar os divisores de , e, dessa forma,</p><p>precisamos obter os divisores próprios de 60 até o 7.</p><p>Sabemos que 1 não é primo. Excluiremos então a célula do 1, pois ele</p><p>não nos servirá. 0 número 2 é o primeiro primo; vamos circulá-lo.</p><p>Eliminaremos, então, os pares maiores que 2, pois não são primos.</p><p>Acompanhe!</p><p>O primeiro número não marcado foi o 3 e, como não tem divisores</p><p>primos menores, é primo. Em seguida, eliminamos os múltiplos de 3,</p><p>contando de 3 em 3 a partir do próprio 3. Veja!</p><p>O próximo número não marcado é o 5, que é primo. Circulamos o 5</p><p>então e eliminamos os múltiplos de 5.</p><p>O próximo número não marcado é o 7, que é primo. Circulamos o 7,</p><p>então, e eliminamos os seu múltiplos.</p><p>É o último teste que precisamos realizar. Os números não eliminados</p><p>até então são primos. Confira o resultado!</p><p>Com esse procedimento, obtemos os números primos menores que 60:</p><p>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 e 59.</p><p>Primos gêmeos</p><p>Dois inteiros positivos primos, ímpares e consecutivos são ditos primos</p><p>gêmeos.</p><p>Exemplos</p><p>60, √60 ≅7, 7</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 59/72</p><p>3 e 5, 5 e 7, 11 e 13, 17 e 19, 29 e 31.</p><p>Interessante observar a existência de um terno de inteiros positivos</p><p>ímpares e consecutivos, primos: 3,5 e 7.</p><p>Sequências de inteiros consecutivos</p><p>compostos</p><p>Qualquer que seja o inteiro positivo , há sequências de inteiros</p><p>positivos consecutivos e compostos.</p><p>Demonstração</p><p>Na sequência a seguir, seus termos são inteiros positivos</p><p>consecutivos.</p><p>Ainda, cada termo da sequência é composto, uma vez que</p><p>é divisível por se .</p><p>Exemplo</p><p>Considerando , temos a sequência:</p><p>Nesse caso, temos quatro termos, todos inteiros positivos consecutivos</p><p>e compostos.</p><p>Exemplos de inteiros consecutivos compostos:</p><p>24,25,26, 27</p><p>32,33,34,35</p><p>54,55,56,57</p><p>74,75,76,77</p><p>n n</p><p>n</p><p>(n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4, ⋯ , (n + 1)! + (n</p><p>(n + 1)! + j</p><p>j 2 ≤ j ≤ n + 1</p><p>n = 4</p><p>5! + 2, 5! + 3, 5! + 4, 5! + 5</p><p>5! + 2 = 120 + 2 = 122 = 2 ⋅ 61</p><p>5! + 3 = 120 + 3 = 123 = 3 ⋅ 41</p><p>5! + 4 = 120 + 4 = 124 = 4 ⋅ 31</p><p>5! + 5 = 120 + 5 = 125 = 5 ⋅ 25</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 60/72</p><p>Conjectura de Goldbach e</p><p>método de fatoração de</p><p>Fermat</p><p>Conjectura de Goldbach</p><p>Christian Goldbach (1690-1764), professor na Academia de Ciências de</p><p>São Petersburgo, Rússia, discutia problemas e resoluções, por</p><p>correspondência, com Leonhard Euler, um matemático e físico suíço. A</p><p>proposta era que Euler analisasse os resultados de Goldbach.</p><p>Em 1742, em uma dessas cartas, Goldbach enunciou o que conhecemos</p><p>por conjectura de Goldbach: todo inteiro par maior que 4 pode ser</p><p>expresso como a soma de dois primos ímpares.</p><p>Atenção!</p><p>Uma conjectura é uma inferência ou dedução provável, uma suposição.</p><p>Vamos ver alguns exemplos!</p><p>Em 2006, Harald Helfgott, nascido no Peru, começou a tentar provar a</p><p>conjectura fraca de Goldbach, segundo a qual todo número ímpar maior</p><p>do que cinco pode ser expresso como uma soma de três números</p><p>primos. Em junho de 2013, demonstrou que a conjectura era verdadeira.</p><p>Método de fatoração de Fermat</p><p>A fatoração de números é um assunto importante de segurança quando</p><p>lidamos com certos métodos de criptografia. Quando precisar fatorar</p><p>um número e o primeiro fator primo é muito grande, ainda que o cálculo</p><p>seja realizado com auxílio de um computador, pode se tornar um</p><p>problema delicado.</p><p>6 = 3 + 3</p><p>8 = 5 + 3</p><p>10 = 3 + 7 = 5 + 5</p><p>12 = 5 + 7</p><p>14 = 7 + 7</p><p>16 = 13 + 3</p><p>18 = 13 + 5</p><p>20 = 13 + 7</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 61/72</p><p>Pierre de Fermat (1601-1665) propôs um procedimento bem</p><p>interessante para se fatorar números cujo fator é próximo à sua raiz</p><p>quadrada. Pelo método de fatoração de Fermat, considerando o inteiro</p><p>positivo ímpar , podemos obter a decomposição de em um produto</p><p>de dois fatores distintos da seguinte forma:</p><p>Construímos uma tabela, com linhas, obtida adicionando a ,</p><p>sucessivamente, inteiros ímpares consecutivos</p><p>em cada linha.</p><p>Se na -ésima linha aparecer o quadrado perfeito , então, temos</p><p>que .</p><p>Se somente na última linha aparecer um quadrado perfeito, ou seja, a</p><p>linha , temos que é um número primo.</p><p>Exemplo 1</p><p>Considerando , a tabela ficará com linhas.</p><p>Denise Candal.</p><p>Na segunda linha, temos e, na décima linha, temos . As duas</p><p>únicas formas de decompormos o inteiro positivo ímpar 21 em um</p><p>produto de dois fatores distintos é:</p><p>As demais formas são variações dessas decomposições, por exemplo:</p><p>.</p><p>n n</p><p>n−1</p><p>2 n</p><p>{1, 3, 5, 7, 9, ⋯ n−1</p><p>2 }</p><p>r t2</p><p>n = (t + r)(t − r)</p><p>L = n−1</p><p>2 n</p><p>n = 21 n−1</p><p>2 = 21−1</p><p>2 = 10</p><p>1 21 + 1 = 22</p><p>2 22 + 3 = 25 = 52</p><p>3 25 + 5 = 30</p><p>4 30 + 7 = 37</p><p>5 37 + 9 = 46</p><p>6 46 + 11 =</p><p>57</p><p>7 57 + 13 = 70</p><p>8 70 + 15 = 85</p><p>9 85 + 17 = 102</p><p>10 102 + 19 = 121 = 112</p><p>52 112</p><p>21 = (5 + 2)(5 − 2) = 7 ⋅ 3</p><p>21 = (11 + 10)(11 − 10) = 21 ⋅ 1</p><p>21 = (−7) ⋅ (−3)</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 62/72</p><p>Atenção!</p><p>Vale lembrar que 21 não é um número primo.</p><p>Exemplo 2</p><p>Vamos utilizar o método de fatoração de Fermat para obtermos a</p><p>decomposição de em um produto de dois fatores distintos e</p><p>determinar se o número 33 é primo.</p><p>Considerando , a tabela ficará com linhas.</p><p>Denise Candal.</p><p>Na quarta linha, temos e, na décima sexta linha, temos . As duas</p><p>únicas formas de decompor o inteiro positivo ímpar 21 em um produto</p><p>de dois fatores distintos é:</p><p>n = 33</p><p>n = 33 n−1</p><p>2 = 33−1</p><p>2 = 16</p><p>1 33 + 1 = 24</p><p>2 34 + 3 = 37</p><p>3 37 + 5 = 42</p><p>4 42 + 7 = 49 = 72</p><p>5 49 + 9 = 58</p><p>6 58 + 11 = 69</p><p>7 69 + 13 = 82</p><p>8 82 + 15 = 97</p><p>9 97 + 17 = 114</p><p>10 114 + 19 = 133</p><p>11 133 + 21 = 154</p><p>12 154 + 23 = 177</p><p>13 177 + 25 = 202</p><p>14 202 + 27 = 229</p><p>15 229 + 29 = 258</p><p>16 258 + 31 = 289 = 172</p><p>72 172</p><p>33 = (7 + 4)(7 − 4) = 11 ⋅ 3</p><p>33 = (17 + 16)(17 − 16) = 33 ⋅ 1</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 63/72</p><p>Lembrando que 33 não é um número primo.</p><p>Agora, vamos demonstrar que todo primo, exceto 2 e 3, é da forma</p><p>ou , com inteiro positivo.</p><p>Demonstração</p><p>Utilizando o algoritmo da divisão, todo número quando dividido por 6</p><p>assume uma destas formas:</p><p>Concluímos então:</p><p>Se é múltiplo de 6. Não é primo.</p><p>Se , pode ser primo.</p><p>Se , é múltiplo de 2. Dessa forma,</p><p>não é primo.</p><p>Se é múltiplo de 3. Dessa forma,</p><p>não é primo.</p><p>Se , é múltiplo de 2. Dessa forma,</p><p>não é primo.</p><p>Se . Pode</p><p>ser primo.</p><p>Assim, se for primo, não pode ser das formas e</p><p>No entanto, pode ser da forma ou .</p><p>Teoria na prática</p><p>Vamos utilizar o método de fatoração de Fermat para obtermos a</p><p>decomposição de em um produto de dois fatores distintos e</p><p>determinar se o número 31 é primo.</p><p>Mão na massa</p><p>6k − 1 6k + 1 k</p><p>6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5</p><p>n = 6k,n</p><p>n = 6k + 1</p><p>n = 6k + 2 = 2(3k + 1) n</p><p>6k + 2</p><p>n = 6k + 3 = 3(2k + 1),n</p><p>6k + 3</p><p>n = 6k + 4 = 2(3k + 2) n</p><p>6k + 4</p><p>n = 6k + 5 = 6k + 6 − 1 = 6(k + 1) − 1 = 6k′ − 1</p><p>n 6k, 6k + 2, 6k + 3</p><p>6k + 4. 6k − 1 6k + 1</p><p>_black</p><p>n = 31</p><p>Mostrar solução</p><p></p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 64/72</p><p>Questão 1</p><p>Com o auxílio do crivo de Eratóstenes, quais são os números</p><p>primos menores que 40?</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Determinando os quatro menores primos da forma , quais</p><p>números obtemos?</p><p>Parabéns! A alternativa C está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>A 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37</p><p>B 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37</p><p>C 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37</p><p>D 3, 5, 7, 11, 13, 17, 19, 23, 29, 31</p><p>E 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31</p><p>n2 − 2</p><p>A 3, 5, 7, 11</p><p>B 2, 3, 5, 7</p><p>C 2, 7, 23, 47</p><p>D 1, 7, 23, 47</p><p>E 1, 2, 3, 5, 7</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 65/72</p><p>Questão 3</p><p>Com relação aos números 239 e 241, analise as afirmativas a</p><p>seguir.</p><p>I. São primos.</p><p>II. São primos gêmeos.</p><p>III. São pares primos.</p><p>É correto o que se afirma</p><p>Parabéns! A alternativa D está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 4</p><p>Considere o Método de Fatoração de Fermat, e a tabela abaixo, para</p><p>, linhas, sobre a decomposição de</p><p>em um produto de dois fatores distintos.</p><p>A somente na alternativa I.</p><p>B somente na alternativa II.</p><p>C somente na alternativa III.</p><p>D nas alternativas I e II.</p><p>E nas alternativas I e III.</p><p>n = 29 com n−1</p><p>2 = 29−1</p><p>2 = 14</p><p>n = 29</p><p>1 29 + 1 = 30</p><p>2 30 + 3 = 33</p><p>3 33 + 5 = 38</p><p>4 38 + 7 = 45</p><p>5 45 + 9 = 54</p><p>6 54 + 11 = 65</p><p>7 65 + 13 = 78</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 66/72</p><p>Denise Candal.</p><p>Analise as afirmativas a seguir.</p><p>I) O quadrado perfeito ocorre somente na décima quarta linha.</p><p>II) A decomposição ficará .</p><p>III) 29 é um número composto.</p><p>É correto o que se afirma</p><p>Parabéns! A alternativa D está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 5</p><p>Determinando uma sequência de três termos inteiros positivos</p><p>consecutivos e compostos, obtemos</p><p>1 29 + 1 = 30</p><p>8 78 + 15 = 93</p><p>9 93 + 17 = 110</p><p>10 110 + 19 = 129</p><p>11 129 + 21 = 150</p><p>12 150 + 23 = 173</p><p>13 173 + 25 = 198</p><p>14 198 + 27 = 225</p><p>29 = (15 + 14)(15 − 14) = 29 ⋅ 1</p><p>A somente na alternativa I.</p><p>B somente na alternativa II.</p><p>C somente na alternativa III.</p><p>D nas alternativas I e II.</p><p>E nas alternativas II e III.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 67/72</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 6</p><p>Das sequências abaixo, podemos dizer que são sequencias de 100</p><p>inteiros positivos consecutivos e compostos as sequências:</p><p>I)</p><p>II)</p><p>III)</p><p>É correto o que se afirma</p><p>Parabéns! A alternativa A está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EAssista%20ao%20v%C3%ADdeo%20para%20conferir%20a%20resolu%C3%A7%C3%A3o%20da%</p><p>video-</p><p>player%20src%3D%22https%3A%2F%2Fplay.yduqs.videolib.live%2Findex.html%3Ftoken%3D59d94d3f5f164373</p><p>6%22%20width%3D%22100%25%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fyduqs-</p><p>A 26, 27 e 28.</p><p>B 13, 14 e 15.</p><p>C 66, 67 e 68.</p><p>D 22, 23 e 24.</p><p>E 36, 37 e 38.</p><p>101! + 2; 101! + 3; 101! + 4 … 101! + 100; 101! + 101</p><p>100! + 2; 100! + 3; 100! + 4 … 100! + 101; 100! + 102</p><p>102! + 2; 102! + 3; 102! + 4 … 102! + 101; 102! + 102</p><p>A somente na alternativa I.</p><p>B somente na alternativa II.</p><p>C somente na alternativa III.</p><p>D nas alternativas I e II.</p><p>E nas alternativas II e III.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 68/72</p><p>video-</p><p>player%3E%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20</p><p>Falta pouco para atingir seus objetivos.</p><p>Vamos praticar alguns conceitos?</p><p>Questão 1</p><p>Considere o método de fatoração de Fermat e a tabela a seguir.</p><p>Denise Candal.</p><p>Sendo que , com linhas, sobre a</p><p>decomposição de em um produto de dois fatores distintos.</p><p>Dessa forma, analise as seguintes afirmativas:</p><p>I. O quadrado perfeito ocorre somente na sétima linha.</p><p>II. A decomposição ficará .</p><p>III. Dezessete é um número composto.</p><p>É correto o que se afirma</p><p>1 17 + 1 = 18</p><p>2 18 + 3 = 21</p><p>3 21 + 5 = 6</p><p>4 26 + 7 = 33</p><p>5 33 + 9 = 42</p><p>6 42 + 11 = 53</p><p>7 53 + 13 = 66</p><p>8 66 + 15 = 81</p><p>n = 17 n−1</p><p>2 = 17−1</p><p>2 = 8</p><p>n = 15</p><p>17 = (9 + 8)(9 − 8) = 17 ⋅ 1</p><p>A somente na alternativa I.</p><p>B somente na alternativa II.</p><p>C somente na alternativa III.</p><p>23/04/2024, 19:17 MDC, MMC e números primos</p><p>https://stecine.azureedge.net/repositorio/00212en/40914/index.html?brand=estacio# 69/72</p><p>Parabéns! A alternativa B está correta.</p><p>%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Com relação aos números 109 e 111, analise as afirmativas a</p><p>seguir.</p><p>I. São primos</p>