Benedito Tadeu Vasconcelos Freire
UFRN, Natal, RN

Você pode dizer se o 264.° e o 118.° dias do ano ocorrem num mesmo dia da semana?

Quais são os inteiros que deixam resto 3 quando divididos por 4?

Qual é o resto da divisão de   5¹¹⁰   por   6?

O número     9.619.874.315  é divisível por  9?

Qual é o critério de divisibilidade por   9?

A partir da noção de congruência vamos responder a todas essas questões.

O conceito de congruência pode explicar muitas "adivinhações", o que permite ao leitor brincar com os amigos resolvendo muitos problemas interessantes, como o que se segue:

Peça a um amigo que pense um número natural qualquer, com quantos algarismos ele quiser, e que faça o seguinte:

-    escreva o número pensado,

-    mude como queira a ordem de seus algarismos, obtendo um novo número,

-    diminua o menor do maior,

-   retire um dos algarismos do resto (diferente de zero), e diga os demais algarismos na ordem que quiser.

Em resposta você dirá qual o algarísmo retirado.

Como explicar a "mágica"? A resposta encontra-se no final deste artigo (v. também RPM 9, p. 30).

O estudo da   congruência   foi apresentado por   CARL FRIEDRICH GAUSS (1777-1855) em seu livro Disquisitiones arithmeticae - um tratado em latim sobre a teoria dos números -, publicado em 1800.    Foi a partir dessa obra que se desenvolveu essa teoria. A notação usada hoje é a mesma adotada por Ga,uss no seu livro.

O que vem a ser congruência? É uma linguagem na qual muitas abordagens acerca da divisibilidade de números inteiros podem ser simplificadas.

O que realmente é esta linguagem?

Para responder a esta questão comecemos examinando um calendário, por exemplo, o do mês de outubro de 1992.
 

Destaquemos uma coluna correspondente a um dia da semana, por exemplo, sexta-feira. Os números correspondentes a essa coluna são 2, 9, 16, 23 e 30. Observe que cada um desses números, a partir do segundo, é o anterior mais 7, e, conseqüentemente, a diferença entre dois quaisquer é um múltiplo de 7. O mesmo acontece com as colunas correspondentes aos outros dias da semana.

Você já tinha percebido isso antes?

O número 7 reparte os dias do mês em sete classes, domingos, segundas, terças, .. .sábados. Do mesmo modo o número 7 reparte os números inteiros em sete classes. E fácil ver que qualquer número natural   n   reparte os inteiros em   n   classes.

Essas mesmas idéias poderiam ser apresentadas usando um relógio, considerando as 24 horas do dia. E aqui vemos que o número 12   divide as vinte e quatro horas do dia em   12  classes:

Essas idéias levam-nos à nossa noção principal, que é a de congruência de inteiros.

Retornemos ao calendário apresentado no início. Como vimos, a diferença entre dois números quaisquer, constantes em uma coluna correspondente a um dia da semana, é um múltiplo de   7. De fato:

9 2 = 7 = 7 x 1,         30 2 = 28 = 7 x 4.

Dizemos então que

9  é congruente a  2   módulo  7,
30  é congruente a 2  módulo  7.

No caso das horas, podemos adotar a mesma linguagem:

1   é congruente a   13  módulo  12 ,
7  é congruente a   19   módulo  12, etc.

Desse modo, se os inteiros m e n diferem por um múltiplo do número natural a, dizemos que m é congruente a n módulo a. Notação de Gauss:   m n    (mod a).

A frase "m é congruente a n módulo a" significa, simplesmente, que  a   divide a diferença  m - n.

Agora já estamos em condições de resolver a 1.ª questão apresentada anteriormente na introdução. Pelo que vimos, a pergunta pode ser colocada no ponto de vista da congruência:

264   é congruente a   118   módulo  7?

Ou, mais resumidamente,   264 118   (mod 7)?

Para responder à questão basta verificar se 7 divide 204 118 = 146.   A resposta é claramente não.

A 2.ª questão - quais inteiros deixam resto 3 quando divididos por 4? pode ser respondida olhando para os inteiros n congruentes a  3   módulo 4.   Ou, mais resumidamente,  n 3   (mod 4).

