.Sala de Estudo: Aritmética dos Restos

Muitas questões em nosso cotidiano, como as apresentadas acima, envolvem restos; e o ramo da Matemática responsável pelo seu estudo é a Aritmética dos Restos ou Aritmética Modular. Apesar de questões como estas serem resolvidas comumente pelo “Algoritmo da Divisão Euclidiana”, alguns problemas e demonstrações mais complexas exigem um conhecimento aprofundado do assunto, bem como notações mais elaboradas.
Há muito estudo sobre o tema em livros sobre Aritmética e Teoria dos Números. No entanto, apesar de utilizarmos os restos de divisões para resolver inúmeros problemas, tanto teóricos quanto reais, esse assunto não está presente nos currículos do Ensino Médio e, portanto, o material destinado aos alunos nessa fase de ensino é escasso.
O objetivo desta Sala de Estudos é permitir que você, caro leitor, aprofunde um pouco mais seus conhecimentos acerca dos elementos da divisão e, sobretudo, do resto. Ao final do conteúdo, apresentaremos também alguns problemas sobre o assunto, muito comuns tanto em concursos e vestibulares como em Olimpíadas de Matemática mais avançadas.
Se você ficou curioso(a) com relação às soluções dos problemas apresentados acima, é só clicar no botão abaixo!

I – Divisão e Aritmética: Um pouco de História…

          De acordo com os historiadores, quem introduziu o estudo da Matemática na Grécia, berço do pensamento ocidental, foi Tales de Mileto (640-546 a.C.). Tales teria trazido consigo para a Grécia os conhecimentos de Geometria e Aritmética que aprendera com os sacerdotes egípcios. Interessado em Astronomia e Filosofia, Tales difundiu a Geometria na sua cidade, chamada Mileto. Ao fazê-lo, acabou por introduzir uma inovação revolucionária que em muito se diferia da matemática egípcia: a ideia de que as verdades matemáticas devem ser provadas. A diferença entre a Matemática que se iniciava na Grécia Antiga e a egípcia era que, enquanto para os egípcios ela se tratava de uma arte que os auxiliava em seus trabalhos de engenharia e agrimensura, na Grécia ela adquiriu de fato um caráter científico, graças à atividade filosófica que lá já se desenvolvia. (Para saber mais sobre Tales de Mileto, clique AQUI.)
          Logo em seguida, foi Pitágoras de Samos (580-500 a.C.), discípulo de Tales, quem, juntamente com sua famosa e histórica Escola Pitagórica, se encarregou de desenvolver e difundir a Matemática pela Grécia e suas colônias. A Escola Pitagórica atribuía aos números um poder místico, havendo uma ideia de que o Universo era regido por uma inteligência superior, essencialmente matemática. (Para saber mais sobre Pitágoras, clique agora AQUI.)
          Os gregos tinham uma forte inclinação à filosofia e à lógica, de modo que isto influenciou fortemente toda a sua cultura e, particularmente, seu modo de fazer Matemática. Um grande exemplo disso foi o filósofo Platão (429-348 a.C.) que, apesar de não ser matemático, nela via um treinamento indispensável ao filósofo, pois ressaltava a metodologia axiomático-dedutiva a ser seguida, de acordo com ele, em todos os campos do conhecimento. A importância que Platão atribuía à Matemática era tão forte que o fez escrever no portal de sua escola a famosa frase “Que não entre nesse local alguém ignorante em Geometria”.
          Com toda essa herança cultural, surge em Alexandria, por volta de 300 a.C., um tratado que futuramente viria a se tornar um dois mais importantes da Matemática, Os Elementos, de Euclides. Esse tratado, composto por treze livros, contém a maior parte do conhecimento matemático da época sistematizado.
          Dos treze livros de Os Elementos, dez tratam de Geometria e três, de Álgebra. Em um desses três, o livro VII, Euclides define os conceitos de divisibilidade, de número primo, de números perfeitos, de máximo divisor comum (MDC) e mínimo múltiplo comum (MMC), entre outros. Nesse livro, além das definições feitas, todas bem definidas e até hoje muito utilizadas, encontra-se enunciada a divisão com resto de um número natural por outro, chamada divisão euclidiana. Com o uso dessa divisão, Euclides estabelece o algoritmo mais eficiente para se fazer o cálculo do MDC entre dois inteiros, chamado de Algoritmo de Euclides. (Para saber mais sobre Euclides, clique AQUI.)
          Após Euclides, a Aritmética estagnou-se por cerca de 500 anos, tendo ressuscitado com os trabalhos de Diofanto de Alexandria. A obra que ele nos legou chama-se Arithmetica e foi escrita também em treze volumes, apesar de nem todos terem chegado até nós, de modo a tornar-se o primeiro trabalho de Álgebra com abordagem não revestida de qualquer linguagem ou interpretação tão somente geométrica, como fizeram seus predecessores. Tido por muitos como “pai da álgebra”, uma das importantes contribuições de Diofanto são as chamadas equações diofantinas, as quais serão melhor exploradas nos tópicos seguintes. (Para saber mais sobre Diofanto, clique AQUI.)

