Teroria_do_Numeros

Prévia do material em texto

1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Apostila 
TEORIA DOS 
NÚMEROS 
 
Notas de Aula – 1ª Parte 
 
Prof. Caetano Rodrigues 
 
MORAÚJO - CE 
 
2 
 
 
 
 
 
 
 
 
 
 
 
ITEM ASSUNTO PAG 
1 PRINCIPIO DA BOA ORDENANÇA 3 
2 DIVISIBILIDADE 4 
3 ALGORITIMO DA DIVISÃO 4 
4 MÁXIMO DIVISOR COMUM 5 
5 TEOREMA DE BÉZOUT 6 
6 ALGORITIMO DE EUCLIDES 7 
7 INDUÇÃO MATEMÁTICA 8 
8 CRITÉRIOS DE DIVISIBILIDADE 9 
9 QUESTÕES 12 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Sumário 
3 
 
TEORIA DOS NÚMEROS 
O PRINCÍPIO DA BOA ORDENAÇÃO 
Todo subconjunto não vazio dos números naturais têm um elemento mínimo. 
Se S ∈ ℕ e S ≠∅, então existe um n0 ∈ S tal que n0 ≤n, ∀ n ∈ S. 
Esse é um dos dogmas da matemática e é a base da construção da matemática de hoje. 
Com esse princípio podemos comprovar fatos básicos sobre os números naturais. 
FATO: Não existe número natural entre 0 e 1. 
PROVA: Suponha o contrário, então define o seguinte S = *n ∈ ℕ: 0 < n <1}, então S ≠ ∅, pelo PBO, existe 
n0 ∊ S (é o menor número natural que está entre 0 e 1), daí 0 <n0<1. Multiplicando a desigualdade por n0 
temos 0<n02<n0<1 ⇒ n02 ∊ S, mas é um absurdo, pois n02 < n0, então contradiz dizer que n0 é o elemento 
mínimo de S, o que leva a conclusão que S = ∅, ou seja, não existe nenhum número natural entre 0 e 1. 
 
Números Interessantes 
A matemática é viva, intensa, impressionante e nos faz pensar, refletir e nos divertir. Conhecer a face 
divertida da matemática, com suas curiosidades e revelações, é fundamental para despertar o gosto por 
essa ciência fascinante que geralmente é vista com maus olhos. Vejamos algumas curiosidades que 
envolvem os números e quanta coisa interessante deixamos de aprender por achar que diversão e 
matemática não se misturam. 
1. Raízes de números quadrados perfeitos. 
Observe os seguintes pares de quadrados perfeitos: 
144 e 441 (Note o que esses números apresentam em comum) 
Extraindo a raiz quadrada de cada um deles, obtemos: 
 
O que você consegue perceber? 
Veja mais dois pares de quadrados perfeitos: 
169 e 961 
Extraindo as raízes de cada um, teremos: 
 
Conseguiu observar o que ocorre? 
Veja que 144 e 441, 169 e 961 são pares de quadrados perfeitos compostos pelos mesmos algarismos só 
que escritos de trás para frente. O interessante é que suas respectivas raízes também apresentam essa 
característica. 
Observe mais um exemplo: 
Os pares de quadrados perfeitos 14884 e 48841 apresentam os mesmos algarismos só que escritos de 
trás para frente. 
Calculando a raiz quadrada de cada um, temos: 
 
Suas raízes também apresentam os mesmos algarismos só que escritos em ordem inversa. 
2. O número mágico 1089. 
Vejamos o motivo de esse número ser chamado de número mágico. 
Escreva um número de três algarismos distintos (diferentes). 
598, por exemplo. 
Escreva este número de trás para frente e subtraia o menor do maior. 
895 – 598 = 297 
Agora, inverta também esse resultado e efetue a adição. 
792 + 297 = 1089 
Independente do número escolhido, teremos sempre como resultado final o número 1089. Mas lembre-
se, só vale para números de três algarismos distintos. Se utilizarmos, por exemplo, 555 ou 988 a 
propriedade não será válida. 
3. A forma pitagórica de calcular potências. 
Pitágoras foi um grande matemático que se dedicou ao estudo geométrico, trigonométrico e dos números. 
Dentre seus inúmeros estudos ele descobriu outra forma de se calcular potências com expoente 2. Depois 
de muito estudo e observação, notou que qualquer potência de números naturais do tipo n2 pode ser 
obtida somando os n primeiros números naturais ímpares. Veja como funciona: 
4 
 
