{"id":219855,"date":"2024-06-04T18:02:22","date_gmt":"2024-06-04T21:02:22","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=219855"},"modified":"2025-06-23T23:02:02","modified_gmt":"2025-06-24T02:02:02","slug":"a-sala-de-estudo-aritmetica-dos-restos","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/a-sala-de-estudo-aritmetica-dos-restos\/","title":{"rendered":"(A) Sala de Estudo: Aritm\u00e9tica dos Restos"},"content":{"rendered":"

Clique no bot\u00e3o abaixo para visualizar a Sala.<\/p>\n

\n <\/p>\n
\n
\n
Aritm\u00e9tica dos Restos
\n<\/strong><\/div>\n
\n
\n
<\/p>\n
\n1)<\/strong> J\u00falia tem 132 balas e deseja dividi-las, inicialmente, entre 15 amigos e, o que sobrar, entre outros 5 amigos. Quantas balas sobrar\u00e3o para J\u00falia?
\n2)<\/strong> Agora, J\u00falia quer dividir um n\u00famero diferente de balas entre 13 amigos, de modo que cada um deles receba 4 balas a mais do que restar\u00e1 a ela. Quais as quantidades poss\u00edveis de balas que J\u00falia pode ter?<\/em>\n<\/div>\n

<\/center><\/p>\n

\nMuitas quest\u00f5es em nosso cotidiano, como as apresentadas acima, envolvem restos; e o ramo da Matem\u00e1tica respons\u00e1vel pelo seu estudo \u00e9 a Aritm\u00e9tica dos Restos<\/strong><\/span> ou Aritm\u00e9tica Modular<\/strong><\/span>. Apesar de quest\u00f5es como estas serem resolvidas comumente pelo “Algoritmo da Divis\u00e3o Euclidiana”, alguns problemas e demonstra\u00e7\u00f5es mais complexas exigem um conhecimento aprofundado do assunto, bem como nota\u00e7\u00f5es mais elaboradas.
\nH\u00e1 muito estudo sobre o tema em livros sobre Aritm\u00e9tica e Teoria dos N\u00fameros. No entanto, apesar de utilizarmos os restos de divis\u00f5es para resolver in\u00fameros problemas, tanto te\u00f3ricos quanto reais, esse assunto n\u00e3o est\u00e1 presente nos curr\u00edculos do Ensino M\u00e9dio e, portanto, o material destinado aos alunos nessa fase de ensino \u00e9 escasso.
\nO objetivo desta Sala de Estudos \u00e9 permitir que voc\u00ea, caro leitor, aprofunde um pouco mais seus conhecimentos acerca dos elementos da divis\u00e3o e, sobretudo, do resto<\/strong>. Ao final do conte\u00fado, apresentaremos tamb\u00e9m alguns problemas sobre o assunto, muito comuns tanto em concursos e vestibulares como em Olimp\u00edadas de Matem\u00e1tica mais avan\u00e7adas.
\nSe voc\u00ea ficou curioso(a) com rela\u00e7\u00e3o \u00e0s solu\u00e7\u00f5es dos problemas apresentados acima, \u00e9 s\u00f3 clicar no bot\u00e3o abaixo!<\/p>\n

\n

<\/p>\n
\n
\n1)<\/strong> A divis\u00e3o de 132 por 15 deixa resto 12 (132=15\u00d78+12) e a divis\u00e3o de 12 por 5 deixa resto 2 (12=2\u00d75+2); portanto, sobrar\u00e3o 2 balas para J\u00falia.
\n2)<\/strong> Pelo Algoritmo da Divis\u00e3o Euclidiana, o qual veremos logo adiante, temos que o problema pode ser equacionado do seguinte modo: sendo [tex]a[\/tex] a quantidade inicial de balas, ent\u00e3o:
\n [tex]\\quad a=13(r+4)+r[\/tex], sendo [tex]0\\leq r \\leq12, r \\in \\mathbb{\u2124}. [\/tex]
\nOs valores positivos de [tex]a[\/tex] que podem ser obtidos a partir dessas informa\u00e7\u00f5es s\u00e3o, portanto, os seguintes:
\n[tex]\\qquad a \\in \\{52,66,80,94,108,122,136,150,164,178,192,206,220\\}.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n

I – Divis\u00e3o e Aritm\u00e9tica: Um pouco de Hist\u00f3ria…<\/p>\n

          De acordo com os historiadores, quem introduziu o estudo da Matem\u00e1tica na Gr\u00e9cia, ber\u00e7o do pensamento ocidental, foi Tales de Mileto<\/strong> (640-546 a.C.). Tales teria trazido consigo para a Gr\u00e9cia os conhecimentos de Geometria e Aritm\u00e9tica que aprendera com os sacerdotes eg\u00edpcios. Interessado em Astronomia e Filosofia, Tales difundiu a Geometria na sua cidade, chamada Mileto. Ao faz\u00ea-lo, acabou por introduzir uma inova\u00e7\u00e3o revolucion\u00e1ria que em muito se diferia da matem\u00e1tica eg\u00edpcia: a ideia de que as verdades matem\u00e1ticas devem ser provadas. A diferen\u00e7a entre a Matem\u00e1tica que se iniciava na Gr\u00e9cia Antiga e a eg\u00edpcia era que, enquanto para os eg\u00edpcios ela se tratava de uma arte que os auxiliava em seus trabalhos de engenharia e agrimensura, na Gr\u00e9cia ela adquiriu de fato um car\u00e1ter cient\u00edfico, gra\u00e7as \u00e0 atividade filos\u00f3fica que l\u00e1 j\u00e1 se desenvolvia. (Para saber mais sobre Tales de Mileto, clique AQUI<\/span><\/strong><\/a>.)
