TeoNum-U4

Prévia do material em texto

OBJETIVOS
• Compreender mais teoremas com congruências.
• Entender como as congruências ajudam na teoria das equações diofantinas.
• Entender como as congruências podem ser úteis para determinar critérios 
de divisibilidade. 
• Estudar problemas práticos com congruências, que podem ser aplicados em 
turmas de Ensino Fundamental ou Médio. 
CONTEÚDOS
• Teorema de Euler, Pequeno Teorema de Fermat e Teorema de Wilson. 
• Equações diofantinas (continuação). 
• Critérios de divisibilidade.
• Problemas que abrangem datas. 
ORIENTAÇÕES PARA O ESTUDO DA UNIDADE
Antes de iniciar o estudo desta unidade, leia as orientações a seguir: 
1) Procure entender os teoremas apresentados e refaça as demonstrações no 
papel, formulando seus próprios exemplos.
2) Tome muito cuidado ao resolver equações diofantinas pelo algoritmo de Eu-
clides, pois é muito fácil cometer erros nesse ponto. 
3) Esta unidade difere mais ainda da anterior, em relação ao livro-texto, justa-
mente por apresentar aplicações mais práticas de congruência. Por isso, é 
importante que você verifique os Conteúdos Digitais Integradores.
Congruências: Aplicações 4
Claretiano - Centro Universitário
111
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
1. INTRODUÇÃO
A Teoria dos Números pode atingir resultados tão complexos 
quanto se possa imaginar, assim como a teoria sobre congruência. 
Porém, este estudo é apenas introdutório, e, como é voltado para 
futuros professores de Ensino Fundamental e Médio, é preferív-
el apresentarmos resultados mais simples, com aplicações mais 
palpáveis, do que resultados mais complexos.
Alguns tópicos desta unidade, em especial, são os mais 
úteis para aplicação em sala de aula. Tendo em mente apenas a 
definição e as propriedades mais básicas de congruência, é pos-
sível resolvermos problemas interessantes, como os critérios de 
divisibilidade e os que abrangem datas.
2. CONTEÚDO BÁSICO DE REFERÊNCIA
2.1. OS TEOREMAS DE EULER, FERMAT E WILSON
Antes de começarmos, relembremos o que é a função ϕ de 
Euler, definida na unidade anterior: ϕ (m) representa a quantida-
de de elementos de um conjunto reduzido de resíduos mod m, ou 
seja, a quantidade de números incongruentes mod m entre si, sen-
do todos relativamente primos com m. Por exemplo, no caso do 
número 10, um conjunto possível seria 1, 3, 5 e 7. Logo, ( )10 4φ =
. Existem métodos para calcular ϕ (m), mas esse não é nosso ob-
jetivo agora. 
Nosso objetivo é demonstrar dois teoremas conhecidos: o 
Teorema de Euler e o Pequeno Teorema de Fermat. Landau (2002) 
denomina ambos os teoremas de Pequeno Teorema de Fermat 
(um seria o resultado principal, e o outro, uma consequência), mas 
vamos utilizar a nomenclatura adotada por vários outros autores. 
Apesar de, historicamente, o Teorema de Euler vir depois do de 
Fermat, como uma generalização, para fins didáticos, o Teorema 
© Teoria dos Números112
de Euler vem primeiro, e fica fácil demonstrar o de Fermat como 
um caso particular. 
Teorema 75 (Teorema de Euler) 
“Se ( , 1a m = , então ( 1 ma mod mφ ≡ .”
Demonstração 
Seja a1, a2, …, aϕ(m) um conjunto reduzido de resíduos mod 
m. Então, conforme o Teorema 63 demonstrado na Unidade 3, aa1, 
aa2, …, aaϕ(m) também é um conjunto reduzido de resíduos. Em ou-
tras palavras, cada elemento do primeiro conjunto é congruente 
mod m a algum elemento do segundo conjunto. Simbolicamen-
te, escrevemos que os números an são congruentes aos aan (com 
)1, ... ,n mφ= ). 
O Teorema 53 garante que é possível multiplicar "sequências 
de congruências", portanto: 
( ) ( )
 
1 1
( )n n
m m
n n
a aa mod m
ϕ ϕ
= =
≡∏ ∏ . 
Note que, no lado direito da congruência, o termo a será 
multiplicado ϕ (m) vezes, ou seja, faremos aϕ(m). Então, podemos 
escrever 
( ) ( )
( )
1 1
( )n n
m m
m
n n
a a a mod m
ϕ ϕ
ϕ
= =
≡∏ ∏ . 
Sabemos que para cada n, ( ) , 1na m = , portanto ( )
1
( , ) 1n
m
n
a m
ϕ
=
=∏ . 
Podemos aplicar a lei do cancelamento, dividindo 
ambos os lados da congruência por esse termo, ficando com 
( ) ( ) ( ) ( )1 1 m ma mod m a mod mφ φ≡ → ≡ , que é o que queríamos 
demonstrar. 
Exemplo: sabemos que )5, 3 1= e que {1, 2, 3, 4} é um 
sistema reduzido de resíduos mod 5, portanto ( )5 4φ = . Então, o 
Teorema de Euler deduz que )43 1 5mod≡ .
O teorema a seguir é mais um caso particular do Teorema de 
Euler para números primos. 
113
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
Teorema 76 (Pequeno Teorema de Fermat) 
“Se p ł a, então ( )–1 1 pa mod p≡ .”
Demonstração 
Se p ł a, então ), 1p a = (Teorema 19 da Unidade 2). 
Podemos aplicar, portanto, o Teorema de Euler. Pela definição de 
número primo, p será relativamente primo com qualquer número 
menor do que ele. Tomando o sistema completo de restos formado 
por 0, 1, ..., –1p , basta retirarmos o 0 para obtermos um conjunto 
reduzido de restos. A quantidade de elementos será –1p , ou seja, 
( –1p pφ = . 
Assim, aplicando o Teorema de Euler, temos que 
( –1 1 pa mod p≡ . Multiplicando essa congruência por a, 
encontramos outro resultado útil, que é ) pa a mod p≡ . 
Quando citarmos o Teorema Pequeno de Fermat daqui por diante, 
poderemos nos referir a qualquer uma das duas congruências. 
Exemplo: como 17 ł 4, esse teorema deduz que 
(164 1 17mod≡ . É possível verificar que essa congruência é 
verdadeira, utilizando as técnicas vistas na unidade anterior. Afinal, 
sabemos que (4² – 1 17mod≡ . Como ( 8² 84 1 17mod≡
, então (164 1 17mod≡ . Dessa maneira, concluímos que o 
Pequeno Teorema de Fermat é um "atalho" para provar certos 
resultados que já conseguíamos provar anteriormente. 
Exemplo: mostre que 232 –1 é divisível por 47. 
Resolvemos esse exemplo na unidade anterior de uma 
maneira muito complicada, mas agora será muito simples. 
Sabemos que ( )232 47x mod≡ , para algum x, tal que 0 47x≤ < . 
Então, obtemos ( ) ( )223 22 47x mod≡ , ou seja, )46 22 47x mod≡ . 
Pelo Pequeno Teorema de Fermat, ( )462 1 47mod≡ .
© Teoria dos Números114
Logo, ² 1 1x x= → = ou –1x = . Como supomos: 0x > , 
1x = . 
Exemplo: mostre que 70 702 3+ é divisível por 13. 
De acordo com o Pequeno Teorema de Fermat: 
( )122 1 13mod≡ , então: 
) ( ) ( )512 5 602 1 13 2 1 13mod mod≡ → ≡ . 
( )52 32 6 13mod= ≡ , logo: 
) ( ) ( ) ( )25 2 102 6 13 2 36 13 – 3 13mod mod mod≡ → ≡ ≡ . 
Assim, ( )70 60 102 2 2 1 – 3 – 3 13mod= ⋅ ≡ ⋅ ≡ . 
)33 27 1 13mod= ≡ , então: 
( ) ( ) ( )233 23 693 1 13 3 1 13mod mod≡ → ≡ . E, como 
)3 3 13mod≡ , temos que ( )70 693 3 3 1 3 3 13mod= ⋅ ≡ ⋅ ≡
) ( )70 70 70 702 3 – 3 3 13 2 3 0 13mod mod+ ≡ + ≡ → + ≡ , 
ou seja, 70 702 3+ é divisível por 13. 
Teorema 47 (Teorema de Wilson) 
“Para p primo, ) ( )–1 ! – 1 p mod p≡ .” 
Vamos primeiro dar um exemplo dessa demonstração para 
11p = . 
Lembre que, dados a e b, a é o inverso de b mod p, se 
( )1 a b mod p⋅ ≡ . Além disso, a é o seu próprio inverso mod p, se 
)1 a mod p≡ ou ( )– 1 a mod p≡ . 
Considere os números 1, 2, 3, ... 10. Como cada um desses 
números é relativamente primo com 11, pelo Teorema 65, a 
equação )1 11sr mod≡ tem uma única solução; ou seja, cada um 
desses números possui um inverso mod 11. Por tentativa, vemos 
que apenas 1 e 10 são seus próprios inversos, pois ( )1 1 11mod≡
115
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
, e )10 – 1 11mod≡ , e que isso não ocorre com nenhum outro 
número. 
Mas, como os demais números precisam ter um inverso, en-
tão é possível agrupar a sequência 2, 3, ..., 9 em 4 pares (o conjun-
to tem 8 elementos) de números em que cada um é o inverso do 
outro. 
Os pares serão: 
• 2.6 ≡ 1(mod 11)
• 3.4 ≡ 1(mod 11)
• 5.9 ≡ 1(mod 11)
• 7.8 ≡ 1 (mod 11)
Multiplicando lado a lado, obteremos: 
( )2 3 4 5 6 7 8 9 1 11mod⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡ . Como ( )10 1 11mod≡
, se multiplicarmos ambos os lados por 10, obteremos: 
) ( )2 3 4 5 6 7 8 9 10 – 1 11 10! – 1 11mod mod⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡ → ≡ .
Para entender a demonstração que vem a seguir,note que 
o conjunto 2, 3, ..., 9 possui 11– 3 8= elementos, e, por isso, é 
possível formarem-se 8 / 2 4= pares. De modo geral, o conjunto 
2, 3 ..., – 2p possui – 3p elementos, e é possível formarem-se 
– 3
2
p pares. 
Demonstração do Teorema de Wilson 
Tome o conjunto 1, ..., –1p . Pelo Teorema 65, para cada 
elemento r desse conjunto, há certo s, tal que ( )1 rs mod p≡ , pois 
( ), 1p r = . )–1 – 1 p mod p≡ , e ( )1 1 mod p≡ , então nos resta 
que as demais soluções possíveis estão no conjunto 2, 3, ..., – 2p . 
Esse conjunto possui – 3p elementos, então é possível formarem-
se – 3
2
p pares de números r e s, tais que (1 11rs mod≡ . 
© Teoria dos Números116
Multiplicando as congruências membro a 
membro, obtemos: (2 3 4 ... – 2 1 p mod p⋅ ⋅ ≡ . 
Sabendo que ( – 1 – 1 p mod p≡ e multiplicando 
ambos os lados por esse termo, ficamos com a relação 
(2 3 ... – 2 – 1 – 1 p p mod p⋅ ≡ , ou seja, 
( – 1 ! – 1 p mod p≡ . 
Exemplos: 
Temos que ( )5 –1 ! 4 3 2 1 24= ⋅ ⋅ ⋅ = . 
De fato, ( )24 – 1 mod p= . 
Encontre o resto da divisão de 
12 13 14 15 16 17 18 19 20 21⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ por 11. 
Primeiro, note que: 
)12 1 11mod≡ ,
( )13 2 11mod≡ ,
)14 3 11mod≡ e 
( ) ... 21 10 11mod≡ .
Então, 
( ) ( )12 13 14 15 16 17 18 19 20 21 1 2 3 4 5 6 7 8 9 10 11 10! 11mod mod⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡
. Conforme o Teorema de Wilson, )10! – 1 11mod≡ , portanto, 
o resto procurado é 11–1 10= . 
2.2. EQUAÇÕES DIOFANTINAS
Vamos estudar um pouco mais as equações em que os coefi-
cientes, as variáveis e as soluções são números inteiros.
Já vimos que a equação 1ax by+ = possui solução se, e 
somente se, ), 1a b = . Agora, estudaremos a equação mais geral, 
ax by c+ = . 
117
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
Teorema 66 
“Sendo ), a b d= , então a equação diofantina ax + by = c 
tem solução, se, e somente se, d|c.”
Demonstração 
De acordo com o Teorema 65, a congruência ( ) ax c mod b≡ 
tem solução, se, e somente se, (a, b)|c. Por hipótese, (a, b)|c, 
portanto, a congruência tem solução. Se ) ax c mod b≡ possui 
solução, então existe um q, tal que – –ax c qb ax qb c= → = . 
Concluímos que a equação ax by c+ = possui solução. 
Por outro lado, se (a, b) ł c, a congruência ( ) ax c mod b≡ 
não terá solução, e, consequentemente, ax by c+ = também não. 
Exemplos: 12 30 24x y+ = possui solução, pois )12, 30 6= , 
e 6|24. 
12 30 35x y+ = não possui solução, pois 6 ł 35.
Podemos obter soluções para esse tipo de equação do 
mesmo modo que fazíamos quando tínhamos 1ax by+ = . Assim, 
primeiro escrevemos o MDC de 12 e 30 como uma combinação 
linear desses números. Veja a seguir. 
30 2 12 6= ⋅ + . Então, 6 30 – 2 12= ⋅ . Como 24 4 6= ⋅ , basta 
multiplicarmos a igualdade por 6. Logo, 24 4 30 – 8 12= ⋅ ⋅ . 
Concluímos que uma solução possível é 0 – 8x = , 0 4y =
. Porém, ela não é a única. Existem infinitas soluções possíveis. 
Veremos a seguir como encontrá-las. 
Teorema 67 
Se x0, y0 são uma solução de ax by c+ = , então todas as 
soluções são da forma 0
bx x h
d
= + , 0
ay y h
d
−= , em que h é um 
inteiro qualquer.”
© Teoria dos Números118
Demonstração 
Para verificarmos que x e y, descritos como 
anteriormente, satisfazem a equação, basta 
substituirmos tais valores nela. Ficaremos com: 
0 0 0 0 0 0 ( ) ( )
b a b aa x h b y h ax ah by bh ax by c
d d d d
−+ + = + + − = + = 
(pois o par x0, y0 é uma solução).
Agora, precisamos mostrar que toda solução é da forma 
descrita no enunciado do teorema. Seja o par x, y outra solução 
da equação que estamos estudando. Então, ax by c+ = (1), assim 
como 0 0ax by c+ = (2).
De (1), –ax c by= , ou seja, ( )– 0 ax c mod b≡ . 
De (2), 0 0–ax c by= , ou seja, ( )0 – 0 ax c mod b≡ . 
Subtraindo as congruências, obtemos ) ( )0– 0 a x x mod b≡ . 
Para utilizarmos a lei do cancelamento, devemos ter em mente 
que ( ), a b d= , então, para podermos dividir a congruência por a, 
ficaremos com 0( ) 0 ( )
bx x mod
d
− ≡ . 
Chamando 0– x x de h, ou seja, fazendo 0–x x h= , temos 
que 0
bx x h
d
= + (3). 
Agora, tratemos do y. 
Da equação (1), –by c ax= . Substituindo o que encontramos 
em (3), ficamos com 0 0( )
b abby c a x h by c ax h
d d
= − + → = − − (4).
Por (2), obtemos 0 0–by c ax= , e, substituindo em (4), 
0
abby by h
d
= − (5). 
Supondo 0b ≠ (caso contrário, a equação diofantina 
estudada se reduziria a uma equação elementar), podemos dividir 
ambos os lados (5) por b, ficando com 0
ay y h
d
= − . 
119
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
Está demonstrado o teorema. 
Exemplo: 
Vimos que uma solução para a equação 12 30 24x y+ = é x0 
= -8 y0 = 4, e que (12,30) = 6.
Portanto, todas as outras soluções serão da forma: 
308 8 5
6
124 4 2
6
x h h
y h h
= − + = − +
= − = −
Fazendo, por exemplo, 1h = , teremos que –3x = e 2y = 
satisfazem a equação. Verifique! 
Observação: na unidade anterior, resolvemos a equação 
diofantina 37 8 1x y+ = , obtendo –3x = e 14y = . No momento, 
estávamos preocupados apenas em encontrar o inverso de 8 
mod 37, e não todas as soluções possíveis, mas agora sabemos 
que existem infinitas soluções, descritas por – 3 8x h= + e 
14 – 37y h= . 
Exemplo: 
Determinar todas as duplas de frações positivas que tenham 
3 e 5 como denominadores e cuja soma seja igual. 
Nosso problema é encontrar x e y, tais que: 
57 5 3 57
3 5 15 15 15
x y x y+
+ = → =
 
