Crit de div e o uso da congruência e dos teo de Fermat e de Wilson

Prévia do material em texto

Critérios de divisibilidade e o uso da 
congruência e dos teoremas de 
Fermat e de Wilson
Apresentação
No conjunto dos números inteiros existem diversos conceitos importantes. Entre esses conceitos, 
destaca-se o conceito de divisibilidade. Além disso, a equivalência entre os números inteiros pode 
ser destacada pela relação de congruência desses números.
Para que você possa acompanhar adequadamente esta Unidade, é necessário revisar a 
divisibilidade no conjunto dos números inteiros e suas propriedades, bem como os conceitos de 
fatorial e binômio de Newton. Adicionalmente, é de suma importância relembrar o conceito de 
congruência dos elementos de Z.
Nesta Unidade de Aprendizagem, você aprenderá a relação entre os conceitos de divisibilidade e de 
congruência. Você também descobrirá a aplicação desses conceitos nos teoremas de Fermat e de 
Wilson. Assim, poderá resolver problemas, na prática, tratando a divisibilidade e a congruência 
simultaneamente.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Construir critérios de divisibilidade utilizando a congruência.•
Interpretar os teoremas de Wilson e de Fermat.•
Resolver problemas de congruência utilizando os teoremas de Wilson e de Fermat.•
Infográfico
Os conceitos de divisibilidade e de congruência são abordados na teoria dos números. Mais 
especificamente, suas propriedades são deduzidas, e, dessa forma, é possível tratar suas aplicações.
No Infográfico a seguir, veja a relação existente entre a divisibilidade e a congruência.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Conteúdo do livro
Em 1801, Carl Friedrich Gauss teve sua obra Disquisitiones Arithmeticae publicada, cujo conceito e 
notação de congruência eram apresentados pela primeira vez à comunidade científica. Nesse 
contexto, a definição de congruência pode embasar diversos trabalhos que tratam a teoria dos 
números.
No capítulo Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de 
Wilson, da obra Álgebra, base teórica desta Unidade de Aprendizagem, você aprofundará seus 
conhecimentos sobre divisibilidade e congruência, suas relações e aplicações.
Boa leitura.
ÁLGEBRA
Stephanie Loi Brião
Critérios de divisibilidade 
e o uso da congruência 
e dos teoremas de 
Fermat e de Wilson
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Construir critérios de divisibilidade utilizando a congruência.
 � Interpretar os teoremas de Wilson e de Fermat.
 � Resolver problemas de congruências utilizando os teoremas de Wilson 
e de Fermat.
Introdução
Na teoria dos números, a divisibilidade é um conceito fundamental. Nesse 
contexto, a definição de congruência é uma verificação da divisibilidade. 
Pierre de Fermat (1601–1665) teve vários estudos consolidados no ramo 
da teoria dos números. Entretanto, Carl Friedrich Gauss (1777–1855) foi o 
primeiro matemático a tratar a teoria das congruências como uma área 
da matemática.
Neste capítulo, você vai estudar quais características comuns a divi-
sibilidade e a congruência possuem e como resolver exemplos de con-
gruência aplicando conceitos de divisibilidade. Você também vai verificar 
como deduzir propriedades importantes que utilizam as definições de 
congruência e de divisibilidade. Por fim, você vai aprender a identificar e 
demonstrar os teoremas de Wilson e Fermat e a fazer uso desses teoremas 
na resolução de problemas de congruência.
1 Critérios de divisibilidade aplicando 
congruência
Antes de interpretar a relação entre a divisibilidade e a congruência, vamos 
relembrar alguns conceitos relevantes. Considerando o conjunto dos inteiros, 
dizemos que um número b é divisível pelo número a se b é múltiplo de a 
(CAMPOS, 2009). A recíproca também é válida. Conforme Santos (2018), 
a aritmética a seguir, pertencente ao conjunto dos números inteiros, pode ser 
definida.
 � Definição 1: Se a e b são inteiros, dizemos que a divide b, denotando 
por a|b se, e somente se, existir um inteiro c ∈ ℤ tal que b = ac.
 ■ Observação: caso um inteiro a não divida b, vamos denotar a∤b.
 ■ Exemplo: o número divide 8 porque existe um inteiro c = –2,tal 
que 8 = (–4)(–2).
Fenômenos cíclicos ou periódicos possuem em seu comportamento a 
repetição dos acontecimentos. Podemos exemplificar matematicamente o 
fenômeno das horas (COUTINHO, 1997). Os dias mudam, mas as horas são 
mantidas equivalentes. 
Diante disso, vamos considerar um número inteiro n, o qual será o módulo 
(período). Mais especificamente, adotaremos dois inteiros a e b equivalentes 
de n em n períodos. Podemos dizer que a e b são congruentes módulo n. 
Assim, definimos formalmente a congruência dos elementos em ℤ, com base 
em Gonçalves (2017).
 � Definição 2: Se a e b são números inteiros, dizemos que a é congruente 