II – A Divisão Euclidiana

A Divisão Euclidiana, ou divisão com resto, é uma operação que toda criança aprende na escola. Escrita de maneira formal, e não como ela é tratada nas séries iniciais do Ensino Fundamental, a Divisão Euclidiana afirma o seguinte:

As duas versões podem ser demonstradas pelo chamado Princípio da Boa Ordem ou Princípio da Boa Ordenação, o qual garante que: “Todo subconjunto não vazio do conjunto dos números naturais possui um menor elemento”.

Um caso particular, e geralmente o mais explorado ao iniciarmos o aprendizado sobre o processo de divisão quando crianças, é o caso em que a divisão é dita exata. Neste caso, o resto da divisão é igual a zero e podemos falar sobre o conceito de divisibilidade.

O estudo da divisibilidade de inteiros é muito importante para o estudo de congruências, que trataremos logo a seguir, pois nos permite perceber se um número terá ou não resto zero em uma determinada divisão.
Vale lembrar que em algumas situações não precisamos fazer divisões para saber se um dado número [tex]a[/tex] é divisível por um dado número [tex]b[/tex]: basta utilizar os conhecidos como Critérios de Divisibilidade, que são regras que permitem verificar se um número é divisível por outro sem a realização de longos cálculos. Para conhecer alguns critérios de divisibilidade, clique AQUI.

III – Congruências

É bastante natural escrevermos 23+7=30. Porém, você já se deparou com uma igualdade do tipo “23+7=6”?
Em que contexto afirmar isso faz sentido?
Bem, nesta Sala de Estudos veremos que expressões como “23+7=6” fazem sentido quando estamos trabalhando com Congruências e Aritmética Modular. Ficou confuso(a)?
Então, imagine que Joana adormeceu às 23h e dormiu por 7 horas. Em que horário ela acordou?
Provavelmente, a sua primeira ideia de resolução foi somar 23+7. No entanto, não faz sentido dizer que Joana acordou às 30h do mesmo dia, afinal, o dia só tem 24 horas! Nesse contexto, estabelecer a igualdade “23+7=6” faz sentido, de modo que podemos dizer corretamente que Joana acordou às 6h do dia seguinte. Para diferenciar a igualdade “23+7=6” da igualdade usual 23+7=30, é usual escrever [tex]23+7\equiv6\, (\text{mod}\,24)[/tex], que podemos ler como “vinte e três mais sete é congruente a 6 módulo 24”.
Agora, vejamos uma definição formal da ideia apresentada acima:

Algumas propriedades

Vamos apresentar a seguir algumas propriedades da relação de congruência. Cada uma delas está ilustrada por um pequeno exemplo. Para fins de simplificação, vamos assumir que os números com os quais estamos lidando sejam sempre inteiros e, particularmente o inteiro [tex]m[/tex] seja positivo ([tex]m \gt 0[/tex]).