Precisamos, então, resolver a equação 5 3 57x y+ = . Você 
poderá resolvê-la e obter 0 – 57x = , 0 114y = . Portanto, todas as 
soluções serão descritas por – 57 3x h= + , 114 – 5y h= .
Como as frações são positivas, queremos 0x > e 0y > .
Então, –57 3 0 19h h+ > → > .
114 – 5 0 22h h h> → <→ ≤ .
© Teoria dos Números120
Então, temos que h pode ser 20, 21 e 22. 
Testando: 20 3h x= → = , 14y = .
21 6h x= → = , 9y = . 
22 9h x= → = , 4y = . 
Logo, as frações (já simplificadas) são 141
15
+ , 
92
5
+ e 
43
5
+ . 
Você já pode resolver o exercício 3 das Questões Autoava-
liativas.
Observação: há muitos outros tipos de equações diofantinas. 
Descobrir que trios de números satisfazem o Teorema de Pitágoras 
( 2² ²a b c+ = ) é um problema que abrange equações diofantinas, 
assim como o Último Teorema de Fermat, que deduz que não exis-
te nenhum conjunto de inteiros positivos, x e z, que, com n maior 
do que 2, satisfaça n n nx y z+ = . Essa conjectura levou mais de 300 
anos para ser demonstrada, então pode ser chamada, de fato, de 
teorema. 
2.3. CRITÉRIOS DE DIVISIBILIDADE 
Nos Conteúdos Digitais Integradores da Unidade 1, já havia 
sido disponibilizado um material que apresentava os mais conhe-
cidos critérios de divisibilidade. Agora, vamos demonstrar esses 
critérios partindo do conceito de congruência. Para fazer essas de-
monstrações, suporemos válido o resultado do Teorema 8 do Ca-
pítulo 1 do livro Teoria elementar dos números, de Landau (2002), 
que traz o seguinte:
Teorema 8 
“Seja 1g > . Então, qualquer número 0a > pode ser expresso 
de uma única maneira na forma: 0 1 nna c c g c g= + + … + , com 
0n ≥ , 0nc > e 0 mc g≤ < , para 0 m n≤ ≤ ."
121
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
Você pode consultar a demonstração desse teorema no livro-
-texto. Nossa preocupação é com seu significado. Note que, para 
10g = , esta é a representação decimal de um número, ou seja, 
0 110 10
n
na c c c= + + … + , com 0n ≥ , 0nc > e 0 10mc≤ < , 
para 0 m n≤ ≤ .
Exemplos: 
02 2 10= ⋅
1 017 1 10 7 10= ⋅ + ⋅ 
2 1 0345 3 10 4 10 5 10= ⋅ + ⋅ + ⋅
3 2 1 05.648 5 10 6 10 4 10 8 10= ⋅ + ⋅ + ⋅ + ⋅ , e assim por diante. 
Vamos, então, aos critérios de divisibilidade. 
Divisibilidade por 2 
Um número a é divisível por 2, se, e somente se, a termina 
em 0, 2, 4, 6, ou 8. 
Demonstração 
Temos que 0 1 10 10
n
na c c c= + + … + .
Então: 0 1 – 10 10
n
na c c c= + … + .
Sabemos que 10 0 ( 2)mod≡ , portanto, 10 0 ( 2)n mod≡ . 
Então: 0– 0 ( 2)ac mod≡ (Porque é possível somar congru-
ências, lembra-se?). 
Como 0 ( 2)a c mod≡ , logo 0 ( 2)a mod≡ . De acordo com a 
transitividade, devemos ter 0 0 ( 2)c mod≡ . Em outras palavras, 
c0, o algarismo das unidades de a, deve ser um número par. Lem-
bre que a transitividade é recíproca, e isso justifica o “se, e somen-
te se” do enunciado. 
© Teoria dos Números122
Divisibilidade por 9 
Um número a é divisível por 9, se, e somente se, a soma dos 
algarismos de a for divisível por 9.
Demonstração 
Como 10 1 ( 9)mod≡ , então, para 0n > , 10 1 ( 9)n mod≡ , e 
dado qualquer cn, 10 ( 9)nn nc c mod≡ .
Temos que 0 1 10 10
n
na c c c= + + … + . Então: 
0 1( ) ( 9)na c c c mod≡ + + … + . 
Assim, 0 ( 9)a mod≡ , se, e somente se, 
0 1( ) 0 ( 9)nc c c mod+ + …+ ≡ . 
Exemplos: 
2.313 é divisível por 9, pois 2 3 1 3 9+ + + = . 
1.333 não é divisível por 9, pois 1 3 3 3 10+ + + = , e 10 não é 
divisível por 9.
A divisibilidade por 3 pode ser deduzida partindo da divisibi-
lidade por 9.
Divisibilidade por 3 
Um número a é divisível por 3, se, e somente se, a soma de 
seus algarismos for divisível por 3. 
Demonstração 
Como 3|9, 10 ( 9) 10 ( 3)n nn n n nc c mod c c mod≡ → ≡ , e o 
mesmo raciocínio da demonstração anterior se aplica aqui. 
Divisibilidade por 4 
Um número a é divisível por 4, se, e somente se, o número 
formado por seus dois últimos algarismos for divisível por 4.
123
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
Em primeiro lugar, note que 
1 210 –2 ( 4) 10 4 ( 4) 0 ( 4)mod mod mod≡ → ≡ ≡ .
Assim, para 0n > , 210 0 ( 4)n mod≡ .
Note, também, que 210 10 0 ( 4)n mod⋅ ≡ , ou seja, 
210 1 0 ( 4)n mod+ ≡ . 
Por 102n entende-se “10 elevado a um expoente par”, e, por 
102n + 1, entende-se "10 elevado a um expoente ímpar". Consi-
derando as potências com expoente par e com expoente ímpar, 
estamos abrangendo todas as potências (com expoentes intei-
ros) de 10. Assim, exceto para 101, todas as potências de 10 são 
0 ( 4)mod≡ . 
Temos que 
2
0 1 2 0 110 10 10 10 0 0 0 ( 4)
n
na a c c c c c c mod= = + + +… + ≡ + + + … + ≡
Para que a seja divisível por 4, é necessário que 0 110c c+ , ou seja, 
o número formado pelos seus dois últimos algarismos deve ser 
divisível por 4.
Exemplos: 
324 é divisível por 4, pois 24 é divisível por 4. 
123233232 é divisível por 4, pois 32 é divisível por 4. 
1232131223900 é divisível por 4, pois 00 é divisível por 4.
978932413 não é divisível por 4, pois 13 não é divisível por 4.
Deixaremos os critérios de divisão por 5, 6 e 8 como exercícios 
no final desta unidade.
Em primeiro lugar, note que 5 7 13 1001⋅ ⋅ = , e, então, 
0 ( 1001) 0 ( 5)a mod a mod≡ → ≡ , 0 ( 7)a mod≡ , e 
0 ( 13)a mod≡ . Logo, para testar a divisibilidade por 5, 7 ou 13, 
podemos testar a divisibilidade por 1001. E por que isso seria mais 
fácil? 
© Teoria dos Números124
Note que 10³ 1000 –1 ( 1001)mod= ≡ . Então, para 0p > 
par e 0q > ímpar, 310 1 ( 1001)p mod≡ , e 310 –1 ( 1001)q mod≡ . 
Agora, sendo 
2 4 5 6 7 8
0 1 2 3 4 5 6 7 810 10 10³ 10 10 10 10 10 10
n
na c c c c c c c c c c= + + + + + + + + + … + 
note que, a partir da quarta parcela, podemos agrupar cada trio 
de parcelas, colocando 103 em evidência, ficando com:
( ) ( )² /33 2 3 2 3 22 1 0 5 4 3 8 7 6 –2 –1(10² 10 ) 10 (10 10 ) 10 (10 10 ) 10 ( 10 10 )
n
n n na c c c c c c c c c c c c= + + + + + + + + +…+ + + 
Perceba que, na expressão anterior, a primeira parcela é do tipo 
103p ( 0p = ), a segunda é 103q, a terceira, 103p, e assim por diante. 
Portanto, 22 1 0 5 4 3
2
8 7 6
(10² 10 ) – (10 10 )
(10 10 ) – ( 1001)
a c c c c c c
c c c mod
≡ + + + + +
+ + …+…
. 
Assim, para verificarmos a congruência de um número 
mod 1001, devemos tomar o número formado pelos três últimos 
algarismos, subtrair do número formado pelo segundo bloco de 
três algarismos, somar com o número formado pelo terceiro bloco 
de três algarismos, e assim por diante. Obviamente, nosso objetivo 
não é verificar a congruência mod 1001, mas sim, a congruência 
mod 7, 11, ou 13.
Exemplos: 
Para o número 4.102, temos: 102 – 004 98= . 98 divide 7, 
mas não divide 11 nem 13; portanto, 4.102 é divisível por 7, mas 
não por 11 e 13.
Para 40.887, temos: 887 – 0040 847= . 847 é divisível por 7 
e 11, mas não por 13. Logo, 40.887 é divisível por 7 e 11, mas não 
por 13. 
Para o número 123579456, temos: 456 – 579 123 0+ = . 0 é 
divisível por 7, 11 e 13, portanto, 123579456 também é.
125
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
2.4. PROBLEMAS ENVOLVENDO DATAS 
Antes de resolver os problemas a seguir, vamos estudar como 
obter os múltiplos de n número que estão entre dois inteiros a e b.
Exemplo: 
Quantos múltiplos de 5 existem entre 28 e 66? Sabemos que 
o primeiro múltiplo de 5 após 28 é 30, e o último múltiplo de 5 
antes de 66 é 65. 
Entre 65 e 30 (sem contar o 30) há 65 – 30 35= inteiros. 
Como os múltiplos de 5 se repetem de 5 em 5, fazemos 35 5 7÷ = 
múltiplos de 5. Como não havíamos contado o 30, são 8 os 
múltiplos de 5 nesse intervalo.
Assim, para calcular quantos múltiplos de n há entre a e b, 
obtemos o primeiro múltiplo de n após a (chamemos de c) e o 
último múltiplo de n antes de b (chamemos de d). Então, fazemos 
( – ) / 1d c n + e obtemos a quantidade procurada.
Precisamos, também, lembrar que os anos bissextos são os 
representados por múltiplos de 4 (há exceções, como o ano 1900, 
mas é a única que precisaremos considerar em nossos problemas). 
Exemplo: 
Em 2013, o dia dos professores, 15 de outubro, comemorou-
se em uma terça-feira. Em que dia da semana se comemorará o dia 
dos professores, no ano de 2014? 
Problemas com dias da semana são resolvidos da seguinte 
maneira: convenciona-se que o dia da semana em que estamos 
é congruente a 0 mod 7 (afinal, a semana possui 7 dias). O dia 
seguinte, portanto, é congruente a 1 (mod 7), e assim por diante. 
O problema consiste em saber quantos dias se passaram a 
partir do dia dado e saber a congruência mod 7 dessa quantidade. 
Resolução: como 2013 não é um ano bissexto, passar-se-ão 
365 dias até 15 de outubro de 2014. 
© Teoria dos Números126
Por tentativa, vemos que o número mais próximo de 365 que 
é divisível por 7 é 364, portanto 365 1 ( 7)mod≡ . 
Então, o dia dos professores, em 2014, cairá em uma quarta-
feira.
Exemplo: 
Andrew Wiles, matemático britânico que ficou mundialmente 
famoso por demonstrar o Último Teorema de Fermat, nasceu 
no dia 11 de abril de 1953, um sábado. Caso alcance tamanha 
longevidade, em que dia da semana esse cientista completará 100 
anos de idade? 
Andrew Wiles completará 100 anos em 11 de abril de 2053. 
Precisamos saber quantos dias terão se passado desde 1953, 
tomando cuidado com os anos bissextos.
O primeiro múltiplo entre 1953 e 2053 é 1956, e o último é 
2052. Sendo 2052 –1956 96= , e 96 4 1 25÷ + = , logo, são 25 anos 
bissextos entre 1953 e 2053. Isso significa que há 25 dias 29 de 
fevereiro nesse intervalo de 100 anos. Concluímos que se passarão 
365 100 25⋅ + dias.
365 1 ( 7) 100 365 100 ( 7) 2 ( 7)mod mod mod≡ → ⋅ ≡ ≡ 
(por tentativa).
Então: 365 100 25 2 25 2 4 6 ( 7)mod⋅ + ≡ + ≡ + ≡ .
Sendo nosso “0” o sábado, Andrew Wiles comemorará 100 
anos numa sexta-feira.
Vídeo complementar –––––––––––––––––––––––––––––––––
Neste momento, é fundamental que você assista ao vídeo complementar. 
• Para assistir ao vídeo, pela Sala de Aula Virtual, clique no ícone Videoaula, 
localizado na barra superior. Em seguida, selecione o nível de seu curso 
(Graduação), a categoria (Disciplinar) e a disciplina (Teoria dos Números – 
Complementar 4).
• Para assistir ao vídeo, pelo seu CD, clique no Botão Vídeos e selecione: 
Teoria dos Números – Vídeos Complementares – Complementar 4. 
127
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
3. CONTEÚDOS DIGITAIS INTEGRADORES
Os Conteúdos Digitais Integradores são a condição 
necessária e indispensável para você compreender integralmenteos conteúdos apresentados nesta unidade.
3.1. TEOREMAS DE EULER, FERMAT E WILSON
Os textos indicados a seguir apresentam alguns aspectos 
relacionados a esses assuntos.
O primeiro texto traz o Pequeno Teorema de Fermat. O se-
gundo apresenta o Teorema de Fermat (p. 78), o Teorema de Wil-
son (p. 82 a 84) e o Teorema de Euler (p. 119 e 120). 
• FONSECA, T. J. O Pequeno Teorema e o grande erro de 
Fermat. Disponível em: <http://legauss.blogspot.com.
br/2009/12/o-pequeno-teorema-e-o-grande-erro-de.
html>. Acesso em: 26 fev. 2014.
• MAIER, R. R. Teoria dos números. Disponível em: <http://
www.mat.unb.br/~maierr/tnotas.pdf>. Acesso em: 26 
fev. 2014. 
3.2. CRITÉRIOS DE DIVISIBILIDADE
Os textos indicados a seguir mostram como o conceito de 
congruência pode ser utilizado para determinar os critérios de di-
visibilidade. 
No primeiro texto, esse assunto é tratado nas páginas 9 e 10, 
e no segundo, na página 3. 
• GIMENES, L. P. Teorema fundamental da Aritmética. Dis-
ponível em: <http://www.dma.uem.br/kit/arquivos/ar-
quivos_pdf/teoremafundamental.pdf>. Acesso em: 27 
fev. 2014. 
© Teoria dos Números128
• UNESP. Fundamentos de Álgebra Moderna. Disponível 
em: <http://www.feg.unesp.br/~anachiaradia/Material/
FAM-%20congruencia.pdf>. Acesso em: 27 fev. 2014. 
3.3. APLICAÇÕES
Uma aplicação ainda não citada sobre congruência trata so-
bre criptografia RSA, que é o método para codificar qualquer tipo 
de informação enviada pela internet. 
O texto a seguir é muito interessante, e é possível entendê-
-lo com base em tudo o que aprendemos aqui. 
• PEROTTO, T. Criptografia RSA. Disponível em: <http://pes-
soal.utfpr.edu.br/ronie/arquivos/posterRSA.pdf>. Acesso 
em: 27 fev. 2014. 
4. QUESTÕES AUTOAVALIATIVAS
A autoavaliação pode ser uma ferramenta importante para 
você testar o seu desempenho. Se encontrar dificuldades em res-
ponder as questões a seguir, você deverá revisar os conteúdos es-
tudados para sanar as suas dúvidas. 
1) Mostre que 267 334+ é divisível por 17.
2) Utilize o Teorema de Wilson para obter o resto da divisão de 
² ² ² ² ² ² ²3 5 7 9 11 13 15⋅ ⋅ ⋅ ⋅ ⋅ ⋅ por 17.
3) Obtenha todas as soluções das equações diofantinas:
a) 3 5 3x y+ = 
b) 8 7 9x y+ =
c) 10 5 18x y+ = 
d) 12 10 4x y+ = 
e) 15 18 9x y+ = 
4) Determinar as duas menores frações positivas que tenham 5 e 7 para deno-
minadores e cuja soma seja igual a 31/35.
129
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
5) Utilizando o conceito de congruência, prove que:
a) Um número é divisível por 5, se, e somente se, terminar em 0 ou 5.
b) Um número é divisível por 6, se, e somente se, for divisível por 2 e 3.
c) Um número é divisível por 8, se, e somente se, o número formado pelos 
seus três últimos algarismos for divisível por 8.
6) Verifique, sem utilizar a calculadora, se os seguintes números são divisíveis 
por 7, 11 e 13.
a) 17780
b) 195580
c) 2542540
d) 123456789
7) Resolva:
a) Suponha que hoje seja 14 de outubro, e uma segunda-feira. Qual dia da 
semana será daqui a 1.512 dias?
b) O matemático Bernhard Riemann nasceu no dia 17 de setembro de 
1826, em um domingo. Caso estivesse vivo em 2013, em que dia da se-
mana Riemann comemoraria seu aniversário? Lembrando que 1900 não 
foi um ano bissexto. 
c) O cantor Roberto Carlos nasceu no dia 19 de abril de 1941. Sabendo que 
19 de abril de 2013 foi uma sexta-feira, em que dia da semana Roberto 
Carlos nasceu? 
Gabarito
Confira, a seguir, as respostas corretas para as questões au-
toavaliativas propostas: 
1) Pelo Pequeno Teorema de Fermat, temos que 162 1 ( 17)mod≡ , e 
2³ 8 8 ( 17)mod= ≡ .
( )467 64 3 16 32 = 2 2 2 2 1 8 ( 17) 8 ( 17)mod mod= ⋅ ≡ ⋅ ≡ . 
Além disso, 163 1 ( 17)mod≡ , e 23 9 9 ( 17)mod= ≡ .
Então: ( )234 32 2 16 23 3 3 3 3 1 9 9 ( 17)mod= ≡ ⋅ ≡ ⋅ ≡ .
Portanto: 67 342 3 8 9 17 0 ( 17)mod+ ≡ + ≡ ≡ . 
2) Note que 3, 5, 7, 11, 13 e 15, por serem menores que 17, são congruentes a 
si mesmos mod 17. 
Além disso, 3 – 14 ( 17)mod≡ , 5 – 12 ( 17)mod≡ , 
7 –10 ( 17)mod≡ , 9 – 8 ( 17)mod≡ , 11 – 6 ( 17)mod≡ , 
© Teoria dos Números130
13 – 4 ( 17)mod≡ , 15 – 2 ( 17)mod≡ .
Assim, podemos fazer, por exemplo, ( )²3 3 – 14 ( 17)mod≡ ⋅ .
Fazendo isso com todos os números, e efetu-
ando o produto das congruências, teremos: 
( ) ( ) ( ) ( ) ( ) ( ) ( )3 5 7 9 11 15 3 – 14 5 – 12 7 – 10 9 – 8 11 – 6 13 9 – 4 15 – 2 ( 17)mod⋅ ⋅ ⋅ ⋅ ⋅ ≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
, que, reorganizando, fica: 
– 15 14 13 12 11 10 9 8 7 6 5 4 3 1 ( 17) – 15! ( 17)mod mod≡ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≡
Pelo Teorema de Wilson, 15! – 1 ( 17)mod≡ , logo – 15! 1 ( 17)mod≡ . 
Portanto, o resto procurado é 17 –1 16= . 
3) Utilizando o algoritmo de Euclides e o Teorema 67, as soluções serão: 
a) 1 5x h= + , –3y h= 
b) 2 7x h= + , – 1– 8y h= 
c) Não existem soluções inteiras, pois ( )10, 5 5= não divide 18. 
d) 2 5x h= + , – 2 – 6y h=
e) 3 6x h= + , – 2 – 5y h=
4) Basta resolver a equação 7 5 31x y+ = . Teremos como soluções 
0 3 5x h= + e 0 2 – 7y h= .
 0 – 3 / 5x h> → > , 0 2 / 7y h> → < . Portanto, 0h = e as frações 