a) 62 = 1 + 3 + 5 + 7 + 9 + 11 = 36 
b) 72 = 1 + 3 + 5 + 7 + 9 + 11 + 13 = 49 
c) 42 = 1 + 3 + 5 + 7 = 16 
d) 52 = 1 + 3 + 5 + 7 + 9 = 25 
(Fonte:http://alunosonline.uol.com.br/matematica/curiosidades-sobre-os-numeros.html) 
 
Prova Heurística 
Heurística significa o ato de inventar, de fazer descobertas. É a ciência que tem por objeto a descoberta 
por fatos. 
Existe um fato heurístico que diz que “todo número natural é interessante”, quer dizer, sempre será 
encontrada uma propriedade interessante. 
Prova: seja S={n ∊ ℕ: n é não interessante+. Temos que provar que S = ∅. Suponha por absurdo que S 
≠∅, deve existir que haja algum número não interessante. Pelo PBO vai existir n0 ∊ S mínimo. O n0 é o 
menor número não interessante, mas isso já é uma propriedade interessante, isso contradiz o fato de ele 
está em S, isso nos faz chegar a um argumento absurdo, devido não existir, matematicamente, uma 
definição. 
DIVISIBILIDADE 
ℤ={..., -2, -1, 0, 1,2,...+. Conjunto dos números inteiros ℤ. “As primeiras citações sobre o uso de números 
inteiros vem dos chineses, no primeiro século de nossa era eles efetuavam cálculos com o uso de gravetos 
pretos e vermelhos sobre um tabuleiro, indicando os coeficientes positivos por gravetos vermelhos e os 
negativos por gravetos pretos.”(Menos com menos dá..., Darci Dala Costa, 2010). “(...) foi preciso ampliar 
o conjunto dos números naturais, com adjunção de novos números inteiros negativos, introduzidos para 
possibilitar uma resposta a uma subtração qualquer de dois elementos de ℕ” (Domingues, Álgebra 
Moderna, 2003). 
Definição: dizemos que a divide b se existe c ∊ ℤ, tal que b = c.a. (Notação: a ∣ b) 
Exemplo 1: 4 ∣ 8, pois 8 = c.4 (onde c = 2). 
Exemplo 2: 3 ∤ 8, pois 8 = c.3, não existe c ∊ ℤ. 
 
Propriedades 
(i) a ∣ a (reflexidade), consideremos a ≠ 0. 
(ii) a ∣ 0 
(iii) 1 ∣ a 
(iv) Se a ∣ b e b ∣ c, então a ∣ c (transitividade); 
(v) Se a ∣ b e a ∣ c, então a ∣ mb + nc, ∀ m, n ∊ ℤ. Essa é a propriedade mais usada, a divide qualquer 
combinação linear entre b e c. 
(vi) Se a ∣ b e b ≠ 0, então ∣ a ∣ ≤ ∣ b ∣. 
(vii) Se a ∣ b, então a ∣ bk, para todo k ∊ ℤ. 
 
Demonstração de Prop.(v): Se a ∣ b e a ∣ c ⇒ b = d1.a e c = d2. a, logo mb + nc = md1a + nd2a = (md1 + 
nd2)a, ou seja o mb + nc = (md1 + nd2)a e md1 + nd2 ∊ ℤ (é algum inteiro multiplicado por a) ⇒ a ∣ mb + 
nc. 
 
Problema: Encontre todos os n ∊ ℕ tais que 3n + 1 ∣ n2 + 1. 
Solução: primeiramente aceitamos como verdade que: 3n + 1 ∣ n2 + 1 
 
3n + 1 ∣ 3n + 1 (xn) 
3𝑛 + 1 ∣ 𝑛2 + 1 (𝑥3)
 Usa a prop. (vii) ⇒ 
3𝑛 + 1 ∣ 3n2 + 𝑛
3𝑛 + 1 ∣ 3𝑛2 + 3
 ⇒ Prop. (v): 3n + 1 ∣ (3n2 + n) – (3n2 +3) 
⇒ 3n + 1 ∣ n – 3 
Logo, aplicando as prop.(ii/vi): 
𝑛 − 3 = 0 𝑜𝑢
 ∣ 3n + 1 ∣ ≤ ∣ n − 3 ∣
 ⇒ 
𝑛 = 3
3𝑛 + 1 ≤∣ 𝑛 ∣ + ∣ −3 ∣
 
 
 
𝑛 = 3 𝑜𝑢
3𝑛 + 1 ≤ 𝑛 + 3
 (desigualdade de triangular) ⇒ 3n + 1 ≤ n + 3 ⇒ 2n ≤ 2 ⇒ n ≤ 1 ⇒ n = 1, pois já era n ≥ 1 
Temos duas possibilidades n = 3 e n = 1 
3n + 1 ∣ n2 + 1 ⇒ 
𝑠𝑒 𝑛 = 1, 𝑡𝑒𝑚𝑜𝑠 4 ∣ 2
𝑠𝑒 𝑛 = 3, 𝑡𝑒𝑚𝑜𝑠 10 ∣ 10
 logo a única solução é n = 3. 
 
O ALGORÍTIMO DA DIVISÃO 
5 
 
Nem sempre é possível efetuar uma divisão, ou seja, uma divisão exata, para essa situação temos a 
seguinte definição: seja, a, b ∊ ℕ, então existem q e r ∊ ℤ tais que a = bq + r, com 0 ≤ r < b e além disso q e 
r são únicos. O q é o quociente e o r é o resto da divisão. 
Temos também as seguintes situações: 
 Quando r = 0 ⇒ a = bq ⇒ b ∣ a. 
Demonstração: considere os seguintes intervalos: 
ℝ+≥0 = ,0, b) ∪ ,b, 2b) ∪ ,2b, 3b) ∪ ,3b, 4b) ∪ ,4b, 5b) ∪ ,5b, 6b) ∪ ...∪,kb, (k+1)b) ∪ .... são intervalos 
disjuntos e por isso vão cobrir toda a reta e irão permitir a unicidade. 
Como o a > 0 ele está dentro de algum intervalo discriminado, ou seja, no intervalo onde os extremos são 
múltiplos consecutivos de b, então existe q ≥ 0 único, porque os intervalos são disjuntos e o a só pode ser 
encontrado em um desses intervalos, tal que a ∊ ,qb, (q + 1)b). Se um número está em um intervalo 
significa que ele satisfaz certa desigualdade que no caso é qb ≤ a < (q + 1)b, e o produto (q + 1)b = qb + 
b, dá temos: 
qb ≤ a < qb + b ⇒ 0 ≤ a – qb < b 
Os números a e b são fixos e o q é único o que faz concluir que a – qb é único e que a – qb = r (resto) que 
também é único. Entãotemos que: 
 r = a – qb ⇒ a = qb + r e 0 ≤ r < b. 
 
 
 
Conseqüências do Algoritmo da Divisão 
 Caso b = 2. Nesse caso a = 2q + r, onde 
0 ≤ r < b = 2, ou r = 1 ou r = 0. 
Todo número tem que assumir uma das 
formas: 
Quando r = 0 temos a = 2q que chamamos de números PARES; ou 
Quando r = 1 temos a = 2q + 1 que chamamos de números ÍMPARES. 
Essa é a definição original de números pares e impares. 
 Caso b = 3. Nesse caso a = 3q + r, onde 0 ≤ r < b = 3, ou r = 2 ou r = 1, ou r = 0. 
Todo número tem que assumir uma das formas: 
Quando r = 0, temos a = 3q. 
Quando r = 1, temos a = 3q + 1. 
Quando r = 2, temos a = 3q + 2. 
Para estes últimos não existe nomenclatura espacial, mas é bastante utilizado na aritmética abordada em 
congruências. 
Problema: ∀ n ∊ ℕ, mostrar n, n+1, n + 2 é divisível por 3, (ou que 3 divide um deles.). 
Solução: Se existem três números consecutivos, pode-se afirmar que o 3 divide um deles. De acordo com o 
algoritmo da divisão, n = 3q ou n = 3q + 1 ou n = 3q + 2. Isto é, os restos da divisão por 3 somente 
podem ser 0, 1 ou 2. 
Se n = 3q, está comprovada a hipótese, ou seja, 3 ∣ n. 
Se n = 3q + 1, então n + 2 = 3q + 1 + 2 = 3q + 3 = 3(q + 1) ⇒ n + 2 é divisível por 3. 
Se n = 3q + 2, então n + 1 = 3q + 2 + 1 = 3q + 3 = 3(q + 1) ⇒ n + 1 é divisível por 3. 
Quando n for da forma 3q + 2, então o n + 1 será divisível por 3, (observe se q = 3). 
Vale a generalização, perceba, se tiver k números consecutivos, o k irá dividir um deles para qualquer k ∊ 
ℕ. 
 