Exercícios de Fixação

Que tal alguns exercícios antes de prosseguir?

Classes Residuais e Aritmética Modular

Considerando, por exemplo, a divisão euclidiana de números inteiros por 2, o conjunto [tex] \mathbb{ℤ}[/tex] pode ser particionado em dois subconjuntos disjuntos: o dos números que deixam resto 0 na divisão por 2 (conjunto dos números pares) e o dos números que deixam resto 1 na divisão por 2 (conjunto dos números ímpares).
No estudo que estamos iniciando, esses dois conjuntos receberão nomes e notações especiais; respectivamente:
● classe residual módulo [tex]2[/tex] do número inteiro [tex]0[/tex], denotada por [tex]\overline{0}[/tex]
● classe residual módulo [tex]2[/tex] do número inteiro [tex]1[/tex], denotada por [tex]\overline{1}.[/tex]
Assim, só para ir nos acostumando com os novos conceitos, temos que:
[tex]\qquad \{\cdots -4,-2,0,2,4,6 \cdots \}=\{x \in \mathbb{Z}~;~x\equiv 0 \,(\text{mod}\,2)\}=\overline{0} [/tex]
[tex]\qquad \{\cdots −3,−1,1,3,5,7 \cdots \}=\{x \in \mathbb{Z}~;~x\equiv 1 \,(\text{mod}\,2)\}=\overline{1}.[/tex]

De forma análoga, considerando a divisão euclidiana de números inteiros por 5, outro exemplo, [tex]\mathbb{Z}[/tex] pode ser particionado em cinco subconjuntos: os subconjuntos disjuntos dos números que deixam resto 0, 1, 2, 3 e 4 quando divididos por 5.
Assim, fixada a congruência módulo 5, teremos: [tex]\mathbb{Z}= \overline{0} \cup \overline{1} \cup \overline{2} \cup \overline{3} \cup \overline{4}.[/tex]
Os subconjuntos [tex] \overline{0} \,;\, \overline{1} \,;\, \overline{2} \,;\, \overline{3} \,;\, \overline{4}[/tex] são igualmente denominados classes residuais; mas neste caso, são classes residuais módulo 5.
Cuidado: Observe que a classe residual [tex]\overline{0}[/tex] módulo [tex]2[/tex] é diferente da classe residual [tex]\overline{0}[/tex] módulo [tex]5[/tex]; o mesmo valendo para as respectivas classes residuais [tex]\overline{1}.[/tex]
Vamos generalizar essas ideias e conceitos.

E a tal Aritmética dos Restos?

IV – Equações Diofantinas

O estudo de Equações Diofantinas é uma aplicação interessante do conceito de divisibilidade. Elas são equações polinomiais com coeficientes inteiros, para as quais se buscam soluções também inteiras. Além disso, as variáveis da equação podem ter grau maior do que 1, o que gera uma grande diversidade de problemas envolvendo esse tipo de equação, desde o estudo do Teorema de Pitágoras, ou seja, equações na forma [tex]a^2+b^2=c^2[/tex], até a prova do Último Teorema de Fermat (mais informações podem ser encontradas neste link). Contudo, por se tratar de um tópico introdutório às equações diofantinas, nos limitaremos nesta Sala de Estudo às equações com duas incógnitas de grau 1, ou seja, aquelas do tipo [tex] \boxed{\,ax+by=c\,}[/tex], com coeficientes [tex]a,\, b,\, c \in \mathbb{Z}[/tex] e soluções inteiras, ou seja, [tex](x,y)\in \mathbb{Z}^2.[/tex]
Observe, por exemplo, a equação [tex]2x−6y=7.[/tex]
Muitos já devem estar familiarizados com equações desse tipo e com sua representação no plano cartesiano: uma reta. Portanto, os pares [tex](x,y)\in \mathbb{R}^2[/tex] que são solução dessa equação são todos os pontos que pertencem a essa reta. No entanto, nenhuma dessas soluções é um par ordenado pertencente a [tex]\mathbb{Z}^2[/tex], pois uma soma entre dois números pares ([tex]2x[/tex] e [tex]-6y[/tex]) não pode resultar no número ímpar [tex]7.[/tex] Além disso, o que torna esse fato ainda mais interessante é a análise do gráfico da reta definida por [tex]2x−6y=7[/tex], representado na próxima figura.