são 3/5 e 2/7. 
5) a) Mostre que 10 0 ( 5)n mod≡ a 0n > . Portanto, basta analisar o úl-
timo dígito do número.
b) Sabemos que se 1 20 ( )a mod m m≡ ⋅ , então 10 ( )a mod m≡ e 
20 ( )a mod m≡ . Como 6 2 3= ⋅ úmero ser divisível por 6, ele deve 
ser divisível por 2 e por 3. 
c) Mostre que 10 0 ( 8)n mod≡ , para 2n > (baseie-se no que foi feito 
com o 4). Portanto, basta analisarmos o número formado pelos três alga-
rismos do número estudado. 
131
Claretiano - Centro Universitário
© U4 - Congruências: Aplicações 
6) Utilizando o critério mostrado nesta unidade, temos:
a) É divisível apenas por 7.
b) É divisível apenas por 7 e 11.
c) É divisível por 7, 11 e 13.
d) Não é divisível por 7, 11 ou 13. 
7) a) Segunda-feira.
b) Note que, como 1900 não é ano bissexto, ao obter os 47 divisores de 4, 
você deve subtrair 1. Serão 46 dias 29 de fevereiro ao longo desses 187 
anos. Utilizando as congruências, obteremos que o dia será terça-feira.
c) Utilizando o mesmo raciocínio que viemos fazendo, descobriremos que 
entre 19 de abril de 1941 e 19 de abril de 2013, há uma congruência 6 
(mod 7). Porém, como estamos referindo-nos ao passado, precisamos 
voltar 6 dias na semana. Assim, Roberto Carlos nasceu em um sábado. 
5. CONSIDERAÇÕES
Chegamos ao final de nossa última unidade. Vamos relem-
brar tudo o que você aprendeu? 
Na Unidade 1, foram apresentadas a definição de divisibili-
dade, suas propriedades, a demonstração do algoritmo da divisão 
( )b = e do algoritmo de Euclides para o cálculo do MDC entre dois 
números.
Na Unidade 2, estudamos a definição de números primos, a 
demonstração do Teorema Fundamental da Aritmética (todo intei-
ro pode ser escrito, de forma única, como um produto de primos), 
e como ela é útil para calcularmos o MMC e o MDC entre dois 
números. 
Na Unidade 3, você aprendeu a definição de congruência, 
como ela simplifica questões com divisibilidade e como resolver 
congruências lineares.
Na última unidade, foram apresentadas mais aplicações de 
congruências para resolver questões de divisibilidade. 
Este assunto é inesgotável, mas você já pôde ter uma base 
do que é a Teoria de Números e como ela é essencial para provar-
mos resultados que julgamos "básicos" da Matemática. 
© Teoria dos Números132
6. E-REFERÊNCIA
UNICAMP. Prova 1: teoria de números. Disponível em: <http://www.ime.unicamp.
br/~smartin/cursos/teonum13/Prova1%20Resolvida.pdf>. Acesso em: 28 fev. 2014. 
7. REFERÊNCIA BIBLIOGRÁFICA
LANDAU, E. Teoria elementar dos números. Rio de Janeiro: Ciência Moderna, 2002.