\n          Logo em seguida, foi Pit\u00e1goras de Samos<\/strong> (580-500 a.C.), disc\u00edpulo de Tales, quem, juntamente com sua famosa e hist\u00f3rica Escola Pitag\u00f3rica, se encarregou de desenvolver e difundir a Matem\u00e1tica pela Gr\u00e9cia e suas col\u00f4nias. A Escola Pitag\u00f3rica atribu\u00eda aos n\u00fameros um poder m\u00edstico, havendo uma ideia de que o Universo era regido por uma intelig\u00eancia superior, essencialmente matem\u00e1tica. (Para saber mais sobre Pit\u00e1goras, clique agora AQUI<\/span><\/strong><\/a>.)
\n          Os gregos tinham uma forte inclina\u00e7\u00e3o \u00e0 filosofia e \u00e0 l\u00f3gica, de modo que isto influenciou fortemente toda a sua cultura e, particularmente, seu modo de fazer Matem\u00e1tica. Um grande exemplo disso foi o fil\u00f3sofo Plat\u00e3o <\/strong>(429-348 a.C.) que, apesar de n\u00e3o ser matem\u00e1tico, nela via um treinamento indispens\u00e1vel ao fil\u00f3sofo, pois ressaltava a metodologia axiom\u00e1tico-dedutiva a ser seguida, de acordo com ele, em todos os campos do conhecimento. A import\u00e2ncia que Plat\u00e3o atribu\u00eda \u00e0 Matem\u00e1tica era t\u00e3o forte que o fez escrever no portal de sua escola a famosa frase \u201cQue n\u00e3o entre nesse local algu\u00e9m ignorante em Geometria<\/em>\u201d.
\n          Com toda essa heran\u00e7a cultural, surge em Alexandria, por volta de 300 a.C., um tratado que futuramente viria a se tornar um dois mais importantes da Matem\u00e1tica, Os Elementos<\/em><\/strong>, de Euclides<\/strong>. Esse tratado, composto por treze livros, cont\u00e9m a maior parte do conhecimento matem\u00e1tico da \u00e9poca sistematizado.
\n          Dos treze livros de Os Elementos, dez tratam de Geometria e tr\u00eas, de \u00c1lgebra. Em um desses tr\u00eas, o livro VII, Euclides define os conceitos de divisibilidade, de n\u00famero primo, de n\u00fameros perfeitos, de m\u00e1ximo divisor comum (MDC) e m\u00ednimo m\u00faltiplo comum (MMC), entre outros. Nesse livro, al\u00e9m das defini\u00e7\u00f5es feitas, todas bem definidas e at\u00e9 hoje muito utilizadas, encontra-se enunciada a divis\u00e3o com resto de um n\u00famero natural por outro, chamada divis\u00e3o euclidiana<\/strong>. Com o uso dessa divis\u00e3o, Euclides estabelece o algoritmo mais eficiente para se fazer o c\u00e1lculo do MDC entre dois inteiros, chamado de Algoritmo de Euclides<\/strong>. (Para saber mais sobre Euclides, clique AQUI<\/span><\/strong><\/a>.)
\n          Ap\u00f3s Euclides, a Aritm\u00e9tica estagnou-se por cerca de 500 anos, tendo ressuscitado com os trabalhos de Diofanto de Alexandria<\/strong>. A obra que ele nos legou chama-se Arithmetica <\/em> e foi escrita tamb\u00e9m em treze volumes, apesar de nem todos terem chegado at\u00e9 n\u00f3s, de modo a tornar-se o primeiro trabalho de \u00c1lgebra com abordagem n\u00e3o revestida de qualquer linguagem ou interpreta\u00e7\u00e3o t\u00e3o somente geom\u00e9trica, como fizeram seus predecessores. Tido por muitos como \u201cpai da \u00e1lgebra\u201d, uma das importantes contribui\u00e7\u00f5es de Diofanto s\u00e3o as chamadas equa\u00e7\u00f5es diofantinas<\/strong>, as quais ser\u00e3o melhor exploradas nos t\u00f3picos seguintes. (Para saber mais sobre Diofanto, clique AQUI<\/span><\/strong><\/a>.)<\/p>\n

\n
\n
\n

II – A Divis\u00e3o Euclidiana<\/p>\n

A Divis\u00e3o Euclidiana, ou divis\u00e3o com resto, \u00e9 uma opera\u00e7\u00e3o que toda crian\u00e7a aprende na escola. Escrita de maneira formal, e n\u00e3o como ela \u00e9 tratada nas s\u00e9ries iniciais do Ensino Fundamental, a Divis\u00e3o Euclidiana afirma o seguinte:
\n