De fato, a inexistência de soluções em [tex]\mathbb{Z}^2[/tex] para a equação [tex]2x−6y=7[/tex] pode ser percebida no gráfico da imagem acima, na medida em que a reta parece “desviar” de todos os pontos com coordenadas inteiras, isto é, a reta não intercepta nenhum dos cruzamentos da malha quadriculada pontilhada da imagem.

Equações Diofantinas e Congruências

A fim de evidenciar a relevância das Equações Diofantinas em problemas do dia-a-dia, pensemos na seguinte questão:

Visitei uma livraria que estava com uma promoção imperdível: todos os livros estavam custando R$ 10,00 ou R$ 18,00. Meus pais me deram R$ 100,00 para comprar os livros que eu quisesse. Pensando em gastar todo o dinheiro que me foi dado, quantas e quais são as maneiras que me permitem realizar essa compra?

O problema pode ser matematicamente “traduzido” pela seguinte equação diofantina: [tex]10x+18y=100[/tex], sendo [tex]x,\, y \in \mathbb{N}[/tex] ([tex]x[/tex] e [tex] y [/tex] representam quantidades). Podemos reescrever essa equação pensando em congruências módulo [tex]5[/tex]:
[tex]\qquad 10x+18y\equiv 100 \,(\text{mod}\,5)\\
\qquad 0x+3y\equiv 0 \,(\text{mod}\,5)\\
\qquad 3y\equiv 0 \,(\text{mod}\,5).[/tex]
Dessa forma, [tex]5 \mid 3y[/tex], ou seja, estamos procurando números naturais que quando multiplicados por [tex]3[/tex] sejam múltiplos de [tex]5.[/tex]
Assim, [tex]y \in \{0,5,10,15,20,\cdots\}[/tex]; em termos de congruência, isso significa que [tex]y\equiv 0 \,(\text{mod}\,5).[/tex]
A nossa equação inicial pode ser reescrita como [tex]5x+9y=50[/tex] e, para cada valor de [tex]y[/tex] encontrado, temos um valor de [tex]x[/tex] correspondente. Vamos então fazer algumas continhas.
Perceba que [tex]x \geq 0[/tex] e [tex]5x=50-9y[/tex]; logo devemos ter [tex]50-9y \geq 0[/tex], ou seja, [tex]9y \leq 50[/tex], o que acarreta [tex]y \leq 5.[/tex]
Portanto, temos apenas dois valores de [tex]y[/tex] que interessam para o problema: [tex]y=0[/tex] e [tex]y=5.[/tex]
Para [tex]y=0[/tex], obtemos [tex]x=10[/tex]; e para [tex]y=5[/tex], obtemos [tex]x=1.[/tex]
Dessa forma, posso realizar a compra dos livros somente de duas maneiras:

• “Comprando 10 livros de R$ 10,00 somente” ou “1 livro de R$ 10,00 e 5 livros de R$ 18,00”.

Observe, no entanto, que à parte do contexto de compra de livros (que exige que [tex]x[/tex] e [tex]y[/tex] sejam inteiros positivos), a equação [tex]10x+18y=100[/tex] possui infinitos pares [tex](x,y) \in \mathbb{Z}^2[/tex] como solução. Na verdade, como veremos mais adiante, isso sempre ocorre: se uma equação diofantina admite uma solução, então ela admite infinitas.

Utilizar artifícios algébricos como o apresentado acima para resolver equações diofantinas é, de fato, muito útil para a resolução delas. No entanto, será que há alguma maneira de certificarmos que dada equação possui, de fato, solução inteira, antes de tentar resolvê-la?
A resposta é afirmativa, e faremos isso usando uma ferramenta que você provavelmente já domina: o MDC – Máximo Divisor Comum.