b módulo n (n >0) se n|(a – b). Denotamos isso por a ≡ b (mod n). 
Se n∤(a – b), dizemos que a é incongruente a b módulo n e denotamos 
a ≢ b (mod n).
Veja a seguir alguns exemplos da Definição 2.
1. 16 ≡ –4 (mod 10), pois 16 – (–4) = 20, sendo que 10|20.
2. 8 ≢ 3 (mod 2), pois 8 – 3 = 5, sendo que 2∤5 no conjunto ℤ.
3. 72 ≡ –5 (mod 7), pois 7|(72 – (–5)).
4. 27 ≢ 8 (mod 9), pois 9|(27 – 8).
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson2
O estudo do resto da divisão de dois inteiros diferentes por outro inteiro é 
chamado de módulo. Ou seja, se dois números inteiros possuem o mesmo resto 
na divisão pelo n, esses números são congruentes módulo n (LIPSCHUTZ; 
LIPSON, 2009).
 � Proposição 1: Se a e b são inteiros, temos quea ≡ b (mod n) se, e somente 
se, existir um inteiro k tal que a = b + km.
 ■ Demonstração: se a ≡ b (mod n), então n|(a – b). O que implica na 
existência de um número inteiro k tal que a – b = kn, isto é, a = b + kn. 
A recíproca é trivial, pois, da existência de um k satisfazendo a = b 
+ kn, temos kn = a – b, ou seja, que n|(a – b), isto é, a ≡ b (mod n).
Agora que você relembrou a associação de números divisíveis e de números 
congruentes, serão especificados os critérios de divisibilidade utilizando a 
congruência.
Critérios de divisibilidade
Para manipular as congruências de forma mais simplificada, você precisa 
construir os critérios de divisibilidade. Assim, poderá resolver problemas de 
congruência com números muito elevados. Ao tratarmos os critérios de divi-
sibilidade de inteiros a = anan–1 ⋯ a1a0, podemos representá-los pelo seguinte 
polinômio (DOMINGUES; IEZZI, 2003):
a = an10n + an–110n–1 + ⋯ + a110 + a0 (1)
onde a0 é o algarismo das unidades, a1 é o algarismo das dezenas e assim 
por diante.
Logo, o intuito de usar as propriedades de congruência é para reduzir os 
algarismos do numeral expressado em (1). Assim, podemos calcular a divisi-
bilidade de números inteiros sem a necessidade de um sistema computacional, 
como mostrado a seguir.
Critério de divisibilidade por 2
Iniciamos pela simples congruência 10 ≡ 0 (mod 2), verdadeira também para 
potências de 10 — isto é, a congruência 10t ≡ 0 (mod 2) é válida para todo 
t ≥ 1. Como o polinômio (1) possui potências de 10, podemos reescrever a 
congruência para o inteiro a — assim, a – a0 ≡ 0 (mod 2).
3Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
Então a ≡ a0 (mod 2) e, pela definição 2, a divisão 2|(a – a0) é válida. O 
que implica 2|a se, e somente se, 2|a0. Logo, o algarismo da unidade a0 deve 
ser par. Em outras palavras, isso demonstra que todo inteiro com algarismo 
da unidade par é divisível por 2.
Critério de divisibilidade por 3
Pela congruência verdadeira 10 ≡ 1 (mod 3), vamos começar a construir esse 
critério de divisibilidade. Utilizando a propriedade de potência na congruência, 
isso resulta em 10t ≡ 1 (mod 3) para todo t ≥ 1. Dessa forma, vamos multiplicar 
os coeficientes at na congruência anterior.
Assim, at10t ≡ at (mod 3), sendo 1 ≤ t ≤ n. Somando-se todas essas congru-ências, fica a ≡ an + an–1 + ⋯ + a1 + a0 (mod 3). Pela Definição 2, a é divisível 
por 3 se, e somente se, o termo an + an–1 + ⋯ + a1 + a0 é divisível por 3. Portanto, 
isso mostra que, para todo inteiro divisível por 3, a soma dos seus algarismos 
também é divisível por 3.
Critério de divisibilidade por 4
Observamos que 102 ≡ 0 (mod 4), 103 ≡ 0 (mod 4) e assim sucessivamente 
até 10n ≡ 0 (mod 4) Se multiplicarmos os coeficientes do polinômio (1) nas 
congruências respectivas, obtemos: a2102 ≡ 0 (mod 4), a3103 ≡ 0 (mod 4), ⋯, 
an10n ≡ 0 (mod 4).
Pelas propriedades aritméticas de números côngruos, podemos somar 
todas as congruências e adicionar o termo a0 + a110 no resultado obtido. Isso 
implica a ≡ a0 + a110 (mod 4). É importante notar que a0 + a110 = a1a0, ou seja, 
são os dois últimos algarismos do número a. Então, o inteiro a e o termo a0a1 
possuem o mesmo resto na divisão por 4. Logo, a e a1a0 são divisíveis por 4. 
Essa construção mostra que, se o termo formado pelos dois últimos algarismos 
de um inteiro é divisível por 4, o inteiro é divisível também.
Critério de divisibilidade por 8
Pela congruência simples 10 ≡ 2 (mod 8), podemos elevar na potência 3. 
Assim, 103 ≡ 23 ≡ 0 (mod 8) é verdadeira. Também segue que, para todo ai, 
i ≥ 3, a congruência ai10i ≡ 0 (mod 8) é válida. Isso mostra que a congruência 
a ≡ a2a1a0 (mod 8) é satisfeita para qualquer inteiro a divisível por 8.
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson4
Portanto, o critério de divisibilidade por 8 mostra que, para qualquer nú-
mero inteiro com dígitos iguais ou maiores do que 3, um inteiro é divisível 
por 8 se, e somente se, os três últimos algarismos desse inteiro formam um 
número divisível por 8.
Critério de divisibilidade por 11
Sabemos que 10 ≡ –1 (mod 11). Assim, podemos elevar a potência k ∈ ℕ na 
congruência anterior, tornando 10k ≡ (–1)k (mod 11). Considerando a de (1), 
multiplicamos os coeficientes a1, ⋯, an em cada n congruências, somamos 
esses termos e o a0 e obtemos:
a ≡ (–1)nan + (–1)n–1an–1 + ⋯ + (–1)1a1 + a0 (mod 11)
Mais especificamente, isso implica a congruência:
a ≡ (a0 + a2 + ⋯) – (a1 + a3 + ⋯) (mod 11).
Logo, um número inteiro é divisível por 11 se, e somente se, a soma dos 
algarismos de ordem par subtraída da soma dos algarismos de ordem ímpar 
resulta em um número inteiro divisível por 11.
Agora você terá a oportunidade de aprender a resolver problemas numéricos 
que envolvem critérios de divisibilidade.
Exemplos
A seguir, serão apresentados cinco problemas.
1. Calcule o resto da divisão de 230 por 17.
Como a congruência 24 ≡ –1 (mod 17) é verdadeira, podemos elevar à 
potência 7. Isso resulta em 228 ≡ –1 (mod 17). Agora, multiplicamos na con-
gruência o número 4 = 22. Dessa forma, obtemos 230 ≡ –4 (mod 17). Sabendo 
que –4 ≡ 13 (mod 17) e que a propriedade de transitividade é válida, então 
230 ≡ 13 (mod 17). Logo, o resto da divisão é 13.
5Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
2. Mostre que 10200 – 1 é divisível por 11.
Iniciamos pela congruência 10 ≡ –1 (mod 11). Depois, utilizamos a pro-
priedade de potência resultando em 10200 ≡ (–1)200 (mod 11). Assim, 10200 ≡ 1 
(mod 11), e pela Definição 2, a expressão numérica 10200 – 1 é divisível por 11.
3. Mostre que 12.564.890 é divisível por 3.
Pela congruência 10 ≡ 1 (mod 3) válida, obtemos 10t ≡ 1 (mod 3), t ∈ ℕ. 
Então, pelo critério de divisibilidade por 3: 12.564.890 ≡ (1 + 2 + 5 + 6 + 4 + 
8 + 9 + 0) (mod 3). Ou seja, 12.564.890 ≡ 45 (mod 3). Como 45 ≡ 0 (mod 3), 
pela propriedade de transitividade, isso resulta em 12.564.890 ≡ 0 (mod 3). 
Logo, 12.564.890 é divisível por 3.
4. Calcule o resto da divisão de 25.384 por 2.
Fazendo a decomposição do número inteiro 25.384 no polinômio de 
base 10, representado na equação (1), isso implica 25.384 ≡ (2 ⋅ 104 + 5 ⋅ 
103 + 3 ⋅ 102 + 8 ⋅ 101 + 4) (mod 2). Assim, pelo critério de divisibilidade 2, 
a congruência anterior é equivalente a 25.384 ≡ 4 (mod 2). Também sabemos 
que 4 ≡ 0 (mod 2), então, pela transitividade, 25.384 ≡ 0 (mod 2). Portanto, 
o resto da divisão buscada é zero.
5. Calcule o resto da divisão de 172002 por 13.
Pelas congruências 17 ≡ 4 (mod 13), 16 ≡ 3 (mod 13) e pelas propriedades 
de potência em congruências, segue que 172002 ≡ 42002 ≡ 161001 ≡ 31001 (mod 13). 
Observamos que 33 ≡ 1 (mod 13); então:
31001 = 32 ⋅ 3999 = 9 ⋅ (33)333 ≡ 9 ⋅ 1333 = 9 (mod 13)
Portanto, 172002 ≡ 9 (mod 13), isto é, 172002 possui resto 9 na divisão por 13.
Os teoremas de Wilson e Fermat são consequências de conceitos intro-
dutórios de congruência e de critérios de divisibilidade. Você aprenderá a 
construção desses teoremas a seguir.
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson6
2 Estruturação dos teoremas de Wilson 
e de Fermat
Para interpretar os teoremas de Wilson e de Fermat, vamos apresentar pro-
posições, definições e corolários, os quais serão a base do conhecimento. 
Todo inteiro com o mesmo resto em módulo pertence à mesma classe. Isto é, 
os números que pertencem à mesma classe possuem o mesmo resto. Desse 
modo, podemos definir uma classe residual a seguir (HEFEZ, 2016).
 � Definição 3: Dado um inteiro m > 1. A classe residual módulo m do 