<\/p>\n
\n➤<\/span> Dados [tex]x,y \\in \\mathbb{N}, \\,y\\ne 0[\/tex], existem \u00fanicos n\u00fameros naturais [tex]q,\\,r[\/tex], chamados respectivamente de quociente e resto, tais que
\n[tex]\\qquad x=y \\cdot q+r[\/tex], com [tex] 0 \\leq r \\lt y.[\/tex]
\nVeja o esqueminha:
\n[tex]\\qquad \\qquad ~~~~~~~~~~~~~~~~~~~~ \\begin{array}{r}
\nx \\, \\end{array} \\begin{array}{|r}
\n \\, y \\, \\, \\, \\\\ \\hline
\n\\end{array}[\/tex]
\n[tex]\\qquad \\qquad ~~~~~~~~~~~~~~~~~~~~ \\begin{array}{r}
\nr
\n\\end{array}\\begin{array}{r}
\n \\, \\, \\, q
\n\\end{array}\\qquad \\qquad[\/tex]<\/div>\n

<\/center>
\nPara os nossos prop\u00f3sitos, precisaremos estender esse resultado para o conjunto dos n\u00fameros inteiros e, portanto, trabalharemos com o seguinte enunciado para a Divis\u00e3o de Euclides:
\n

<\/p>\n
Dados [tex]x,y \\in \\mathbb{Z}, \\,y\\ne 0[\/tex], existem \u00fanicos inteiros [tex]q,\\,r[\/tex], chamados respectivamente de quociente <\/strong>e resto<\/strong>, tais que [tex]x=y \\cdot q+r[\/tex], com [tex] 0 \\leq r \\lt |y|.[\/tex]<\/div>\n

<\/center><\/p>\n

As duas vers\u00f5es podem ser demonstradas pelo chamado Princ\u00edpio da Boa Ordem ou Princ\u00edpio da Boa Ordena\u00e7\u00e3o, o qual garante que: “Todo subconjunto n\u00e3o vazio do conjunto dos n\u00fameros naturais possui um menor elemento”.<\/p>\n

Um caso particular, e geralmente o mais explorado ao iniciarmos o aprendizado sobre o processo de divis\u00e3o quando crian\u00e7as, \u00e9 o caso em que a divis\u00e3o \u00e9 dita exata. Neste caso, o resto da divis\u00e3o \u00e9 igual a zero e podemos falar sobre o conceito de divisibilidade.
\n

<\/p>\n
\n
Divisibilidade<\/span><\/strong><\/center>
\nDefini\u00e7\u00e3o:<\/strong> Dados n\u00fameros inteiros [tex]a~[\/tex] e [tex]~b[\/tex], com [tex]b \\ne 0[\/tex], dizemos que [tex]b[\/tex] divide [tex]a[\/tex], ou que [tex]b[\/tex] \u00e9 divisor de [tex]a[\/tex], ou ainda que [tex]a[\/tex] \u00e9 m\u00faltiplo de [tex]b[\/tex], quando existe um valor inteiro [tex]q[\/tex] tal que [tex]a=b \\cdot q[\/tex], e neste caso denotamos [tex]b \\mid a[\/tex].
\nQuando n\u00e3o existe um inteiro [tex]q[\/tex] satisfazendo [tex]a=b \\cdot q[\/tex], dizemos que [tex]b[\/tex] n\u00e3o divide [tex]a[\/tex] e denotamos [tex]b \\nmid a[\/tex].
\nObserve que neste \u00faltimo caso, vale a divis\u00e3o euclidiana entre [tex]a~[\/tex] e [tex]~b[\/tex] com resto [tex]\\textcolor{red}{1} \\leq r \\lt |b|.[\/tex]
\nObserva\u00e7\u00e3o:<\/strong> \u00c9 comum n\u00e3o escrever o sinal [tex] \\cdot[\/tex] para indicarmos, por exemplo, o produto [tex]\\boxed{g \\cdot h}[\/tex] e escrever esse produto apenas por justaposi\u00e7\u00e3o dos fatores: [tex]\\boxed{gh}.[\/tex]<\/p>\n

\n

N\u00e3o vamos aprofundar o estudo de divisibilidade, j\u00e1 temos muito material sobre esse assunto no nosso Blog. Mas vamos apresentar um resultado que ser\u00e1 muito utilizado, impl\u00edcita ou explicitamente, nas nossas discuss\u00f5es:
\nPropriedade (*):<\/strong> Sejam [tex]a~[\/tex], [tex]b~[\/tex] e [tex]~c[\/tex] n\u00fameros inteiros, com [tex]c \\ne 0.[\/tex]
\nSe [tex]c \\mid a~[\/tex] e [tex]~c \\mid b[\/tex], ent\u00e3o [tex]c \\mid (ax+by)[\/tex], para quaisquer [tex]x,y \\in \\mathbb{Z}.[\/tex]<\/p>\n