MÁXIMO DIVISOR COMUM (MDC) 
Definição: dizemos que d é o máximo divisor comum de a e b se d ∣ a e d ∣ b e se existe c ∣ a e c ∣ b, então d 
≥ c. 
Exemplo: MDC (12, 9) 
D+(12) = {1, 2, 3, 4, 6, 12} 
D+(9) = {1, 3, 9} 
Max. D+(12) ∩ D+(9) = 3 
 
Propriedades: sejam a, b ∊ ℕ. 
(a) MDC (a,b) ≥ 1, porque 1 ∣ a e 1 ∣ b; 
(a) (b) 
(r) (q) 
6 
 
(b) MDC (a, ± b) = MDC (a, b), se d ∣ a, então – d ∣ a; 
(c) MDC (a, b) = MDC (b, a), simetria; 
(d) MDC (1, a) = 1, pois, D+(1) = {1} e D+(a) = {a}; 
(e) MDC (0, a) = a, pois, todo número positivo é divisor de zero, então o maior divisor de a é o próprio a; 
(f) Se a ∣ b, então MDC (a, b) = a; pois, o maior divisor de a é o próprio a e se esse mesmo a ∣ d, então ele 
dividirá os dois e não tem “ninguém” maior; 
(g) MDC (a + Kb, b) = MDC (a, b); 
(h) MDC (a, b) ∣ MDC (a, kb). 
Não existe MDC (0, 0). 
 
Demonstração da Prop. (g): MDC (a + Kb, b) = MDC (a, b), primeiramente associamos MDC (a + Kb, b) = 
d1 e MDC (a, b) = d2, conseqüentemente, d 1 ∣ a + Kb e d 1 ∣ b, isso significa, pela propriedade (v) da 
divisibilidade, que o d1 divide qualquer combinação linear de (a + Kb, b), então podemos escrever que: 
d 1 ∣ a + Kb + (- Kb), o que significa que d 1 ∣ a. 
Logo, d1 ≤ d2. 
No caso do d2 temos que d 2 ∣ a e d 2 ∣ b ⇒ d 2 ∣ a + Kb; 
Logo, d 2 ≤ d1. Se d1 ≤ d2 e d2 ≤ d1, daí d1= d2. 
 
Teorema de Bézout 
Se d = MDC (a, b), então, existem m0 e n0 ∊ ℤ, tais que d = m0a + n0b, ou seja, o MDC (a,b) pode ser escrito 
como uma combinação linear inteira entre a e b. 
Provar o Teorema: considere a definição do conjunto S = *ma + nb > 0 : mn ∊ ℤ+. Observe que no MDC (a, 
b) pelo menos um deles tem que ser diferente de zero, pois não existe MDC (0, 0), outro aspecto a 
observar é que está sendo considerado somente as combinações lineares positivas, ou seja, (ma + nb) é 
um número natural. 
Conclusões: 
S = *ma + nb > 0 : mn ∊ ℤ+ ⊆ ℕ, no entanto, esse subconjunto poderia ser vazio. A questão é provar que 
ele não é vazio, para isso tome m = a e n = b, como m e n estão variando entre todos os inteiros positivos, 
então é possível escolher em particular que eles assumam esses valores, segue que: 
ma + nb = a2 + b2 > ⇒ ma + nb ∊ S, isto é, S ≠ ∅. 
S é um subconjunto dos naturais diferente do vazio, por isso, sobre ele podemos aplicar o Princípio da 
Boa Ordenação (PBO) afirmando que: 
Existe um d que é um menor elemento de S, notação: d = min S, então existem m0, n0 ∊ ℤ, tais que d = m0a 
+ n0b, isso significa que o menor elemento “d” de S existe e é escrito como uma combinação linear 
particular entre a e b, mas é preciso provar que o d é o MDC (a, b). 
Para provar que o d é o MDC (a, b) temos que aplicar sobre d os critérios para que ele seja Máximo 
Divisor Comum de S, os critérios são: 
(i) d ∣ a e d ∣ b, tem que ser divisor comum. 
Prova do critério (i) vamos supor que d ∤ a. Nesse caso podemos aplicar o algoritmo da divisão a = d.q + 
r, como d não divide a , então 0 < r < d, mas r = a – qd ⇒ r = a – q(m0a + n0b) = (1 - q m0)a + (- q n0)b, 
perceba que o r é uma combinação positiva entre a e b, quer dizer que o r ∊ S, mas isso é um absurdo 
porque constatamos que o r < d e o d é o mínimo de S, significa também dizer que d ∤ a, logo d ∣ a e pelo 
mesmo motivo e analogamente d ∣ b. 
(ii) O “d” tem que ser o maior divisor comum. Suponha que c ∣ a e c ∣ b , então c ∣ m0a + n0b = d. 
Lembrando que d ≠ 0 e que c ≤ d, portanto d = MDC (a, b) = m0a + n0b . 
Observe o aluno que provamos que o MDC (a, b) = min (S), ou seja, o MDC (a, b) é o menor elemento de S. 
Podemos inferir que: 
 d = MDC (a, b) = min {m0a + n0b > 0; m, n ∊ ℤ} 