elemento a ∈ ℤ é definida como a classe de equivalência de a, conforme 
a seguinte relação de equivalência dada pela congruência módulo m:
[a] = {x ∈ ℤ; x ≡ a (mod m)}.
 ■ Exemplo: seja m = 2. Então:
[0] = {x ∈ ℤ; x ≡ 0 (mod 2)} = {x ∈ ℤ; x é par} e
[1] = {x ∈ ℤ; x ≡ 1 (mod 2)} = {x ∈ ℤ; x é ímpar}.
Também podemos perceber que [a] = [0], se a é par, e [a] = [1], se a é ímpar. 
Logo, as classes residuais, por serem classes de equivalência, possuem as 
seguintes propriedades:
a) [a] = [b] se, e somente se, a ≡ b (mod m);
b) se [a] ∩ [b] ≠ ∅, então [a] = [b];
c) ⋃a∈ℤ[a] = ℤ.
O conjunto de todas as classes residuais módulo m pode ser denotado por ℤm.
 � Proposição 2: Para cada a ∈ ℤ, existe um, e somente um, r ∈ ℤ, com 
0 ≤ r < m, tal que [a] = [r].
 ■ Demonstração: seja a ∈ ℤ, e considerando-se a divisão euclidiana, 
existem dois únicos inteiros q e r, com 0 ≤ r < m, tais que a = m ⋅ q 
+ r. Então, o inteiro r é único, tal que 0 ≤ r < m e a ≡ r (mod m). Por 
consequência, o inteiro r é único tal que 0 ≤ r < m e [a] = [r].
7Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
Adicionalmente, todo resto de um número de uma classe residual é conside-
rado resíduo em módulo. Em Niven, Zuckerman e Montgomery (1991), podemos 
encontrar a definição de resíduo em módulo, conforme apresentado a seguir.
 � Definição 4: Se x ≡ y (mod m) para x e y sendo inteiros, então y é 