<\/p>\n
\n
\nProva:<\/strong> Com efeito, note que:
\nDe [tex]c \\mid a[\/tex], segue que existe um inteiro [tex]m[\/tex] tal que [tex]a=c m.[\/tex]
\nDe [tex]c \\mid b[\/tex], segue que existe um inteiro [tex]n[\/tex] tal que [tex]b=c n.[\/tex]
\nAssim, se [tex]x~[\/tex] e [tex]~y[\/tex] s\u00e3o n\u00fameros inteiros quaisquer, segue que:
\n[tex]\\qquad ax+by=(cm)x+(cn)y=c(mx+ny).[\/tex]
\nEnt\u00e3o, se [tex]mx+ny=t[\/tex], podemos afirmar que
\n[tex]\\qquad \\boxed{ax+by=ct \\text{ com } t \\in \\mathbb{Z}}[\/tex],
\numa vez que [tex] m,n,x,y \\in \\mathbb{Z}.[\/tex]
\nAssim, pela defini\u00e7\u00e3o de divisibilidade no conjunto dos n\u00fameros inteiros, segue que [tex]c \\mid (ax+by).[\/tex]\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

<\/center><\/p>\n

\n

O estudo da divisibilidade de inteiros \u00e9 muito importante para o estudo de congru\u00eancias, que trataremos logo a seguir, pois nos permite perceber se um n\u00famero ter\u00e1 ou n\u00e3o resto zero em uma determinada divis\u00e3o.
\nVale lembrar que em algumas situa\u00e7\u00f5es n\u00e3o precisamos fazer divis\u00f5es para saber se um dado n\u00famero [tex]a[\/tex] \u00e9 divis\u00edvel por um dado n\u00famero [tex]b[\/tex]: basta utilizar os conhecidos como Crit\u00e9rios de Divisibilidade<\/strong>, que s\u00e3o regras que permitem verificar se um n\u00famero \u00e9 divis\u00edvel por outro sem a realiza\u00e7\u00e3o de longos c\u00e1lculos. Para conhecer alguns crit\u00e9rios de divisibilidade, clique AQUI<\/span><\/strong><\/a>.<\/p>\n

\n
\n
\n

III – Congru\u00eancias<\/p>\n

\u00c9 bastante natural escrevermos 23+7=30<\/strong>. Por\u00e9m, voc\u00ea j\u00e1 se deparou com uma igualdade do tipo “23+7=6”<\/strong>?
\nEm que contexto afirmar isso faz sentido?
\nBem, nesta Sala de Estudos veremos que express\u00f5es como “23+7=6” fazem sentido quando estamos trabalhando com Congru\u00eancias e Aritm\u00e9tica Modular. Ficou confuso(a)?
\nEnt\u00e3o, imagine que Joana adormeceu \u00e0s 23h e dormiu por 7 horas. Em que hor\u00e1rio ela acordou?
\nProvavelmente, a sua primeira ideia de resolu\u00e7\u00e3o foi somar 23+7. No entanto, n\u00e3o faz sentido dizer que Joana acordou \u00e0s 30h do mesmo dia, afinal, o dia s\u00f3 tem 24 horas! Nesse contexto, estabelecer a igualdade “23+7=6” faz sentido, de modo que podemos dizer corretamente que Joana acordou \u00e0s 6h do dia seguinte. Para diferenciar a igualdade “23+7=6” da igualdade usual 23+7=30, \u00e9 usual escrever [tex]23+7\\equiv6\\, (\\text{mod}\\,24)[\/tex], que podemos ler como \u201cvinte e tr\u00eas mais sete \u00e9 congruente a 6 m\u00f3dulo <\/strong>24<\/em>\u201d.
\nAgora, vejamos uma defini\u00e7\u00e3o formal da ideia apresentada acima:
\n

<\/p>\n
\nSejam [tex]a~[\/tex] e [tex]~b[\/tex] inteiros quaisquer e seja [tex]m[\/tex] um inteiro positivo fixado.
\nDiz-se que [tex]a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m[\/tex]<\/strong> (ou que [tex]a~[\/tex] e [tex]~b[\/tex] s\u00e3o congruentes<\/strong>) se, e somente se, [tex]m[\/tex] divide a diferen\u00e7a [tex]a-b.[\/tex]
\nNeste caso, escrevemos [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] e lemos [tex]a~[\/tex] \u00e9 congruente a [tex]~b.[\/tex]
\nQuando a rela\u00e7\u00e3o [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] \u00e9 falsa, dizemos que [tex]a~[\/tex] e [tex]~b[\/tex] n\u00e3o s\u00e3o congruentes<\/strong> e denotamos este fato por [tex]a \\not\\equiv b \\,(\\text{mod}\\,m).[\/tex]<\/div>\n

<\/center>
\nPor exemplo, temos que [tex]12\\equiv 2 \\,(\\text{mod}\\,5)[\/tex], pois [tex]5\\mid (12\u22122)~[\/tex]; e [tex]~19\\equiv 4 \\,(\\text{mod}\\,15)[\/tex], pois [tex]15\\mid (19\u22124).[\/tex] Mas [tex]11\\not \\equiv 4 \\,(\\text{mod}\\,5)[\/tex], j\u00e1 que [tex]5\\nmid (11\u22124)[\/tex]; e [tex]~25\\not \\equiv 6 \\,(\\text{mod}\\,15)[\/tex], j\u00e1 que [tex]15\\nmid (25\u22126).[\/tex]
\nParticularmente, [tex](23+7)\\equiv6\\, (\\text{mod}\\,24)[\/tex], pois [tex]24\\mid (30\u22126).[\/tex]
\nUma propriedade que ser\u00e1 fundamental na utiliza\u00e7\u00e3o de congru\u00eancias para conseguirmos definir a chamada Aritm\u00e9tica dos Restos<\/strong> ir\u00e1 relacionar congru\u00eancias com restos de divis\u00f5es euclidianas. Observe:
\n