Colorário 1: é a conseqüência de um teorema ou proposição e como conseqüência temos: 
Considere t >0, então MDC (ta, tb) = t.MDC(a, b), ou seja, podemos retirar o fator comum entre a e b 
através do MDC. 
Prova do Colorário 1: O fator comum entre a e b podemos tirar do MDC, para provar isso recorremos ao 
teorema de Bézout. O MDC (ta, tb) = min {m(ta) + n(tb) > 0; m, n ∊ ℤ+ = min {t(ma + nb) > 0; m, n ∊ ℤ+. 
Explicando: 
Vamos supor que temos o conjunto A = {a, b, c} e outro conjunto B = {ta, tb, tc}, com t>0. Interessante 
observar que se queremos saber o MDC dos elementos de B, basta saber qual o MDC dos elementos de A e 
7 
 
multiplicar esse MDC por t, porque o t é um fator comum de todos os elementos do conjunto B. Isso 
significa que o t saí do mínimo, que é o menor elemento da combinação linear, por este motivo temos: 
 
MDC (ta, tb) = min {m(ta) + n(tb) > 0; m, n ∊ ℤ+ = min {t(ma + nb) > 0; m, n ∊ ℤ+ 
MDC (ta, tb) = min {m(ta) + n(tb) > 0; m, n ∊ ℤ+ = t min {ma + nb > 0; m, n ∊ ℤ+; 
MDC (ta, tb) = t MDC (a, b) 
 
Colorário 2: se o c>0, c ∣ a e c ∣ b, então MDC (𝑎
𝑐
 , 
𝑏
𝑐
) = 1
𝑐
 MDC (a, b). 
 
Prova do colorário 2: podemos dizer que a’ = 𝑎
𝑐
 e b’ = 𝑏
𝑐
, vamos multiplicar o c para as duas afirmações: 
ca’ = a e cb’ = b, então o MDC (ca’, cb’) = cMDC (a’, b’), substituindo temos MDC (a, b) = c MDC (𝑎
𝑐
 , 
𝑏
𝑐
) 
Continuando, MDC (a, b) = c MDC (𝑎
𝑐
 , 
𝑏
𝑐
) ⇒ 1
𝑐
 MDC (a, b) = MDC (𝑎
𝑐
 , 
𝑏
𝑐
). 
Como conseqüência temos uma característica interessante: 
 
Dizemos que 
𝑎
𝑏
 ∊ ℚ (número racional, fração, quociente de dois inteiros) com b ≠0 é irredutível, ou 
dizemos que o numero irracional é irredutível, ou dizemos que a fração é irredutível, se o MDC (𝑎
𝑏
 ) = 1. 
Relembrando que se MDC (a, b) = 1, significa que a e b são coprimos ou primos entre si. 
Nesse caso todos os números racionais podem ser escritos com uma fração irredutível, porque se temos a 
fração 
𝑎
𝑏
 , cujo d é o o MDC entre a e b pode ser escrito da seguinte forma: 
Se d = MDC (a, b) ⇒ 
𝑎
𝑏
 =
𝑎
𝑑
𝑏
𝑑
 , mas quando ao MDC (𝑎
𝑑
 , 
𝑏
𝑑
) = 1
𝑑
 MDC (a, b)= 1, isso significa que 
𝑎
𝑏
 e 
𝑏
𝑑
 são 
coprimas, ou seja, toda fração pode ser escrita como uma fração irredutível. 
 
Propriedades do Teorema de Bézout 
Proposição 1: essa proposição é bastante útil na resolução de problemas e diz que se a ∣ bc e MDC (a, b) = 
1, então a ∣ c, em outras palavras se o “a” divide o produto de dois números e ele é primo de um dos 
números então ele tem que dividir o outro. 
Prova da Proposição 1 
O teorema de Bézout diz em palavras que o MDC entre dois números é escrito como combinação linear 
desses dois números, então se MDC (a, b) = 1= ma + nb (× c) ⇒ c = mac + nbc. 
Observa que o a divide “mac” porque é um múltiplo de a, também o a divide “nbc” pois como já foi 
proposto a ∣ bc, então o a também divide a soma“mac + nbc”, no entanto a soma é c, então, a ∣ c. Sempre é 
bom lembrar se a divide dois números então ele divide qualquer combinação linear desses dois números. 
 
Proposição 2: O MDC (a + bk, b) = MDC (a, b). Temos um múltiplo de b que é k, é possível desconsiderá-lo 
como fator do MDC, pois não influência, pois, todos os fatores de b já estão si, ou seja, seus atributos, o k 
não aumenta fator nenhum para o b, então é como se cancelasse. 
 
Prova da Proposição 2: supomos que d = MDC (a + bk, b) e c = MDC (a, b). Pela definição temos que d ∣ a 
+ bk e d ∣ b, então, o d divide qualquer combinação linear, podemos escrever na forma d ∣ (a + bk) – bk ⇒ 
d ∣ a, se o d divide a e também divide b, então d ≤ MDC (a, b) = c. 
Analogamente para c: 
c ∣ a e c ∣ b ⇒ c ∣ a + bk ⇒ c ≤ MDC (a + bk, b) = d, então, c = d. 
 
ALGORÍTIMO DE EUCLIDES 
Sejam a e b ∊ ℕ, podemos dizer que 
b = a.q1 + r1 , 0 <r1 < a; 
a = r1.q2 + r2, 0 < r2 < r1; ⇒ 
r1 = r2.q3 + r3, 0 < r3 < r2; 
r2 = r3.q4 + r4, 0 < r4 < r3 .... 
 
Observe que existe uma ordem decrescente dos restos (r2 < r1; r3 < r2...), sequencia decrescente de 
números inteiros, então não pode ser infinita, pois se trata de números maiores ou iguais a zero, então o 
resto será zero em dado momento: 
r n - 2 = r n - 1.qn + rn , 0 < r n < r n - 1 
8 
 
rn-1 = rn.qn+1, (rn+1= 0) 
Então o algoritmo de Euclides diz que: MDC (a, b) = rn 
Significa que o MDC (a, b) é o último resto não nulo quando é feito o algoritimo da divisão várias vezes até 
chegar no resto zero. 
 
Prova do Algoritimo de Euclides: consideremos o MDC (a, b) = MDC (a, aq1 + r1), pela proposição 2 temos 
que MDC (a, b) = MDC (a, aq1 + r1) = MDC (a, r1), considerando que a = r1.q2 + r2 temos que: 
MDC (a, b) = MDC (a, aq1 + r1) = MDC (a, r1)= MDC (r1.q2 + r2, r1), observe que r1.q2 é um múltiplo de r1 
dando condições para aplicarmos novamente a proposição 2, ficando assim: 
MDC (a, b) = MDC (a, aq1 + r1) = MDC (a, r1)= MDC (r1.q2 + r2, r1) = MDC (r2, r1), então pode continuar 
isso sempre, pois o algoritimo da divisão permite até chegar no ultimo resto não nulo e fica assim: 
MDC (a, b) = MDC (a, aq1 + r1) = MDC (a, r1)= MDC (r1.q2 + r2, r1) = MDC (r2, r1) ...= MDC (rn-1, rn) = MDC 
(rn, rn+1), (lembrando que rn+1= 0), = MDC (rn, 0) = rn. 
Então: 
MDC (a, b) = rn 
Problema: calcular o MDC (471, 1176). 
Para resolver é só usar o algoritimo da divisão várias vezes: 
1176 = 471 x 2 + 234 ⇒ 471 = 234 x 2 + 3 ⇒ 234 = 3 x 78 + 0, o ultimo resto não nulo é 3, logo MDC 
(471, 1176) = 3. 
 
INDUÇÃO MATEMÁTICA 
Imaginemos uma sequencia de dominós enfileirados de tal forma que essa fila de dominós é infinita, de 
tal forma que quando se derruba um dominó isso garante que derrubará o dominó seguinte, pergunta-se: 
o que acontece quando de derruba o primeiro dominó? Intuitivamente sabemos que “todos” os dominós 
vão cair, seguindo a linha de tempo para o infinito, essa é a ideia de indução matemática. 
Princípio de Indução Matemática (PIM) 
Seja S ⊆ ℕ tal que satisfaça duas condições: 
(I1) 1 ∊ S; (base da indução) 
(I2) se k ∊ S (hipótese de indução), então k + 1 ∊ S. (tese de indução) 
Se essas duas condições forem satisfeitas o S = ℕ. 
Podemos perceber de forma mais generalizada, como por exemplo, se existe uma propriedade que pode 
ser aplicada aos números naturais, se o número 1 satisfaz essa propriedade e toda as vezes que k satisfaz 
essa propriedade, percebe-se que k + 1 também satisfaz essa propriedade então essa propriedade é 
satisfeita por todos os números naturais. Ao invés de 1 podemos considerar o “a”, pois se ele satisfaz essa 
propriedade e o k + a também satisfaz a propriedade em questão, então o S contém todos os números 
naturais maiores iguais a “a”. 
Prova do PIM: utiliza-se o PBO para provar que S = ℕ, então suponha que o S ≠ ℕ, para isso entende-se 
que existem elementos que estão em ℕ e não estão em S. Em notação temos o conjunto diferença S’ = ℕ - 
S ≠ ∅, no entanto o S’ ⊆ ℕ, então pelo P.B.O existe n0 que é o menor elemento de S’, em notação: n0 = min 
(S’). Observe que o n0 não pode ser 1 (n0 ∉ 1), pois 1 ∊ S. Daí n0 - 1 ∉ S’, porque n0 é o menor elemento de 
S’, mas se n0 - 1 não está em S’ ele tem que está no complementar de S’ dentro dos naturais, logo chega-se 
a conclusão que n0 - 1 ∊ S, no entanto pela propriedade (I2) se um elemento está em S o sucessor deste 
elemento também está em S, então (n0 – 1) + 1 ∊ S o que leva a conclusão que n0 ∊ S contradizendo com a 
conclusão anterior de que n0 ∊ S’, portanto é um absurdo supor que S ≠ ℕ concluindo que S = ℕ. 
 
Problema 1: Prove que 1 + ...+ 𝑛 = 
𝑛(𝑛+1)
2
, para todo n ≥ 1. 
Solução: A questão quer que provemos que a propriedade 𝑛 = 𝑛
𝑛+1
2
 seja satisfeita para todos ℕ, por isso 
se deve aplicar o PIM. 
Defina S = *n ∊ ℕ: 1 + ...+ 𝑛 = 
𝑛(𝑛+1)
2
}, ou seja, S é conjunto de todos os naturais que satisfazem a 
propriedade em questão, então tem que provar que S = ℕ. 
Base de indução: provar que 1 ∊ S, para isso tem que provar que 1 satisfaz a igualdade: 1 + ...+ 𝑛 = 
𝑛(𝑛+1)
2
 
Do lado esquerdo da igualdade quando se soma de 1 até 1 o resultado é 1 e do lado direito substitui. 
1 = 1 1+1
2
 ⇒ 1 = 1 ⇒ 1 ∊ S. 
Hipótese de indução: vamos supor que o K ∊ S ⇒ 1 + ...+ 𝑘 = 
𝑘(𝑘+1)
2
. A hipótese é sempre verdadeira. 
9 
 
Tese de Indução: k + 1 ∊ S ⇒ 1 + ...+ (𝑘 + 1) = 
(𝑘+1)(𝑘+2)
2
. 
A partir da hipótese temos que provar a tese: 
Tese: 1 + ...+ (k + 1) na primeira parte da igualdade temos que utilizar a H.I para provar que existe a 
igualdade para justificar a segunda parte. 
A H.I é a soma de 1 até k, mas temos que perceber que dentro da soma de 1 até k + 1 aparece a soma de 1 
até k. 
Desenvolver a tese através da H.I: 1 + ...+ (k + 1) = 1 + ... + k + (k + 1) ⇒ 
𝑘(𝑘+1)
2
 + (k + 1) 
𝑘(𝑘+1)+ 2(𝑘+1)
2
 ⇒ (𝑘2 + 𝑘 + 2𝑘 + 2)/2 ⇒ (k2 + 3k + 2)/2 ⇒ 
(𝑘+1)(𝑘+2)
2
 
Significa que k + 1 ∊ S, então S satisfaz (I1) e (I2), por isso S = ℕ, ou seja, todo número natural satisfaz a 
propriedade 1 + ...+ 𝑛 = 
𝑛(𝑛+1)
2
. 
Problema 2: (IDENTIDADES) prove que 12 + ...+ n2 = 
𝑛(𝑛+1)(2𝑛+1)
6
, ∀ n ≥ 1. 
B.I: provar que 1 ∊ S: 
É o caso em n = 1, ou seja, na esquerda da igual a soma que vai de 1 até 1, quer dizer dá 1. 
No lado direito substitui n por 1. 
12 = 
1(1+1)(2.1+1)
6
 ⇒ 1 = 1, então a B.I está provada. 
H.I: vamos supor que o K ∊ S ⇒ 12 + ...+ k2 = 
𝑘(𝑘+1)(2𝑘+1)
6
. 
T.I: k + 1 ∊ S ⇒12 + ...+ (k+1)2 = 
(𝑘+1)(𝑘+2)(2𝑘+3)
6
. 
 
12 + ...+ k2 + (k+1)2 = 
𝑘(𝑘+1)(2𝑘+1)
6
 + (k+1)2 
 = 
𝑘(𝑘+1)(2𝑘+1)+ 6 (𝑘+1)2
6
 
 = 
(𝑘+1)(𝑘(2𝑘+1)+ 6 (𝑘+1))
6
 (coloca (k + 1) em evidência) 
 
𝑘(2𝑘 + 1) + 6 (𝑘 + 1) = (𝑘 + 2)(2𝑘 + 3) ??? 
2k2 + k + 6k + 6 = 2 k2 + 3k + 4K + 6 
2k2 + 7k + 6 = 2 
Problema 3: (Desigualdade) Prove que 10n > n, n ≥ 1 
B.I: provar que 1 ∊ S ⇒ 101 > 1, verdadeiro. 
H.I: 10k >k, n = k ≥ 1 
T.I: 10k + 1 >(k + 1) 
Partindo da H.I, 10k >k temos que chegar na tese: 
10k> k (mult. Por 10) ⇒ 10.10k> 10k 
10k+1 > 10k. 
Sabemos que k ≥ 1 por imposição da questão e pela H.I., podemos desenvolve-la para chegar a k + 1: 
K ≥ 1 (mult. Por 9) ⇒ 9k ≥ 9 ⇒ 9k ≥ 9 > 1 ⇒ 9k > 1 
9k > 1 (somar k) ⇒ 9k + k > k + 1 ⇒ 10k > k + 1. 
Logo 10k+1 > 10k > k + 1 ⇒ 10k + 1 >(k + 1) CQD 
 
Problema 4: (divisiblidade) prove que 7 divide 32n+1 + 2n + 2, ∀ n ∊ ℕ. 
B.I: caso n = 1 ⇒ 32.1+1 + 21 + 2 ⇒ 33 + 23 = 27 + 8 = 35, então 7 ∣ 35, vamos chamar 35 de m1, provado 
que 7 ∣ m1 
H.I: quando n = k ⇒ 7 ∣ 32k+1 + 2k + 2, vamos chamá-lo de mk e supor que 7 ∣ mk 
T. I: 7 ∣ mk + 1 = 32(k+1)+1 + 2k + 3 = 32k+3 + 2k + 3. 
Queremos provar que o 7 ∣ mk + 1, então podemos utilizar o seguinte artifício mk + 1 – mk. 
mk + 1 – mk = 32k+3 + 2k + 3 - 32k+1 - 2k + 2 = 32k+3 - 32k+1 + 2k + 3 - 2k + 2 = 32k + 1. (32 – 1) + 2k+ 2. (2 - 1) = 32k 
+ 1. 8 + 2k+ 2. 
32k + 1.8 + 2k+ 2, observe que é muito parecido com mk (32k+1 + 2k + 2), então separa o mk efica: 
Mk + 7. 32k + 1. 
mk + 1 – mk = mk + 7. 32k + 1 ⇒ mk + 1 = 2mk + 7. 32k + 1, lembrando que queremos que 7 divida mk + 1. 
Como mk + 1 = 2mk + 7. 32k + 1 sabemos que o 7 divide 2mk e o 7 divide 7. 32k + 1, devido a H.I e combinação 
linear e também porque o 7 divide seus múltiplos. Se 7 divide a soma, então 7 ∣ mk+1. 
 
10 
 
Problema 5: (Existência) prove que todo quadrado pode ser subdividido em n quadrados , para todo n ≥ 
6. 
Solução: partição de quadrados. 
Não é possível dividir um quadrado em dois, três e cinco. 
 
Temos que provar que para todo n ≥ 
6. 
 
 
Então a B.I.: se n = 6 está comprovado. 
H.I: todo quadrado pode ser subdividido e k quadrados com 6 ≤ k ≤ n, entre 6 e n. 
T.I: dividir um quadrado em n+1 subquadrados. 
É possível dividir qualquer quadrado em k quadrados para todo k entre 6 e n, 
então o quadrado fica dividido em n + 1 quadrados. 
 
 
 
 
 
CRITÉRIOS DE DIVISIBILIDADE 
Temos os algarismos, são os números {0, 1, 2, 3, 4, 5, 6, 7, ,8, 9}, eles são equivalentes ao alfabeto, com eles 
formamos os números, colocando eles um ao lado direito do outro, por exemplo:131, escrevemos os 
números sobre a base dez. 
Podemos decompor os números: 
131 = 1 x 102(centena) + 3 x 10 (dezenas) + 1x 100 (unidade). O número 131 tem uma combinação de 
potências de 10. 
1431 = 1 x 103 + 4 x 102 + 3x 10 + 1x 100. 
Outra forma pode envolver letras: a = 2, b = 5 ⇒ ab = 10. Temos também a seguinte notação 𝑎𝑏 = 25, 
nesse caso com essa barra de ênfase significa que estamos colocando os números um ao lado do outro, ou 
seja, vinte e cinco, não um produto, então consideremos os seguintes números: 
𝒂𝒏 𝒂𝒏−𝟏 …𝒂𝟏𝒂𝟎 neste caso estamos escrevendo na base 10 onde o “a índice i” são ai ∊ *0, 1, 2,..., 9} e o 
primeiro dígito tem que ser diferente de zero, an ≠ , o que fica: 
𝒂𝒏 𝒂𝒏−𝟏 …𝒂𝟏𝒂𝟎 = 𝑎𝑛 . 10
𝑛 + 𝑎𝑛−1 . 10
𝑛−1 + … + 𝑎1 . 10 + 𝑎0 escrito na base 10 e nesta notação, significa 
escrever na base 10. Os números representados por “ai” são chamados dígitos dos números 
representados na base 10. 
Os critérios de divisibilidade são aplicados para saber quando um número é divisível pelo outro usando 
apenas os dígitos. 
Critérios 
(i) critério de divisibilidade por 1: vamos adotar m = 𝒂𝒏 …𝒂𝟏𝒂𝟎 , qualquer m ∊ ℤ é divisível por 1; 
(ii) critério de divisibilidade por 2: quando o ultimo dígito do número, o mais a direta for a0 ∊ *0, 2, 4, 6, 8+ 
ou seja, quando ele for par. 
(iii) critério de divisibilidade por 3: quando o 3 divide a soma dos algarismos, 3 ∣ 𝒂𝒏 …𝒂𝟏𝒂𝟎, por exemplo 
3 divide 111300, 3 ∣ 111300, porque 1 + 1 + 1 + 3 = 6 e 3 ∣ 6; 
(iv) critério de divisibilidade por 4: quando 4 ∣ 𝒂𝟏𝒂𝟎, por exemplo 4 ∣ 1128, porque 4 ∣ 28; 
(v) critério de divisibilidade por 5: quando o ultimo algarismo é a0 = *0, 5+, 5 ∣ 125; 
(vi) critério de divisibilidade por 6: quando o 2 divide ele e o 3 dividi ele, 2 ∣ m e 3 ∣ m. 
(vii) critério de divisibilidade por 8: quando o 8 divide o número formado pelos 3 últimos algarismos, 8 ∣ 
𝑎2𝑎1𝑎0 , por exemplo 8 ∣ 102008. 
(vii) critério de divisibilidade por 9: quando 9 divide a soma dos algarismos, 9 ∣ 𝒂𝒏 + … + 𝒂𝟏 + 𝒂𝟎 por 
exemplo o 9 ∣ 111.111.111. 
(viii) critério de divisibilidade por 10: quando 2 ∣ m e 5 ∣ m e quando a0 = 0; 
(ix) critério de divisibilidade por 11: quando o 11 divide a combinação da soma alternada 11 ∣ 
𝒂𝒏 − 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 − 𝒂𝒏−𝟑 … + 𝒂𝟎 , por exemplo 11 ∣ 121 ⇒ 11 ∣ 1 - 2 + 1 = 0 ⇒ 11 ∣ 0. 
(x) critério de divisibilidade por 12: quando 4 ∣ m e 3 ∣ m; 
(xi) critério de divisibilidade por 14: quando 2 ∣ m e 7 ∣ m; 
(xii) critério de divisibilidade por 15: quando 3 ∣ m e 5 ∣ m; 
4 6 7 8 
n-2 n-1 
n n + 1 
11 
 
(xiii) critério de divisibilidade por 14: quando divide o numero formado pelos últimos quatro algarismos 
16 ∣ 𝑎3 𝑎2𝑎1𝑎0 ; 
(xiv) critério de divisibilidade por 18: quando 2 ∣ m e 9 ∣ m; 
(xvi) critério de divisibilidade por 20: quando 4 ∣ m e 5 ∣ m; 
 
Divisibilidade por 7, 13, 17 e 19 
(xvii) critério de divisibilidade por 7: quando 7 ∣ m ⇔ 7 ∣ 𝑎𝑛 … 𝑎2 – 2a1, quer dizer, separa o último dígito, 
o número restante da separação é subtraído do dobro do último digito, por exemplo, 7 ∣ 441 ⇔ 7 ∣ 44 – 2 
⇒ 7 ∣ 42. Outro exemplo 7 ∣ 985 ⇔ 7 ∣ 98 – 10 ⇒ 7 ∣ 88 ⇔ 7 ∣ 8 – 16 ⇒ 7 ∣ - 8 ⇒ 7 ∤ -8 ⇒ 7 ∤ 985. 
(xviii) critério de divisibilidade por 13: quando 13 ∣ m ⇔ 13 ∣ 𝑎𝑛 … 𝑎2 + 4a1; 
(xix) critério de divisibilidade por 17: quando 17 ∣ m ⇔ 17 ∣ 𝑎𝑛 … 𝑎2 - 5a1; 
(xx) critério de divisibilidade por 19: quando 19 ∣ m ⇔ 17 ∣ 𝑎𝑛 … 𝑎2 + 2a1; 
A vantagem dos critérios é porque sempre estará diminuindo um dígito dele, todas as vezes que diminui 
vai ficando mais fácil ter certeza da divisibilidade. 
 
Proposição para critério de divisibilidade por 7: Podemos estabelecer que m = 𝑎𝑛 … 𝑎1 podemos escrevê –
lo como 10k + i, então, m = 𝑎𝑛 … 𝑎1 = 10k + i, onde o k = 𝑎𝑛 … 𝑎2 e i = a1. Partindo disso reescrevendo e 
aplicando o critério 7 ∣ 10k + i ⇔ 7 ∣ k – 2i 
Prova do critério por 7: 
Vamos utilizar a técnica de demonstração do se e somente se: prove que 7 ∣ 10k +i sss 7 ∣ k – 2i. 
Hipótese: 7 ∣ 10k +i 
Tese: 7 ∣ k – 2i 
(⇒)Da hipótese temos que 7 ∣ 10k +i ⇒ 10k +i = 7l (éle). Explicando 7 ∣ 10k +i se somente se existe um 
número l inteiro tal que 10k +i = 7l. 
Podemos isolar o valor de i ⇒ i = 7l – 10k 
Para provar que 7 ∣ k – 2i devemos recorrer a hipótese: k – 2(7l – 10k) = k – 14l + 20k = 21k – 14l. Tanto 
o 14 como o 21 são divisíveis por 7, então 7 divide qualquer combinação linear entre 14 e 21. Logo 7 ∣ k – 
2i . 
(⇐) Na volta o que era tese vira hipótese: 
Hipótese: 7 ∣ k – 2i 
Tese: 7 ∣ 10k +i 
Da hipótese temos que 7 ∣ k – 2i ⇒ k – 2i = 7l ⇒ k = 7l + 2i. 
Para provar que 7 ∣ 10k +i devemos recorrer a hipótese: 10(7l + 2i) + i = 70l + 20i +i = 70l + 21i, do 
resultado percebemos que o 7 divide o 70 e o 21, então o 7 divide qualquer combinação linear desses 
dois, logo 7 ∣ 10k +i. 
CONGRUÊNCIAS 
Sejam a, b ∊ ℤ e m ≥ 1. Dizemos que a é congruente a b módulo m, se m ∣ (a – b). Escrevemos a ≡ b (mod 
m) Caso contrário, dizemos que a é incongruente a b módulo m e escrevemos a ≢ b (mod m). 
 
Se m ∣ (a – b) ⇒ ∃ k ∊ ℤ tal que a – b = k.m ⇔ a = b + k.m. Dizer que dois números são congruentes 
módulo m é o mesmo que dizer que eles são iguais a menos de um múltiplo de m. a congruência pode ser 
vista como uma igualdade, a igualdade hoje seria a congruência módulo zero. 
Exemplo: 
2 ≡ 2 (mod 7) ⇒ 7 ∣ 2 – 2 = 0 
7 ≡ 2 (mod 5) ⇒ 5 ∣ 7 – 2 
3 ≡ - 1 (mod 2) ⇒ 2 ∣ 3 + 1 
7 ≢ 1 (mod 5) ⇒ 5 ∤ 7 – 1 
 
Se a ≡ 0 (mod m) ⇒ m ∣ a 
 
Propriedades das congruências 
(P1) a ≡ a (mod m) ⇒ m ∣ a – a , qualquer número diferente de zero divide zero, propriedade reflexiva; 
(P2) a ≡ b (mod m), então b ≡ a (mod m), propriedade simétrica; 
Prova de (P2): se m divide a – b, então m divide qualquer múltiplo de a – b. Pode-se dizer que m ∣ (-1)(a – 
b) ⇒ m ∣ (b – a) ⇒ b ≡ a (mod m); 
(P3) se a ≡ b (mod m) e b ≡ c (mod m), então a ≡ c (mod m), propriedade transitiva; 
12 
 
Prova da (P3): se a ≡ b (mod m) ⇒ m ∣ (a – b) e se b ≡ c (mod m) ⇒ m ∣ (b – c). Se m divide dois números, 
então m divide a soma deles, m ∣ (a – b) + (b – c) ⇒ m ∣ (a – c) ⇒ a ≡ c (mod m). 
 
Essas três propriedade indicam, assim como a igualdade, que a congruencia é relação de equivalência. 
 
P(4) se a ≡ b (mod m) e se c ≡ d (mod m), então a + c ≡ b + d (mod m). 
Prova da (P4): m ∣ (a – b) e m ∣ (c – d) ⇒ m ∣ (a – b) + (c – d) ⇒ m ∣ (a + c) – (b + d) ⇒ a + c ≡ b + d (mod 
m). 
(P5) se a ≡ b (mod m) e se c ≡ d (mod m), então ac ≡ bd (mod m). 
Prova da (P5): consideremeos ac - bd agora verificar se esse número é dividido por m. 
Desenvolver ac – bd, para isso vamos somar ou subtrair algo conveniente ao nosso objetivo: 
ac – bd= ac - bc + bc – bd = c(a – b) + b(c – d), como m divide (a – b) e (c – d) então eledivide qualquer 
combinação linear deles, ou seja, ⇒ m ∣ (ac – bd) ⇒ ac ≡ bd (mod m). 
 
(P6) Se a ≡ b (mod m), então an ≡ bn (mod m), ∀ n ≥ 1. 
 Prova da (P6): se m ∣ (a – b), provar que m ∣ an - bn. 
(an - bn) é um produto notável = (𝑎 − 𝑏)(𝑎𝑛−1 + 𝑎𝑛−2𝑏 + ⋯+ 𝑏𝑛−1), então se o m divide (a – b) e o 
número 𝑎𝑛−1 + 𝑎𝑛−2𝑏 + ⋯ + 𝑏𝑛−1 é um inteiro o m divide qualquer produto de (a – b) por inteiro, então 
podemos afirmar que m ∣ (an - bn) ⇒ an ≡ bn (mod m). 
 
QUESTÕES 
1) Provar por indução que 3 divide 5n + 2.11n, n ∊ ℕ. 
 
2) Prove que 2n > n2 para todo n ≥ 5. 
 
3) Mostre que: 
a) n ≡ 7 (mod 12) ⇒ n ≡ 3 (mod 4) 
 