chamado de resíduo de x módulo m.
Para definir uma característica em comum de um grupo de resíduos, foram 
propostas as definições a seguir (ANDREWS, 1994).
 � Definição 5: O conjunto dos inteiros {r1, ⋯, rs} é chamado de um sistema 
completo de resíduo módulo m se ri ≢ rj (mod m) para i ≠ j; para cada 
inteiro n existe um correspondente ri tal que n ≡ ri (mod m). Em outras 
palavras, o sistema é completo de resíduos {r1, ⋯, rs} módulo m se, 
e somente se, [r1], ⋯, [rm] são as m classes residuais módulo m.
 � Definição 6: Um sistema reduzido de resíduos módulo m é um conjunto 
ϕ(m) inteiros r1, ⋯, rϕ(m), tais que cada elemento do conjunto é relati-
vamente primo com m, e se i ≠ j, então ri ≢ rj (mod m).
Teorema 1: Seja a um inteiro positivo tal que MDC(a, m) = 1, sendo MDC 
o máximo denominador comum. Se r1, ⋯, rϕ(m) é um sistema reduzido de 
resíduos módulo m, então ar1, ⋯, arϕ(m) é, também, um sistema reduzido de 
resíduos módulo m.
Demonstração: Na sequência ar1, ⋯, arϕ(m), temos ϕ(m) elementos. Assim, 
devemos provar que todos os elementos são relativamente primos com m. 
Como o MDC(a, m) = 1 e o MDC(ri, m) = 1, isso implica que MDC(ari, m) = 1. 
Basta provar que ari ≢ arj (mod m) se i ≠ j. Porém, como MDC(a, m) = 1 de 
ari ≡ arj (mod m), obtemos ri ≡ rj (modm). Então, i = j, para r1, ⋯, rϕ(m) ser um 
sistema reduzido de resíduos módulo m.
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson8
Exemplo 1
Para um módulo m = 15, existem oito números inteiros entre 1 e 15, os quais são 
coprimos de 15, como: 1, 2, 4, 7, 8, 11, 13, 14. Assim, φ(15) = 8 e os inteiros citados formam 
um sistema de resíduos reduzidos módulo 15.
Exemplo 2
Encontre para os elementos a seguir um sistema reduzido de resíduos módulo m e φ(m).
 � Para m = 9: {1, 2, 4, 5, 7, 8}, então φ(9) = 6.
 � Para m = 16: {1, 3, 5, 7, 9, 11, 13, 15}, então φ(16) = 8.
 � Para m = 7: {1, 2, 3, 4, 5, 6}, então φ(7) = 6, pois 7 é um número primo.