<\/p>\n
\nPropriedade:<\/strong> Sejam [tex]a~[\/tex] e [tex]~b[\/tex] inteiros quaisquer e seja [tex]m[\/tex] um inteiro positivo fixado.
\nEnt\u00e3o, [tex]a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m[\/tex] se, e somente se, [tex]a~[\/tex] e [tex]~b[\/tex] deixam o mesmo resto quando divididos por [tex]m.[\/tex]<\/p>\n

\n

<\/p>\n
\n
\nProva:<\/strong>
\nTemos que provar duas afirma\u00e7\u00f5es:
\n(i) Se [tex]a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m[\/tex], ent\u00e3o [tex]a~[\/tex] e [tex]~b[\/tex] deixam o mesmo resto quando divididos por [tex]m.[\/tex]
\n(ii) Se [tex]a~[\/tex] e [tex]~b[\/tex] deixam o mesmo resto quando divididos por [tex]m[\/tex], ent\u00e3o [tex]a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m.[\/tex]
\nVamos l\u00e1!
\n(i) Suponhamos que [tex]a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m.[\/tex] Ent\u00e3o, por defini\u00e7\u00e3o, temos que [tex]m[\/tex] divide a diferen\u00e7a [tex]a-b.[\/tex]
\nAssim, existe [tex]k \\in \\mathbb{Z} [\/tex] tal que [tex]\\boxed{a-b=km}.[\/tex]
\nAgora, seja [tex]r[\/tex] o resto da divis\u00e3o de [tex]b[\/tex] por [tex]m[\/tex]; ent\u00e3o, pela Divis\u00e3o Euclidiana, [tex]\\boxed{b=qm+r}[\/tex], sendo [tex]0 \\leq r \\lt m.[\/tex]
\nPelo exposto. segue que:
\n[tex]\\qquad a=b+km=(qm+r)+km=(q+k)m+r.[\/tex]
\nComo [tex]0 \\leq r \\lt m[\/tex], pela unicidade do resto e do quociente de uma divis\u00e3o, conclu\u00edmos que
\n[tex]\\quad \\rhd q+k[\/tex] \u00e9 o quociente da divis\u00e3o de [tex]a[\/tex] por [tex]m.[\/tex]
\n[tex]\\quad \\rhd r[\/tex] \u00e9 o resto da divis\u00e3o de [tex]a[\/tex] por [tex]m.[\/tex]
\nPortanto, os inteiros [tex]a~[\/tex] e [tex]~b[\/tex] deixam o mesmo resto quando divididos por [tex]m.[\/tex]
\n(ii) Suponhamos agora que [tex]a~[\/tex] e [tex]~b[\/tex] deixam o mesmo resto [tex]r[\/tex] quando divididos por [tex]m.[\/tex]
\nEnt\u00e3o, existem inteiros [tex]q_1[\/tex] e [tex]q_2[\/tex] tais que:
\n[tex]\\qquad a=mq_1+r[\/tex], com [tex]0 \\leq r \\lt m[\/tex]
\ne
\n[tex]\\qquad b=mq_2+r[\/tex], com [tex]0 \\leq r \\lt m.[\/tex]
\nPortanto, segue que:
\n[tex]\\qquad a-b=\\left(m q_1+r\\right)-\\left(mq_2+r\\right)\\\\
\n\\qquad a-b=m q_1+r-mq_2-r\\\\
\n\\qquad a-b=m\\left(q_1-q_2\\right).[\/tex]
\nComo [tex]q_1-q_2 \\in \\mathbb{Z}[\/tex], ent\u00e3o [tex]m \\mid (a-b)[\/tex] e, por defini\u00e7\u00e3o, [tex]a\\equiv b \\,(\\text{mod}\\,m).[\/tex]<\/div>\n<\/div>\n<\/div>\n<\/div>\n

<\/center>
\nPodemos, ent\u00e3o, utilizar duas caracteriza\u00e7\u00f5es de inteiros c\u00f4ngruos [tex]a~[\/tex] e [tex]~b[\/tex]; quais sejam:
\n[tex]\\quad \\rhd a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m[\/tex] se, e somente se, [tex]m[\/tex] divide a diferen\u00e7a [tex]a-b.[\/tex]
\n[tex]\\quad \\rhd a~[\/tex] \u00e9 congruente a [tex]~b[\/tex] m\u00f3dulo [tex]m[\/tex] se, e somente se, [tex]a~[\/tex] e [tex]~b[\/tex] deixam o mesmo resto quando divididos por [tex]m.[\/tex]
\nA seguir, vamos apresentar propriedades que poder\u00e3o nos ajudar nas nossas discuss\u00f5es.<\/p>\n