b) n2 ≡ 0 (mod 4) ou n2 ≡ 1 (mod 4) 
 
4) O número 368 é divisível por 2? Justifique através dos critérios de divisibilidade. 
 
5) O número 3471 é divisível por 3? Justifique através dos critérios de divisibilidade. 
 
6) O número 12937 é divisível por 3? Justifique através dos critérios de divisibilidade. 
 
7) O número 578428 é divisível por 4? Justifique através dos critérios de divisibilidade. 
 
8) O número 3478900 é divisível por 4? Justifique através dos critérios de divisibilidade. 
 
9) O número 347189035 é divisível por 5? Justifique através dos critérios de divisibilidade. 
 
10) O número 37914703 é divisível por 5? Justifique através dos critérios de divisibilidade. 
 
11) O número 53427 é divisível por 6? Justifique através dos critérios de divisibilidade. 
 
12) Provar que a soma dos números ímpares tem a seguinte propriedade: 1 + 3 + 5 + ...+ 2n – 1= n2, ∀ n 
∊ ℕ. 
 
13) Prove que 2n + 1 < 2n, ∀ n ≥ 3. 
 
14) O número 106.424 é divisível por 6? Justifique através dos critérios de divisibilidade. 
 
15) O número 812472 é divisível por 6? Justifique através dos critérios de divisibilidade. 
 