Proposição 3: Um elemento [a] ∈ ℤm é invertível se, e somente se, MDC(a, m) 
= 1.
 ■ Demonstração: se [a] é invertível, então existe [b] ∈ ℤm tal que [1] 
= [a] ⋅ [b] = [a ⋅ b]. Isso implica a ⋅ b ≡ 1 (mod m). Ou seja, existe um 
t, tal que a ⋅ b + t ⋅ m = 1. Logo, MDC(a, m) = 1. Se MDC(a, m) = 1, 
existem números inteiros b e t, sendo a ⋅ b + m ⋅ t = 1, implicando 
em [1] = [a ⋅ b + m ⋅ t] = [a ⋅ b] + [m ⋅ t] = [a] ⋅ [b] + [0] = [a] ⋅ [b]. 
Portanto, [a] é invertível.
Os números coprimos também são chamados de primos entre si ou primos relativos.
Podemos concluir por essa proposição e pelo Teorema 1 que um conjunto 
{r1, ⋯, rϕ(m)} ⊂ ℤ é um sistema reduzido de resíduos módulo m se [r1], ⋯, [rϕ(m)] 
são elementos invertíveis de ℤm. Então, podemos denotar o conjunto dos ele-
mentos invertíveis como ℤ*m. Além disso, na bibliografia de Galdino (2014), 
você poderá encontrar como uma solução de uma congruência é nomeada.
9Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
 � Definição 7: Para a e m números inteiros, a solução a̅ de x em ax ≡ 1 
(mod m) é chamada de um inverso de a módulo m.
Em Santos (2018), a proposição a seguir foi apresentada.
 � Proposição 4: Seja p um número primo. O inteiro positivo a é o seu 
próprio inverso módulo p se, e somente se, a ≡ 1 (mod p) ou a ≡ –1 
(mod p).
Agora vamos abordar os teoremas propostos no início deste estudo. 
O teorema de Wilson possui diversas demonstrações, mas apresentaremos a 
demonstração de Andrews (1994).
Teorema de Wilson
A congruência (m – 1)! ≡ –1 (mod m) é satisfeita se, e somente se, m for um 
número primo.
Demonstração 1
Vamos supor m um número primo e 1, ⋯, m – 1 inteiros positivos. Pela Defini-
ção 5, se a é um número inteiro, então existe um inverso ã de a módulo m tal 
que aã ≡ 1 (mod m). Caso a seja seu próprio inverso, a2 ≡ 1 (mod m). Assim, 
m|(a – 1)(a + 1), o que resulta em m|(a – 1) ou m|(a – 1). Pela Definição 2, 
a ≡ ±1 (mod m). Como 1 e m - 1 são os únicos próprios inversos de módulo m, 
vamos agrupar os números m – 2, ⋯, 2 em pares congruentes a 1 módulo m.
Dessa forma, o produto dessas congruências resulta em 2 × ⋯ × m – 2 ≡ 
1 (mod m). Multiplicando-se pelo termo m – 1, isso implica (m – 1)! ≡ (m – 1)
(mod m). Pela congruência, m – 1 ≡ –1 (mod m), e, pela transitividade, obtemos 
(m – 1)! ≡ –1 (mod m).
Supondo que m não é primo, então existe um número a (1 < a < m) tal que 
a|m. Também podemos observar que a|(m – 1)!. Se (m – 1)! ≡ –1 (mod m), 
então, pela definição de congruência, existirá um inteiro k tal que (m – 1)! + 
1 = km. Como a|m e a|(m – 1)!, utilizando a equação anterior, obtemos a|1. 
Isso contradiz a hipótese a > 1. Logo, se (m – 1)! ≡ –1 (mod m), o número m 
deve ser primo.
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson10
Demonstração 2
A expansão de Maclaurin da função ln é:
Pelas propriedades logarítmicas e exponenciais, isso resulta em:
Reescrevemos a equação em:
O que é equivalente a:
Sabemos que, pela função inicial, o termo xp = 1. Esse coeficiente, pela 
equação anterior, é da forma , sendo r/s a soma de um número finito 
de racionais que não possuem o fator p no denominador, caso MDC(r, s) = 1 
e p∤s. Então, para = 1, obtemos:
Desse modo:
11Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
Como o termo (s – r)(p – 1)! é um inteiro e p∤s, então p|(1 + (p – 1)!).
Também será abordada a seguinte definição de função de Euler, a qual 
forma a base para um importante teorema.
 � Definição 8: A função ϕ: ℤ+ → ℤ+, que associa a cada número inteiro 