Vamos voltar ao que foi mencionado acima, sobre a infinidade de soluções de uma equação diofantina.
Já sabemos que a equação diofantina [tex]~ax+by=c~[/tex] terá uma solução se [tex]c[/tex] é divisível por [tex]mdc(a,b).[/tex]
Seja, então, [tex]x_0,y_0[/tex] uma solução particular para [tex]~ax+by=c.[/tex]
Para qualquer inteiro [tex]t[/tex], considere o par ordenado
[tex]\qquad (x,y)=\left(x_0-\dfrac{b}{mdc(a,b)}\cdot t\,,\,y_0+\dfrac{a}{mdc(a,b)}\cdot t\right)[/tex]
e observe, antes de mais nada, que [tex]\dfrac{b}{mdc(a,b)}[/tex] e [tex]\dfrac{a}{mdc(a,b)}[/tex] são números inteiros.
Temos, então, que:
[tex]\qquad ax+by=a\left(x_0-\dfrac{b}{mdc(a,b)}\cdot t\right)+b\left(y_0+\dfrac{a}{mdc(a,b)}\cdot t\right)\\
\qquad ax+by=ax_0-\dfrac{ab}{mdc(a,b)}\cdot t+by_0+\dfrac{ab}{mdc(a,b)}\cdot t\\
\qquad ax+by=ax_0-\cancel{\dfrac{ab}{mdc(a,b)}\cdot t}+by_0+\cancel{\dfrac{ab}{mdc(a,b)}\cdot t}\\
\qquad ax+by=ax_0+by_0\\
\qquad \boxed{\,ax+by=c\,}.[/tex]
Assim, para cada valor inteiro [tex]t[/tex], o par ordenado [tex]\left(x_0-\dfrac{b}{mdc(a,b)}\cdot t\,,\,y_0+\dfrac{b}{mdc(a,b)}\cdot t\right)[/tex]
fornece uma solução para a equação [tex]~ax+by=c.[/tex]
Portanto, havendo infinitos valores possíveis para [tex]t[/tex], temos infinitas soluções possíveis para a equação diofantina [tex]~ax+by=c.[/tex]

V – Alguns Problemas…

VI – Criptografia: uma Aplicação Interessante

Imagem extraída de Kaspersky.

Atualmente, uma das grandes aplicações da Aritmética Modular no dia a dia é na criptografia – a ciência que tem como objeto de estudo a codificação e decodificação de mensagens e outras informações por meio de algoritmos, no intuito de proteger dados.
A codificação de uma mensagem se dá por meio de uma correspondência biunívoca entre todos os grafemas (letras) usados na mensagem e um conjunto finito e sequencial que será a mensagem codificada. Assim, ela se torna ilegível para aqueles que não possuem a sua “chave”, ou seja, a informação restrita que controla toda a operação dos algoritmos de criptografia.
Para explicar como se dá essa relação, podemos analisar um exemplo bastante conhecido na área:

Por fim, o uso da Aritmética Modular na criptografia não se limita apenas à comunicação. Atualmente, esse sistema é utilizado para guardar senhas e arquivos na Internet, além de garantir a segurança de transações bancárias. Vale ressaltar que os números utilizados nesses casos possuem dezenas ou centenas de algarismos, o que torna praticamente impossível a quebra dessa criptografia por “hackers” ou meios tradicionais utilizando computadores. O exemplo explicado acima é apenas uma forma simples de estabelecer a relação entre criptografia e Aritmética Modular, pois da mesma forma que Bob e Alice esconderam sua chave secreta a partir de uma chave pública que não apresentava riscos, os vários sistemas computacionais podem usufruir dessa mesma técnica, porém com variações numéricas mais complexas.

COM Geomestres Slay (Colégio Militar de Porto Alegre, RS)
Equipe COM – OBMEP