Temos que encontrar os inteiros n tais que n 3 seja divisível por 4. Então n — 3 = 4k, onde k é um número inteiro. E, portanto, n 3 + 4k, onde k é um inteiro qualquer. E fácil ver que os inteiros procurados são:   ...,-9,  5,  1, 3, 7, 11, 15,...

Muitos conceitos podem ser expressos em termos de congruências. Vejamos alguns exemplos.

Exemplo 1. A noção fundamental "a divide n" pode ser escrita como  n = 0   (mod a).

Exemplo 2. Um número é par se pode ser escrito na forma 2k, onde k é um inteiro. Podemos dizer isso de uma outra forma equivalente: um número n é par se n 0 (mod 2). De modo semelhante podemos ver que m é ímpar se m 1 (mod 2). E, portanto, o 2 separa os inteiros em duas classes: os pares e os ímpares. Resumidamente:

n é par    n 0    (mod 2),

m é ímpar m 1    (mod 2).

Exemplo 3. Os elementos do conjunto M = {1,4,7,10,...} são números naturais que deixam resto 1 quando divididos por 3. Observe que esses elementos satisfazem a congruência n 1 (mod 3). Isso sugere que a congruência m n (mod a) pode ser interpretada como "m e n deixam o mesmo resto quando divididos por a". Esse é um resultado muito importante para esse nosso ponto de vista. Vamos chamá-lo, por isso, de

Teorema 1

a)    Se os números naturais  m  e  n  deixam o mesmo resto quando divididos por  a,  então  m n    (mod a).

b)   Se os números naturais   m   e   n   são congruentes módulo  a, então eles deixam o mesmo resto quando divididos por  a.

Prova: Primeiro, vamos provar a parte a). Quando fazemos a divisão de m por a, temos um quociente q₁ e o resto r; e o resultado é expresso como   m = q₁a + r.

De maneira análoga, quando fazemos a divisão de  n  por  a,  obtemos um quociente q₂, um resto r (o mesmo da divisão de m por  a,  por hipótese), e temos  n = q₂a + r.   Fazendo a diferença,

m n= (q₁a + r) (q₂a + r) = (q₁ - q₂) a .

Logo,   m n é múltiplo de  a, e , portanto,  m n    (mod a).

Agora vamos provar a parte b).

Os resultados da divisão de  m  e  n  por a podem ser expressos como:

m =q₁a +  r₁,      onde      0   r₁ < a        e

n =q₂a +  r₂,      onde      0   r₂ < a.

Temos assim que:

r₁ r₂ = (m - q₁a) (n q₂a) = (m n) + (q₂ q₁)a.

Observe que o lado direito da igualdade é múltiplo de  a,  pois   m n   é múltiplo de a. Como r₁ r₂  é um múltiplo de a entre (a +1) e  (a 1),  r₁ r₂   tem que ser igual a zero. O que conclui a prova.

E fácil ver que a congruência se comporta de maneira semelhante à igualdade. De fato, são verdadeiras as seguintes propriedades:

(i)        m m    (mod a)    (reflexiva),

( ii) Se   m n    (mod a),  então  n m    (mod a)     (simétrica),

(iii) Se   m n    (mod a)  e  n s    (mod a),  então   m s    (mod a)     (transitiva),

( iv) Se  m = n    (mod a)  e   r s    (mod a),  então    m + r = n + s    (mod a),

(v) Se   m n    (mod a)   e   r s    (mod a),   então   mr  ns    (mod a).

As provas dessas propriedades são muito simples e as deixamos como exercício para o leitor.

Agora podemos resolver mais uma das questões propostas qual o resto da divisão de  5¹¹⁰   por   6?

Para obtermos a resposta, basta observar que 5 = 1 (mod 6), em seguida, "escrever"   110   congruências:

5 l    (mod 6), 5 l    (mod 6), ..., 5 1    (mod 6), e aplicar a propriedade (v) para obter   5¹¹⁰ = ( l)¹¹⁰    (mod 6). Como   (1)¹¹⁰ = 1, pois 110   é par, temos   5¹¹⁰ = 1    (mod 6).