positivo m a quantidade de elementos do conjunto {k ∈ ℤ+|1 ≤ k ≤ m – 1 
e MDC(k, n) = 1}, é chamada função de Euler.
Pela Definição 6, podemos deduzir que a função ϕ(m) mostra quantos 
dos números do conjunto {1, ⋯, m – 1} são primos entre si. Caso m seja um 
número primo qualquer, todos os números 1, ⋯, m – 1 são coprimos de m. 
Logo, ϕ(m) = m – 1. Dessa forma, Euler também teve sua contribuição na 
teoria das congruências. O teorema a seguir mostra isso.
Teorema de Euler
Se m é um inteiro positivo e a um inteiro com MDC(m, a) = 1, então aϕ(m) ≡ 1 
(mod m). Veja a seguir a demonstração.
Demonstração
Seja r1, ⋯, rϕ(m) um sistema reduzido de resíduos módulo m. Observamos que 
ar1, ⋯, arϕ(m) são todos primos relativos a m e que também formam um sistema 
de resíduos reduzidos módulo m. Então, para cada ri, i = 1, ⋯, ϕ(m), existe 
um e somente um arj, j = 1, ⋯, ϕ(m), tal que ri ≡ arj (mod m). Notamos que 
diferentes ri correspondem a diferentes arj. Isto é, os números ar1, ⋯, arϕ(m) são 
apenas resíduos módulo m de r1, ⋯, rϕ(m), mas não necessariamente na mesma 
ordem. Assim, multiplicando todas as congruências, obtemos:
O que, pelas propriedades do produtório, implica:
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson12
Sabendo que MDC(rj, m) = 1 e os rj são primos relativos em m, concluímos 
que
aϕ(m) ≡ 1 (mod m)
Com o resultado de Euler, podemos enunciar o teorema de Fermat (GAR-
CIA; LEQUAIN, 2006), cuja demonstração é apresentada em Monteiro (1978).
Teorema de Fermat
Se p é um número primo, a é um número inteiro e p∤a, então ap–1 ≡ 1 (mod p). 
Veja a seguir a demonstração. 
Demonstração
Como p∤a, o MDC entre p e a é 1. Pelo teorema de Euler, aϕ(p) ≡ 1 (mod p), 
onde ϕ(p) é um número inteiro positivo menor ou igual a p. Assim, devemos 
buscar os números de ϕ(p) primos entre si. Logo, sendo p primo, ϕ(p) = p – 1. 
Portanto, o teorema de Euler é uma generalização do teorema de Fermat.
3 Aplicações dos teoremas de Wilson 
e de Fermat
Com os conhecimentos adquiridos para elaborar e demonstrar os teoremas de 
Wilson e de Fermat, agora você vai aprender a aplicar esses conhecimentos 
por meio de proposições lógicas e exemplos. Por consequência do teorema de 
Fermat, foi construído o corolário descrito a seguir (LEMOS, 2001).
Corolário 1: Se p é um número primo e n um inteiro positivo, então np ≡ n 
(mod p). Veja a seguir a demonstração.
Se p|n, então np ≡ 0 ≡ n (mod p). Se p∤n, então MDC(p, n) = 1. Assim, pelo 
teorema de Euler:
np–1 ≡ 1 (mod p)
13Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
onde ϕ(p) = p – 1. Agora, multiplicando ambos os lados da congruência por 
n, concluímos que:
np ≡ n (mod p)
Também foi construída, a partir do teorema de Euler, a seguinte proposição: 
se p é primo, então ϕ(pn) = pn – pn–1 = pn–1 (p – 1). Veja a demonstração a seguir.
O número p|a se, e somente se, MDC(pn, a) ≠ 1. Assim, os únicos números 
entre 1 e pn que não são primos relativos com pn são os múltiplos de p, isto é, 
p, 2p, ⋯, pn–1(p). Então, existem pn–1 múltiplos de p. O restante dos números 
são primos relativos com pn. Logo, a expressão ϕ(pn) = pn – pn–1 = pn–1(p – 1)
é verdadeira.
Agora vamos apresentar exemplos numéricos para que você possa aprender 
como colocar em prática seus estudos na área de congruência com aplicações 
de teoremas.
Exemplos
No primeiro exemplo você precisa utilizar a Definição 4, a qual mostra o que 
é um resíduo. Já o segundo exemplo trata de uma congruência com módulo 
de um número primo. No terceiro exemplo, demonstraremos o teorema de 
Fermat por um exemplo numérico. O exemplo 4 apresenta o cálculo do restode uma divisão que utiliza o teorema de Euler.
1. Encontre o menor resíduo positivo da expressão 6 × 7 × 8 × 9 módulo 
5 utilizando o teorema de Wilson.
Observamos que os resíduos menores de cada número da multiplicação 
acima são 6 ≡ 1 (mod 5), 7 ≡ 2 (mod 5), 8 ≡ 3 (mod 5) e 9 ≡ 4 (mod 5). Então, 
pelas propriedades aritméticas de congruência, obtemos 6 × 7 × 8 × 9 ≡ 1 
× 2 × 3 × 4 (mod 5). Também, sabemos pelo teorema de Wilson que 4! ≡ –1 
(mod 5). Pela transitividade, 6 × 7 × 8 × 9 ≡ –1 ≡ 4 (mod 5). Logo, o menor 
resíduo positivo é 4.
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson14
2. Calcule o valor 25432675 módulo 13 utilizando o teorema de Fermat.
Não precisamos calcular essa potência elevada nem usar as propriedades 
de potência. Devido ao teorema de Fermat, basta calcular a congruência do 
expoente 5432675 pelo módulo de p – 1 = 13 – 1 = 12 — ou seja, encontrar 
o resto da divisão, o que resulta no valor 11. Logo, 25432675 ≡ 211 ≡ 7 (mod 13) 
e o resto r = 7.
3. Mostre pelo teorema de Fermat que 213 ≡ 2 (mod 7).
Seja 26 ≡ 1 (mod 7) pelo teorema de Fermat, então a congruência é equi-
valente a (26)2 ≡ 12 (mod 7), o que resulta em 212 ≡ 1 (mod 7). Multiplicamos a 
congruência pelo número 2, assim, obtemos 213 ≡ 2 (mod 7). Logo, mostramos 
que a congruência acima é verdadeira.
4. Calcule o resto da divisão 31239 por 10, utilizando o teorema de Euler.
Realizando os cálculos, obtemos ϕ(10) = 4 e MDC(3, 10) = 1. Dessa forma, 
pelo teorema de Euler, isso resulta em 34 ≡ 1 (mod 10). Agora, pela divisão 
do número 1239 por 4, escrevemos 1239 = 309 ⋅ 4 + 3. Elevando à potência 
309, a congruência inicial fica (34)309 ≡ 1309 (mod 10). Multiplicando-se pelo 
termo 33 na congruência anterior, segue que 31239 ≡ 27 (mod 10). Pela definição 
de congruência, podemos buscar a seguinte equivalência: 31239 ≡ 7 (mod 10). 
Logo, o resto da divisão procurada é 7.
5. Encontre os valores das funções de Euler ϕ(81) e ϕ(76).
Como ϕ(81) = ϕ(33), então ϕ(81) = 33(3 – 1) = 27(2) = 54. Sendo ϕ(76) = 
75(7 – 1) = 6(75) = 100842.
Com os exemplos apresentados, ampliamos o estudo na resolução de con-
gruências de números primos e de números muito elevados. Diante desses 
estudos de congruência e divisibilidade, você poderá resolver problemas de 
forma autônoma.
15Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
ANDREWS, G. E. Number theory. Massachusetts: Courier Corporation, 1994.
CAMPOS, E. de. A noção de congruência algébrica no curso de Matemática: uma análise 
das respostas dos estudantes. 2009. Tese (Doutorado em Educação) - Universidade 
Federal do Paraná, Curitiba, 2009. Disponível em: http://www.ppge.ufpr.br/teses/
D09_campos.pdf. Acesso em: 8 out. 2020.
COUTINHO, S. C. Números inteiros e criptografia RSA. Rio de Janeiro: Instituto de Mate-
mática Pura e Aplicada, 1997.
DOMINGUES, H. H.; IEZZI, G. Álgebra moderna. São Paulo: Atual, 2003.
GALDINO, U. A. Teoria dos números e criptografia com aplicações básicas. 2014. Dissertação 
(Mestrado em Matemática) - Universidade Estadual da Paraíba, Campina Grande, 2014. 
Disponível em: http://tede.bc.uepb.edu.br/jspui/bitstream/tede/2266/5/PDF%20-%20
Uelder%20Alves%20Galdino.pdf. Acesso em: 8 out. 2020.
GARCIA, A.; LEQUAIN, Y. Elementos de álgebra. Rio de Janeiro: Instituto de Matemática 
Pura e Aplicada, 2006.
GONÇALVES, A. Introdução à álgebra. Rio de Janeiro: Impa, 2017.
HEFEZ, A. Curso de álgebra. Rio de Janeiro: Instituto de Matemática Pura e Aplicada, 
2016. v. 1.
LEMOS, M. Criptografia, números primos e algoritmos. Rio de Janeiro: Instituto de Mate-
mática Pura e Aplicada, 2001.
LIPSCHUTZ, S.; LIPSON, M. Matemáticas discretas. 3. ed. São Paulo: McGraw-Hill, 2009. 
(Coleção Schaum).
MONTEIRO, L. H. J. Elementos de álgebra. 2. ed. Rio de Janeiro: Livro Técnico e Científico, 
1978.
NIVEN, I.; ZUCKERMAN, H. S.; MONTGOMERY, H. L. An introduction to the theory of numbers. 
Hoboken: John Wiley & Sons, 1991.
SANTOS, J. P. de O. Introdução à teoria dos números. Rio de Janeiro: Instituto de Mate-
mática Pura e Aplicada, 2018.
Leitura recomendada
BOYER, C. B.; MERZBACH, U. C. História da matemática. São Paulo: Blucher, 2019.
Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson16
Os links para sites da web fornecidos neste capítulo foram todos testados, e seu fun-
cionamento foi comprovado no momento da publicação do material. No entanto, a 
rede é extremamente dinâmica; suas páginas estão constantemente mudando de 
local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade 
sobre qualidade, precisão ou integralidade das informações referidas em tais links.
17Critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de Wilson
Dica do professor
Uma importante habilidade do professor de Matemática é aprender a realizar a demonstração de 
teoremas, corolários, proposições, etc. Nesse sentido, faz-se necessário conhecer o teorema de 
Fermat e suas consequências com exemplos de demonstração.
Nesta Dica do Professor, acompanhe os tipos de demonstrações existentes e entenda como aplicá-
los na área do teorema de Fermat.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Exercícios
1) Na teoria dos números inteiros, a relação de equivalência, mais conhecida como 
congruência, tem critérios de divisibilidade. Nesse caso, o critério utilizado será o do número 
7.
Então, a partir de seus conhecimentos de congruência e divisibilidade, calcule o resto da 
divisão de 10135 por 7 e assinale a alternativa correta.
A) O valor do resto da divisão é 6.
B) O valor do resto da divisão é 8.
C) O valor do resto da divisão é 3.
D) O valor do resto da divisão é 5.
E) O valor do resto da divisão é 2.
2) Na teoria de congruência, existem diversas propriedades aritméticas e proposições lógicas.
Utilizando o critério de divisibilidade do número 10, calcule o algarismo referente à unidade 
do número 31050 e assinale a alternativa correta.
A) O algarismo da unidade é 10.
B) O algarismo da unidade é 5.
C) O algarismo da unidade é 2.
D) O algarismo da unidade é 7.
E) O algarismo da unidade é 9.
Entre as aplicações de congruência, está a determinação do resto de uma divisão. Esse 
procedimento é muito útil quando se está lidando com números muito grandes, ou seja, não 
é necessário executar a divisão para determinar o resto, basta usar propriedades da 
congruência.
3) 
Usando seus conhecimentos de critérios de divisibilidade do número 17, e lembrando as 
aplicações em teoremas da teoria de congruências, calcule o resto da divisão de 2194 por 17, 
utilizando o teorema de Fermat, e assinale a alternativa correta.
A) O resto da divisão é 3.
B) O resto da divisão é 1.
C) O resto da divisão é 4.
D) O resto da divisão é 7.
E) O resto da divisão é 2.
4) Uma das propriedades das congruências, muito útil na resolução de problemas, é a da 
potência.
Considerando essa propriedade e a relação de congruência e de divisibilidade, assinale a 
única alternativa verdadeira.
A) 220 − 1 é divisível por 19.
B) 220 − 1 é divisível por 14.
C) 220 − 1 é divisível por 23.
D) 220 − 1 é divisível por 11.
E) 220 − 1 é divisível por 26.
5) A relação entre divisibilidade e congruência, mais especificamente as propriedades 
aritméticas e de potência em congruências, são muito úteis para avaliar se dado número é 
divisor de outro número cujo valor é muito alto para fazer os cálculos manualmente.
Nesse contexto, assinale a única alternativa verdadeira.
A) 9 | (270 + 370).
B) 15 | (270 + 370).
C) 11 | (270 + 370).
D) 7 | (270 + 370).
E) 13 | (270 + 370).
Na prática
Com o uso da Internet, as atividades rotineiras tornaram-se mais práticas e ágeis. Por sua vez, 
aumentou a demanda pela segurança cibernética. Assim, o estudo dos códigos ocultos pela teoria 
dos números, mais especificamente pela teoria das congruências, é fundamental. Esse estudo é 
conhecidocomo criptografia.
Neste Na Prática, acompanhe uma situação em que o conhecimento em congruência, utilizando a 
divisibilidade, pode ser aplicado na criptografia.
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
Saiba +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:
Divisibilidade, congruência e aritmética modular em 
problemas olímpicos
As Olimpíadas de Matemática foram criadas com objetivo de difundir o conhecimento matemático 
tanto no Ensino Básico quanto no Ensino Superior. Para apoiar os problemas abordados por essas 
competições, este estudo traz definições e diversas aplicações de congruência e divisibilidade. 
Confira.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Uma aplicação da congruência na determinação de critérios de 
divisibilidade
Esta dissertação apresenta definições de congruência e divisibilidade, além da aplicabilidade da 
teoria de congruência com a divisibilidade. Aproveite a leitura.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Introdução à teoria dos números
Acompanhe esta videoaula, em que o professor Carlos Gustavo Moreira, do Instituto de 
Matemática Pura e Aplicada, aborda uma introdução à teoria dos números, incluindo os conceitos 
de divisibilidade e congruência.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Lista de exercícios
Para aprender critérios de divisibilidade e o uso da congruência e dos teoremas de Fermat e de 
Wilson, é importante que você treine fazendo diversos exercícios. Para tanto, baixe a lista de 
exercícios a seguir e resolva as questões.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.