16) O número 22.389.651.536 é divisível por 7? Justifique através dos critérios de divisibilidade. 
 
13 
 
17) O número 3.958.743.328 é divisível por 8? Justifique através dos critérios de divisibilidade. 
 
18) O número 4.901.067 é divisível por 9? Justifique através dos critérios de divisibilidade. 
 
19) O número 307.410.541 é divisível por 9? Justifique através dos critérios de divisibilidade. 
 
20) O número 10.832.041 é divisível por 11? Justifique através dos critérios de divisibilidade. 
 
21) O número 2.347.014.982 é divisível por 11? Justifique através dos critérios de divisibilidade. 
 
22) O número 1785 é divisível por 7? Justifique através dos critérios de divisibilidade. 
 
23) calcule pelo Algoritmo de Euclides o MDC (144, 96). 
 
24) calcule pelo Algoritmo de Euclides o MDC (92, 72). 
25) calcule pelo Algoritmo de Euclides o MDC (36, 48, 54). 
 
26) Prove que 1 + 
1
𝑛
 𝑛 < n + 1, n ≥ 2. 
 
27) Descubra e justifique se as congruências abaixo são verdadeiras ou falsas: 
 
a) 3 ≡ 228 (mod 5) b) 15 ≡ 45 (mod 7) c) 13 ≡ 19 (mod 6) 
 
d) 212 ≡ 37 (mod 12) e) -22 ≡ 140 (mod 9) f) – 2433 ≡ 3432 (mod 6) 
 
28) Prove que o MDC (a, b) = d ⇒ MDC 
𝑎
𝑑
,
𝑏
𝑑
 = 1. 
 
29) Prove que se a ∣ b e MDC (b, c ) = 1 ⇒ MDC (a, c). 
 
30) Prove que se a ∣ c , b ∣ c e MDC (a, b) = 1, então a ∣ c. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
14