\n
\n

Algumas propriedades<\/strong><\/p>\n

Vamos apresentar a seguir algumas propriedades da rela\u00e7\u00e3o de congru\u00eancia. Cada uma delas est\u00e1 ilustrada por um pequeno exemplo. Para fins de simplifica\u00e7\u00e3o, vamos assumir que os n\u00fameros com os quais estamos lidando sejam sempre inteiros e, particularmente o inteiro [tex]m[\/tex] seja positivo ([tex]m \\gt 0[\/tex]).<\/p>\n

\n►<\/span> Propriedade 1.<\/strong><\/span> [tex]a\\equiv a \\,(\\text{mod}\\,m).[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nComo [tex]m \\cdot 0=0[\/tex] e [tex]a-a=0[\/tex], temos que [tex]m \\mid (a-a).[\/tex] Logo, por defini\u00e7\u00e3o, [tex]a\\equiv a \\,(\\text{mod}\\,m).[\/tex]
\nExemplo<\/strong>:
\n[tex]\\boxed{2\\equiv 2 \\,(\\text{mod}\\,3)}[\/tex] ([tex]2\u22122=3\\times 0[\/tex])\n<\/div>\n<\/div>\n<\/div>\n
\n►<\/span> Propriedade 2.<\/strong><\/span> Se [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o [tex]b\\equiv a \\,(\\text{mod}\\,m).[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSe [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o [tex]m \\mid (a-b).[\/tex] Assim, existe [tex]k \\in \\mathbb{Z}[\/tex] tal que [tex]a-b=km.[\/tex]
\nDessa forma, segue que:
\n[tex]\\qquad b-a=\u2212(a-b)=-(km)=(-k)m[\/tex], com [tex]-k \\in \\mathbb{Z}[\/tex],
\ndonde [tex]b\\equiv a \\,(\\text{mod}\\,m).[\/tex]
\nExemplo: <\/strong>
\n[tex]\\boxed{15\\equiv 3 \\,(\\text{mod}\\,12)}[\/tex], j\u00e1 que [tex] 15\u22123=12\\times 1.[\/tex]
\nLogo, [tex]\\boxed{3\\equiv 15 \\,(\\text{mod}\\,12)}.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n
\n►<\/span> Propriedade 3.<\/strong><\/span> Se [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] e [tex]b\\equiv c \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o [tex]a\\equiv c \\,(\\text{mod}\\,m).[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSe [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] e [tex]b\\equiv c \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o [tex]m \\mid (a-b)~[\/tex] e [tex]m \\mid (b-c).[\/tex]
\nAssim, existem inteiros [tex]k[\/tex] e [tex]t[\/tex] tais que [tex]a-b=km~[\/tex] e [tex]~b-c=tm.[\/tex]
\nPortanto,
\n[tex]\\qquad a-c=(a-b)+(b-c)=km+tm=(k+t)m.[\/tex]
\nComo [tex]z=k+t \\in \\mathbb{Z}[\/tex], ent\u00e3o [tex]a-c=zm[\/tex], com [tex]z\\in \\mathbb{Z}[\/tex] e, portanto, [tex]m \\mid (a-c)[\/tex], ou seja, [tex]a\\equiv c \\,(\\text{mod}\\,m).[\/tex]
\n(Observe que poder\u00edamos ter utilizado a Propriedade (*)<\/strong> para concluir diretamente que, se [tex]m \\mid (a-b)~[\/tex] e [tex]m \\mid (b-c),[\/tex] ent\u00e3o [tex]m \\mid \\left((a-b)+(b-c)\\right)[\/tex] e, portanto, [tex]m \\mid (a-c).[\/tex])
\nExemplo: <\/strong>
\nObserve que [tex]\\boxed{9\\equiv 5 \\,(\\text{mod}\\,4)}~[\/tex] e [tex]~\\boxed{5\\equiv 1 \\,(\\text{mod}\\,4)}[\/tex], pois [tex]9-5=1\\times 4~[\/tex] e [tex]~5-1=1\\times 4[\/tex].
\nPortanto, [tex]\\boxed{9\\equiv 1 \\,(\\text{mod}\\,4)}.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n
\n►<\/span> Propriedade 4.<\/strong><\/span> Se [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] e [tex]n \\gt 0[\/tex] \u00e9 um inteiro tal que [tex]n \\mid m[\/tex], ent\u00e3o [tex]a\\equiv b \\,(\\text{mod}\\,n).[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSe [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o [tex]m \\mid (a-b)~[\/tex] e, com isso, existe um inteiro [tex]k[\/tex] tal que [tex]a-b=km.[\/tex]
\nPor outro lado, se [tex]n \\mid m[\/tex], com [tex]n \\gt 0[\/tex], ent\u00e3o existe um inteiro [tex]t[\/tex] de modo que [tex]m=tn.[\/tex]
\nFazendo as devidas substitui\u00e7\u00f5es, temos [tex]a-b=(kt)n[\/tex], como [tex]kt \\in \\mathbb{Z}.[\/tex] Portanto [tex] n \\mid (a-b)[\/tex], donde segue que [tex]a\\equiv b \\,(\\text{mod}\\,n).[\/tex]
\nExemplo:<\/strong>
\nComo [tex]\\boxed{9\\equiv 1 \\,(\\text{mod}\\,4)}[\/tex], pois [tex]9-1=2\\times 4~[\/tex], e [tex]\\boxed{2 \\mid 4}[\/tex], ent\u00e3o [tex]\\boxed{9\\equiv 1 \\,(\\text{mod}\\,2)}.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n
\n►<\/span> Propriedade 5.<\/strong><\/span> Se [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] e [tex]c\\equiv d \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o:
\n(i) [tex](a+c)\\equiv (b+d) \\,(\\text{mod}\\,m).[\/tex]
\n(ii) [tex]ac\\equiv bd \\,(\\text{mod}\\,m).[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSe [tex]a\\equiv b \\,(\\text{mod}\\,m)[\/tex] e [tex]c\\equiv d \\,(\\text{mod}\\,m)[\/tex], ent\u00e3o [tex]m \\mid (a-b)~[\/tex] e [tex]m \\mid (c-d).[\/tex]
\nAssim, existem inteiros [tex]k[\/tex] e [tex]t[\/tex] tais que [tex]a-b=km~[\/tex] e [tex]~c-d=tm.[\/tex]
\nDessa forma:
\n(i)<\/em> [tex](a+c)-(b+d)=(a-b)+(c-d)=km+tm\\\\
\n\\qquad \\qquad \\qquad \\quad =(k+t)m=zm,[\/tex]
\ncom [tex]z=k+t \\in \\mathbb{Z}~~[\/tex] e, portanto, [tex]m \\mid [(a+c)-(b+d)][\/tex].
\nLogo, por defini\u00e7\u00e3o de congru\u00eancia, [tex](a+c)\\equiv (b+d) \\,(\\text{mod}\\,m).[\/tex]
\n(Aqui tamb\u00e9m poder\u00edamos ter utilizado a Propriedade (*) e, de [tex]m \\mid (a-b)~[\/tex] e [tex]m \\mid (c-d)[\/tex], concluir diretamente que [tex]m \\mid \\left((a-b)+(c-d)\\right)[\/tex] e, como isso, [tex]m \\mid \\left((a+c)-(b+d)\\right).[\/tex]<\/p>\n

\n

(ii)<\/em> [tex]ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)=a(tm)+d(km)=\\\\
\n\\qquad \\qquad \\qquad=(at+dk)m=ym,[\/tex]
\ncom [tex]y=at+dk \\in \\mathbb{Z}.[\/tex]
\nLogo, [tex]m \\mid (ac-bd)[\/tex] e, portanto, [tex]ac\\equiv bd \\,(\\text{mod}\\,m).[\/tex]
\nExemplo: <\/strong>
\nVeja que [tex]\\boxed{9\\equiv 6 \\,(\\text{mod}\\,3)}~[\/tex] e [tex]~\\boxed{5\\equiv 2 \\,(\\text{mod}\\,3)}[\/tex], pois [tex]9-6=1\\times 3~[\/tex] e [tex]~5-2=1\\times 3[\/tex].
\nLogo, [tex]\\boxed{(9+5)\\equiv (6+2) \\,(\\text{mod}\\,3)}~[\/tex] e [tex]\\boxed{(9\\times 5)\\equiv (6\\times 2) \\,(\\text{mod}\\,3)}~[\/tex], isto \u00e9, [tex]\\boxed{14 \\equiv 8 \\,(\\text{mod}\\,3)}~[\/tex] e [tex]\\boxed{45 \\equiv 12 \\,(\\text{mod}\\,3)}.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n

\n►<\/span> Propriedade 6.<\/strong><\/span> Sejam [tex]a[\/tex], [tex]b[\/tex], [tex]m[\/tex] e [tex]n[\/tex] inteiros positivos.
\nSe [tex]a\\equiv b \\,(\\text{mod}\\,n)[\/tex], ent\u00e3o [tex]a^m\\equiv b^m \\,(\\text{mod}\\,n).[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSe [tex]a\\equiv b \\,(\\text{mod}\\,n)[\/tex], temos que [tex] n \\mid (a-b)[\/tex], ou seja, existe um inteiro [tex]k[\/tex] de modo que [tex]a-b=kn.[\/tex]
\nPela identidade alg\u00e9brica
\n[tex]\\quad a^m-b^m=(a-b)\\left(a^{m-1}+a^{m-2}b+a^{m-3}b^2+\\cdots +ab^{m-2}+b^{m-1}\\right),[\/tex]
\npodemos concluir que
\n[tex]\\quad a^m-b^m=n\\left(k\\left(a^{m-1}+a^{m-2}b+a^{m-3}b^2+\\cdots +ab^{m-2}+b^{m-1}\\right)\\right).[\/tex]
\nComo [tex]a[\/tex], [tex]b[\/tex], [tex]m[\/tex] e [tex]k[\/tex] s\u00e3o inteiros positivos, ent\u00e3o [tex]a^m-b^m=nt[\/tex], com
\n[tex]\\quad k\\left(a^{m-1}+a^{m-2}b+a^{m-3}b^2+\\cdots +ab^{m-2}+b^{m-1}\\right)=t \\in \\mathbb{Z}.[\/tex]
\nEnt\u00e3o, [tex]n \\mid a^m-b^m[\/tex], donde conclu\u00edmos que [tex]a^m\\equiv b^m \\,(\\text{mod}\\,n).[\/tex]
\nExemplo:<\/strong>
\nNote que [tex]\\boxed{7\\equiv 3 \\,(\\text{mod}\\,4)}[\/tex], pois [tex]7-3=1\\times 4.[\/tex]
\nPortanto, por exemplo,
\n[tex]\\boxed{7^2\\equiv 3^2 \\,(\\text{mod}\\,4)}[\/tex], ou seja, [tex]49\\equiv 9 \\,(\\text{mod}\\,4).[\/tex]
\n[tex]\\boxed{7^3\\equiv 3^3 \\,(\\text{mod}\\,4)}[\/tex], ou seja, [tex]343\\equiv 27 \\,(\\text{mod}\\,4).[\/tex]
\n[tex]\\boxed{7^5\\equiv 3^5 \\,(\\text{mod}\\,4)}[\/tex], ou seja, [tex]16807\\equiv 243 \\,(\\text{mod}\\,4).[\/tex]\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n

Exerc\u00edcios de Fixa\u00e7\u00e3o<\/strong><\/p>\n

Que tal alguns exerc\u00edcios antes de prosseguir?<\/p>\n

\n➤<\/span> Exerc\u00edcio 1.<\/strong><\/span> Encontre o resto na divis\u00e3o de [tex] 100\\times 101\\times 102[\/tex] por [tex]7.[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nO que procuramos para a solu\u00e7\u00e3o do problema \u00e9 o valor de [tex]x[\/tex], [tex]0\\leq x \\lt 7[\/tex], para o qual [tex]100\\times 101\\times 102\u2261 x \\,(\\text{mod}\\,7).[\/tex]
\nComo [tex]100\\equiv 2 \\,(\\text{mod}\\,7)[\/tex], pela Propriedade 5, temos que, [tex]\\left(100+1\\right)\\equiv \\left(2+1\\right) \\,(\\text{mod}\\,7)[\/tex] e, ent\u00e3o, [tex]101\\equiv 3 \\,(\\text{mod}\\,7)[\/tex].
\nDa mesma forma, temos [tex]102\\equiv 4 \\,(\\text{mod}\\,7).[\/tex]
\nAinda pela Propriedade 5, temos:
\n[tex]\\qquad 100\\times 101\\times 102\\equiv 2\\times 3\\times 4\\,(\\text{mod}\\,7)[\/tex],
\ndonde [tex]100\\times 101\\times 102\\equiv 24\\,(\\text{mod}\\,7)[\/tex], ou ainda, [tex]100\\times 101\\times 102\\equiv 3\\,(\\text{mod}\\,7)[\/tex], uma vez que [tex]24\\equiv 3\\,(\\text{mod}\\,7).[\/tex]
\nPortanto, o resto na divis\u00e3o de [tex] 100\\times 101\\times 102[\/tex] por [tex]7[\/tex] \u00e9 [tex]3.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

\n➤<\/span> Exerc\u00edcio 2.<\/strong><\/span> Encontre o resto na divis\u00e3o de [tex] 34^2\\times 5[\/tex] por [tex]11.[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSabemos que [tex]34\u2261 1 \\,(\\text{mod}\\,11)[\/tex]; portanto, pela Propriedade 6, temos que, [tex]34^2\\equiv 1^2 \\equiv 1\\,(\\text{mod}\\,11).[\/tex]
\nAl\u00e9m disso, pela Propriedade 1, [tex]5\u2261 5 \\,(\\text{mod}\\,11).[\/tex]
\nLogo, pela propriedade 5,segue que:
\n[tex]\\qquad 34^2 \\times 5\\equiv 1 \\times 5 \\equiv 5\\,(\\text{mod}\\,11).[\/tex]
\nPortanto, o resto na divis\u00e3o de [tex] 34^2\\times 5[\/tex] por [tex]11[\/tex] \u00e9 [tex]5.[\/tex]\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

\n➤<\/span> Exerc\u00edcio 3.<\/strong><\/span> Encontre o resto na divis\u00e3o de [tex] 16^{100}[\/tex] por [tex]7.[\/tex]<\/p>\n
<\/p>\n
\n
\nProva:<\/strong>
\nSabemos que [tex]16\u2261 2 \\,(\\text{mod}\\,7)[\/tex]; portanto, pela Propriedade 6, temos que, [tex]16^{100}\\equiv 2^{100} \\,(\\text{mod}\\,7).[\/tex]
\nAgora, resta-nos encontrar o resto na divis\u00e3o de [tex]2^{100}[\/tex] por [tex]7.[\/tex]
\nNote que podemos encontrar um padr\u00e3o nas divis\u00f5es das pot\u00eancias de [tex]2[\/tex] por [tex]7[\/tex]; observe:<\/p>\n

\n

\"\"<\/p>\n

\n