Congruências, sistemas lineares e funções aritméticas

Prévia do material em texto

<p>Congruências, sistemas lineares e funções</p><p>aritméticas</p><p>Profa. Ana Lucia de Sousa</p><p>Descrição</p><p>Você irá conhecer as propriedades da aritmética modular, as equações</p><p>diofantinas lineares, as congruências lineares, os métodos de resolução</p><p>de sistemas de congruências lineares e as funções aritméticas.</p><p>Propósito</p><p>A teoria dos números é uma área antiga que estuda os números inteiros</p><p>e suas propriedades aritméticas. Esse estudo é de suma importância</p><p>para o aluno do curso de matemática, que deve conhecer com clareza</p><p>essa teoria, seus principais teoremas e sua importância na resolução de</p><p>problemas mais complexos.</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>Equações diofantinas lineares e</p><p>congruências</p><p>Resolver as equações diofantinas.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 1/101</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/pdfs/solucionario.pdf</p><p>Módulo 2</p><p>Congruências lineares</p><p>Determinar a solução das congruências lineares.</p><p>Módulo 3</p><p>Métodos de resolução de</p><p>sistemas de congruências</p><p>lineares</p><p>Reconhecer os métodos para lidar com sistemas lineares</p><p>congruentes.</p><p>Módulo 4</p><p>Divisores, funções e classes</p><p>residuais</p><p>Identificar os resultados referentes a divisores de número inteiro,</p><p>funções aritméticas e classes residuais.</p><p>Introdução</p><p>Olá! Antes de começarmos, assista ao vídeo e entenda os</p><p>conceitos tratados na teoria dos números, como a aritmética</p><p>modular, as equações diofantinas lineares, as congruências</p><p>lineares, os métodos de resolução de sistemas de congruências</p><p>lineares e as funções aritméticas.</p><p></p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 2/101</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 - Equações diofantinas lineares e</p><p>congruências</p><p>Ao �nal deste módulo, você será capaz de resolver as equações</p><p>diofantinas.</p><p>Equações diofantinas</p><p>Assista ao vídeo e conheça os teoremas e corolários das equações</p><p>diofantinas (teoremas da condição de existência de solução e das</p><p>soluções da equação diofantina linear) e as congruências, incluindo a</p><p>aritmética modular, as propriedades das congruências e os sistemas</p><p>complexos de restos.</p><p>Equações diofantinas</p><p>lineares</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 3/101</p><p>javascript:CriaPDF()</p><p>O nome diofantina foi dado em homenagem ao matemático grego</p><p>Diofanto de Alexandria. Ele é considerado por muitos como o pai da</p><p>álgebra, pois apresentou diversas contribuições no campo da álgebra e</p><p>da teoria dos números. É difícil informar com precisão a data do seu</p><p>nascimento, mas acredita-se que tenha ocorrido no início do século III.</p><p>Seus trabalhos foram publicados por volta de 350 EC.</p><p>Sua obra principal, chamada de Arithmetica, é composta por treze livros,</p><p>dos quais seis estão em grego. Na atualidade, os historiadores</p><p>encontraram quatro livros em árabe, que acreditam fazer parte dessa</p><p>coletânea. Nesse trabalho, ele deu início ao estudo da existência de</p><p>soluções inteiras de algumas equações polinomiais a partir da álgebra.</p><p>Essas equações são chamadas de equações diofantinas e podem ser</p><p>lineares e não lineares.</p><p>De�nição</p><p>Podemos definir de forma mais geral uma equação diofantina linear</p><p>como sendo uma equação polinomial da seguinte forma:</p><p>Em que:</p><p>são os coeficientes inteiros da equação.</p><p>são as incógnitas.</p><p>é o termo constante.</p><p>Vamos considerar apenas a equação diofantina linear com duas</p><p>incógnitas, apresentada da seguinte forma:</p><p>Nesse caso, são números inteiros dados, sendo e</p><p>diferentes de zero.</p><p>Muitos problemas podem ser modelados a partir dessa equação. Veja</p><p>um exemplo simples:</p><p>Carlos recebe uma mesada de R$ 40 por semana e deseja comprar com</p><p>esse dinheiro balas de R$ 5 e R$ 3. Considerando essas informações,</p><p>quantas balas, de R$ 5 e R$ 3 Carlos pode comprar, gastando o máximo</p><p>de sua mesada?</p><p>Veja que podemos modelar esse problema como em</p><p>que representa a quantidade de balas que custam R$ 5 e a</p><p>quantidade de balas que custam R$ 3. Os coeficientes dessa equação</p><p>são: e</p><p>Confira outros exemplos de equações diofantinas lineares:</p><p>a1x1 + a2x2 + ⋯ + anxn = b</p><p>a1 + a2 + ⋯ + an</p><p>x1 + x2 + ⋯ + xn</p><p>b</p><p>ax + by = c</p><p>a, b, c ∈ Z a b</p><p>5x + 3y = 40,</p><p>x y</p><p>a = 5, b = 3 c = 40.</p><p>9x + 6y = 85</p><p>5x − 11y = 29</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 4/101</p><p>Podemos modelar inúmeras situações com essas equações. A partir da</p><p>modelagem, é necessário determinar o valor das incógnitas que</p><p>satisfazem a equação. Ou seja, estamos procurando por números</p><p>inteiros. Assim, é importante conhecer com clareza as condições</p><p>necessárias para que uma equação diofantina linear tenha solução</p><p>inteira.</p><p>Teorema 1: condição de existência de solução</p><p>Uma equação diofantina linear tem solução se, e somente</p><p>se, divide em que:</p><p>Demonstração</p><p>Imagine que exista um par de inteiros que é solução da</p><p>equação diofantina, tal que</p><p>Como o existem números inteiros e tais que</p><p>e</p><p>Em podemos substituir e Observe!</p><p>Como é um número inteiro, concluímos então que divide</p><p>Suponhamos que divide isto é, que:</p><p>(1)</p><p>Em que é um número inteiro.</p><p>Como o existem números inteiros e tais que:</p><p>(2)</p><p>Substituindo (2) em (1), obtemos:</p><p>Em que:</p><p>x + y = 23</p><p>ax + by = c</p><p>d c,</p><p>d = mdc(a, b)</p><p>(x0, y0)</p><p>ax0 + by0 = c.</p><p>mdc(a, b) = d, p q</p><p>a = dp b = dq.</p><p>ax0 + by0 = c, a = dp b = dq.</p><p>(dp)x0 + (dq)y0 = c</p><p>d(px0 + qy0</p><p>∈Z</p><p>) = c</p><p>px0 + qy0 d</p><p>c(d ∣ c).</p><p>d c(d ∣ c),</p><p>c = dk</p><p>k</p><p>mdc(a, b) = d, x0 y0,</p><p>d = ax0 + by0</p><p>c = (ax0 + by0)k</p><p>c = a (kx0) + b (ky0)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 5/101</p><p>(3)</p><p>(4)</p><p>Mas de (1) temos que podemos substituir em (3) e (4).</p><p>Logo, e uma solução inteira da equação</p><p>diofantina</p><p>Comentário</p><p>O teorema 1 mostra que, dada uma equação diofantina, podemos</p><p>analisar se ela apresenta solução inteira verificando se o</p><p>divide</p><p>Exemplo 1</p><p>Dada a equação diofantina verifique se ela tem</p><p>solução.</p><p>Solução</p><p>Na equação dada, temos e Confira!</p><p>Como 2 divide 2354, então a equação diofantina tem solução inteira.</p><p>Exemplo 2</p><p>Dada a equação diofantina verifique se ela tem</p><p>solução.</p><p>Solução</p><p>Na equação dada, temos e Veja!</p><p>x = kx0</p><p>y = ky0</p><p>k = c</p><p>d′ ,</p><p>x = kx0 ⇒ x = ( c</p><p>d</p><p>)x0</p><p>y = ky0 ⇒ y = ( c</p><p>d</p><p>)y0</p><p>x = ( c</p><p>d )x0 y = ( c</p><p>d )y0,</p><p>ax + by = c.</p><p>mdc(a, b) = d c.</p><p>2x + 16y = 2354,</p><p>a = 2, b = 16 c = 2354.</p><p>mdc(2, 16) = 2</p><p>5x + 15y = 37,</p><p>a = 5, b = 15 c = 37.</p><p>mdc(5, 15) = 5</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 6/101</p><p>Como 5 não divide 37, então a equação diofantina não tem solução</p><p>inteira.</p><p>Exemplo 3</p><p>Denise foi à feira e comprou 9 mangas e 6 abacaxis. Ela disse para a</p><p>mãe que gastou R$ 65. Diante disso, sua mãe perguntou quanto custou</p><p>cada manga e cada abacaxi. Dada a equação diofantina</p><p>verifique se ela tem solução.</p><p>Solução</p><p>Na equação dada, temos e Confira!</p><p>Como 3 não divide 65, então a equação diofantina não tem solução</p><p>inteira. Isso significa que Denise não falou a verdade para sua mãe, ou</p><p>seja, não gastou R$ 65.</p><p>Teorema 2: soluções da equação diofantina linear</p><p>Se divide em que e o par de números</p><p>inteiros é uma solução particular da equação diofantina linear</p><p>então todas as outras soluções inteiras dessa equação</p><p>são dadas pelas seguintes fórmulas:</p><p>Lembre-se que é um inteiro arbitrário.</p><p>Demonstração</p><p>Suponha que o par de inteiros é uma solução</p><p>mod 5)</p><p>y2 ≡ 1 ( mod 5)</p><p>y2 = 1.</p><p>y3 M3. M3y3 ≡ 1 ( mod 7).</p><p>15y3 ≡ 1 ( mod 7)</p><p>y3 ≡ 1 ( mod 7)</p><p>y3 = 1.</p><p>X ≡ c1M1y1 + c2M2y2 + c3M3y3 ( mod m1 ⋅ m2 ⋅ m3)</p><p>X ≡ 2 ⋅ 35 ⋅ 2 + 3 ⋅ 21 ⋅ 1 + 2 ⋅ 15 ⋅ 1( mod 105)</p><p>X ≡ 140 + 63 + 30( mod 105)</p><p>X ≡ 233( mod 105)</p><p>X ≡ 23( mod 105)</p><p>X = 105t + 23</p><p>X = 105t + 23</p><p>m1,m2, ⋯ ,mr</p><p>mdc (mi,mj) = 1 i ≠ j.</p><p>a1, a2, ⋯ , ar mdc (ak,mk) = 1</p><p>k = 1, 2, 3, ⋯ , r.</p><p>m = m1m2 ⋯mr.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 63/101</p><p>Demonstração</p><p>Pela hipótese, temos que condição que indica que</p><p>a congruência linear apresenta uma única solução</p><p>módulo tal que:</p><p>Portanto, a congruência linear é equivalente à</p><p>congruência:</p><p>Segue, então, que o sistema de congruências lineares é equivalente:</p><p>Pelo teorema do resto chinês, esse sistema apresenta uma única</p><p>solução módulo:</p><p>Exemplo 1</p><p>Determine a solução do sistema de congruências lineares.</p><p>Solução</p><p>Devemos verificar inicialmente se o sistema apresenta solução</p><p>Veja que os módulos 5, 7 e 11 são primos entre si dois a dois. Ou seja,</p><p>e</p><p>Além disso, e</p><p>Logo, o sistema dado possui solução única módulo</p><p>⎧⎪⎨⎪⎩a1x ≡ b1 ( mod m1)</p><p>a2x ≡ b2 ( mod m2)</p><p>⋮</p><p>arx ≡ br ( mod mr)</p><p>mdc (ak,mk) = 1,</p><p>akx ≡ 1 ( mod mk)</p><p>x = a∗</p><p>k mk,</p><p>aka</p><p>∗</p><p>k ≡ 1 ( mod mk)</p><p>akx ≡ bk ( mod mk)</p><p>x ≡ bka</p><p>∗</p><p>k ( mod mk)</p><p>⎧⎪⎨⎪⎩x ≡ b1a</p><p>∗</p><p>1 ( mod m1)</p><p>x ≡ b2a</p><p>∗</p><p>2 ( mod m2)</p><p>⋮</p><p>x ≡ bra</p><p>∗</p><p>r ( mod mr)</p><p>m = m1m2 ⋯mr</p><p>⎧⎪⎨⎪⎩2x ≡ 1( mod 5)</p><p>3x ≡ 2( mod 7)</p><p>4x ≡ 3( mod 11)</p><p>mdc(5, 7) = 1, mdc(5, 11) = 1 mdc(7, 11) = 1.</p><p>mdc(2, 5) = 1, mdc(3, 7) = 1 mdc(4, 11) = 1.</p><p>m = 5 ⋅ 7 ⋅ 11 ⇒ m = 385.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 64/101</p><p>De acordo com o teorema, podemos escrever as congruências lineares</p><p>do seguinte modo:</p><p>Agora, vamos encontrar uma solução para cada congruência linear.</p><p>Agora, temos um sistema equivalente ao sistema dado:</p><p>A solução desse sistema é dada por:</p><p>Em que:</p><p>e</p><p>classe inversa de módulo 5, então</p><p>Note que 77 deixa resto 2 na divisão por 5. Então, podemos trocar o 77</p><p>por 2.</p><p>2x ≡ 1 ( mod 5)</p><p>3x ≡ 1 ( mod 7)</p><p>4x ≡ 1 ( mod 11)</p><p>a∗</p><p>k</p><p>2x ≡ 1( mod 5) ⇒ a∗</p><p>1 = 3,  pois 2 ⋅ 3 = 6 ≡ 1( mod 5)</p><p>3x ≡ 1( mod 7) ⇒ a∗</p><p>2 = 5,  pois 2 ⋅ 5 = 15 ≡ 1( mod 7)</p><p>4x ≡ 1( mod 11) ⇒ a∗</p><p>3 = 3,  pois 4 ⋅ 3 = 12 ≡ 1( mod 11)</p><p>⇓</p><p>⎧⎪⎨⎪⎩x ≡ b1a</p><p>∗</p><p>1 ( mod m1)</p><p>x ≡ b2a</p><p>∗</p><p>2 ( mod m2)</p><p>⋮</p><p>x ≡ bra</p><p>∗</p><p>r ( mod mr)</p><p>⎧⎪⎨⎪⎩x ≡ 1 ⋅ (3)( mod 5) ⇒ x ≡ 3( mod 5)</p><p>x ≡ 2. (5)( mod 7) ⇒ x ≡ 10( mod 7)</p><p>x ≡ 3. (3)( mod 7) ⇒ x ≡ 9( mod 11)</p><p>X = b1M1x1 + b2M2x2 + b3M3x3 ≡ brMrxr ( mod mk)</p><p>b1 = 3, b2 = 10 b3 = 9.</p><p>M1 = m1⋅m2⋅m3</p><p>m1</p><p>⇒ M1 = 5⋅7⋅11</p><p>5 = 77.</p><p>M2 = m1⋅m2⋅m3</p><p>m2</p><p>⇒ M1 = 5⋅7⋅11</p><p>7 = 55.</p><p>M3 = m1⋅m2⋅m3</p><p>m3</p><p>⇒ M1 = 5⋅7⋅11</p><p>11 = 35.</p><p>x1 = M1 = 77</p><p>M1 ⋅ x1 ≡ 1( mod 5).</p><p>77 ⋅ x1 ≡ 1( mod 5).</p><p>2 ⋅ x1 ≡ 1( mod 5)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 65/101</p><p>Agora, vamos procurar um número que multiplicado por 2 deixa resto 1</p><p>na divisão por 5.</p><p>Veja que o número é pois</p><p>Como é a classe inversa de módulo 7, então</p><p>Note que 55 deixa resto 6 na divisão por 7. Então, podemos trocar o 55</p><p>por 6.</p><p>Agora, vamos procurar um número que multiplicado por 6 deixa resto 1</p><p>na divisão por 7.</p><p>Veja que o número é pois</p><p>Como é a classe inversa de módulo 11 , então</p><p>Note que 35 deixa resto 2 na divisão por 11. Então podemos trocar o 35</p><p>por 2.</p><p>Agora vamos procurar um número que multiplicado por 2 deixa resto 1</p><p>na divisão por 11.</p><p>Veja que o número é pois</p><p>Em</p><p>realizamos as substituições:</p><p>mas 878 deixa resto 108 na divisão por 385.</p><p>é a única solução do sistema de</p><p>congruência.</p><p>Com as seguintes observações:</p><p>693 deixa resto 308 na divisão por 385.</p><p>x1 = 3, 2 ⋅ 3 = 6 ≡ 1( mod 5).</p><p>x2 M2 = 55</p><p>M2 ⋅ x2 ≡ 1( mod 7).</p><p>55 ⋅ x2 ≡ 1( mod 7)</p><p>6 ⋅ x2 ≡ 1( mod 7)</p><p>x2 = 6, 6 ⋅ 6 = 36 ≡ 1( mod 7).</p><p>x3 M3 = 35</p><p>M3 ⋅ x3 ≡ 1( mod 11).</p><p>35 ⋅ x2 ≡ 1( mod 11)</p><p>2 ⋅ x2 ≡ 1( mod 11)</p><p>x3 = 6, 6 ⋅ 2 = 12 ≡ 1( mod 11).</p><p>X = b1M1x1 + b2M2x2 + b3M3x3 ≡ brMrxr ( mod mk),</p><p>X ≡ (3) ⋅ (77) ⋅ (3)</p><p>693</p><p>+ (10). (55) ⋅ (6)</p><p>3.300</p><p>+ (9) ⋅ (35) ⋅ (6)</p><p>1890</p><p>( mod 5  </p><p>X ≡ 308 + 220 + 350( mod 385).</p><p>X ≡ 878( mod 385),</p><p>X ≡ 108( mod 385)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 66/101</p><p>3.300 deixa resto 220 na divisão por 385.</p><p>1.890 deixa resto 350 na divisão por 385.</p><p>Exemplo 2</p><p>Determine a solução da congruência linear</p><p>Solução</p><p>Podemos escrever essa congruência linear na forma de um sistema de</p><p>congruências lineares que é equivalente à congruência. Note que</p><p>podemos escrever</p><p>Observe o sistema de congruências lineares!</p><p>Podemos escrever essa congruência linear na forma de um sistema de</p><p>congruências lineares que é equivalente à congruência. Note que</p><p>podemos escrever</p><p>Confira o sistema de congruências lineares!</p><p>Veja que os módulos 2, 3 e 7 são primos entre si dois a dois. Ou seja,</p><p>e Além disso,</p><p>e Logo, o sistema</p><p>dado possui solução única módulo</p><p>Também podemos escrever a congruência na forma de um sistema</p><p>equivalente a ela.</p><p>Resolvendo o sistema por substituição:</p><p>(1)</p><p>Substituindo (1) em</p><p>(2)</p><p>13x ≡ 17( mod 42).</p><p>42 = 2 ⋅ 3 ⋅ 7.</p><p>⎧⎪⎨⎪⎩13x ≡ 17( mod 2)</p><p>13x ≡ 17( mod 3)</p><p>13x ≡ 17( mod 7)</p><p>42 = 2 ⋅ 3 ⋅ 7.</p><p>⎧⎪⎨⎪⎩13x ≡ 17 ( mod 2)</p><p>13x ≡ 17 ( mod 3)</p><p>13x ≡ 17 ( mod 7)</p><p>mdc(2, 3) = 1, mdc(2, 7) = 1 mdc(3, 7) = 1.</p><p>mdc(13, 2) = 1, mdc(13, 3) = 1 mdc(13, 7) = 1.</p><p>m = 2 ⋅ 3 ⋅ 7 ⇒ m = 42.</p><p>⎧⎪⎨⎪⎩13x ≡ 17( mod 2)</p><p>13x ≡ 17( mod 3)</p><p>13x ≡ 17( mod 7)</p><p>⎧⎪⎨⎪⎩x ≡ 1( mod 2)</p><p>x ≡ 2( mod 3)</p><p>x ≡ 4( mod 7)</p><p>x ≡ 1( mod 2) ⇒ x = 2a + 1 a ∈ N</p><p>x ≡ 2( mod 3).</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 67/101</p><p>Em que</p><p>Substituindo (2) em (1), temos:</p><p>(3)</p><p>Substituindo (3) em obtemos:</p><p>Temos, então:</p><p>(4)</p><p>Substituindo (4) em (3), encontramos a solução da congruência linear:</p><p>Atividade discursiva</p><p>Resolva o sistema de congruência linear formado pelas equações</p><p>e</p><p>Digite sua resposta aqui</p><p>Chave de resposta</p><p>Dada a equação de congruência podemos</p><p>escrever:</p><p>Agora, vamos substituir (1) em</p><p>Usando as propriedades de congruências, temos:</p><p>2a + 1 ≡ 2( mod 3) ⇒ 2a ≡ 1( mod 3) ⇒ a ≡ 2( mod 3) ⇒ a = 3b + 2</p><p>b ∈ N.</p><p>x = 2a + 1 ⇒ x = 2(3b + 2) + 1 ⇒ x = 6b + 4 + 1 ⇒ x = 6b + 5</p><p>x ≡ 4( mod 7),</p><p>6b + 5 ≡ 4( mod 7) ⇒ 6b ≡ −1( mod 7) ⇒ 6b ≡ 6 ( mod 7)</p><p>b ≡ 1( mod 7) ⇒ b = 7c + 1, c ∈ N</p><p>x = 6(7c + 1) + 5 ⇒ x = 42c + 6 + 5 ⇒ x = 42c + 11 ⇒ x ≡ 11( mod 42)</p><p></p><p>x ≡ 1( mod 2) x ≡ 1 ( mod 3).</p><p>x ≡ 1( mod 2),</p><p>x = 2a + 1, a ∈ N(1)</p><p>x ≡ 1( mod 3).</p><p>2a + 1 ≡ 1 ( mod 3)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 68/101</p><p>Podemos escrever:</p><p>Substituindo (2) em (1), temos:</p><p>Portanto, é a solução do sistema.</p><p>Teoria na prática</p><p>Em uma caixa temos quantidades de lápis de cor. Agrupando esses</p><p>lápis de 3 em 3, verificamos que sobram 2 lápis. Quando agrupamos de</p><p>4 em 4 sobra apenas 1 lápis. Considerando essa análise, determine o</p><p>número de lápis que podemos ter na caixa.</p><p>Mão na massa</p><p>Questão 1</p><p>Resolva o sistema de congruência linear formado pelas equações</p><p>2a ≡ 0( mod 3)</p><p>a = 3b, b ∈ N(2)</p><p>x = 2(3b) + 1 ⇒ x = 6b + 1</p><p>x ≡ 1( mod 6)</p><p>_black</p><p>X</p><p>Mostrar solução</p><p></p><p>x ≡ 8( mod 26)e x ≡ 11( mod 33).</p><p>A x ≡ 9 ( mod 26)</p><p>B x ≡ 26 ( mod 33)</p><p>C x ≡ 364 ( mod 26)</p><p>D x ≡ 234 ( mod 858)</p><p>E x ≡ 242 ( mod 858)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 69/101</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'%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%3D47dc197c352f4f3d</p><p>1%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%0A%20%20%20%20%20</p><p>Questão 2</p><p>(ENQ 2020 - SBM) Determine um número inteiro entre 1200 e 1400</p><p>que deixa resto 2 e 6 quando dividido, respectivamente, por 11 e 13.</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 3</p><p>Marque a alternativa que indica a solução do sistema formado</p><p>pelas equações de congruências</p><p>A 1200</p><p>B 1220</p><p>C 1267</p><p>D 1350</p><p>E 1400</p><p>x ≡ 3( mod 5),x ≡ 4( mod 7).</p><p>A x ≡ 3( mod 5)</p><p>B x ≡ 4( mod 3)</p><p>C x ≡ 7( mod 8)</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 70/101</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>Três corredores de uma assessoria de corrida disputam uma prova</p><p>em uma pista circular. Antes da prova os três corredores resolvem</p><p>fazer um aquecimento. 0 corredor 1 faz um aquecimento inicial de 3</p><p>minutos, o corredor 2 faz o aquecimento de 5 minutos e o corredor</p><p>3 prefere aquecer durante 11 minutos. Considerando que o corredor</p><p>1 saiu após um minuto do início do aquecimento, o segundo após</p><p>dois minutos e o terceiro corredor após 7 minutos do início,</p><p>determine em que momento após a saída os três corredores</p><p>passaram juntos pela linha da saída.</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>Determine a solução geral do sistema de congruências lineares</p><p>e</p><p>D x ≡ 8( mod 35)</p><p>E x ≡ 9( mod 35)</p><p>A 12 min</p><p>B 43 min</p><p>C 165 min</p><p>D 172 min</p><p>E 185 min</p><p>x ≡ 2( mod 5) x ≡ 2( mod 6), x ≡ 1( mod 7)</p><p>x ≡ 0( mod 11).</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 71/101</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 6</p><p>Denise resolveu participar de uma ultramaratona. Nesse tipo de</p><p>prova o isotônico e a água são distribuídos ao longo do percurso. A</p><p>água foi distribuída a cada 3 km começando no quilômetro 2. O</p><p>isotônico foi distribuído a cada 5 km começando no quilômetro 3.</p><p>Considerando o inteiro igual a 5, determine em que quilômetro o</p><p>isotônico foi distribuído junto com a água.</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>A X = 1015t + 225</p><p>B X = 2225t + 1200</p><p>C X = 1225t + 1105</p><p>D X = 2330t + 1562</p><p>E X = 1330t + 125</p><p>t</p><p>A 42 km</p><p>B 55 km</p><p>C 75 km</p><p>D 83 km</p><p>E 92 km</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 72/101</p><p>Falta pouco para atingir seus objetivos.</p><p>Vamos praticar alguns conceitos?</p><p>Questão 1</p><p>Marque a alternativa que indica a solução do sistema formado</p><p>pelas equações de congruências</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>(Adaptado de: OBMEP) Uma escola levou um total de 2000 alunos</p><p>de suas 4 unidades para os jogos interescolares. Todos os alunos</p><p>que participaram receberiam no final do campeonato um certificado</p><p>de participação. Assim, ao final das atividades, a escola verificou</p><p>quantos alunos não participaram dos jogos. Para facilitar o</p><p>trabalho, ela alinhou os alunos de 7 em 7 e verificou que sobraram 5</p><p>alunos. Alinhou de 9 em 9 e sobraram 7 alunos. Por fim, alinhou os</p><p>alunos de 10 em 10 e verificou que sobrou 1 aluno. A escola</p><p>verificou, ainda, que havia mais de 1500 alunos aguardando pelos</p><p>certificados de participação. Verifique quantos alunos não</p><p>participaram dos jogos.</p><p>2x ≡ 1( mod 3),</p><p>3x ≡ 2( mod 5), 5x ≡ 3( mod 7).</p><p>A X = 3t + 14</p><p>B X = 5t + 23</p><p>C X = 105t + 35</p><p>D X = 105t + 37</p><p>E X = 105t + 44</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 73/101</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 - Divisores, funções e classes residuais</p><p>Ao �nal deste módulo, você será capaz de identi�car os resultados</p><p>referentes a divisores de número inteiro, funções aritméticas e</p><p>classes residuais.</p><p>Divisores de inteiro,</p><p>funções aritméticas e</p><p>restos</p><p>Assista ao vídeo e conheça os teoremas e exemplos de aplicação dos</p><p>divisores de número inteiro, as funções aritméticas e as classes</p><p>residuais.</p><p>A 481</p><p>B 259</p><p>C 1500</p><p>D 1741</p><p>E 1832</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 74/101</p><p>Divisores de um número</p><p>inteiro</p><p>Vamos apresentar alguns resultados importantes sobre os divisores de</p><p>um número inteiro.</p><p>Teorema 1: divisores de um número inteiro</p><p>Se é a decomposição canônica do inteiro positivo</p><p>então os divisores positivos de são precisamente os inteiros</p><p>da forma:</p><p>Em que</p><p>Demonstração</p><p>Considere e de divisores triviais, que são obtidos</p><p>quando:</p><p>E ainda:</p><p>Suponha que seja um divisor não trivial de em que:</p><p>Expressando e como produtos de (não necessariamente distintos)</p><p>primos:</p><p>(1)</p><p>Obtemos:</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr</p><p>n > 1, n d</p><p>d = p</p><p>h1</p><p>1 p</p><p>h2</p><p>2 ⋯ phr</p><p>r</p><p>0 ≤ hi ≤ ki(i = 1, 2, ⋯ , r).</p><p>d = 1 d = n n</p><p>h1 = h2 = ⋯ = hr = 0</p><p>h1 = k1, h2 = k2, ⋯hr = kr</p><p>d n,</p><p>n = dd1,  com d > 1 e d1 > 1</p><p>d d1</p><p>d = q1q2 ⋯ qs, d1 = t1t2 ⋯ tu</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 75/101</p><p>(2)</p><p>Temos (1) e (2), duas decomposições do inteiro positivo como</p><p>produto de primos, e como é única uma decomposição de de tal</p><p>natureza, então cada primo coincide com um de modo que,</p><p>substituindo os produtos de primos iguais por potências de expoente</p><p>inteiro, teremos:</p><p>Em que é possível algum Reciprocamente, todo inteiro é um</p><p>divisor de Veja!</p><p>Portanto, podemos escrever:</p><p>Em que para cada Logo, é um divisor de</p><p>Exemplo</p><p>Os divisores positivos do inteiro são os inteiros</p><p>da forma:</p><p>Em que</p><p>Isto é:</p><p>Assim, com obtemos o divisor do inteiro</p><p>1350. Veja!</p><p>Realmente:</p><p>Com e com achamos os</p><p>divisores triviais e do inteiro dado 1350.</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr = q1q2 ⋯ qst1t2 ⋯ tu</p><p>n</p><p>n</p><p>qi pj,</p><p>d = q1q2 ⋯ qs = p</p><p>h1</p><p>1 p</p><p>h2</p><p>2 ⋯ phr</p><p>r</p><p>hi = 0.</p><p>n.</p><p>d = p</p><p>h1</p><p>1 p</p><p>h2</p><p>2 ⋯ phr</p><p>r (0 ≤ hi ≤ ki)</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr = (ph1</p><p>1 p</p><p>h2</p><p>2 ⋯ phr</p><p>r )(p</p><p>k1−h1</p><p>1 p</p><p>k2−h2</p><p>2 ⋯ pkr−hr</p><p>r )</p><p>= d(pk1−h1</p><p>1 p</p><p>k2−h2</p><p>2 ⋯ pkr−hr</p><p>r )</p><p>ki − hi ≥ 0 i. d n(d ∣ n).</p><p>n = 1350 = 2 ⋅ 33 ⋅ 52</p><p>d</p><p>d = 2h1 ⋅ 3h2 ⋅ 5h3</p><p>0 ≤ h1 ≤ 1, 0 ≤ h2 ≤ 3, 0 ≤ h3 ≤ 2.</p><p>h1 = 0, 1, h2 = 0, 1, 2, 3, h3 = 0, 1, 2</p><p>h1 = 1,h2 = 2,h3 = 0,</p><p>d = 2 ⋅ 33 ⋅ 50 = 2 ⋅ 9 ⋅ 1 = 18</p><p>1350 = 18 ⋅ 75</p><p>h1 = h2 = h3 = 0 h1 = 1,h2 = 2,h3 = 2,</p><p>d1 = 1 d = 1350</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 76/101</p><p>Número de divisores</p><p>De�nição</p><p>Considerando um inteiro positivo, definimos o número de divisores</p><p>positivos de e indica-se por</p><p>Exemplo</p><p>Os divisores positivos de 12 são 1, 2, 3, 4, 6 e 12, de modo que</p><p>Observação: sendo um número primo, então pois os únicos</p><p>divisores positivos de são</p><p>Como os divisores positivos de são e temos</p><p>De modo geral, porque os divisores positivos de</p><p>são</p><p>Teorema 2: número de divisores de um inteiro</p><p>Se é a decomposição canônica do inteiro positivo</p><p>então:</p><p>Demonstração</p><p>De acordo com o teorema (Se é a decomposição</p><p>canônica do inteiro positivo então os divisores positivos de</p><p>são precisamente os inteiros da forma: em que</p><p>os divisores positivos de são</p><p>precisamente os inteiros da forma:</p><p>Em que</p><p>Temos maneiras de escolher o expoente maneiras</p><p>de escolher o expoente maneiras de escolher o</p><p>expoente e, portanto, o número total de maneiras de escolher os</p><p>expoentes é dado pelo produto:</p><p>Assim sendo, o número de divisores positivos do inteiro é</p><p>dado pela fórmula:</p><p>n</p><p>n d(n).</p><p>d(12) = 6.</p><p>p d(p) = 2,</p><p>p 1e p.</p><p>p2 1, p p2, d (p2) = 3.</p><p>d (pn) = n + 1, pn</p><p>1, p, p2, ⋯ pn.</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr</p><p>n > 1,</p><p>d(n) = (k1 + 1) (k2 + 1) ⋯ (kr + 1)</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr</p><p>n > 1, n</p><p>d d = p</p><p>h1</p><p>1 p</p><p>h2</p><p>2 ⋯ phr</p><p>r ,</p><p>0 ≤ hi ≤ ki(i = 1, 2, ⋯ , r)), n</p><p>d = p</p><p>h1</p><p>1 p</p><p>h2</p><p>2 ⋯ phr</p><p>r</p><p>0 ≤ hi ≤ ki(i = 1, 2, ⋯ , r).</p><p>k1 + 1 h1, k2 + 1</p><p>h2, ⋯ , kr + 1</p><p>hr</p><p>h1,h2, ⋯hr</p><p>(k1 + 1) (k2 + 1) ⋯ (kr + 1)</p><p>d(n) n > 1</p><p>d(n) = (k1 + 1) (k2 + 1) ⋯ (kr + 1)</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 77/101</p><p>Ou seja:</p><p>Note-se que:</p><p>Exemplo 1</p><p>O número de divisores positivos do inteiro é:</p><p>Esses 24 divisores positivos de 756 são os inteiros expressos na</p><p>forma:</p><p>Em que e</p><p>Podemos determinar os 24 divisores positivos de 756 do seguinte</p><p>modo:</p><p>Vamos entender melhor!</p><p>d(n) =</p><p>r</p><p>∏</p><p>i=1</p><p>(ki + 1)</p><p>d(n) = d(ph1</p><p>1 )d(p</p><p>h2</p><p>2 )⋯ d (phr</p><p>r )</p><p>n = 756 = 22 ⋅ 33 ⋅ 7</p><p>d(756) = (2 + 1)(3 + 1)(1 + 1) = 3 ⋅ 4 ⋅ 2 = 24</p><p>d</p><p>d = 2h13h27h3</p><p>h1 = 0, 1, 2,h2 = 0, 1, 2, 3 h3 = 0, 1.</p><p> Primeira linha - lado direito</p><p>Colocamos as potências do primeiro fator primo 2:</p><p>1, 2 e 4.</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 78/101</p><p>Exemplo 2</p><p>Determine o menor inteiro positivo que tem 10 divisores positivos.</p><p>Solução</p><p>Podemos decompor logo, temos o seguinte:</p><p>Portanto, os expoentes e dos fatores primos de são 9 e 0 , ou 4</p><p>e 1. E como é menor que o menor inteiro positivo com 10</p><p>divisores positivos é</p><p>Soma de divisores</p><p> Segunda, terceira e quarta</p><p>linhas - lado esquerdo</p><p>Colocamos as diversas potências do segundo fator</p><p>primo 3, a partir da primeira potência, no caso 3, 9 e</p><p>27.</p><p> Segunda, terceira e quarta</p><p>linhas - lado direito</p><p>Temos os produtos dessa potência por todos os</p><p>inteiros da primeira linha.</p><p> Na sequência - lado esquerdo</p><p>Temos as potências do terceiro fator primo 7, a</p><p>partir da primeira (no caso 7).</p><p> Na sequência - lado direito</p><p>Colocamos os produtos dessas potências por</p><p>todos os inteiros que do lado direito figuram nas</p><p>linhas anteriores. Se houvesse mais fatores primos,</p><p>procedia-se com eles como para o caso do terceiro</p><p>fator.</p><p>n</p><p>10 = 10 ⋅ 1 = 5 ⋅ 2,</p><p>d(n) = (k1 + 1) (k2 + 2) = 10 ⋅ 1 ou d(n) = (k1 + 1) (k2 + 2) = 5 ⋅ 2</p><p>k1 k2 n</p><p>24 ⋅ 3 29,</p><p>24 ⋅ 3 = 48.</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 79/101</p><p>Indicamos por a soma dos divisores positivos de (inclusive 1 e</p><p>). Por exemplo, os divisores positivos de 12 são e 12, de</p><p>modo que:</p><p>Se é um primo, então porque os únicos divisores</p><p>positivos de são 1 e</p><p>E como os divisores positivos de são e temos:</p><p>De modo geral, os divisores positivos de são:</p><p>E, portanto:</p><p>Em particular:</p><p>Logo, a soma dos divisores positivos dos inteiros de 1 até 10 é dada por:</p><p>Teorema 3: soma dos divisores de um inteiro</p><p>Se é a decomposição canônica do inteiro positivo</p><p>então:</p><p>Demonstração</p><p>Consideremos o produto:</p><p>s(n) n n</p><p>1, 2, 3, 4, 6</p><p>s(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28</p><p>p s(p) = 1 + p,</p><p>p p.</p><p>p2 1, p p2,</p><p>s (p2) = 1 + p + p2 =</p><p>p3 − 1</p><p>p − 1</p><p>pn</p><p>1, p, p2, ⋯ , pn</p><p>s (pn) = 1 + p + p2 + ⋯ + pn =</p><p>pn+1 − 1</p><p>p − 1</p><p>s (2n) = 2n+1 − 1  e  s (3n) =</p><p>1</p><p>2</p><p>(3n+1 − 1)</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ pkrr</p><p>n > 1,</p><p>s(n) =</p><p>p</p><p>k1+1</p><p>1 − 1</p><p>p1 − 1</p><p>⋅</p><p>p</p><p>k2+1</p><p>2 − 1</p><p>p2 − 1</p><p>⋅ ⋯ ⋅</p><p>pkr+1</p><p>r − 1</p><p>pr − 1</p><p>(1 + p1 + p2</p><p>1 + ⋯ p</p><p>k1</p><p>1 )(1 + p2 + p2</p><p>2 + ⋯ p</p><p>k2</p><p>2 )⋯ (1 + pr + p2</p><p>r + ⋯ pkrr )</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 80/101</p><p>Pelo teorema 2, temos que cada divisor positivo é um termo desse</p><p>produto e vice-versa, de modo que:</p><p>Aplicando a cada parêntese do segundo membro dessa igualdade a</p><p>fórmula que dá a soma dos termos de uma progressão geométrica</p><p>finita, temos:</p><p>Ou seja:</p><p>Note-se que:</p><p>Exemplo</p><p>Determine a soma dos divisores positivos do inteiro</p><p>Produto de divisores</p><p>Teorema 4: Produto de divisores de um inteiro</p><p>O produto dos divisores positivos de um inteiro positivo é igual a</p><p>Demonstração</p><p>Sejam todos os divisores positivos de de modo que</p><p>existam os inteiros tais que:</p><p>Multiplicando ordenadamente todas essas igualdades, obtemos:</p><p>n</p><p>s(n) = (1 + p1 + p2</p><p>1 + ⋯ p</p><p>k1</p><p>1 )(1 + p2 + p2</p><p>2 + ⋯ p</p><p>k2</p><p>2 )⋯ (1 + pr + p2</p><p>r + ⋯ pkrr )</p><p>s(n) =</p><p>p</p><p>k1+1</p><p>1 − 1</p><p>p1 − 1</p><p>⋅</p><p>p</p><p>k2+1</p><p>2 − 1</p><p>p2 − 1</p><p>⋯ ⋯</p><p>pkr+1</p><p>r − 1</p><p>pr − 1</p><p>s(n) =</p><p>r</p><p>∏</p><p>i=1</p><p>p</p><p>ki+1</p><p>i − 1</p><p>pi − 1</p><p>s(n) = s(ph1</p><p>1 )s(p</p><p>h2</p><p>2 )⋯ s (phr</p><p>r )</p><p>n = 180 = 22 ⋅ 32 ⋅ 5.</p><p>Solução </p><p>n > 1</p><p>n</p><p>d(n)</p><p>2 .</p><p>d1, d2, ⋯ , dk n,</p><p>q1, q2, ⋯ , qk,</p><p>n = d1q1, n = d2q2, ⋯ , n = dkqk</p><p>k</p><p>nk = (d1d2 ⋯ dk) (q1q2 ⋯ qk)</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 81/101</p><p>Como porque cada um dos inteiros</p><p>também é divisor de temos:</p><p>Em que</p><p>Ou seja:</p><p>Exemplo</p><p>O produto dos divisores positivos do inteiro é:</p><p>Realmente, os divisores positivos de 16 são 1, 2, 4, 8, 16 e o produto</p><p>desses 5 divisores é igual a 1024.</p><p>Funções aritméticas</p><p>Algumas funções, dentro da teoria dos números, assumem um papel</p><p>importante na resolução de problemas e no desenvolvimento de outras</p><p>teorias, devido às propriedades que elas possuem. Agora vamos</p><p>conhecer algumas funções aritméticas multiplicativas!</p><p>De�nição</p><p>Uma função aritmética é toda função definida no conjunto dos</p><p>números naturais e com valores no conjunto dos números reais. Isto é:</p><p>Dada a definição, apresentamos as funções. Confira!</p><p>Indica o número de divisores positivos de</p><p>(d1d2 ⋯ dk) = (q1q2 ⋯ qk),</p><p>q1, q2, ⋯ q,k n,</p><p>nd(n) = (d1d2 ⋯ dk)2</p><p>d1d2 ⋯ dk = n</p><p>d(n)</p><p>2</p><p>∏</p><p>d∣n</p><p>d = n</p><p>d(n)</p><p>2</p><p>n = 16</p><p>∏</p><p>d∣16</p><p>d = 16</p><p>d(16)</p><p>2 = 16</p><p>5</p><p>2 = (42)</p><p>5</p><p>2 = 45 = 1024</p><p>f</p><p>f : N → R</p><p>d(n)</p><p>n.</p><p>s(n)</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 82/101</p><p>Indica a soma dos divisores positivos de</p><p>Essas duas funções definidas para todo número inteiro positivo são</p><p>funções aritméticas.</p><p>A função é uma função aritmética. Ela indica o número de fatores</p><p>primos do número natural Consideramos também a multiplicidade.</p><p>Exemplo</p><p>Determine e</p><p>Função aritmética multiplicativa</p><p>De�nição</p><p>Uma função aritmética é multiplicativa se para todo par de números</p><p>inteiros e tais que temos:</p><p>São funções aritméticas multiplicativas:</p><p>Indica o número de divisores positivos de</p><p>Indica a soma dos divisores positivos de</p><p>Exemplo</p><p>Dado verifique se a função é uma função aritmética</p><p>multiplicativa.</p><p>Observação: a função aritmética é considerada completamente</p><p>multiplicativa sem a restrição do Por exemplo, se</p><p>Agora</p><p>veja que a função aritmética não é completa, pois:</p><p>O mesmo ocorre com as funções e</p><p>n.</p><p>n</p><p>Ω(n)</p><p>n.</p><p>Ω(10) Ω(54).</p><p>Ω(10) = Ω(2 ⋅ 5) = 2</p><p>Ω(54)</p><p>= Ω (2 ⋅ 33) = Ω(2 ⋅ 3 ⋅ 3 ⋅ 3) = 4</p><p>f</p><p>m n, mdc(m,n) = 1,</p><p>f(mn) = f(m) ⋅ f(n)</p><p>d(n)</p><p>n.</p><p>s(n)</p><p>n.</p><p>n = 144, d(n)</p><p>Solução </p><p>mdc.</p><p>f(p) = p3 ⇒ f(mn) = (mn)3 = m3 ⋅ n3 = f(m). f(n).</p><p>d(n)</p><p>d(20) = d(2 ⋅ 10) = 6 ≠ 2 ⋅ 4 = d(2) ⋅ d(10)</p><p>s(n) μ(n).</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 83/101</p><p>Teorema 1: existência da função aritmética</p><p>multiplicativa</p><p>Se é uma função aritmética multiplicativa e se é uma função</p><p>aritmética definida por então a função</p><p>também é uma função aritmética multiplicativa.</p><p>Demonstração</p><p>Suponhamos e inteiros positivos tais que o</p><p>Considerando que o conjunto dos divisores positivos de é formado</p><p>por todos os produtos em que e o temos:</p><p>Pela definição da função aritmética multiplicativa, temos:</p><p>Logo:</p><p>Assim, provamos que função também é uma função aritmética</p><p>multiplicativa.</p><p>Exemplo</p><p>De acordo com a demonstração do teorema 1, temos:</p><p>Veja o seguinte:</p><p>Função de Mobius</p><p>f g</p><p>g(n) = ∑d∣n f(d), g(n)</p><p>m n mdc(m,n) = 1.</p><p>mn</p><p>rs, r|m, s|n mdc(r, s) = 1,</p><p>g(mn) = ∑</p><p>d∣mn</p><p>f(d) = ∑</p><p>r|m,s|n</p><p>f(rs)</p><p>f(rs) = f(r) ⋅ f(s).</p><p>g(mn) = ∑</p><p>r|m,s|n</p><p>f(r) ⋅ f(s) = ∑</p><p>r∣m</p><p>f(r) ∑</p><p>s∣m</p><p>f(s) = g(m)g(n)</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>g(n)</p><p>24 = 3 ⋅ 8 e o mdc(3, 8) = 1</p><p>g(3 ⋅ 8) = ∑</p><p>d∣24</p><p>f(d) = f(1) + f(2) + f(3) + f(4) + f(6) + f(8) + f(12) + f(24),  pois</p><p>g(3 ⋅ 8) = f(1 ⋅ 1) + f(1 ⋅ 2) + f(1 ⋅ 3) + f(1 ⋅ 4) + f(2 ⋅ 3) + f(1 ⋅ 8) + f(3 ⋅ 4) + f(3 ⋅ 8) =</p><p>= f(1)f(1) + f(1)f(2) + f(1)f(3) + f(1)f(4) + f(2)f(3)+</p><p>+ f(1)f(8) + f(3 ⋅ 4) + f(3)f(8)</p><p>f(3 ⋅ 8) = [f(1) + f(3)][f(1) + f(2) + f(4) + f(8)]</p><p>f(3 ⋅ 8) = ∑</p><p>d∣3</p><p>f(d) ∑</p><p>d∣8</p><p>f(d) = g(3) ⋅ g(8)</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 84/101</p><p>De�nição</p><p>A função de Mobius é a função aritmética chamada de (letra grega:</p><p>mi) definida por:</p><p>Em que indica a quantidade de primos. Além disso, se é primo,</p><p>temos:</p><p>Por exemplo: sendo temos</p><p>Exemplo 1</p><p>Sendo determine :</p><p>Exemplo 2</p><p>Sendo determine :</p><p>Teorema 2: Função de Mobius como função</p><p>aritmética multiplicativa</p><p>A função de Mobius é uma função aritmética multiplicativa.</p><p>Demonstração</p><p>Dados e inteiros positivos tais que</p><p>Queremos mostrar que</p><p>Se temos:</p><p>Se temos:</p><p>μ</p><p>μ(n) =</p><p>⎧⎪⎨⎪⎩1  se n = 1</p><p>0  se p2 ∣ n,  sendo p primo</p><p>(−1)r  se n = p1p2 ⋯ pr com pi primos distintos</p><p>r p</p><p>μ(p) = −1 e μ (pk) − 0 com k ≥ 2</p><p>n = 7, μ(7) = −1.</p><p>n = 6, μ(6)</p><p>μ(6) = μ(2 ⋅ 3)</p><p>r=2</p><p>= (−1)2 = 1</p><p>n = 12, μ(12)</p><p>μ(12) = μ (22 ⋅ 3) = 0</p><p>μ</p><p>m n omdc(m,n) = 1.</p><p>μ(m ⋅ n) = μ(m)μ(n).</p><p>m = 1,</p><p>μ(1 ⋅ n) = μ(1)μ(n) = 1 ⋅ μ(n) = μ(1) ⋅ μ(n) = μ(m)μ(n)</p><p>n = 1,</p><p>μ(m ⋅ 1) = μ(m)μ(1) = μ(m) ⋅ 1 = μ(m) ⋅ μ(1) = μ(m)μ(n)</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 85/101</p><p>Suponhamos e Se ou sendo um</p><p>número primo, então e nesse caso</p><p>Supondo que e não são divisíveis pelo quadrado do número primo,</p><p>temos:</p><p>(1)</p><p>(2)</p><p>Com primos e todos distintos.</p><p>De (1) e (2), obtemos:</p><p>Assim, provamos que a função de Mobius é uma função aritmética</p><p>multiplicativa.</p><p>Teorema 3: Função</p><p>A função de Mobius é uma função aritmética multiplicativa. Observe!</p><p>Em que é uma função aritmética.</p><p>Demonstração</p><p>Seja uma função aritmética.</p><p>Para temos que é verdadeira, pois</p><p>Suponhamos Seja em que é um número primo e</p><p>um número inteiro, então podemos dizer que os divisores</p><p>positivos de são os inteiros e assim, temos:</p><p>m > 1 n > 1. p2 ∣ m p2 ∣ n, p</p><p>p2 ∣ mn,</p><p>μ(mn) = 0 = μ(m)μ(n).</p><p>m n</p><p>m = p1p2 … pk</p><p>n = q1q2 … qr</p><p>pi pj</p><p>μ(mn) = μ (p1p2 … pkq1q2 … qr) = (−1)k+r = (−1)k(−1)r = μ(m)μ(n)</p><p>v(n)</p><p>μ</p><p>v(n) = ∑</p><p>d∣n</p><p>μ(d) = {1  se n = 1</p><p>0  se n > 1</p><p>v(n)</p><p>g(n) = ∑d∣n μ(d)</p><p>n = 1 P(1)</p><p>g(1) = ∑d∣1 μ(d) = μ(1) = 1.</p><p>n > 1. n = pk, p</p><p>k ≥ 1</p><p>n k + 1 1, p, p2, ⋯ , pk,</p><p>g (pk) = ∑</p><p>d∣pk</p><p>μ(d) = μ(1) + μ(p) + μ (p2) + ⋯ + μ (pk)</p><p>g (pk) = ∑</p><p>d∣pk</p><p>μ(d) = μ(1) + μ(p) = μ(1) + μ(p) = 1 + (−1) = 0</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 86/101</p><p>Seja a decomposição canônica de Como é uma</p><p>função multiplicativa, segue então pelo teorema 2 que a função</p><p>também é uma função multiplicativa, pois:</p><p>Exemplo</p><p>Para temos:</p><p>Agora vamos ver o teorema referente à fórmula de inversão de Mobius.</p><p>Através desse resultado podemos relacionar duas funções aritméticas</p><p>em que uma das funções pode não ser multiplicativa, ou seja, pode ser</p><p>uma função qualquer. A ideia central da fórmula é recuperar a função</p><p>arbitrária a partir da outra função.</p><p>Teorema 4: Fórmula de inversão de Mobius</p><p>Sejam duas funções e em que é uma função aritmética qualquer</p><p>e é uma função aritmética definida por:</p><p>Então, para todo número inteiro positivo :</p><p>Demonstração</p><p>Vamos considerar Podemos escrevê-la como:</p><p>Em que:</p><p>n = p</p><p>k1</p><p>1 p</p><p>k2</p><p>2 ⋯ p</p><p>ki</p><p>i n. μ</p><p>v(n)</p><p>v(pk1</p><p>1 p</p><p>k2</p><p>2 ⋯ p</p><p>ki</p><p>i ) = v(pk1</p><p>1 )v(p</p><p>k2</p><p>2 )⋯ v(pkii ) = 0</p><p>n = 12,</p><p>v(12) = ∑</p><p>d∣15</p><p>μ(d) = μ(1) + μ(2) + μ(3) + μ(4) + μ(6) + μ(12) =</p><p>= 1 + (−1) + (−1) + 0 + 1 + 0 = 1 − 1 − 1 + 0 + 1 + 0 = 0</p><p>f g, f</p><p>g</p><p>g(n) = ∑</p><p>d∣n</p><p>f(d)</p><p>n</p><p>f(n) = ∑</p><p>d∣n</p><p>μ(d)g( n</p><p>d</p><p>)</p><p>∑d∣n μ(d)g ( n</p><p>d ).</p><p>∑</p><p>d∣n</p><p>μ(d)g( n</p><p>d</p><p>) = ∑</p><p>d∣n</p><p>μ(d)∑</p><p>d1∣ n</p><p>d</p><p>f (d1)</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 87/101</p><p>Veja que pelo teorema 3, temos que para e</p><p>para</p><p>Assim:</p><p>Portanto:</p><p>Exemplo</p><p>Para vamos verificar na função</p><p>Temos:</p><p>∑</p><p>d∣n</p><p>μ(d)∑</p><p>d1∣ nd</p><p>f (d1) = ∑</p><p>d∣n</p><p>∑</p><p>d1∣ nd</p><p>μ(d)f (d1) = ∑</p><p>d1∣n</p><p>∑</p><p>d1∣ nd</p><p>μ(d)f (d1) =</p><p>= ∑</p><p>d1∣n</p><p>∑</p><p>d∣ n</p><p>d1</p><p>μ(d)f (d1) = ∑</p><p>d1∣n</p><p>f (d1)∑</p><p>d∣ n</p><p>d1</p><p>μ(d)</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>⎛⎜⎝ ⎞⎟⎠∑d∣n/d1</p><p>μ(d) = 1 n</p><p>d1</p><p>= 1</p><p>∑d∣n/d1</p><p>μ(d) = 0 n</p><p>d1</p><p>> 1.</p><p>∑</p><p>d1∣n</p><p>f (d1)∑</p><p>d∣ n</p><p>d1</p><p>μ(d) = f(n)∑</p><p>d∣ n</p><p>d1</p><p>μ(d) = f(n)μ(1) = f(n)</p><p>f(n) = ∑</p><p>d∣n</p><p>μ(d)g( n</p><p>d</p><p>) = ∑</p><p>d∣n</p><p>μ( n</p><p>d</p><p>)g(d)</p><p>n = 8, f(8) f(n) = ∑d∣n μ(d)g ( n</p><p>d</p><p>).</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 88/101</p><p>Classes residuais (ou</p><p>restos)</p><p>De�nição</p><p>Seja um número inteiro, definimos o conjunto de todos os números</p><p>inteiros que são congruentes ao número módulo como classe</p><p>residual também conhecidas por inteiros módulo Esse conjunto</p><p>é representado por:</p><p>Observação: a notação mais utilizada para representar uma classe</p><p>residual é</p><p>Essa classe residual (ou classe de restos), também é chamada de</p><p>classe de equivalência de módulo Ou seja, na classe do elemento</p><p>temos os elementos que são congruentes a módulo Lembrando</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = ∑</p><p>d∣8</p><p>μ(d)∑</p><p>d1|8</p><p>d</p><p>f (d1)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = μ(d)∑</p><p>d1∣ nd</p><p>f (d1)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = μ(1)∑</p><p>d1∣8</p><p>f (d1) + μ(2)∑</p><p>d1∣4</p><p>f (d1) + μ(4)∑</p><p>d1∣2</p><p>f (d1) + μ(8)∑</p><p>d1∣1</p><p>f (d1)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = (1)∑</p><p>d1∣8</p><p>f (d1) + (−1)∑</p><p>d1∣4</p><p>f (d1) + (0)∑</p><p>d1∣2</p><p>f (d1) + (0)∑</p><p>d1∣1</p><p>f (d1)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = ∑</p><p>d1∣8</p><p>f (d1) −∑</p><p>d1∣4</p><p>f (d1)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = ∑</p><p>d1∣8</p><p>f (d1) − ∑</p><p>d1∣4</p><p>f (d1)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = (f(1) + f(2) + f(4) + f(8)) − (f(1) + f(2) + f(4))</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = f(1) + f(2) + f(4) + f(8) − (1) − f(2) − f(4)</p><p>∑</p><p>d∣8</p><p>μ(d)g( 8</p><p>d</p><p>) = f(8)</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>⎛</p><p>⎝</p><p>⎞</p><p>⎠</p><p>a</p><p>a m</p><p>m, m.</p><p>ā = am = {x ∈ Z;x ≡ a( mod m)}</p><p>ā = am = {x ∈ Z;m ∣ (x − a)} = {x ∣ x = a + km, k ∈ Z}</p><p>ā.</p><p>a m.</p><p>a, m.</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 89/101</p><p>que ser congruente significa deixar o mesmo resto na divisão de por</p><p>Exemplos</p><p>Exemplo 1</p><p>Se o módulo temos Ou seja, a</p><p>classe residual módulo 1 de um inteiro qualquer é o próprio conjunto</p><p>dos números inteiros</p><p>Exemplo 2</p><p>Determine o conjunto da classe residual módulo 4 do inteiro 3.</p><p>Solução</p><p>Temos:</p><p>Vamos atribuir alguns valores positivos e negativos para</p><p>Para</p><p>temos</p><p>Para temos</p><p>Para temos</p><p>Para temos</p><p>Para temos</p><p>Para temos</p><p>Teorema: propriedades das classes residuais</p><p>Dadas as classes residuais e módulo de dois inteiros quaisquer</p><p>e são válidas algumas propriedades. Confira!</p><p>a</p><p>m.</p><p>m = 1, ā = {x ∈ Z; 1 ∣ (x − a)} = Z.</p><p>Z.</p><p>–</p><p>3 = a4 = {x ∈ Z;x ≡ 3( mod 4)}</p><p>–</p><p>3 = a4 = {x ∣ x = 3 + 4k, k ∈ Z}</p><p>k.</p><p>k = 0, x = 3 + 4k ⇒ x = 3 + 4.0 = 3.</p><p>k = 1, x = 3 + 4k ⇒ x = 3 + 4 ⋅ 1 = 7.</p><p>k = 2, x = 3 + 4k ⇒ x = 3 + 4 ⋅ 2 = 11.</p><p>k = 3, x = 3 + 4k ⇒ x = 3 + 4 ⋅ 3 = 15.</p><p>k = −1, x = 3 + 4k ⇒ x = 3 + 4 ⋅ (−1) = −1.</p><p>k = −2, x = 3 + 4k ⇒ x = 3 + 4 ⋅ (−2) = −5.</p><p>–</p><p>3 = a4 = {⋯ , −5, −1, 3, 7, 11, 15, ⋯}</p><p>ā b̄ m a</p><p>b,</p><p> Propriedade I</p><p>As classes e são iguais se, e somente seā b</p><p>a ≡ b( mod m).</p><p> Propriedade II</p><p>S l ã ã di j t )¯ b̄ (¯ ∩ b̄ ≠ ∅</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 90/101</p><p>Conjunto das classes residuais</p><p>Denotamos por o conjunto das classes residuais módulo Isto é,</p><p>Além disso, há classes residuais distintas possíveis:</p><p>Logo:</p><p>Isso significa, por exemplo, que o conjunto é formado por todas as</p><p>classes que deixam o mesmo resto na divisão de por 4.</p><p>Ou seja:</p><p>A classe</p><p>A classe</p><p>A classe</p><p>A classe</p><p>Agora observe, por exemplo, as seguintes classes:</p><p>A classe</p><p>A classe</p><p>Se as classes e não são disjuntas ),</p><p>então</p><p>a b (a ∩ b ≠ ∅</p><p>ā = b̄.</p><p> Propriedade III</p><p>Se as classes e não são distintas</p><p>então são disjuntas</p><p>ā b̄ (ā ≠ b̄),</p><p>ā ∩ b̄ = ∅.</p><p>Zm m.</p><p>Zm = {ā; a ∈ Z}</p><p>m</p><p>–</p><p>0,</p><p>–</p><p>1,</p><p>–</p><p>2, ⋯ ,m − 1.</p><p>–</p><p>Zm = {</p><p>–</p><p>0,</p><p>–</p><p>1,</p><p>–</p><p>2, ⋯ ,m − 1}</p><p>–</p><p>Z4</p><p>a</p><p>Z4 = {</p><p>–</p><p>0,</p><p>–</p><p>1,</p><p>–</p><p>2,</p><p>–</p><p>3}</p><p>–</p><p>0 = {x ≡ 0( mod 4)} = {x ∣ x = 0 + 4k, k ∈ Z} = {… , −8,</p><p>–</p><p>1 = {x ≡ 1( mod 4)} = {x ∣ x = 1 + 4k, k ∈ Z} = {… , −7,</p><p>–</p><p>2 = {x ≡ 2( mod 4)} = {x ∣ x = 2 + 4k, k ∈ Z} = {… , −6,</p><p>–</p><p>3 = {x ≡ 3( mod 4)} = {x ∣ x = 3 + 4k, k ∈ Z} = {… , −5,</p><p>−4 = {x ≡ −4( mod 4)} = {x ∣ x = −4 + 4k, k ∈ Z} = {…</p><p>–</p><p>−2 = {x ≡ −2( mod 4)} = {x ∣ x = −2 + 4k, k ∈ Z} = {…</p><p>–</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 91/101</p><p>A classe</p><p>A classe</p><p>Note, por exemplo, que:</p><p>Observação: para determinarmos a classe residual módulo de um</p><p>número inteiro qualquer, basta determinar o resto da divisão de</p><p>por</p><p>Exemplo</p><p>Determine a classe residual módulo 8 de 75.</p><p>Solução</p><p>Dividindo 75 por 8 encontramos Assim, podemos</p><p>escrever que:</p><p>Operações no conjunto</p><p>No conjunto definimos duas operações:</p><p>Adição</p><p>temos que</p><p>Multiplicação</p><p>temos que</p><p>Demonstração (adição)</p><p>Sejam em que e Então:</p><p>Demonstração (multiplicação)</p><p>Sejam em que e Então:</p><p>−3 = {x ≡ −3( mod 4)} = {x ∣ x = −3 + 4k, k ∈ Z} = {…</p><p>–</p><p>−1 = {x ≡ −1( mod 4)} = {x ∣ x = −1 + 4k, k ∈ Z} = {…</p><p>–</p><p>–</p><p>0 = −4 =</p><p>–</p><p>4;</p><p>–</p><p>1 = −3 =</p><p>–</p><p>5;</p><p>–</p><p>2 = −2 =</p><p>–</p><p>6;</p><p>–</p><p>3 = −1 =</p><p>–</p><p>7</p><p>––––</p><p>m</p><p>a r a</p><p>m.</p><p>75 = 8 ⋅ 9 + 3.</p><p>75 ≡ 3( mod 8) = {x ∣ x = 3 + 8k, k ∈ Z} = {⋯ , −13, −5, 3, 11, 19, ⋯}</p><p>Zm</p><p>Zm,</p><p>∀ā, b̄ ∈ Zm ā + b̄ = a + b</p><p>–</p><p>∀ā, b̄ ∈ Zm ā ⋅ b̄ = a ⋅ b</p><p>–</p><p>∀ā, b̄ ∈ Zm, ā = a′–̄b = b̄′.</p><p>a ≡ a′( mod m)</p><p>b ≡ b′( mod m)</p><p>∀ā, b̄ ∈ Zm, ā = a′–̄b = b̄′.</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 92/101</p><p>Multiplicando as congruência membro a membro, obtemos:</p><p>Exemplos</p><p>Considerando o conjunto determine o seguinte.</p><p>Classe inversa de</p><p>Um elemento é dito invertível se tal que</p><p>Nesse caso, é dito inverso de Além disso, podemos dizer que</p><p>é divisível por Usando a equação diofantina</p><p>temos que Logo, tem</p><p>inverso somente se o</p><p>Exemplo</p><p>Verifique o inverso de em</p><p>Solução</p><p>Veja que o então possui inverso em</p><p>Agora vamos escrever 1 como combinação linear de 4 e 9.</p><p>O inverso de em é Veja que</p><p>Resolução de equações de congruências</p><p>através das classes residuais</p><p>Por meio das classes residuais podemos resolver equações de</p><p>congruências lineares de forma mais simples no conjunto Ou seja,</p><p>vamos transformar uma equação de congruência em uma equação de</p><p>classes residuais.</p><p>Na congruência linear podemos isolar</p><p>se o 1.</p><p>a ≡ a′( mod m)</p><p>b ≡ b′( mod m)</p><p>a ⋅ b ≡ a′ ⋅ b′( mod m)</p><p>ā ⋅ b̄ = a′ ⋅ b′–</p><p>Z6 = {</p><p>–</p><p>0,</p><p>–</p><p>1,</p><p>–</p><p>2,</p><p>–</p><p>3,</p><p>–</p><p>4,</p><p>–</p><p>5}</p><p>Exemplo 1 </p><p>Exemplo 2 </p><p>Zm</p><p>ā ∈ Zm ∃ȳ ∈ Zm ā ⋅ ȳ = 1.</p><p>ȳ ā.</p><p>ā ⋅ ȳ − 1 m.</p><p>ay + km = 1, ∀k ∈ Z, omdc(a,m) = 1. ā</p><p>mdc(a,m) = 1.</p><p>–</p><p>4 Z9.</p><p>mdc(4, 9) = 1,</p><p>–</p><p>4 Z9.</p><p>1 = 4(−2) + 9 ⋅ 1</p><p>–</p><p>4 Z9 −2 =</p><p>–</p><p>7.</p><p>––</p><p>4 ⋅</p><p>–</p><p>7 = 4 ⋅ 7 = 28 = 1.</p><p>––</p><p>Zm.</p><p>ax ≡ b( mod m), a, b ∈ Z, x,</p><p>mdc(a,m) =</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 93/101</p><p>Nesse caso, dizemos que existe um número inteiro tal que</p><p>Veja que é o inverso de em Podemos</p><p>multiplicar os dois lados da congruência por</p><p>Portanto, , é a solução da equação de congruência.</p><p>Exemplo 1</p><p>Resolva a equação de congruência</p><p>Solução</p><p>Como o então a equação tem apenas uma solução.</p><p>Assim, resolver essa equação é equivalente a resolver a equação</p><p>que tem solução em</p><p>Como temos que é o inverso de em</p><p>Logo:</p><p>Portanto, a solução da equação de congruência é dada por</p><p>ou</p><p>Exemplo 2</p><p>Resolva a equação de congruência</p><p>Solução</p><p>Como o então a equação tem apenas uma solução.</p><p>Note que pois Assim, temos a</p><p>congruência Podemos multiplicar os dois membros</p><p>da congruência por 3.</p><p>Portanto, a solução da equação de congruência é dada por</p><p>ou</p><p>y,</p><p>ya ≡ 1( mod m). ȳ ā Zm.</p><p>y.</p><p>ax ≡ b</p><p>y ⋅ ax ≡ y ⋅ b ( mod m)</p><p>x ≡ y ⋅ b ( mod m)</p><p>x = yb + mt</p><p>3x ≡ 1( mod 17).</p><p>mdc(3, 17) = 1,</p><p>–</p><p>3 ⋅ y =</p><p>–</p><p>1, Z17.</p><p>1 = 3 ⋅ (6) + 17(−1),</p><p>–</p><p>6</p><p>–</p><p>3 Z17.</p><p>6 ⋅ 3x ≡ 6 ⋅ 1( mod 17)</p><p>18x ≡ 6( mod 17)</p><p>x ≡ 6( mod 17)</p><p>x = 6 + 17t, t ∈ Z x ≡ 6( mod 17).</p><p>5x ≡ −3( mod 7).</p><p>mdc(5, 7) = 1,</p><p>−3 ≡ 4( mod 7), 7 ∣ (−3 − 4).</p><p>5x ≡ 4( mod 7).</p><p>3 ⋅ 5x ≡ 3 ⋅ 4( mod 7)</p><p>15x ≡ 12( mod 7)</p><p>x ≡ 5( mod 7)</p><p>x = 5 + 7t, t ∈ Z x ≡ 5( mod 7).</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 94/101</p><p>Atividade discursiva</p><p>Seja um número natural, mostre que, se não é um quadrado perfeito,</p><p>então é um número par.</p><p>Digite sua resposta aqui</p><p>Chave de resposta</p><p>Pela hipótese, temos que não é um quadrado perfeito. Temos,</p><p>então, que pelo menos um dos expoentes de sua fatoração é um</p><p>número ímpar e um dos números consecutivos é par. Porém,</p><p>quando um dos fatores é par, o produto é par. Portanto, o número</p><p>de divisores que é calculado, produto dos números consecutivos</p><p>dos expoentes da fatoração, é par.</p><p>Teoria na prática</p><p>Considerando verifique se a função é uma função</p><p>aritmética multiplicativa.</p><p>Mão na massa</p><p>Questão 1</p><p>Determine o inteiro positivo da forma e que admite 27</p><p>divisores positivos.</p><p></p><p>n n</p><p>d(n)</p><p>n</p><p>n</p><p>_black</p><p>n = 63, s(n)</p><p>Mostrar solução</p><p></p><p>9 ⋅ 10m</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 95/101</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 2</p><p>Determine a soma dos divisores positivos de inteiro</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>Sendo a função de Mobius, determine</p><p>A 100</p><p>B 288</p><p>C 308</p><p>D 900</p><p>E 1008</p><p>n = 512.</p><p>A 125</p><p>B 234</p><p>C 723</p><p>D 850</p><p>E 1023</p><p>μ(n) μ(30).</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 96/101</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 4</p><p>Marque a alternativa que indica a classe residual módulo 9 de 1913.</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>Determine a solução da congruência</p><p>A 0</p><p>B 1</p><p>C -1</p><p>D 2</p><p>E 3</p><p>A {⋯ , −22, −13, −4, 5, 14, 23, 32 ⋯}</p><p>B {⋯ , −27, −13, 5, 9, 14, 28, 32 ⋯}</p><p>C {⋯ , −13, −9, −3, 5, 10, 15, 20 ⋯}</p><p>D {⋯ , −21, −15, −4, 5, 14, 23, 32 ⋯}</p><p>E {⋯ , −22, −13, −4, 5, 15, 20, 25 ⋯}</p><p>4x ≡ 3( mod 5).</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 97/101</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%3D5c2196fdab794074</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%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20</p><p>Questão 6</p><p>Dada a função determine</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>A x = 1 + 5t, t ∈ Z</p><p>B x = 2 + 5t, t ∈ Z</p><p>C x = 2 + 3t, t ∈ Z</p><p>D x = −3 + 5t, t ∈ Z</p><p>E x = 4 + t, t ∈ Z</p><p>Ω(n), Ω(300).</p><p>A 1</p><p>B 2</p><p>C 3</p><p>D 4</p><p>E 5</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 98/101</p><p>Falta pouco para atingir seus objetivos.</p><p>Vamos praticar alguns conceitos?</p><p>Questão 1</p><p>Marque a alternativa que indica o valor de</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%3Cp%20class%3D'c-</p><p>paragraph'%3EVeja%20o%20feedback%20completo%20no%20Solucion%C3%A1rio%20disponibilizado%20no%</p><p>Questão 2</p><p>Determine o conjunto da classe residual módulo 5 do inteiro -4.</p><p>d(s(360)).</p><p>A 12</p><p>B 18</p><p>C 22</p><p>D 24</p><p>E 38</p><p>A −4 = {⋯ , −14, −9, −5, 1, 6, 11, ⋯}</p><p>–</p><p>B −4 = {⋯ , −12, −5, −4, 1, 8, 12, ⋯}</p><p>–</p><p>C −4 = {⋯ , −14, −9, −5, 1, 12, 13, ⋯}</p><p>–</p><p>D −4 = {⋯ , −16, −7, −4, 1, 6, 10, ⋯}</p><p>–</p><p>E −4 = {⋯ , −14, −9, −4, 1, 6, 11, ⋯}</p><p>–</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 99/101</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>Apresentamos aqui um pouco do trabalho de matemáticos que, ao logo</p><p>da história, contribuíram com suas descobertas matemática. Como</p><p>você pode notar, a teoria dos números apresenta um conjunto de</p><p>conteúdos de suma importância na formação do matemático.</p><p>Estudamos as equações diofantinas, as congruências lineares, os</p><p>métodos de resolução de sistemas de congruências lineares e alguns</p><p>dos resultados referentes aos divisores de um número inteiro, bem</p><p>como funções aritméticas e classes residuais.</p><p>Também pudemos ver que cada teoria é fundamentada a partir de</p><p>teoremas. Alguns teoremas não apresentam uma aplicação direta, mas</p><p>são importantes e por meio deles novas teorias vão surgindo. Sendo</p><p>assim, é importante que o matemático compreenda como são</p><p>demonstrados e como trabalhar com eles.</p><p>Explore +</p><p>Assista ao vídeo História da Matemática: capítulos finais da</p><p>Matemática grega: Diofanto e a Álgebra grega. Vale conferir!</p><p>Ficam também como sugestões de leitura as obras Uma abordagem do</p><p>ensino de congruência na educação básica, de Marthus Lobato dos</p><p>Santos, e Congruência e equações diofantinas: algumas aplicações, de</p><p>Rivanildo Garcia da Silva.</p><p>Referências</p><p>ALENCAR FILHO, E. de. Teoria elementar dos números. Rio de Janeiro:</p><p>Livraria Nobel, 1985.</p><p>BENATTI, K. A. B.; BENATTI, N. C. da C. M. Teoria dos números. Curitiba:</p><p>InterSaberes, 2019.</p><p>BOYER, C. B. História da matemática. São Paulo: Blücher, 2012.</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 100/101</p><p>BURTON, D. M. Teoria elementar dos números. 7. ed. Rio de Janeiro:</p><p>LTC, 2016.</p><p>FREIRE, B.; SILVA, C.; DIAS, C. Notas de Aula: teoria dos número. Rio de</p><p>Janeiro: Ciência Moderna, 2021.</p><p>HEFEZ, A. Aritmética. Rio de Janeiro: SBM, 2014. Coleção PROFMAT.</p><p>LEITE, A. E.; CASTANHEIRA, N. P. Teoria dos números e teoria dos</p><p>conjuntos. Curitiba: InterSaberes, 2014. v. 1. (Coleção Desmistificando a</p><p>Matemática).</p><p>RODRIGUEZ, J. E. A. R.; SOUZA, N. R. de. Teoria elementar dos números</p><p>e aplicações: um tratamento elementar. [s. l.]: Novas Edições</p><p>Acadêmicas, 2017.</p><p>STEWART, I. O fantástico mundo dos números: a matemática do zero ao</p><p>infinito. Rio de Janeiro: J. Zahar, 2015.</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>O que você achou do conteúdo?</p><p>Relatar problema</p><p>23/04/2024, 19:21 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 101/101</p><p>javascript:CriaPDF()</p><p>particular da</p><p>equação:</p><p>(1)</p><p>Imagine também que é uma solução qualquer da equação:</p><p>(2)</p><p>Igualando as equações (1) e (2), obtemos:</p><p>9x + 6y = 65,</p><p>a = 9, b = 6 c = 65.</p><p>mdc(9, 6) = 3</p><p>d c, (d ∣ c), d = mdc(a, b),</p><p>(x0, y0)</p><p>ax + by = c,</p><p>x = x0 + (b/d)k</p><p>y = y0 − (a/d)k</p><p>k</p><p>x0, y0</p><p>ax + by = c ⇒ ax0 + by0 = c</p><p>x1, y1</p><p>ax + by = c ⇒ ax1 + by1 = c</p><p>ax0 + by0 = c = ax1 + by1</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 7/101</p><p>Portanto:</p><p>Como o mdc existem inteiros e primos entre si, tais que</p><p>e Substituindo esses valores de e na igualdade</p><p>temos:</p><p>Assim, e, como o segue-se que</p><p>isto é:</p><p>Lembre-se que é um número inteiro. Portanto, temos:</p><p>Veja que, para qualquer valor de e a equação é</p><p>verdadeira, desde que seja um inteiro, pois temos:</p><p>Note que, se divide então a equação diofantina</p><p>linear admite um número infinito de soluções para cada</p><p>valor do inteiro arbitrário</p><p>Corolário sobre a resolução da equação quando o</p><p>Se o e se é uma solução particular da equação</p><p>diofantina linear então todas as outras soluções dessa</p><p>equação são dadas pelas fórmulas:</p><p>a (x1 − x0) = b (y0 − y1)</p><p>(a, b) = d, p q,</p><p>a = dp b = dq. a b</p><p>a (x1 − x0) = b (y0 − y1),</p><p>dp (x1 − x0) = dq (y0 − y1)</p><p>p (x1 − x0) = q (y0 − y1)</p><p>p ∣ q (y0 − y1) mdc(r, s) = 1,</p><p>p ∣ q (y0 − y1),</p><p>y0 − y1 = pk e x1 − x0 = qk</p><p>k</p><p>x1 = x0 + qt = x0 + (b/d)k</p><p>y1 = y0 − pt = y0 − (a/d)k</p><p>x1 y1, ax + by = c</p><p>k</p><p>ax1 + by1 = a [x0 + (b/d)k] + b [y0 − (a/d)k]</p><p>ax1 + by1 = (ax0 + by0) + [a(b/d) − a(b/d)]k</p><p>ax1 + by1 = c + 0 ⋅ k</p><p>ax1 + by1 = c</p><p>d = mdc(a, b) c(d ∣ c),</p><p>ax + by = c</p><p>k.</p><p>mdc(a, b) = 1</p><p>mdc(a, b) = 1 x0, y0</p><p>ax+ by = c,</p><p>x = x0 + bk</p><p>y = y0 − ak</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 8/101</p><p>Lembre-se que é um inteiro arbitrário.</p><p>Comentário</p><p>Uma solução particular da equação diofantina linear é obtida por</p><p>tentativas ou pelo algoritmo de Euclides, e a solução geral é obtida com</p><p>o teorema 2.</p><p>Exemplo 1</p><p>Dada a equação diofantina linear determine a</p><p>solução particular.</p><p>Solução</p><p>Devemos determinar primeiramente o com o algoritmo de</p><p>Euclides. Observe a tabela!</p><p>Quocientes 1 8</p><p>28 25 3</p><p>Restos 3 1</p><p>Tabela: Algoritmo de Euclides para o exemplo 1.</p><p>Ana Lucia de Sousa.</p><p>Logo, o Como a equação</p><p>possui solução. Dessa forma, existem tais que</p><p>Isso significa que existe um número que é</p><p>múltiplo de 25 e um número que é múltiplo de 28 cuja soma é 1.</p><p>Vamos determinar esses números!</p><p>Vamos escrever 1 em função de 25 e 28. Em outras palavras,</p><p>escrevemos 1 como combinação linear de 25 e 28. Esse procedimento é</p><p>realizado com o algoritmo de Euclides.</p><p>Fica mais simples começar pelos restos, veja:</p><p>(1)</p><p>(2)</p><p>Vamos substituir (1) em (2):</p><p>(3)</p><p>k</p><p>25x + 28y = 37,</p><p>mdc(25, 28)</p><p>mdc(25, 28) = 1. 1 ∣ 37, 25x + 28y = 37</p><p>x0, y0,</p><p>25x0 + 28y0 = 1. x0</p><p>y0</p><p>3 = 28 − 1 ⋅ 25</p><p>1 = 25 − 3 ⋅ 8</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 9/101</p><p>Agora, vamos multiplicar os dois lados da equação (3) por 37:</p><p>Então, temos como solução particular:</p><p>Você também pode escrever as expressões a partir do algoritmo de</p><p>Euclides do seguinte modo:</p><p>Agora, basta isolar os restos:</p><p>A partir daí, segue o procedimento realizado no exemplo 1.</p><p>Exemplo 2</p><p>Dada a equação diofantina linear determine a</p><p>solução particular.</p><p>Solução</p><p>Devemos determinar primeiramente o com o algoritmo de</p><p>Euclides. Confira a tabela!</p><p>Quocientes 1 3</p><p>72 56 16</p><p>1 = 25 − (28 − 1 ⋅ 25) ⋅ 8</p><p>1 = 25 − 28 ⋅ 8 + 8 ⋅ 25</p><p>1 = 25 − 8 ⋅ 28 + 8 ⋅ 25</p><p>1 = 9 ⋅ 25 − 8 ⋅ 28</p><p>25 ⋅ 9 + 28(−8) = 1</p><p>25 ⋅ (9 ⋅ 37) + 28(−8 ⋅ 37) = (1 ⋅ 37)</p><p>25 ⋅ (333) + 28(−296) = 37</p><p>x0 = 333 e y0 = −296</p><p>28 = 25 ⋅ 1 + 3</p><p>25 = 3 ⋅ 8 + 1</p><p>3 = 1 ⋅ 3 + 0</p><p>28 = 25 ⋅ 1 + 3 ⇒ 3 = 28 − 25 ⋅ 1</p><p>25 = 3 ⋅ 8 + 1 ⇒ 1 = 25 − 3 ⋅ 8</p><p>56x + 72y = 40,</p><p>mdc(56, 72)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 10/101</p><p>Quocientes 1 3</p><p>Restos 16 8</p><p>Tabela: Algoritmo de Euclides para o exemplo 2.</p><p>Ana Lucia de Sousa.</p><p>Logo, o Como a equação</p><p>tem solução. Dessa forma, existem tais que</p><p>Isso significa que existe um número que é múltiplo de 56 e um</p><p>número que é múltiplo de 72 cuja soma é 8. Vamos determinar esses</p><p>números!</p><p>Considerando o algoritmo de Euclides, temos sucessivamente que:</p><p>(1)</p><p>(2)</p><p>Fica mais simples escrever as expressões a partir dos restos.</p><p>Vamos substituir (1) em (2):</p><p>(3)</p><p>Agora, vamos multiplicar os dois lados da equação (3) por 5:</p><p>Então, temos como solução particular:</p><p>Exemplo 3</p><p>Dada a equação diofantina linear determine a</p><p>solução geral.</p><p>mdc(56, 72) = 8. 8 ∣ 40, 56x + 72y = 40</p><p>x0, y0, 56x0 + 72y0 = 8.</p><p>x0</p><p>y0</p><p>16 = 72 − 56 ⋅ 1</p><p>8 = 56 − 16 ⋅ 3</p><p>8 = 56 − (72 − 56 ⋅ 1) ⋅ 3</p><p>8 = 56 − 72 ⋅ 3 + 56 ⋅ 3</p><p>8 = 56 ⋅ 4 − 72 ⋅ 3</p><p>56 ⋅ 4 + 72(−3) = 8</p><p>56 ⋅ (4 ⋅ 5) + 72(−3 ⋅ 5) = (8 ⋅ 5)</p><p>56 ⋅ (20) + 72(−15) = 40</p><p>x0 = 20 e y0 = −15</p><p>25x − 28y = 37,</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 11/101</p><p>Solução</p><p>Devemos determinar primeiramente o com o algoritmo de</p><p>Euclides. Observe a tabela!</p><p>Quocientes 1 8</p><p>28 25 3</p><p>Restos 3 1</p><p>Tabela: Algoritmo de Euclides para o exemplo 3.</p><p>Ana Lucia de Sousa.</p><p>Logo, o Como a equação</p><p>tem solução. Dessa forma, existem tais que</p><p>Isso significa que existe um número que é múltiplo de 25 e um</p><p>número que é múltiplo de 28 cuja soma é 1. Vamos determinar esses</p><p>números!</p><p>Considerando o algoritmo de Euclides, temos sucessivamente que:</p><p>(1)</p><p>(2)</p><p>Vamos substituir (1) em (2):</p><p>(3)</p><p>Agora, vamos multiplicar os dois lados da equação (3) por 37:</p><p>Agora, vamos multiplicar os dois lados da equação (3) por 37:</p><p>mdc(25, 28)</p><p>mdc(25, 28) = 1. 1 ∣ 37, 25x − 28y = 37</p><p>x0, y0 25x0 − 28y0 = 37.</p><p>x0</p><p>y0</p><p>3 = 28 − 25 ⋅ 1</p><p>1 = 25 − 3 ⋅ 8</p><p>1 = 25 − (28 − 25 ⋅ 1) ⋅ 8</p><p>1 = 25 − 28 ⋅ 8 + 25 ⋅ 8</p><p>1 = 25 ⋅ 9 − 28 ⋅ 8</p><p>25 ⋅ 9 − 28(8) = 1</p><p>25 ⋅ (9 ⋅ 37) − 28(8 ⋅ 37) = (1 ⋅ 37)</p><p>25 ⋅ (333) − 28(296) = 37</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 12/101</p><p>Então, temos como solução particular:</p><p>A solução geral é encontrada a partir das fórmulas:</p><p>Nesse caso, a equação diofantina linear tem infinitas soluções.</p><p>Conjunto solução</p><p>Exemplo 4</p><p>Um mercado está fazendo uma promoção de biscoitos e bolo de</p><p>chocolate. Cada pacote de biscoito custa R$ 8 e cada fatia de bolo de</p><p>chocolate custa R$ 12. Com R$ 80, quais as possíveis quantidades de</p><p>pacotes de biscoitos e fatias de bolo de chocolate que Carlos pode</p><p>comprar, sabendo que ele pretende comprar no mínimo 2 pacotes de</p><p>biscoitos e 3 fatias de bolo?</p><p>Solução</p><p>Seja a quantidade de pacotes de biscoitos e a quantidade de fatias</p><p>de bolo. Veja que esse problema pode ser modelado pela equação</p><p>Devemos determinar primeiramente o</p><p>com o algoritmo de Euclides. Observe a tabela!</p><p>Quocientes 1 2</p><p>12 8 4</p><p>Restos 4 0</p><p>Tabela: Algoritmo de Euclides para o exemplo 4.</p><p>Ana Lucia de Sousa.</p><p>25 ⋅ (9 ⋅ 37) − 28(8 ⋅ 37) = (1 ⋅ 37)</p><p>25 ⋅ (333) − 28(296) = 37</p><p>x0 = 333 e y0 = 296</p><p>x = x0 + ( b</p><p>d</p><p>)k</p><p>y = y0 − ( a</p><p>d</p><p>)k</p><p>x = x0 + (b/d)k ⇒ x = 333 + ( −28</p><p>1</p><p>)k ⇒ x = 333 − 28k, k ∈ Z</p><p>y = y0 − ( a</p><p>d</p><p>)k ⇒ y = 296 − ( 25</p><p>1</p><p>)k ⇒ y = 296 − 25k, k ∈ Z</p><p>S = {(333 − 28k, 296 − 25k); k ∈ Z}.</p><p>x y</p><p>8x + 12y = 80. mdc(8, 12)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 13/101</p><p>Logo, o Como a equação tem</p><p>solução. Dessa forma, existem tais que Isso</p><p>significa que existe um número que é múltiplo de 8 e um número</p><p>que é múltiplo de 12 cuja soma é 4. Vamos determinar esses números!</p><p>Considerando o algoritmo</p><p>de Euclides, temos sucessivamente que:</p><p>Vamos multiplicar essa equação por 20:</p><p>Então, temos como solução particular:</p><p>A solução geral desse problema é dada por:</p><p>Agora, usaremos as restrições do problema para calcular os valores</p><p>possíveis de Temos que comprar, no mínimo, 2 pacotes de</p><p>biscoitos e 3 fatias de bolo.</p><p>Vamos considerar Substituindo em e</p><p>temos:</p><p>Congruências</p><p>mdc(8, 12) = 4. 4 ∣ 80, 8x + 12y = 80</p><p>x0, y0, 8x0 + 12y0 = 80.</p><p>x0 y0</p><p>4 = 12 − 8 ⋅ 1</p><p>4 = 12 + 8 ⋅ (−1)</p><p>80 = 12 ⋅ (20) + 8 ⋅ (−20)</p><p>8 ⋅ (−20</p><p>x0</p><p>) + 12 ⋅ ( 20</p><p>y0</p><p>) = 80 </p><p>x0 = −20 e y0 = 20</p><p>x = x0 + ( b</p><p>d )k ⇒ x = −20 + ( 12</p><p>4 )k = −20 + 3k k ∈ Z</p><p>y = y0 − ( a</p><p>d )k ⇒ y = 20 − ( 8</p><p>4 )k = 20 − 2k k ∈ Z</p><p>k ∈ Z.</p><p>x = −20 + 3k ⇒ −20 + 3k > 2 ⇒ k > 7, 3</p><p>y = 20 − 2k ⇒ 20 − 2k > 3 ⇒ k < 8, 5</p><p>k = 8. k = 8 x = −20 + 3k</p><p>y = 20 − 2k,</p><p>x = −20 + 3k ⇒ x = −20 + 3(8) ⇒ x = −20 + 24 = 4</p><p>y = 20 − 2k ⇒ y = 20 − 2(8) ⇒ y = 20 − 16 = 4</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 14/101</p><p>Vamos conhecer uma ferramenta importante dentro da teoria dos</p><p>números que é a aritmética modular, que estuda a congruência</p><p>modular. Ela está presente no nosso cotidiano e, a partir de suas</p><p>propriedades, veremos que diversos problemas podem ser resolvidos de</p><p>forma mais simples. Essa teoria foi introduzida no início do século XIX</p><p>pelo matemático Carl Friedrich Gauss.</p><p>Aritmética modular (inteiros congruentes)</p><p>Vejamos alguns casos a seguir.</p><p>Caso 1</p><p>De�nição</p><p>Sejam dois números inteiros quaisquer, e e um número natural,</p><p>dizemos que é congruente a módulo quando divide a</p><p>diferença</p><p>Notação</p><p>Acompanhe a notação:</p><p>Assim, podemos dizer que é congruente a módulo se, e somente</p><p>se, existir um inteiro tal que Portanto:</p><p>Exemplos</p><p>Observe alguns exemplos:</p><p>pois</p><p>pois</p><p>pois</p><p>Caso 2</p><p>De�nição</p><p>Dizemos que é incongruente a (ou não é congruente a ) quando</p><p>não divide a diferença</p><p>Notação</p><p>Acompanhe a notação:</p><p>a b, m</p><p>a b m, m</p><p>a − b.</p><p>a ≡ b ( mod m)</p><p>a ≡ b ( mod m) ⇔ m ∣ (a − b)</p><p>a b m</p><p>k a − b = km.</p><p>a ≡ b ( mod m) ⇔ m ∣ (a − b) ⇔ ∃k ∈ Z; a − b = km</p><p>3 ≡ 21 ( mod 6), 6 ∣ (3 − 21).</p><p>−13 ≡ 11 ( mod 8), 8 ∣ (−13 − 11).</p><p>−15 ≡ −60 ( mod 9), 9 ∣ (−15 − (−60)).</p><p>a b a b</p><p>m a − b.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 15/101</p><p>Exemplos</p><p>Observe alguns exemplos:</p><p>pois</p><p>pois</p><p>pois</p><p>Comentário</p><p>Na congruência vamos considerar sempre</p><p>Teorema 1 (caracterização de inteiros congruentes)</p><p>Dois números inteiros e são congruentes módulo se, e somente</p><p>se, e deixarem o mesmo resto quando divididos por</p><p>Demonstração</p><p>(Ida)</p><p>Hipótese: dois números inteiros e são congruentes módulo Ou</p><p>seja, Por definição, temos:</p><p>(1)</p><p>De (1), Considerando o resto da divisão de por e</p><p>pelo algoritmo da divisão, podemos escrever:</p><p>Logo,</p><p>Veja que é o resto da divisão de por</p><p>Concluímos, então, que os inteiros e deixam o mesmo resto</p><p>quando são divididos por</p><p>(Volta)</p><p>Hipótese: e divididos por deixam o mesmo resto Temos, então:</p><p>(2)</p><p>a ≢ b ( mod m)</p><p>5 ≢ 1 ( mod 3), 3 ∤ (5 − 1).</p><p>16 ≢ 9 ( mod 4, 4 ∤ (16 − 9).</p><p>−21 ≢ 6 ( mod 5), 5 ∤ (−21 − 5).</p><p>a ≡ b ( mod m), m ≥ 2.</p><p>a b m</p><p>a b m.</p><p>a b m.</p><p>a ≡ b ( mod m).</p><p>a − b = km, k ∈ Z</p><p>a = b + km. r b m</p><p>b = mq + r</p><p>0 ≤ r < m</p><p>a = b + km = mq + r + km = mq + km + r = (k + q)m + r.</p><p>r a m.</p><p>a b r</p><p>m.</p><p>a b m r.</p><p>a = mq1 + r</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 16/101</p><p>(3)</p><p>Com</p><p>Subtraindo (2) e (3) membro a membro, obtemos:</p><p>Logo,</p><p>Exemplo 1</p><p>Considere os números inteiros -56 e -11. De acordo com o algoritmo da</p><p>divisão, podemos escrever:</p><p>Isso significa que -56 e -11 deixam o mesmo resto 7 quando divididos</p><p>por 9. Sendo assim, pelo teorema, podemos escrever que</p><p>Exemplo 2</p><p>Veja que pois -31 e 11 quando divididos por 7</p><p>deixam o mesmo resto 4.</p><p>Propriedades das congruências</p><p>Agora vamos conhecer as propriedades das congruências necessárias</p><p>quando realizamos operações com números inteiros, pois a partir delas</p><p>os problemas são resolvidos de forma mais simples. Essas</p><p>propriedades são apresentadas por meio dos teoremas.</p><p>Teorema 2: propriedades re�exiva, simétrica e</p><p>transitiva</p><p>Seja um inteiro positivo fixo ( e sejam e inteiros</p><p>quaisquer. Sendo assim, são válidas as propriedades a seguir. Confira!</p><p>b = mq2 + r</p><p>0 ≤ r < m.</p><p>a − b = mq1 + r − mq2 − r</p><p>a − b = (q1 − q2</p><p>k∈Z</p><p>)m ⇒ m ∣ (a − b) ⇒ a ≡ b ( mod m).</p><p>− 56 = 9(−7) + 7</p><p>− 11 = 9(−2) + 7</p><p>−56 ≡ −11 ( mod 9).</p><p>−31 ≡ 11 ( mod 7),</p><p>11 = 7(1) + 4</p><p>−31 = 7(−5) + 4</p><p>m m > 0), a, b c</p><p> Propriedade I</p><p>A ê i é fl i ( d )</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 17/101</p><p>Esse teorema sinaliza que a relação de congruência módulo é uma</p><p>relação de equivalência sobre o conjunto dos números inteiros com as</p><p>operações de adição e multiplicação.</p><p>Demonstração</p><p>Propriedade I</p><p>Considerando um número inteiro qualquer a, podemos escrever que</p><p>Ou seja,</p><p>Propriedade II</p><p>Por hipótese, temos:</p><p>Pelo teorema</p><p>Portanto,</p><p>Propriedade III</p><p>Por hipótese, temos: e Então,</p><p>existem inteiros tais que:</p><p>(1)</p><p>A congruência é reflexiva: a ≡ a ( mod m).</p><p> Propriedade II</p><p>A congruência é simétrica:</p><p>a ≡ b ( mod m) ⇒ b ≡ a ( mod m).</p><p> Propriedade III</p><p>A congruência é transitiva: e</p><p>então</p><p>a ≡ b ( mod m)</p><p>b ≡ c ( mod m), a ≡ c ( mod m).</p><p>a − a = 0 = 0 ⋅ m. a ≡ a ( mod m).</p><p>a ≡ b ( mod m)</p><p>1, a − b = km, k ∈ Z</p><p>b − a = −(km) = (−k)</p><p>−k∈Z</p><p>m ⇒ b ≡ a ( mod m).</p><p>a ≡ b ( mod m) b ≡ c ( mod m).</p><p>k1, k2 ∈ Z,</p><p>a − b = k1m</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 18/101</p><p>(2)</p><p>Somando as equações (1) e (2), obtemos:</p><p>Fazendo temos:</p><p>Assim,</p><p>Teorema 3: propriedades da aritmética modular</p><p>Seja um número inteiro positivo fixo e sejam e</p><p>números inteiros quaisquer. Então, as seguintes propriedades são</p><p>verificadas. Observe!</p><p>Demonstração</p><p>Propriedade I</p><p>b − c = k2m</p><p>(a + b) + (−b − c) = k1m + k2m</p><p>(a − b) + (b − c) = (k1 + k2)m</p><p>k = k1 + k2 ∈ Z,</p><p>(a − c) = km</p><p>a ≡ c ( mod m).</p><p>m (m > 0) a, b, c d</p><p> Propriedade I</p><p>Se e se</p><p>então,</p><p>a ≡ b ( mod m) n ∣ m, comm > 0,</p><p>a ≡ b ( mod n).</p><p> Propriedade II</p><p>Se e se então,a ≡ b ( mod m) c > 0,</p><p>ac ≡ bc ( mod mc).</p><p> Propriedade III</p><p>Se e se e são divisíveis pelo</p><p>número inteiro então</p><p>a ≡ b ( mod m) a b</p><p>d > 0,</p><p>a/d ≡ b/d ( mod m/d).</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 19/101</p><p>Por hipótese, temos: e</p><p>Pelo teorema 1,</p><p>(1)</p><p>Como:</p><p>(2)</p><p>Logo, substituindo (2) em (1), temos:</p><p>Propriedade II</p><p>Por hipótese, temos: e</p><p>Pelo teorema 1,</p><p>(1)</p><p>Multiplicando (1) por temos:</p><p>Portanto:</p><p>Propriedade III</p><p>Por hipótese, temos: e são divisíveis pelo</p><p>número inteiro</p><p>Pelo teorema 1,</p><p>(1)</p><p>Dividindo (1) pord temos:</p><p>Portanto:</p><p>Exemplos</p><p>a ≡ b ( mod m) n ∣ m, comm > 0.</p><p>a − b = km, k ∈ Z</p><p>n ∣ m ⇒ m = nq  e  q > 0</p><p>a − b = k(nq) = (kq)n ⇒ a ≡ b ( mod n)</p><p>a ≡ b ( mod m) c > 0.</p><p>a − b = km, k ∈ Z</p><p>c > 0, (a − b)c = (km)c.</p><p>ac − bc = k(mc) ⇒ ac ≡ bc ( mod mc)</p><p>a ≡ b ( mod m), a b</p><p>d > 0</p><p>a − b = km, k ∈ Z</p><p>> 0, (a − b)/d = (km)/d.</p><p>a/d − b/d = k(m/d) ⇒ a/d ≡ b/d ( mod m/d)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 20/101</p><p>a)</p><p>b)</p><p>Note que, de acordo com o teorema 3, podemos multiplicar a</p><p>congruência por 5.</p><p>c)</p><p>De acordo com o teorema 3, os inteiros 36 e -24 são divisíveis por 4.</p><p>Teorema 4: propriedades das congruências</p><p>Seja um número inteiro positivo fixo e sejam e</p><p>números inteiros quaisquer.</p><p>Então, são válidas as seguintes</p><p>propriedades. Veja!</p><p>−15 ≡ 9 ( mod 8) ⇒ −15 ≡ 9 ( mod 4)</p><p>7 ≡ −8 ( mod 3)</p><p>7 ⋅ 5 ≡ −8 ⋅ 5 ( mod 3 ⋅ 5)</p><p>35 ≡ −40 ( mod 15)</p><p>36 ≡ −24 ( mod 12)</p><p>36/4 ≡ −24/4 ( mod 12/4) ⇒ 9 ≡ −6 ( mod 3)</p><p>m (m > 0) a, b, c d</p><p> Propriedade I</p><p>Se e então</p><p>e</p><p>a ≡ b ( mod m) c ≡ d ( mod m)</p><p>a + c ≡ b + d ( mod m)</p><p>ac ≡ bd ( mod m).</p><p> Propriedade II</p><p>Se então</p><p>e</p><p>a ≡ b ( mod m)</p><p>a + c ≡ b + c ( mod m)</p><p>ac ≡ bc ( mod m).</p><p> Propriedade III</p><p>Se então</p><p>para</p><p>a ≡ b ( mod m) ak ≡ bk ( mod m)</p><p>∀k ∈ N .</p><p> Propriedade IV</p><p>Se entãoa + c ≡ b + c ( mod m)</p><p>a ≡ b ( mod m).</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 21/101</p><p>Demonstração</p><p>Propriedade I</p><p>Por hipótese, temos: e</p><p>Pelo teorema 1:</p><p>(1)</p><p>(2)</p><p>Somando as equações (1) e (2), obtemos:</p><p>Fazendo, temos:</p><p>Assim,</p><p>Considerando as equações (1) e (2), temos:</p><p>(3)</p><p>(4)</p><p>Multiplicando cada membro de e</p><p>e considerando (3) e (4), obtemos:</p><p>a ≡ b ( mod m) c ≡ d ( mod m)</p><p>a − b = k1m, k1 ∈ Z</p><p>c − d = k2m, k2 ∈ Z</p><p>(a + c) + (−b − d) = k1m + k2m</p><p>(a + c) − (b + d) = k1m + k2m</p><p>(a + c) − (b + d) = (k1 + k2)m</p><p>k = k1 + k2 ∈ Z,</p><p>(a + c) − (b + d) = km</p><p>a + c ≡ b + d ( mod m).</p><p>a − b = k1m ⇒ a = b + k1m</p><p>c − d = k2m ⇒ c = d + k2m</p><p>a ≡ b ( mod m)</p><p>c ≡ d ( mod m),</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 22/101</p><p>Sendo temos:</p><p>Propriedade II</p><p>Por hipótese, temos:</p><p>Pela propriedade reflexiva, temos que Dessa forma,</p><p>podemos escrever:</p><p>Propriedade III</p><p>Por hipótese, temos:</p><p>Vamos provar por indução que para</p><p>Note que o resultado é verdadeiro para Ou seja, é</p><p>verdadeira.</p><p>Hipótese de indução: verificar se é verdadeiro.</p><p>Note que se é verdadeira, então o resultado é verdadeiro para</p><p>é verdadeira.</p><p>Agora vamos provar que esse resultado é verdadeiro para</p><p>Considere a hipótese de indução e a hipótese que</p><p>Podemos multiplicar essas congruências membro</p><p>a membro, obtendo:</p><p>Dessa forma, provamos que é verdadeiro.</p><p>Portanto, o resultado da propriedade III é verdadeiro para todo</p><p>Propriedade IV</p><p>ac = (b + k1m) (d + k2m)</p><p>ac = bd + bk2m + dk1m + k1m ⋅ k2m</p><p>ac = bd + (bk2 + dk1 + k1 ⋅ k2m)m</p><p>k = bk2 + dk1 + k1 ⋅ k2m,</p><p>ac = bd + km ⇒ ac − bd = km ⇒ ac ≡ bd ( mod m)</p><p>a ≡ b ( mod m)</p><p>c ≡ c ( mod m).</p><p>a + c ≡ b + c ( mod m)  e  ac ≡ bc ( mod m)</p><p>a ≡ b ( mod m)</p><p>ak ≡ bk ( mod m) ∀k ∈ N .</p><p>k = 1. P(1)</p><p>a1 ≡ b1( mod m)</p><p>a ≡ a( mod m)</p><p>P(k)</p><p>P(1)</p><p>k ≥ 1.</p><p>P(k) : ak ≡ bk ( mod m)</p><p>P(k + 1).</p><p>ak ≡ bk ( mod m)</p><p>a ≡ b ( mod m).</p><p>aka ≡ bkb ( mod m)</p><p>ak+1 ≡ bk+1 ( mod m)</p><p>P(k + 1)</p><p>k ≥ 1.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 23/101</p><p>Por hipótese, temos:</p><p>Suponhamos a congruência pois considerando</p><p>a congruência podemos multiplicar os dois lados</p><p>dela por obtendo:</p><p>Somando as congruências membro a membro, obtemos:</p><p>As propriedades apresentadas são muito utilizadas nas resoluções de</p><p>problemas que envolvem a congruência modular. Vejamos alguns</p><p>exemplos!</p><p>Exemplo 1</p><p>Dadas as congruências e</p><p>podemos somar e multiplicá-las. Entenda!</p><p>Exemplo 2</p><p>Dada a congruência podemos somar e</p><p>multiplicar essa congruência por um número inteiro. Confira!</p><p>Exemplo 3</p><p>Dada a congruência podemos elevar cada</p><p>membro dessa congruência a 3, por exemplo.</p><p>Dada a congruência podemos elevar cada</p><p>membro dessa congruência a 17, por exemplo.</p><p>a + c ≡ b + c ( mod m)</p><p>−c ≡ −c ( mod m),</p><p>c ≡ c ( mod m),</p><p>(−1),</p><p>c(−1) ≡ c(−1) ( mod m) ⇒ −c ≡ −c ( mod m)</p><p>a + c ≡ b + c ( mod m)</p><p>− c ≡ −c ( mod m)</p><p>a + c − c ≡ b + c − c ( mod m) ⇒ a ≡ b ( mod m)</p><p>11 ≡ 4 ( mod 7) 13 ≡ 6 ( mod 7),</p><p>11 + 13 ≡ 4 + 6 ( mod 7) ⇒ 24 ≡ 10 ( mod 7)</p><p>11 ⋅ 13 ≡ 4 ⋅ 6 ( mod 7) ⇒ 143 ≡ 24 ( mod 7)</p><p>12 ≡ 22 ( mod 5),</p><p>Somar a congruência dada por 4 </p><p>Multiplicar a congruência dada por -3 </p><p>−3 ≡ 4 ( mod 7),</p><p>−3 ≡ 4 ( mod 7) ⇒ (−3)3 ≡ 43 ( mod 7) ⇒ −27 ≡ 64 ( mod 7)</p><p>24 ≡ 1 ( mod 15),</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 24/101</p><p>Exemplo 4</p><p>Determine o dígito das unidades de escrito na base 7.</p><p>Sugestão de congruências mais simples</p><p>A seguir, acompanhe uma sugestão de congruências mais simples que</p><p>podemos usar.</p><p>Usaremos a congruência escrita como</p><p>24 ≡ 1 ( mod 15) ⇒ (24)</p><p>17</p><p>≡ 117 ( mod 15) ⇒ 268 ≡ 1 ( mod 15)</p><p>240</p><p>Solução </p><p>ak ≡ 1 ( mod m)</p><p>ak ≡ −1 ( mod m)</p><p>ak ≡ 1 ( mod m)</p><p>23 ≡ 1 ( mod 7).</p><p>Por que essa</p><p>congruência?</p><p>Resposta</p><p>Veja que, em temos</p><p>que divide 7.</p><p>Poderia ser a congruência</p><p>? Não, pois não</p><p>divide 7.</p><p>Então, será a nossa</p><p>congruência inicial.</p><p>A partir dessa congruência e usando as</p><p>propriedades de congruências, devemos</p><p>chegar na congruência</p><p>Na congruência</p><p>devemos elevar a um número que</p><p>multiplicado por 3 fique bem próximo de 40.</p><p>De maneira mais simples, basta dividir 40</p><p>por 3. Nessa divisão, encontramos o</p><p>quociente 13. Temos, então:</p><p>23 ≡ 1 ( mod 7),</p><p>8 − 1</p><p>24 ≡ 1 ( mod 7) 16 − 1</p><p>23 ≡ 1 ( mod 7)</p><p>240 ≡ r ( mod 7).</p><p>23 ≡ 1 ( mod 7),</p><p>23</p><p></p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 25/101</p><p>Lei do cancelamento</p><p>Das propriedades das congruências, a lei do cancelamento é o quinto</p><p>teorema a ser apresentado. Com esse teorema, vamos aprender como</p><p>podemos afirmar que um fator comum pode ser cancelado. Vamos lá!</p><p>Se</p><p>E se</p><p>Então</p><p>Demonstração</p><p>Por hipótese, temos e se o</p><p>Considerando a hipótese temos:</p><p>(1)</p><p>Considerando que o podemos dizer que temos</p><p>inteiros e primos entre si, tais que e Logo,</p><p>mas queremos</p><p>encontrar Então basta multiplicarmos</p><p>essa congruência por 2.</p><p>Portanto, o dígito das unidades é o</p><p>23 ≡ 1 ( mod 7)</p><p>(23)</p><p>13</p><p>≡ 113 ( mod 7)</p><p>239 ≡ 1 ( mod 7),</p><p>240.</p><p>239 ⋅ 2 ≡ 1 ⋅ 2 ( mod 7) ⇒ 240 ≡ 2 (</p><p>r = 2.</p><p>ac ≡ bc ( mod m)</p><p>mdc(c,m) = d</p><p>a ≡ b ( mod m/d)</p><p>ac ≡ bc ( mod m) mdc(c,m) = d.</p><p>ac ≡ bc ( mod m),</p><p>ac − bc = c(a − b) = km, k ∈ Z</p><p>mdc(c,m) = d,</p><p>r s, c = dr m = ds.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 26/101</p><p>podemos substituir e em (1). Obtemos:</p><p>Isso implica que e o Pelo teorema de</p><p>Euclides, temos que e Como</p><p>concluímos que</p><p>Exemplo</p><p>Seja a congruência Veja que ela pode ser escrita</p><p>como e o Usando esse</p><p>teorema, temos que:</p><p>Isso porque:</p><p>Corolário sobre a lei do cancelamento</p><p>A partir do teorema apresentado, observe o seguinte corolário sobre a</p><p>lei do cancelamento.</p><p>Se</p><p>E se</p><p>Então</p><p>Esse corolário basicamente mostra que é possível cancelar um fator</p><p>comum existente na congruência quando esse fator é primo com o</p><p>módulo. Ou seja, Veja!</p><p>Exemplo</p><p>Seja a congruência Veja que ela pode ser</p><p>escrita como e o Usando</p><p>esse corolário podemos, cancelar o fator comum, nesse caso, o 5. Logo,</p><p>Sistemas completos de restos (ou resíduos)</p><p>c = dr m = ds</p><p>c(a − b) = km ⇒ dr(a − b) = kds ⇒ (a − b)r = kds</p><p>s ∣ (a − b)r mdc(r, s) = 1.</p><p>s ∣ (a − b) a ≡ b ( mod s). s = m/d,</p><p>a ≡ b ( mod m/d).</p><p>44 ≡ 20 ( mod 8).</p><p>4 ⋅ 11 ≡ 4 ⋅ 5 ( mod 8) mdc(4, 8) = 4.</p><p>11 ≡ 5 ( mod 8/4) ⇒ 11 ≡ 5 ( mod 2)</p><p>2 ∣ (11 − 5)</p><p>ac ≡ bc ( mod m)</p><p>mdc(c,m) = 1</p><p>a ≡ b ( mod m)</p><p>mdc(c,m) = 1.</p><p>−35 ≡ 45 ( mod 8).</p><p>(−7) ⋅ 5 ≡ 9 ⋅ 5 ( mod 8) mdc(5, 8) = 1.</p><p>−7 ≡ 9 ( mod 8).</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 27/101</p><p>É importante conhecer no estudo das congruências a definição de</p><p>restos ou resíduos. Vamos conhecer primeiro o que é um sistema</p><p>completo de restos.</p><p>De�nição</p><p>Um sistema completo de restos ou resíduos módulo é representado</p><p>por um conjunto de números inteiros Nesse</p><p>conjunto, cada elemento representa o resto da divisão por em uma</p><p>ordem qualquer e sem repetição.</p><p>Os restos são distintos.</p><p>Em outras palavras, considerando um número inteiro qualquer, o</p><p>quociente e o resto da divisão de por</p><p>Pela definição de congruência, temos:</p><p>Nesse caso (resto) e isso implica dizer que o</p><p>inteiro é congruente módulo a um único elemento do conjunto</p><p>Logo, esse conjunto forma um sistema completo de restos ou resíduos</p><p>módulo</p><p>Exemplo 1</p><p>Mostre que o conjunto é um sistema completo de</p><p>restos módulo 5.</p><p>Exemplo 2</p><p>Mostre que o conjunto é um sistema completo</p><p>de restos módulo 5.</p><p>Observação: O sistema completo de restos módulo possui</p><p>elementos. Além disso, se no conjunto de inteiros os</p><p>elementos são dois a dois não congruentes módulo então eles</p><p>formam um sistema completo de restos módulo</p><p>Exemplo 3</p><p>Por exemplo, na congruência temos que 5 é um</p><p>resto ou resíduo de 13 módulo 8, pois quando dividimos 13 por 8</p><p>encontramos 5 como resultado. Veja que o mesmo ocorre na</p><p>congruência Ou seja, 2 é um resto de -12 módulo</p><p>7.</p><p>Exemplo 4</p><p>m</p><p>S = {0, 1, 2, ⋯ ,m − 1}.</p><p>m,</p><p>a q</p><p>r a m.</p><p>a = mq + r  em que  0 ≤ r < m</p><p>a ≡ r ( mod m).</p><p>r ∈ {0, 1, ⋯ ,m − 1}</p><p>a m H.</p><p>m.</p><p>H = {5, 6, 7, 8, 9}</p><p>Solução </p><p>H = {−2, −1, 0, 1, 2}</p><p>Solução </p><p>m m</p><p>{a1, a2, ⋯ , am}</p><p>m,</p><p>m.</p><p>13 ≡ 5 ( mod 8),</p><p>−12 ≡ 2 ( mod 7).</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 28/101</p><p>Supondo que hoje seja sexta-feira, então determine que dia da semana</p><p>será daqui 150 dias.</p><p>Atividade discursiva</p><p>Determine todas as soluções inteiras positivas da equação diofantina</p><p>linear com conjunto solução</p><p>Digite sua resposta aqui</p><p>Chave de resposta</p><p>Como as soluções devem ser inteiras positivas, vamos</p><p>escolher o que satisfaz as seguintes desigualdades:</p><p>Resolvendo essas inequações:</p><p>Note que</p><p>Substituindo</p><p>Portanto, a única solução inteira positiva da equação</p><p>diofantina é e</p><p>Solução </p><p></p><p>18x + 5y = 48</p><p>S = {(96 + 5k, −336 − 18k); k ∈ Z}.</p><p>k</p><p>96 + 5k > 0 e  − 336 − 18k > 0</p><p>96 + 5k > 0 ⇒ k > −19, 2</p><p>− 336 − 18k > 0 ⇒ k < −18, 7</p><p>k = −19.</p><p>k = −19em(333 − 28k, 296 − 25k).</p><p>x = 96 + 5k ⇒ x = 96 + 5(−19) ⇒ x = 96</p><p>y = −336 − 18k ⇒ y = −336 − 18(−19) ⇒ y = −</p><p>x = 1 y = 6.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 29/101</p><p>Teoria na prática</p><p>Mostre que é divisível por 17, qualquer que seja</p><p>Mão na massa</p><p>Questão 1</p><p>(PROFMAT - 2014) Determine duas frações positivas que tenham 17</p><p>e 23 como denominadores e cuja soma seja igual a</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>Determine a solução particular da equação diofantina</p><p>_black</p><p>198k − 1 k ∈ N.</p><p>Mostrar solução</p><p></p><p>234</p><p>391 .</p><p>A e 3</p><p>17</p><p>7</p><p>23</p><p>B e 5</p><p>17</p><p>9</p><p>23</p><p>C e 4</p><p>17</p><p>6</p><p>23</p><p>D e 2</p><p>17</p><p>1</p><p>23</p><p>E e 5</p><p>17</p><p>7</p><p>23</p><p>18x + 7y = 302.</p><p>A e x0 = 604 y0 = −1510</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 30/101</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%3D9386806ea37343e</p><p>2%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%0A%20%20%20%20%20</p><p>Questão 3</p><p>Uma biblioteca cobra R$ 1,80 para emprestar livros para adultos e</p><p>R$ 0,75 para emprestar livros para crianças. Em determinado dia da</p><p>semana, a biblioteca arrecadou R$90,00. Considerando que o</p><p>número de adultos foi maior que o número de crianças, determine</p><p>quantas pessoas no máximo solicitaram livros emprestados de</p><p>acordo com as condições impostas pelo problema.</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>B e x0 = 230 y0 = −1300</p><p>C e x0 = −150 y0 = 210</p><p>D e x0 = 728 y0 = 1234</p><p>E e x0 = 54 y0 = 21</p><p>A 45 pessoas</p><p>B 50 pessoas</p><p>C 57 pessoas</p><p>D 64 pessoas</p><p>E 85 pessoas</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 31/101</p><p>Paulo contraiu um empréstimo para comprar um apartamento, que</p><p>deverá ser pago em 185 meses. O primeiro pagamento ocorreu no</p><p>mês de julho de 2023. Marque a alternativa que indica o mês do</p><p>último pagamento do empréstimo.</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>Através das propriedades das congruências é possível determinar o</p><p>algarismo das unidades de números com potência elevadas. Dessa</p><p>forma, marque a alternativa que indica o algarismo das unidades de</p><p>na base 10.</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>A Dezembro</p><p>B Abril</p><p>C Julho</p><p>D Setembro</p><p>E Outubro</p><p>880</p><p>A 1</p><p>B 2</p><p>C 4</p><p>D 5</p><p>E 6</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 32/101</p><p>Questão 6</p><p>Determine a solução particular da equação diofantina</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>Dada a equação diofantina linear determine a</p><p>solução geral.</p><p>3x + 5y = 47.</p><p>A e x0 = 60 y0 = −15</p><p>B e x0 = 23 y0 = −13</p><p>C e x0 = −15 y0 = 21</p><p>D e x0 = 94 y0 = −47</p><p>E e x0 = 54 y0 = 21</p><p>56x + 72y = 40,</p><p>A S = {(3 + 2k, −15 − 7k); k ∈ Z}</p><p>B S = {(−4 + 5k, −16 − 7k); k ∈ Z}</p><p>C S = {(5 + 7k, −5 − 8k); k ∈ Z}</p><p>D S = {(−20 + 9k, 15 + 7k); k ∈ Z}</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 33/101</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>Considerando que anteontem foi terça-feira, marque a alternativa</p><p>que indica o dia da semana daqui a 698 dias.</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>2 - Congruências lineares</p><p>Ao �nal deste módulo, você será capaz de determinar a solução das</p><p>congruências lineares.</p><p>E S = {(20 + 9k, −15 − 7k); k ∈ Z}</p><p>A Segunda-feira</p><p>B Terça-feira</p><p>C Quarta-feira</p><p>D Quinta-feira</p><p>E Sexta-feira</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 34/101</p><p>Solução das congruências</p><p>lineares</p><p>Assista ao vídeo e acompanhe os teoremas, as demonstrações e os</p><p>exemplos de aplicação das congruências lineares, assim como a</p><p>resolução das equações diofantinas lineares por congruência e o</p><p>inverso de um inteiro.</p><p>Uma análise linear</p><p>De�nição</p><p>Definimos como congruência linear toda equação que apresente a</p><p>forma:</p><p>Em que:</p><p>é um inteiro positivo</p><p>é uma incógnita.</p><p>Exemplos</p><p>Observe os exemplos:</p><p>1.</p><p>2.</p><p>3.</p><p>Desejamos encontrar todas as soluções</p><p>inteiras dessa equação. Assim,</p><p>chamamos de solução da congruência linear a</p><p>todo inteiro de modo que:</p><p>ax ≡ b ( mod m)</p><p>a, b ∈ Z.</p><p>a ≠ 0.</p><p>m</p><p>x</p><p>3x ≡ 5 ( mod 8)</p><p>x ≡ 8 ( mod 9)</p><p>5x ≡ −3 ( mod 7)</p><p>ax ≡ b ( mod m)</p><p>x0,</p><p>ax0 ≡ b ( mod m)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 35/101</p><p>Exemplo 1</p><p>Considere a congruência linear</p><p>Veja que é uma solução dessa equação de congruência.</p><p>Observe que se, e somente se</p><p>Em outras palavras, isso significa que, se existe um inteiro tal que</p><p>então o problema de determinar todos os inteiros que</p><p>satisfazem a equação de congruência linear acaba se reduzindo ao</p><p>problema de se obter todas as soluções da equação diofantina linear</p><p>Observe a fórmula!</p><p>Veja que, se é uma solução da congruência linear</p><p>então todos os inteiros da forma em</p><p>que é um inteiro arbitrário também são soluções da congruência linear</p><p>pois:</p><p>Exemplo 2</p><p>Considere a congruência linear é uma</p><p>solução dessa equação de congruência. Entenda melhor!</p><p>Ou seja, todos os inteiros da forma também serão soluções</p><p>dessa congruência para todo inteiro.</p><p>Note que, a partir de uma solução particular de uma congruência</p><p>linear podemos encontrar uma infinidade de</p><p>outras soluções, todas mutuamente congruentes módulo</p><p>Comentário</p><p>Sejam e duas soluções quaisquer da congruência linear</p><p>então, podemos escrever:</p><p>Essas soluções não são consideradas soluções diferentes, isto é, o</p><p>número de soluções da congruência linear é dado</p><p>pelo número de soluções mutuamente incongruentes módulo que</p><p>satisfazem a equação de congruência.</p><p>Exemplo 3</p><p>4x ≡ 7 ( mod 5).</p><p>x0 = 3</p><p>4(3) ≡ 7 ( mod 5)</p><p>12 ≡ 7 ( mod 5)</p><p>ax0 ≡ b ( mod m) m ∣ (ax0 − b).</p><p>y0</p><p>ax0 − b = my0,</p><p>ax − my = b.</p><p>ax ≡ b ( mod m)</p><p>x0</p><p>ax ≡ b ( mod m), x0 + km,</p><p>k</p><p>ax ≡ b ( mod m),</p><p>a (x0 + km) ≡ ax0 ≡ b ( mod m)</p><p>3x ≡ 9 ( mod 12). x0 = 3</p><p>3(3) ≡ 9 ( mod 12) ⇒ 9 ≡ 9 ( mod 12)</p><p>3 + 12k</p><p>k</p><p>x0</p><p>ax ≡ b ( mod m),</p><p>m.</p><p>x0 x1</p><p>ax ≡ b ( mod m), x0 ≡ x1 ( mod m).</p><p>ax ≡ b ( mod m)</p><p>m</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 36/101</p><p>Dada a congruência linear temos que e</p><p>são soluções da equação e são congruentes módulo 12.</p><p>Logo, não são contadas como soluções distintas dessa congruência.</p><p>Comentário</p><p>Podemos observar que uma congruência linear pode ter apenas uma</p><p>solução, ter várias soluções ou não ter soluções.</p><p>Teorema 1: condição de existência da solução</p><p>A congruência linear tem solução se, e somente</p><p>se divide sendo</p><p>Demonstração</p><p>(Ida)</p><p>Hipótese: A congruência linear tem solução.</p><p>Considerando o inteiro solução da equação</p><p>temos:</p><p>Consequentemente, existe um inteiro tal que:</p><p>Em que o par de inteiros é uma solução da equação diofantina</p><p>linear associada à congruência linear</p><p>Como temos que e Segue, então que</p><p>e, portanto,</p><p>(Volta)</p><p>Hipótese: divide sendo</p><p>Considerando que podemos escrever que em que é um</p><p>inteiro.</p><p>Como então existem inteiros e tais que:</p><p>(1)</p><p>3x ≡ 9 ( mod 12), x0 = 3</p><p>x1 = −9</p><p>x0 ≡ x1 ( mod m)</p><p>3 ≡ −9 ( mod 12)</p><p>ax ≡ b ( mod m)</p><p>d b(d ∣ b), d = mdc(a,m).</p><p>ax ≡ b ( mod m)</p><p>x0 ax ≡ b ( mod m),</p><p>ax0 ≡ b ( mod m) ⇒ m ∣ (ax0 − b)</p><p>y0,</p><p>ax0 − b = my0  ou  ax0 − my0 = b</p><p>(x0, y0)</p><p>ax ≡ b ( mod m).</p><p>ax + (−m)y = b</p><p>d = mdc(a,m), d ∣ a d ∣ m.</p><p>d ∣ (ax0 − my0) d ∣ b.</p><p>d b(d ∣ b), d = mdc(a,m).</p><p>d ∣ b, b = dk, k</p><p>d = mdc(a,m), x0 y0,</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 37/101</p><p>Vamos multiplicar os dois lados da equação (1) por :</p><p>Como temos:</p><p>(2)</p><p>Veja que de (2), temos a seguinte congruência:</p><p>Logo, o inteiro é uma solução da congruência linear.</p><p>Com o próximo teorema, veremos como resolver as congruências</p><p>lineares.</p><p>Teorema 2: soluções da congruência linear</p><p>Se divide sendo então a congruência linear</p><p>tem precisamente soluções mutuamente</p><p>incongruentes módulo</p><p>Demonstração</p><p>Sabemos que a congruência é equivalente à</p><p>equação diofantina linear. Veja!</p><p>Essa equação tem solução se, e somente se divide</p><p>Considerando que e o par de inteiros é uma solução</p><p>particular da equação temos então que as outras</p><p>soluções dessa equação são da forma:</p><p>(1)</p><p>ax0 + my0 = d</p><p>k</p><p>a (kx0) + m (ky0) = dk</p><p>b = dk,</p><p>a (kx0) + m (ky0) = b</p><p>a (kx0) − b = m (−ky0)</p><p>a (kx0) ≡ b ( mod m)</p><p>ax ≡ b ( mod m)</p><p>d b(d ∣ b), d = mdc(a,m),</p><p>ax ≡ b ( mod m) d</p><p>m.</p><p>ax ≡ b ( mod m)</p><p>ax − my = b</p><p>d = mdc(a,m)</p><p>b, (d ∣ b).</p><p>d ∣ b x0, y0</p><p>ax − my = b,</p><p>x = x0 + (m</p><p>d</p><p>)k</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 38/101</p><p>(2)</p><p>Em que é um inteiro arbitrário.</p><p>Na equação (1) vamos considerar somente os valores obtidos quando</p><p>atribuímos ao inteiro os valores isto é, os</p><p>inteiros:</p><p>Vamos mostrar agora que esses inteiros são mutuamente</p><p>incongruentes módulo e que todos os outros inteiros dados pela</p><p>fórmula são congruentes módulo a algum</p><p>desses inteiros.</p><p>Vamos mostrar agora que esses inteiros são mutuamente</p><p>incongruentes módulo e que todos os outros inteiros dados pela</p><p>fórmula são congruentes módulo a algum</p><p>desses inteiros.</p><p>De fato, se:</p><p>Em que teríamos:</p><p>Dado que o podemos cancelar o fator comum</p><p>o que dá a congruência:</p><p>Observe que isso significa que o que é impossível, pois</p><p>Temos que qualquer outro inteiro é congruente módulo</p><p>a algum dos inteiros acima enumerados.</p><p>Considerando o algoritmo da divisão, temos:</p><p>Concluímos que:</p><p>y = y0 + ( a</p><p>d</p><p>)k</p><p>k</p><p>k 0, 1, 2, ⋯ , d − 1, d</p><p>x0,x0 +</p><p>m</p><p>d</p><p>,x0 + 2(m</p><p>d</p><p>), ⋯ ,x0 + (d − 1)(m</p><p>d</p><p>)</p><p>d</p><p>m</p><p>x = x0 + (m/d)k m</p><p>d</p><p>x0,x0 +</p><p>m</p><p>d</p><p>,x0 + 2(m</p><p>d</p><p>), ⋯ ,x0 + (d − 1)(m</p><p>d</p><p>)</p><p>d</p><p>m</p><p>x = x0 + (m/d)k m</p><p>d</p><p>x0 + (m/d)k1 ≡ x0 + (m/d)k2 ( mod m)</p><p>0 ≤ k1 ≤ k2 ≤ d − 1,</p><p>(m/d)k1 ≡ (m/d)k2 ( mod m)</p><p>mdc(m/d,m) = m/d,</p><p>m/d,</p><p>k1 ≡ k2 ( mod d)</p><p>d ∣ (k1 − k2),</p><p>0 < k2 − k1 < d.</p><p>x0 + (m/d)k1</p><p>m d</p><p>k = dq + r,  onde  0 ≤ r ≤ d − 1</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 39/101</p><p>Logo,</p><p>Em que é um dos inteiros que foram selecionados.</p><p>Comentário</p><p>De acordo com o teorema 2, a congruência linear</p><p>possui soluções mutuamente incongruentes módulo</p><p>Se é uma solução qualquer da congruência linear</p><p>então, as suas soluções</p><p>mutuamente incongruentes módulo são os inteiros</p><p>Corolário sobre a condição de existência da</p><p>solução</p><p>Se então a congruência linear</p><p>tem uma única solução módulo</p><p>Exemplo 1</p><p>Dada a congruência linear determine sua</p><p>solução.</p><p>Solução</p><p>Inicialmente, devemos determinar o Observe a tabela!</p><p>quocientes 2 3</p><p>42 18 6</p><p>restos 6 0</p><p>Tabela: Algoritmo de Euclides para o exemplo.</p><p>Ana Lucia de Sousa.</p><p>e como a congruência dada possui 6</p><p>soluções. Vamos considerar uma solução inteira da</p><p>congruência linear.</p><p>x0 + (m/d)k1 = x0 + (m/d)(dq + r) = x0 + mq + (m/d)r</p><p>x0 + (m/d)k ≡ x0 + (m/d)r ( mod m)</p><p>x0 + (m/d)r d</p><p>ax ≡ b ( mod m)</p><p>d m.</p><p>x0</p><p>ax ≡ b ( mod m), d = mdc(a,m)</p><p>m</p><p>x0,x0 + m/d, x0 + 2(m/d), ⋯ ,x0 + (d − 1)(m/d).</p><p>mdc(a,m) = 1, ax ≡ b ( mod m)</p><p>m.</p><p>18x ≡ 30 ( mod 42),</p><p>mdc(18, 42).</p><p>mdc(18, 42) = 6 6 ∣ 30,</p><p>x0 = 4</p><p>18x ≡ 30 ( mod 42)</p><p>18(4) ≡ 30 ( mod 42)</p><p>72 ≡ 30 ( mod 42),  pois 42 ∣ (72 − 30)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 40/101</p><p>As 6 soluções são dadas por:</p><p>Isto é, os inteiros:</p><p>Exemplo 2</p><p>Resolva a congruência linear</p><p>Solução</p><p>Veja que o e Logo, a congruência dada não</p><p>possui solução.</p><p>Exemplo 3</p><p>Resolva a congruência linear</p><p>Solução</p><p>Vamos determinar o</p><p>quocientes 1 1</p><p>39 21 18</p><p>restos 18 3</p><p>Tabela: Algoritmo de Euclides para o exemplo.</p><p>Ana Lucia de Sousa.</p><p>Temos que o e Logo, a congruência dada</p><p>possui 3 soluções.</p><p>Uma solução da congruência pode ser obtida resolvendo</p><p>a equação</p><p>diofantina linear associada à congruência linear.</p><p>Pelo algoritmo de Euclides, temos:</p><p>(1)</p><p>x = 4 +</p><p>42</p><p>6</p><p>k = 4 + 7k, com k = 0, 1, 2, 3, 4, 5</p><p>x = 4, 11, 18, 25, 32, 39</p><p>8x ≡ 25 ( mod 6).</p><p>mdc(8, 6) = 2 2 ∤ 25.</p><p>21x ≡ 15 ( mod 39).</p><p>mdc(21, 39).</p><p>mdc(21, 39) = 3 3 ∣ 15.</p><p>21x − 39y = 15</p><p>18 = 39 − 1 ⋅ 21</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 41/101</p><p>(2)</p><p>Substituindo (1) em (2), temos:</p><p>Multiplicando por 5, obtemos:</p><p>Assim, temos que o par de inteiros e é uma solução</p><p>particular da equação diofantina linear e, portanto,</p><p>é uma solução da congruência:</p><p>Observação: não é solução da congruência linear!</p><p>Portanto, as 3 soluções mutuamente incongruentes módulo 39 dessa</p><p>congruência são dadas por:</p><p>Assim, temos as seguintes soluções: e</p><p>Exemplo 4</p><p>3 = 21 − 1 ⋅ 18</p><p>3 = 21 − 1(39 − 1 ⋅ 21)</p><p>3 = 21 − 1 ⋅ 39 + 1 ⋅ 21</p><p>3 = 2 ⋅ 21 − 1 ⋅ 39</p><p>21(2) − 39(1) = 3</p><p>21(2 ⋅ 5) − 39(1 ⋅ 5) = 3 ⋅ 5</p><p>21(10) − 39(5) = 15</p><p>x0 = 10 y0 = 5</p><p>21x − 39y = 15</p><p>x0 = 10</p><p>21x ≡ 15 ( mod 39)</p><p>21(10) ≡ 15 ( mod 39)</p><p>210 ≡ 15 ( mod 39),  pois 39 ∣ (210 − 15)</p><p>y0 = 5</p><p>21x ≡ 15 ( mod 39)</p><p>21(5) ≡ 15 ( mod 39)</p><p>105 ≡ 15 ( mod 39)</p><p>39 ∤ (105 − 15)</p><p>x = 10 + ( 39</p><p>3</p><p>)k = 10 + 13k, com k = 0, 1, 2</p><p>x = 10,x = 23 x = 26.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 42/101</p><p>Resolva a congruência</p><p>Solução</p><p>Veja que o Portanto, a congruência possui uma</p><p>única solução. Essa solução será obtida através da resolução da</p><p>equação diofantina linear associada a ela.</p><p>Confira a tabela!</p><p>quocientes 28 1</p><p>317 11 9</p><p>restos 9 2</p><p>Tabela: Algoritmo de Euclides para o exemplo.</p><p>Ana Lucia de Sousa.</p><p>Pelo algoritmo de Euclides,</p><p>(1)</p><p>(2)</p><p>(3)</p><p>Substituindo (2) em (3), temos:</p><p>(4)</p><p>Substituindo (1) em (4), temos:</p><p>11x ≡ 2 ( mod 317).</p><p>mdc(11, 317) = 1.</p><p>11x − 317y = 2</p><p>9 = 317 − 28 ⋅ 11</p><p>2 = 11 − 1 ⋅ 9</p><p>1 = 9 − 4 ⋅ 2</p><p>1 = 9 − 4 ⋅ (11 − 1 ⋅ 9)</p><p>1 = 9 − 4 ⋅ 11 + 4 ⋅ 9</p><p>1 = 5 ⋅ 9 − 4 ⋅ 11</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 43/101</p><p>Multiplicando por 2, obtemos:</p><p>Assim, temos que o par de inteiros e é uma</p><p>solução particular da equação diofantina linear e,</p><p>portanto, é a única solução da congruência:</p><p>Assim, temos a solução ou</p><p>Exemplo 5</p><p>Resolver a congruência .</p><p>Solução</p><p>O . Como 7 não divide 5 , a congruência não tem</p><p>solução.</p><p>Exemplo 6</p><p>Resolva a congruência</p><p>Solução</p><p>O Como então a congruência possui 4</p><p>soluções mutuamente incongruentes módulo 84.</p><p>1 = 5 ⋅ (317 − 28 ⋅ 11) − 4 ⋅ 11</p><p>1 = 5 ⋅ 317 − 140 ⋅ 11 − 4 ⋅ 11</p><p>1 = 5 ⋅ 317 − 144 ⋅ 11</p><p>317(5) − 11(144) = 1</p><p>11(−144) + 317(5) = 1</p><p>11(−144 ⋅ 2) + 317(5 ⋅ 2) = 1 ⋅ 2</p><p>11(−288) + 317(10) = 2</p><p>x0 = −288 y0 = 10</p><p>21x − 39y = 15</p><p>x0 = −288</p><p>11x ≡ 2 ( mod 317)</p><p>11(−288) ≡ 2 ( mod 317)</p><p>3168 ≡ 2 ( mod 317),  pois 317 ∣ (3168 − 2)</p><p>x = −288 + ( 317</p><p>1</p><p>)k = −288 + 317k, com t = 0</p><p>x = −288 + ( 317</p><p>1</p><p>)k = −288 + 317k, com t = 1</p><p>x = −288 x = −29.</p><p>35x ≡ 5( mod 14)</p><p>mdc(35, 14) = 7</p><p>64x ≡ 16 ( mod 84).</p><p>mdc(64, 84) = 4. 4 ∣ 16,</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 44/101</p><p>Cancelando o 16 nos dois lados da congruência, temos:</p><p>Como o então podemos dividir 84 por 4. Entenda</p><p>melhor!</p><p>O mdc então podemos cancelar 4 nos dois lados da</p><p>congruência. Observe!</p><p>Portanto, as 4 soluções mutuamente incongruentes módulo 84 dessa</p><p>congruência são dadas por:</p><p>Assim, temos as seguintes soluções inteiras:</p><p>e</p><p>Resolução das equações</p><p>diofantinas lineares por</p><p>16 ⋅ 4x ≡ 16 ⋅ 1 ( mod 84)</p><p>4x ≡ 1 ( mod 84)</p><p>mdc(64, 84) = 4,</p><p>4x ≡ 1 ( mod 21)</p><p>4x ≡ −20 ( mod 21)</p><p>4x ≡ 4 ⋅ (−5) ( mod 21)</p><p>(4, 21) = 1,</p><p>x ≡ −5( mod 21)</p><p>x ≡ 16( mod 21)</p><p>x = 16 + ( 84</p><p>4</p><p>)k = 16 + 21k,  com k = 0, 1, 2, 3</p><p>k = 0 ⇒ x = 16 + 21(0) = 16</p><p>k = 1 ⇒ x = 16 + 21(1) = 37</p><p>k = 2 ⇒ x = 16 + 21(2) = 58</p><p>k = 3 ⇒ x = 16 + 21(3) = 79</p><p>x = 16,x = 37,x = 58</p><p>x = 79.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 45/101</p><p>congruência</p><p>Vamos conhecer o teorema de Euler, que é uma generalização do</p><p>teorema de Fermat. Através do teorema de Euler, resolvemos problemas</p><p>que abordam a congruência modular.</p><p>Sabemos que a equação diofantina linear tem solução se</p><p>e somente se sendo Nesse caso, se o par de</p><p>inteiros é uma solução particular qualquer dessa equação, então:</p><p>Assim, para construir uma solução particular da equação diofantina</p><p>linear basta determinar uma solução qualquer da</p><p>congruência linear. Observe!</p><p>Depois, basta substituir o valor de na equação para</p><p>determinar o valor correspondente de tal que:</p><p>Observação: Também podemos obter uma solução particular da</p><p>equação diofantina determinando uma solução qualquer</p><p>da congruência linear by</p><p>Observe dois exemplos a seguir.</p><p>Inverso de um inteiro</p><p>De�nição</p><p>Considerando um número inteiro. Definimos de inverso de módulo</p><p>um inteiro tal que:</p><p>Nem todo inteiro tem um inverso módulo</p><p>Exemplo</p><p>ax + by = c</p><p>d ∣ c, d = mdc(a, b).</p><p>x0, y0</p><p>ax0 + by0 = c e ax0 − c = −by0</p><p>ax0 ≡ c( mod b)</p><p>ax + by = c, x = x0</p><p>ax ≡ c( mod b)</p><p>x0 ax + by = c</p><p>y0 y,</p><p>ax0 + by0 = c</p><p>ax + by = c</p><p>y = y0 ≡ c( mod a).</p><p>Exemplo 1 </p><p>Exemplo 2 </p><p>a a</p><p>m a∗,</p><p>aa∗ ≡ 1( mod m)</p><p>m.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 46/101</p><p>2 não tem um inverso módulo 4 , pois a congruência linear</p><p>não tem solução.</p><p>Teorema sobre a existência do inverso</p><p>Se então tem um único inverso módulo</p><p>Demonstração</p><p>Se então a congruência linear</p><p>possui uma única solução isto é:</p><p>Assim, o inteiro tem um único inverso módulo</p><p>Na sequência, vamos acompanhar um exemplo.</p><p>Exemplo</p><p>Por ser segue-se que o inverso de 5 módulo</p><p>8 é o próprio 5.</p><p>Note que:</p><p>e também são inversos de 5 módulo 8, mas isso não é</p><p>inconsistente com a unicidade do inverso de 5 módulo 8, pois:</p><p>Exemplos</p><p>Vamos determinar alguns pontos importantes.</p><p>O inverso de 2 módulo 5</p><p>O inverso de 7 módulo 9</p><p>O inverso de 12 módulo 17</p><p>2x ≡ 1( mod 4)</p><p>mdc(a,m) = 1 a m.</p><p>mdc(a,m) = 1 ax ≡ 1( mod ⋅m)</p><p>x0( mod ⋅m),</p><p>ax0 ≡ 1( mod ⋅m)</p><p>a m.</p><p>a∗ = x0</p><p>5 ⋅ 5 = 25 ≡ 1( mod ⋅8),</p><p>5(−3) ≡ 1( mod ⋅8) e 5 ⋅ 13 ≡ 1( mod ⋅8)</p><p>−3 13</p><p>−3 ≡ 5 ≡ 13( mod ⋅8)</p><p>2a∗ ≡ 1( mod 5)</p><p>a∗ = 3</p><p>7a∗ ≡ 1( mod 9)</p><p>a∗ = 4</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 47/101</p><p>Atividade discursiva</p><p>Resolva a congruência</p><p>Digite sua resposta aqui</p><p>Chave de resposta</p><p>O e, portanto, a congruência tem uma única</p><p>solução.</p><p>Veja que Assim, temos:</p><p>Como</p><p>Como temos</p><p>Como o</p><p>12a∗ ≡ 1( mod 17)</p><p>a∗ = 10</p><p></p><p>36x ≡ 53( mod 131).</p><p>mdc(36, 131) = 1</p><p>53x ≡ −78( mod 131).</p><p>36x ≡ −78 ( mod 131)</p><p>6 ⋅ 6x ≡ 6 ⋅ (−13)( mod 131)</p><p>mdc(36, 131) = 1</p><p>6x ≡ −13( mod ⋅131)</p><p>−13 ≡ −144( mod 131),</p><p>6x ≡ −144( mod 131)</p><p>6x ≡ 6(−24)( mod ⋅131)</p><p>mdc(36, 131) = 1,</p><p>x ≡ −24 ≡ 107( mod ⋅131)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 48/101</p><p>Teoria na prática</p><p>Um comerciante decidiu vender 225 ovos em caixas com 6 ou 15 ovos.</p><p>0 comerciante percebeu que poderia determinar a quantidade de caixas</p><p>através da equação diofantina em que a</p><p>quantidade de caixas para 6 ovos e a quantidade de caixas para 15</p><p>ovos. Como o ele escreveu a equação diofantina</p><p>como 75. Resolvendo a equação, ele encontrou a solução</p><p>geral e Considerando a solução</p><p>geral, determine as quantidades de caixas que serão necessárias para</p><p>ele realizar as vendas.</p><p>Mão na massa</p><p>Questão 1</p><p>Determine a solução da congruência</p><p>Parabéns! A alternativa A está</p><p>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>_black</p><p>6n + 15m = 225, n</p><p>m</p><p>mdc(6, 15) = 3,</p><p>2n + 5m =</p><p>n = −150 + 5t m = 75− 2t, t ∈ Z.</p><p>Mostrar solução</p><p></p><p>4x ≡ 12( mod 14).</p><p>A x ≡ 3 ( mod 7)</p><p>B x ≡ 3 ( mod 14)</p><p>C x ≡ 5 ( mod 14)</p><p>D x ≡ 8 ( mod 7)</p><p>E x ≡ 4 ( mod 14)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 49/101</p><p>Determine a solução da congruência</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>Marque a alternativa que indica o resto da divisão de 42023 por 7.</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 4</p><p>Determine o resto da divisão do número por 5</p><p>considerando que o número dividido por 5 deixa resto 2.</p><p>3x ≡ 5 ( mod 7).</p><p>A x ≡ 3 ( mod 7)</p><p>B x ≡ 3 ( mod 14)</p><p>C x ≡ 5 ( mod 14)</p><p>D x ≡ 8 ( mod 7)</p><p>E x ≡ 4 ( mod 7)</p><p>A 0</p><p>B 1</p><p>C 2</p><p>D 3</p><p>E 4</p><p>4n + 13</p><p>n</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 50/101</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>A congruência tem e solução</p><p>geral em que Marque a alternativa que indica</p><p>todas as soluções dessa congruência.</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>Determine a solução geral da equação diofantina por</p><p>congruência.</p><p>A 1</p><p>B 2</p><p>C 3</p><p>D 4</p><p>E 5</p><p>6x ≡ 3( mod 15) mdc(6, 15) = 3</p><p>x = −2 + 5t, t ∈ Z.</p><p>A -2, 1 e 5</p><p>B 11, 3 e 4</p><p>C 13, 3 e 8</p><p>D 10, 15 e 6</p><p>E 15, 1 e 8</p><p>7x + 6y = 9,</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 51/101</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'%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%3Dba8b7d052a124fb2</p><p>6%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%0A%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>A congruência tem e</p><p>solução geral em que Marque a alternativa que</p><p>indica todas as soluções dessa congruência.</p><p>A e x = −3 + 6t y = 1 − 3t</p><p>B e x = 3 + 2t y = −2 − 4t</p><p>C e x = −2 + 6t y = 2 − 5t</p><p>D e x = 1 + 4t y = −3 − 7t</p><p>E e x = 3 + 6t y = −2 − 7t</p><p>12x ≡ 8( mod 28) mdc(12, 28) = 4</p><p>x = 3 + 7t, t ∈ Z.</p><p>A 2, 3, 11 e 15</p><p>B 11, 3, 9 e 4</p><p>C 13, 3, 7 e 16</p><p>D 10, 15, 7 e 9</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 52/101</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>Determine a solução geral da equação diofantina</p><p>por congruência.</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>3 - Métodos de resolução de sistemas de</p><p>congruências lineares</p><p>E 3, 10, 17 e 24</p><p>11x + 27y = 4,</p><p>A e x = 20 + 27t y = −8 − 11t</p><p>B e x = 21 − 17t y = −9 − 23t</p><p>C e x = 22 + 26t y = −10 − 12t</p><p>D e x = 23 − 18t y = 8 + 11t</p><p>E e x = 24 + 25t y = 9 + 23t</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 53/101</p><p>Ao �nal deste módulo, você será capaz de reconhecer os métodos</p><p>para lidar com sistemas lineares congruentes.</p><p>Sistemas de congruências</p><p>lineares: métodos de</p><p>resolução</p><p>Assista ao vídeo e conheça os conceitos e exemplos de aplicação dos</p><p>sistemas de congruências lineares e o teorema chinês dos restos.</p><p>Sistemas de congruências</p><p>lineares</p><p>Vamos estudar os sistemas de congruências lineares. Eles são</p><p>formados por duas ou mais congruências lineares, e nosso objetivo é</p><p>resolver simultaneamente esses sistemas. Nesse caso, vamos</p><p>considerar congruências lineares com uma única solução.</p><p>Observe alguns exemplos de sistemas de congruências lineares!</p><p></p><p></p><p>Na resolução desses sistemas, nosso objetivo é encontrar todos os</p><p>inteiros que satisfazem todas as equações de congruência que formam</p><p>o sistema. O processo não é difícil, pois vamos usar o método da</p><p>substituição.</p><p>Exemplos</p><p>Exemplo 1</p><p>{x ≡ 1( mod 3)</p><p>x ≡ 2( mod 5)</p><p>⎧⎪⎨⎪⎩x ≡ 8( mod 9)</p><p>x ≡ 2( mod 3)</p><p>x ≡ 5( mod 7)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 54/101</p><p>Dado o seguinte sistema de congruências lineares, verifique que todo</p><p>inteiro satisfaz suas equações.</p><p>Solução</p><p>Podemos escolher qualquer uma das congruências para iniciar o</p><p>processo. Por exemplo, vamos considerar a primeira congruência</p><p>Vamos substituir na segunda congruência</p><p>e usar as propriedades das congruências.</p><p>Resolvendo essa congruência, encontramos:</p><p>Temos, então em que</p><p>Agora, substituímos em Entenda melhor!</p><p>O valor será substituído na terceira congruência</p><p>Resolvendo essa congruência, encontramos:</p><p>Temos, então em que</p><p>Substituindo em obtemos:</p><p>x ≡ 52 ( mod 105)</p><p>⎧⎪⎨⎪⎩x ≡ 1( mod 3)</p><p>x ≡ 2( mod 5)</p><p>x ≡ 3( mod 7)</p><p>x ≡ 1( mod 3).</p><p>x ≡ 1( mod 3) ⇒ x = 1 + 3k1 k1 ∈ Z</p><p>x = 1 + 3k1</p><p>x ≡ 2( mod 5)</p><p>x ≡ 2( mod 5)</p><p>1 + 3k1 ≡ 2( mod 5)</p><p>3k1 ≡ 1( mod 5)</p><p>k1 ≡ 2( mod 5)</p><p>k1 ≡ 2( mod 5) ⇒ k1 = 2 + 5k2, k2 ∈ Z.</p><p>k1 = 2 + 5k2 x = 1 + 3k1.</p><p>x = 1 + 3k1 ⇒ x = 1 + 3 (2 + 5k2) ⇒ x = 1 + 6 + 15k2 ⇒ x = 7 + 15k2</p><p>x = 7 + 15k2</p><p>x ≡ 3( mod 7).</p><p>x ≡ 3( mod 7)</p><p>7 + 15k2 ≡ 3( mod 7)</p><p>15k2 ≡ −4( mod 7)</p><p>k2 ≡ 3( mod 7).</p><p>k2 ≡ 3( mod 7) ⇒ k2 = 3 + 7k3, k3 ∈ Z.</p><p>k2 = 3 + 7k3 x = 7 + 15k2,</p><p>x = 7 + 15k2 ⇒ x = 7 + 15 (3 + 7k3) ⇒ x = 7 + 45 + 105k3 ⇒ x = 52 + 105k3</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 55/101</p><p>Portanto, verificamos que todo inteiro satisfaz</p><p>todas as congruências lineares. Vamos a algumas observações!</p><p>Exemplo 2</p><p>Resolva o sistema de congruência linear formado pelas equações</p><p>e</p><p>Solução</p><p>Dada a equação de congruência podemos escrever:</p><p>(1)</p><p>Agora, vamos substituir (1) em</p><p>Usando as propriedades de congruências, temos:</p><p>Multiplicando os dois lados da congruência por 16, obtemos:</p><p>x ≡ 52( mod 105)</p><p> Uma solução do sistema de congruências lineares</p><p>deve satisfazer cada uma das congruências.</p><p> Cada congruência linear do sistema possui solução</p><p>isolada, mas independente disso o sistema pode</p><p>não ter solução.</p><p> Se alguma congruência linear não possui solução, o</p><p>sistema também não terá.</p><p>x ≡ 5 ( mod 12) x ≡ 7 ( mod 19).</p><p>x ≡ 5( mod 12)</p><p>x = 12a + 5, a ∈ N</p><p>x ≡ 7 ( mod 19).</p><p>12a + 5 ≡ 7 ( mod 19)</p><p>12a ≡ 7 − 5( mod 19)</p><p>12a ≡ 2( mod 19)</p><p>6a ≡ 1( mod 19)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 56/101</p><p>Podemos escrever:</p><p>(2)</p><p>Substituindo (2) em (1), temos:</p><p>Portanto, é a solução do sistema.</p><p>Observação: temos um resultado que é muito interessante que também</p><p>pode ser utilizado na resolução de sistemas de congruências lineares.</p><p>Teorema: sejam e números inteiros,</p><p>então:</p><p>Teorema chinês dos restos</p><p>É através desse teorema que podemos resolver sistemas de</p><p>congruências lineares de modo mais simples. Esse teorema foi</p><p>proposto pelo matemático chinês Sun-Tsu, no século I, no seu livro de</p><p>aritmética Suan-Ching. O desenvolvimento do teorema foi motivado pela</p><p>ideia de encontrar um número que deixasse resto 2 quando dividido por</p><p>3; resto 2 quando dividido por 5; e por último, resto 2 quando dividido</p><p>por 7. A partir disso, ele formou o seguinte sistema:</p><p>O sistema de congruências lineares na forma geral é apresentado por:</p><p>16 ⋅ 6a ≡ 16 ⋅ 1( mod 19)</p><p>96a ≡ 16( mod 19)</p><p>a ≡ 16( mod 19)</p><p>a = 19b + 16, b ∈ N</p><p>x = 12(19b + 16) + 5 ⇒ x = 228b + 192 + 5 ⇒ x = 228b + 197</p><p>x ≡ 197 ( mod 228)</p><p>a, b ∈ Z m1,m2,m3 ⋯ ,mk</p><p>mi > 1,</p><p>a ≡ b mod (m1,m2,m3 ⋯ ,mr</p><p>mmc</p><p>)</p><p>⎧⎪⎨⎪⎩x ≡ 2( mod 3)</p><p>x ≡ 3( mod 5)</p><p>x ≡ 2( mod 7)</p><p>⎧⎪⎨⎪⎩a1x ≡ b1 ( mod m1)</p><p>a2x ≡ b2 ( mod m2)</p><p>⋮</p><p>akx ≡ bk ( mod mk)</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 57/101</p><p>Um sistema tem solução se cada uma das congruências tem solução.</p><p>Isto é, dado o então Mas</p><p>essa condição não é tão forte, pois podemos encontrar sistemas de</p><p>congruências lineares que não tem solução e cada congruência possui</p><p>solução isolada.</p><p>Vamos apresentar um lema que mostra como podemos construir um</p><p>sistema em uma forma mais simples, em que cada coeficiente é igual</p><p>a 1. A ideia do lema é encontrarmos um sistema equivalente da forma:</p><p>Lema sobre a congruência linear</p><p>A congruência linear em que o</p><p>com é equivalente a:</p><p>Demonstração</p><p>(Ida)</p><p>Considerando a congruência linear:</p><p>(1)</p><p>Substituindo e em (1), obtemos:</p><p>Podemos cancelar nos dois lados da congruência.</p><p>Como podemos escrever</p><p>Dividindo essa expressão por temos:</p><p>Portanto,</p><p>mdc (ai,mi) = di, di ∣ bi∀i = 1, ⋯ , k.</p><p>ai</p><p>⎧⎪⎨⎪⎩x ≡ c1 ( mod m1)</p><p>x ≡ c2 ( mod m2)</p><p>⋮</p><p>x ≡ ck ( mod mk)</p><p>ax ≡ b ( mod m), mdc(a,m) = d,</p><p>d ∣ b,</p><p>x ≡ rb1( mod n)</p><p>ax ≡ b( mod m)</p><p>a = a1d, b = b1d m = nd</p><p>ax ≡ b( mod m)</p><p>(a1d)x ≡ (b1d)( mod nd)</p><p>d</p><p>a1x ≡ b1( mod n)</p><p>d = ar + sm, d = (a1d)r + s(nd).</p><p>d,</p><p>1 = a1r + sn</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 58/101</p><p>Note que multiplicando a equação por obtemos:</p><p>(2)</p><p>Como segue que Ou seja,</p><p>(Volta)</p><p>Por hipótese, temos:</p><p>(1)</p><p>Considerando o seguinte:</p><p>(2)</p><p>E multiplicando (1) e (2), obtemos:</p><p>Como então temos que</p><p>Agora, podemos cancelar nos dois lados da congruência</p><p>Assim, obtemos:</p><p>(3)</p><p>Mas sabemos que e logo:</p><p>Agora, podemos substituir e em (3).</p><p>ra1 ≡ 1( mod n)</p><p>a1x ≡ b1( mod n) r,</p><p>ra1x ≡ rb1( mod n)</p><p>ra1 ≡ 1( mod n), x ≡ a1rx( mod n).</p><p>x ≡ rb1( mod n)</p><p>x ≡ rb1( mod n)</p><p>ra1 ≡ 1( mod n)</p><p>xra1 ≡ rb1( mod n)</p><p>1 = a1r + sn, mdc(r,n) = 1.</p><p>r</p><p>xra1 ≡ rb1( mod n).</p><p>xa1 ≡ b1( mod n)</p><p>a = a1d, b = b1d m = nd,</p><p>a = a1d ⇒ a1 = a</p><p>d</p><p>b = b1d ⇒ b1 = b</p><p>d</p><p>m = nd ⇒ n = m</p><p>d</p><p>a1, b1 n</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 59/101</p><p>Podemos concluir que</p><p>Exemplo</p><p>Dada a congruência linear encontre uma</p><p>congruência linear equivalente a ela na forma</p><p>Solução</p><p>Dada a congruência linear temos</p><p>De acordo com o lema, temos que determinar em</p><p>que e</p><p>Da congruência e Então:</p><p>Dado que</p><p>Assim, a congruência linear é equivalente à</p><p>congruência linear</p><p>Observe que a solução geral é com inteiro.</p><p>Dessa forma, podemos resolver, através do teorema dos restos chinês,</p><p>um sistema de congruência linear equivalente de forma mais simples.</p><p>Confira!</p><p>Entendendo o teorema chinês dos restos</p><p>Sejam números inteiros positivos e primos entre si dois</p><p>a dois. Ou seja, se Então, nessas condições, o</p><p>xa1 ≡ b1( mod n)</p><p>x( a</p><p>d</p><p>) ≡ ( b</p><p>d</p><p>)( mod</p><p>m</p><p>d</p><p>)</p><p>ax ≡ b( mod m).</p><p>6x ≡ 10( mod 4),</p><p>x ≡ c( mod n).</p><p>6x ≡ 10( mod 4), mdc(6, 10) = 2.</p><p>x ≡ rb1( mod n),</p><p>b = b1d, d = ar + sm m = nd.</p><p>6x ≡ 10( mod 4), a = 6, b = 10 m = 4.</p><p>b = b1d ⇒ b1 =</p><p>10</p><p>2</p><p>= 5</p><p>m = nd ⇒ n =</p><p>4</p><p>2</p><p>= 2</p><p>d = ar + sm ⇒ 2 = 6r + 4s ⇒ 2 = 6(1) + 4(−1) ⇒ r = 1</p><p>x ≡ rb1( mod n) ⇒ x ≡ 1 ⋅ 5( mod 2) ⇒ x ≡ 5( mod 2).</p><p>6x ≡ 10( mod 4)</p><p>x ≡ 5( mod 2).</p><p>x = 5 + 2k, k</p><p>⇓</p><p>⎧⎪⎨⎪⎩a1x ≡ b1 ( mod m1)</p><p>a2x ≡ b2 ( mod m2)</p><p>⋮</p><p>akx ≡ bk ( mod mk)</p><p>⎧⎪⎨⎪⎩x ≡ c1 ( mod m1)</p><p>x ≡ c2 ( mod m2)</p><p>⋮</p><p>x ≡ ck ( mod mk)</p><p>n1,n2, ⋯ ,nr</p><p>mdc (ni,nj) = 1 i ≠ j.</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 60/101</p><p>sistema de congruências lineares possui uma única solução módulo</p><p>Entenda melhor!</p><p>Vamos a uma demonstração, para entendermos de forma prática.</p><p>Demonstração</p><p>Temos por hipótese que números inteiros positivos e</p><p>primos entre si dois a dois. Sendo assim, podemos considerar o produto</p><p>de todos os inteiros expressos por excluindo para</p><p>inteiros. Veja!</p><p>Pela hipótese, temos que Logo, a congruência linear</p><p>possui uma única solução</p><p>Assim, vamos verificar que o inteiro</p><p>satisfaz todas as equações</p><p>de congruências do sistema dado. Em outras palavras, podemos dizer</p><p>que é uma solução do sistema.</p><p>De fato, se considerarmos então e</p><p>mas isso implica o seguinte:</p><p>Como a congruência possui uma única solução</p><p>temos:</p><p>Portanto:</p><p>Provamos que é uma solução do sistema de congruências lineares.</p><p>Agora, podemos provar a unicidade dessa solução simplesmente</p><p>supondo uma outra solução do sistema. Temos o seguinte:</p><p>n = n1n2 ⋯nr.</p><p>⎧⎪⎨⎪⎩x ≡ b1 ( mod n1)</p><p>x ≡ b2 ( mod n2)</p><p>⋮</p><p>x ≡ br ( mod nr)</p><p>n1,n2, ⋯ ,nr</p><p>Nk ni</p><p>k = 1, 2, 3, ⋯ , r</p><p>Nk =</p><p>n</p><p>nk</p><p>= n1n2 ⋯nk−1nk+1 ⋯nr</p><p>mdc (ni,nj) = 1.</p><p>Nkx ≡ 1 ( mod nk) xk.</p><p>X = b1N1x1 + b2N2x2 + ⋯ + brNrxr</p><p>X</p><p>i ≠ j, nk ∣ Ni Ni ≡ 0 ( mod nk),</p><p>X = b1N1x1 + b2N2x2 + ⋯ + brNrxr ≡ brNrxr ( mod nk)</p><p>Nkx ≡ 1 ( mod nk)</p><p>xk,</p><p>Nkxk ≡ 1 ( mod nk)</p><p>X ≡ bk ⋅ 1 ( mod nk)</p><p>X ≡ bk ( mod nk)</p><p>X</p><p>X1</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 61/101</p><p>Como o temos:</p><p>Ou seja,</p><p>Assim, finalizamos a demonstração do teorema chinês dos restos.</p><p>Exemplo</p><p>Determine a solução do sistema de congruências lineares através do</p><p>teorema chinês dos restos.</p><p>Solução</p><p>Precisamos verificar, inicialmente, se o sistema de congruências possui</p><p>solução. Como o o sistema possui solução e</p><p>podemos usar o teorema do resto chinês.</p><p>A solução do sistema é dada por:</p><p>Em que:</p><p>é a classe inversa do Ou seja, Observe!</p><p>X ≡ bk ( mod nk)</p><p>X ≡ X1 ( mod nk),  tal que nk ∣ (X − X1) para k = 1, 2, 3, ⋯ , r inteiros</p><p>mdc (ni,nj) = 1,</p><p>n1n2 ⋯nr ∣ (X − X1)</p><p>n ∣ (X − X1)  e  X ≡ X1( mod n)</p><p>⎧⎪⎨⎪⎩x ≡ 2( mod 3)</p><p>x ≡ 3( mod 5)</p><p>x ≡ 2( mod 7)</p><p>mdc(3, 5, 7) = 1,</p><p>X ≡ c1M1y1 + c2M2y2 + c3M3y3 ( mod m1 ⋅ m2 ⋅ m3)</p><p>M = m1 ⋅ m2 ⋅ m3 ⇒ M = 2 ⋅ 5 ⋅ 7 ⇒ M = 105</p><p>c1 = 2, c2 = 3 e c3 = 2</p><p>M1 =</p><p>M</p><p>m1</p><p>=</p><p>105</p><p>3</p><p>= 35</p><p>M2 =</p><p>M</p><p>m2</p><p>=</p><p>105</p><p>5</p><p>= 21</p><p>M3 =</p><p>M</p><p>m3</p><p>=</p><p>105</p><p>7</p><p>= 15</p><p>y1 M1. M1y1 ≡ 1 ( mod 3).</p><p>23/04/2024, 19:20 Congruências, sistemas lineares e funções aritméticas</p><p>https://stecine.azureedge.net/repositorio/00212en/40915/index.html?brand=estacio# 62/101</p><p>Logo,</p><p>é a classe inversa do Ou seja, Veja!</p><p>Logo,</p><p>é a classe inversa do Ou seja, Veja!</p><p>Logo,</p><p>Substituindo os valores encontrados na equação:</p><p>Obtemos o seguinte:</p><p>solução do sistema de congruências lineares.</p><p>Teorema sobre sistemas de congruências</p><p>lineares</p><p>Sejam números inteiros positivos e primos entre si</p><p>dois a dois. Ou seja, se Sejam, ainda,</p><p>números inteiros tais que o para</p><p>Então, nessas condições, o sistema de congruências lineares a seguir</p><p>possui uma única solução módulo</p><p>35y1 ≡ 1 ( mod 3)</p><p>2y1 ≡ 1 ( mod 3)</p><p>y1 = 2.</p><p>y2 M2. M2y2 ≡ 1 ( mod 5).</p><p>21y2 ≡ 1 (</p>