Agora, de acordo com o Teorema 1, temos que 5¹¹⁰ e 1 deixam o mesmo resto quando divididos por 6. Mas o resto da divisão de 1 por  6   é   1:   1 = 0 x 6 + 1.

Portanto, o resto da divisão de   5¹¹⁰   por   6   é   1.

Vamos resolver outra questão proposta na introdução deste artigo o número   29.619.874.315   é divisível por 9?

Inicialmente escrevemos o número dado na seguinte forma

29.619.874.315 = 2 x 10¹⁰ + 9 x 10⁹ 4- 6 x 10⁸ + 1 x 10⁷ + 9 x 10⁶ + 8 x10⁵ + 7 x 10⁴ + 4x10³ + 3 X 10² + 1 x 10 + 5.

Agora, observe que 10 1 (mod 9), o que implica que 10ⁿ 1 (mod 9), para todo número natural n. Além disso, é verdade que 10ⁿ x m m (mod 9), para todo número inteiro m (propriedade (v) acima). Segue então que

E, aplicando a propriedade (iv), temos

29.619.874.315 = (5 + 1 + 3 + 4 + 7 + 8 + 9 +1 + 6 + 9 + 2)    (mod 9).

Observe, então, que o número dado é congruente à soma, E, de seus algarismos. Isto significa (pelo Teorema 1) que, na divisão por 9, o número 29.619.874.315 deixa o mesmo resto que . Portanto, para responder à questão, basta verificar se a soma dos algarismos do número dado é divisível por 9. Como = 55 não é divisível por 9, o número dado também não é divisível por 9. Isto sugere o critério de divisibilidade por  9,  que enunciamos a seguir:

Teorema 2

Quando um número natural m é dividido por 9, o resto da divisão é o mesmo obtido quando da divisão da soma de seus algarismos por 9. Em particular, um número m é divisível por 9 se a soma de seus algarismos for um número divisível por   9.

Prova: A idéia da prova é a mesma do caso particular feita anteriormente. Deixamos os detalhes para o leitor.

O leitor agora pode enunciar os critérios de divisibilidade por 3, 5, 10, etc. e dar uma justificativa para cada um deles, baseado no que foi feito acima (v. também RPM 10 pp. 33-40).

A questão de tirar os "noves fora" de um número foi tratada na RPM 14, pp. 17-20. Do ponto de vista estudado aqui, tirar os "noves fora" de um número significa achar o resto da sua divisão por 9.

Vamos agora explicar nossa última questão apresentada na introdução:   ... qual foi o algarismo retirado?

Como já sabemos, um número natural e a soma de seus algarismos deixam o mesmo resto quando divididos por 9. Portanto, dois números formados com os mesmos algarismos, colocados em outra ordem, possuem o mesmo resto quando divididos por 9. Logo, se de um desses números se subtrair o outro, a diferença será divisível por 9.

Por isso, sabemos, de antemão, que seu colega obteve, como resultado um número cuja soma dos algarismos é múltiplo de 9.

Para fazer a "mágica" da descoberta do algarismo retirado, efetuamos, primeiramente, a soma dos algarismos ditos pelo seu colega. A seguir, subtraímos essa soma do menor múltiplo de 9 maior que essa soma. O resto é o algarismo procurado.

Para concluir, deixamos dois problemas, que apareceram em competições de Matemática, para o leitor exercitar os conhecimentos aqui apresentados:

Problema 1 — Um número de três algarismos 2a3 é somado com o número 326, dando o número 5b9. Se 5 b9 é divisível por 9, então a + b é igual a ...

Problema 2 — Encontre todos os números naturais m de 5 algarismos, m divisível por 11, cuja soma de seus algarismos seja   43.

Referências Bibliográficas

[1]  PERELMAN, Ya.   I. Problemas y experimentos recreativos.   Moscú, Mir, 1975.
[2]  STEIN, Sherman K. Mathematics, the man-made universe.  San Francisco, W. H. Freeman and Company,        1976.

NR. Além das revistas já citadas no texto, o leitor encontrará temas correlatos nas RPM's 6, p. 21; 7, p. 25; 12, p. 24.