promat

Prévia do material em texto

MA14 - Aritmética
Unidade 1
Resumo
Divisibilidade
Abramo Hefez
PROFMAT - SBM
Julho 2013
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 3 - Seção 3.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 2/1
Introdução
O nosso objeto de estudo neste curso é o conjunto dos números
inteiros:
Z = {. . . ,−2,−1, 0, 1, 2, . . .},
munido com as suas operações de adição e multiplicação, tendo as
seguintes propriedades, para quaisquer a, b, c ∈ Z:
Comutativa: a + b = b + a e a · b = b · a.
Associativa: (a + b) + c = a + (b + c) e (a · b) · c = a · (b · c).
Existência de elementos neutros: a + 0 = a e a · 1 = a.
Existência de simétrico: Para cada a existe b(= −a), tal que
a + b = 0.
Distributiva: a · (b + c) = a · b + a · c .
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 3/1
Introdução - Continuação
Reveja, no Caṕıtulo 1 do livro texto, as propriedades da adição e
da multiplicação, a ordenação dos inteiros, os Prinćıpios da Boa
ordenação e Indução Matemática.
Em Z há um subconjunto que se destaca, o conjunto dos números
naturais:
N = {1, 2, 3, . . .}.
Alguns autores consideram 0 ∈ N. O fato de considerarmos que
0 6∈ N é apenas uma escolha.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 4/1
Divisibilidade - Definições
Dados dois números inteiros quaisquer, é posśıvel somá-los,
subtráı-los e multiplicá-los.
Entretanto, nem sempre é posśıvel dividir um pelo outro, por
exemplo: em Z não é posśıvel dividir 3 por 2, mas é posśıvel dividir
4 por 2.
Só existe a Aritmética nos inteiros porque a divisão nem sempre é
posśıvel.
Diremos que um inteiro a divide um inteiro b, escrevendo
a|b,
quando existir c ∈ Z tal que b = c · a.
Neste caso, diremos também que a é um divisor ou um fator de b
ou, ainda, que b é um múltiplo de a.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 5/1
Exemplos
−2|0, pois 0 é múltiplo de −2: 0 = 0 · (−2);
1|6, pois 6 é múltiplo de 1: 6 = 6 · 1;
−1| − 6, pois −6 é múltiplo de −1: −6 = 6 · (−1);
2|6, pois 6 é múltiplo de 2: 6 = 3 · 2;
−3|6, pois 6 é múltiplo de −3: 6 = (−2) · (−3);
i ! divide o produto de i números naturais consecutivos.
Parece dif́ıcil de mostrar a última afirmação, mas escrevendo os
inteiros consecutivos convenientemente, ou seja,
n, n − 1, . . . , n − (i − 1),
para algum natural n, o resultado segue, imediatamente, da
seguinte igualdade
n · (n − 1) · · · (n − i + 1) = i !
(
n
i
)
,
o que mostra o desejado.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 6/1
Exerćıcio - Aplicação do último exemplo
6 divide todo número da forma n(n + 1)(2n + 1), onde n ∈ N.
Solução
De fato, se n = 1 temos que n(n + 1)(2n + 1) = 6 e 6|6.
Se n > 1, então
n(n + 1)(2n + 1) = n(n + 1)(n + 2 + n − 1)
= n(n + 1)(n + 2) + n(n + 1)(n − 1).
Como cada uma das parcelas n(n + 1)(n + 2) e n(n + 1)(n− 1) é o
produto de três naturais consecutivos, elas são múltiplas de 3! = 6.
Portanto, sendo o número n(n + 1)(2n + 1) soma de dois múltiplos
de 6, ele é também múltiplo de 6.
Este fato não é surpreendente, pois sabemos que
n(n + 1)(2n + 1)
6
= 12 + 22 + 32 + · · ·+ n2.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 7/1
Definições
A negação da sentença a | b é representada pelo śımbolo:
a 6 | b,
significando que não existe nenhum número inteiro c tal que
b = c · a.
Por exemplo, 3 6 | 4 e 2 6 | 5.
Suponha que a|b, onde a 6= 0, e seja c ∈ Z tal que b = c · a.
O número inteiro c , univocamente determinado, é chamado de
quociente de b por a e denotado por c =
b
a
.
Por exemplo,
0
1
= 0,
0
−2
= 0,
6
1
= 6,
−6
−1
= 6,
6
2
= 3,
6
−3
= −2.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 8/1
Proposição (Propriedades da divisibilidade)
Sejam a, b, c ∈ Z. Tem-se que
i) 1|a, a|a e a|0.
ii) 0 | a⇐⇒ a = 0.
iii) a divide b se, e somente se, |a| divide |b|.
iv) se a|b e b|c, então a|c (Propriedade transitiva).
Demonstração
i) Isso decorre das igualdades a = a · 1, a = 1 · a e 0 = 0 · a.
Deixamos as demonstrações dos itens (ii) e (iii) como exerćıcio.
iv) a|b e b|c implica que existem f , g ∈ Z, tais que
b = f · a e c = g · b.
Substituindo o valor de b da primeira equação na outra, obtemos
c = g · b = g · (f · a) = (g · f ) · a,
o que nos mostra que a|c . �
Os itens (i) e (ii) da proposição acima nos dizem que todo número
inteiro a é diviśıvel por ±1 e por ±a.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 9/1
Propriedades da divisibilidade - Continuação
Listaremos a seguir outras propriedades da divisibilidade, cujas
provas são semelhantes às feitas acima.
Proposição
Sejam a, b, c , d ∈ Z. Tem-se que
i) a|b e c |d =⇒ a · c |b · d;
ii) a|b =⇒ a · c|b · c;
iii) a|(b ± c) e a|b =⇒ a|c;
iv) a|b e a|c =⇒ a|(xb + yc), para todos x , y ∈ Z.
v) Seja b 6= 0. Tem-se que a|b =⇒ |a| 6 |b|.
É conveniente entender bem o significado das propriedades acima,
pois elas serão utilizadas a todo momento. É também conveniente
adquirir a habilidade em demonstrar tais propriedades, pois as
demonstrações contêm argumentos usados com frequência.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 10/1
Resultados importantes
Existem três propriedades da divisibilidade que são utilizadas com
frequência ao longo do Curso. A primeira é dada a seguir.
Proposição
Sejam a, b ∈ Z e n ∈ N. Temos que a− b divide an − bn.
Demonstração
Vamos provar isso por indução sobre n.
A afirmação é obviamente verdadeira para n = 1, pois a− b divide
a1 − b1 = a− b.
Suponhamos, agora, que (a− b)|(an − bn). Escrevamos
an+1 − bn+1 = aan − ban + ban − bbn = (a− b)an + b(an − bn).
Como (a− b)|(a− b) e, por hipótese, (a− b)|(an − bn), decorre da
igualdade acima e da Propriedade (iv) que (a− b)|(an+1 − bn+1).
Estabelecendo assim o resultado para todo n ∈ N. �
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 11/1
Na verdade poder-se-ia provar o resultado mais forte:
an − bn = (a− b)(an−1 + an−2b + · · ·+ abn−2 + bn−1).
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 12/1
Resultados importantes - Continuação
Seguem as outras duas propriedades.
Proposição
Sejam a, b ∈ Z e n ∈ N ∪ {0}.
Temos que a + b divide a2n+1 + b2n+1.
Proposição
Sejam a, b ∈ Z e n ∈ N. Temos que a + b divide a2n − b2n.
Novamente, as provas se fazem por indução sobre n, nos mesmos
moldes da prova da primeira propriedade.
Deixamos os detalhes por sua conta. Mãos à obra. Depois confira
as suas soluções na Seção 1 do Caṕıtulo 3 do livro texto.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 13/1
Exerćıcios
a) Mostre que 5 | (137 − 87)
Solução
Da propriedade
(a− b)|(an − bn),
temos, para todo n ∈ N, que
(13− 8)|(13n − 8n).
Portanto, 5 = 13− 8 divide 137 − 87.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 14/1
Exerćıcios - Continuação
b) Mostre que 13 | (270 + 370).
Solução
Note que
270 + 370 = 435 + 935.
Como 35 é ı́mpar, da propriedade
(a + b)|(a2n+1 + b2n+1),
temos que 4 + 9 divide 435 + 935.
Portanto, 13 divide 270 + 370.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 15/1
Exerćıcios - Continuação
c) Mostre que 9 e 41 dividem 524 − 424.
Solução
Temos que
524 − 424 = 52·12 − 42·12 = (25)2·6 − (16)2·6.
Da propriedade
(a + b)|(a2n − b2n),
obtemos que
(5 + 4)|(52·12 − 42·12)
e
(25 + 16)|
(
(52)2·6 − (42)2·6
)
.
Portanto, 9 e 41 dividem 524 − 424.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidadeslide 16/1
Exerćıcios - Continuação
d) Mostre que 14 |
(
34n+2 + 52n+1
)
, para todo n ∈ N ∪ {0}.
Solução
Temos, para todo n ∈ N ∪ {0}, que
34n+2 + 52n+1 =
(
32
)2n+1
+ 52n+1 = 92n+1 + 52n+1.
Pela propriedade
(a + b)|(a2m+1 + b2m+1),
temos que 14 = 9 + 5 divide
(
34n+2 + 52n+1
)
, para todo
n ∈ N ∪ {0}.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 17/1
Exerćıcios - Continuação
e) Mostre que 5 e 13 dividem 92n − 24n, para todo n ∈ N.
Solução
Temos, para todo n ∈ N, que
92n − 24n = 92n −
(
22
)2n
= 92n − 42n.
Pelas propriedades
(a− b)|(a2m − b2m) e (a + b)|(a2m − b2m),
temos que 5 = 9− 4 e 13 = 9 + 4 dividem 92n − 24n, para todo
n ∈ N.
Os exerćıcios (d) e (e) poderiam ser resolvidos utilizando indução.
Tente fazê-lo.
PROFMAT - SBM Aritmética - Unidade 1 - Resumo - Divisibilidade slide 18/1
MA14 - Aritmética
Unidade 2
Resumo
Divisão Euclidiana
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte da disciplina e o seu
estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 3 - Seção 3.2
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Estes resumos contaram com a colaboração de Maria Lúcia T.
Villela.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 2/21
Divisão Euclidiana
Mesmo quando um número inteiro a, não nulo, não divide um
número inteiro b, vale o seguinte fato:
É sempre posśıvel efetuar a divisão de b por a, com resto pequeno.
Este resultado, de cuja justificativa geométrica daremos uma ideia
quando a é natural, foi utilizado por Euclides (Século 3 a.C), nos
seus Elementos, no âmbito dos números naturais, sem enunciá-lo
explicitamente.
Essa propriedade não só é um importante instrumento na obra de
Euclides, como também é um resultado central da teoria elementar
dos números.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 3/21
De fato, suponhamos que a ∈ Z e consideremos a decomposição
de Z em união de intervalos disjuntos:
Z = . . . ∪ [−2a,−a) ∪ [−a, 0) ∪ [0, a) ∪ [a, 2a) ∪ . . .
Fica claro que qualquer número inteiro b pertence a um e somente
um desses intervalos, digamos b ∈ [qa, qa + a).
Portanto, b = qa + r , onde q e r são univocamente determinados,
com 0 6 r < a.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 4/21
Agora enunciamos o resultado geral:
Teorema (Divisão Euclidiana)
Sejam a e b dois números inteiros com a 6= 0. Existem dois únicos
números inteiros q e r tais que
b = a · q + r , com 0 6 r < |a|.
Nas condições do teorema, os números a e b são o divisor e o
dividendo, enquanto q e r são chamados, respectivamente, de
quociente e de resto da divisão de b por a.
Note que
o resto da divisão de b por a é zero se, e somente se, a divide b.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 5/21
Exemplos
Como 19 = 5 · 3 + 4, o quociente e o resto da divisão de 19
por 5 são q = 3 e r = 4.
Como −19 = 5 · (−4) + 1 o quociente e o resto da divisão de
−19 por 5 são q = −4 e r = 1.
Como 32 = (−5) · (−6) + 2 o quociente e o resto da divisão
de 32 por −5 são q = −6 e r = 2.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 6/21
Exemplos - Continuação
Mostrar que o resto da divisão de 10n por 9 é sempre 1,
qualquer que seja o número natural n.
Solução
Como mostrar um tal resultado?
Alguns experimentos ajudam a entender melhor o problema:
101 = 10 = 9× 1 + 1,
102 = 100 = 9× 11 + 1,
103 = 1000 = 9× 111 + 1.
Agora já entendemos melhor a questão e o resultado nos parece
tão óbvio que até podemos dizer que
10n = 9× 1 . . . 11︸ ︷︷ ︸
n vezes
+1,
donde, por ser 0 ≤ 1 < 9, podemos afirmar que o resto da divisão
por 9 é sempre 1.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 7/21
Muito bem, alguém poderia ponderar: Pronto, já mostramos!
Mas, atenção! Mostrar em matemática é sinônimo de provar!
E áı, como provar tal resultado?
Via de regra, quando temos uma asserção que envolve todos os
números naturais maiores do que um dado natural, a tendência é
tentar indução, a menos que tenhamos uma ideia melhor!
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 8/21
A nossa asserção se traduz matematicamente do seguinte modo:
P(n) : Existe q ∈ Z tal que 10n = 9q + 1.
Já verificamos acima que P(1) é verdade.
Para mostrar que P(n) =⇒ P(n + 1), suponhamos que P(n) seja
verdade, ou seja que existe q ∈ Z tal que 10n = 9q + 1.
Multiplicando por 10 ambos os lados dessa última igualdade,
temos que
10n+1 = 10(9q + 1) = 9× 10q + 10 = 9(10q + 1) + 1,
o que mostra que existe q′ = 10q + 1 tal que 10n+1 = 9q′ + 1,
provando que P(n + 1) é verdade.
Pelo Prinćıpio de Indução Matemática, P(n) é verdade ∀ n ∈ N.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 9/21
Outra Solução
Com o que temos em mãos, podeŕıamos ter dado uma
demonstração alternativa da nossa propriedade.
De fato, lembrando da propriedade
(a− b)|(an − bn),
temos que
(10− 1)|(10n − 1n),
ou seja, 9|10n − 1.
Assim, 10n − 1 = 9q, logo 10n = 9q + 1.
Como 0 ≤ 1 < 9, pela unicidade na divisão euclidiana, tem-se que
o resto da divisão de 10n por 9 é sempre 1.
Recomendação: Antes de começar a resolver um problema,
convém ler o enunciado com cuidado e tentar ver como o que se
pede se relaciona com o que já conhecemos, isto pode poupar
tempo e energia preciosos.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 10/21
Exemplos - Continuação
O resto da divisão de 74n − 24n + 93 por 45 é sempre 3, para
todo n ∈ N.
Solução
Note que
74n − 24n + 93 = 492n − 42n + 93.
Temos que 45 = 49− 4 divide 492n − 42n, para todo n ∈ N, logo
74n − 24n = 45q, para algum q ∈ Z.
Por outro lado, como 93 = 45 · 2 + 3,
74n − 24n + 93 = 45q + 2 · 45 + 3 = 45(q + 2) + 3,
com 0 ≤ 3 < 45.
Da unicidade do resto na divisão euclidiana, segue que 3 é o resto
da divisão de 74n − 24n + 93 por 45, para todo n ∈ N.
Tente, como exerćıcio, mostrar essa propriedade por indução.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 11/21
Parte inteira do racional ab , com b > 0
Sejam a, b ∈ Z com b > 0. Escrevamos a divisão euclidiana de a
por b:
a = bq + r , com 0 ≤ r < b.
Vamos dar uma interpretação para o quociente q dessa divisão.
Como
bq ≤ bq + r︸ ︷︷ ︸
a
< bq + b = b(q + 1),
temos que
bq ≤ a < b(q + 1).
Então, dividindo por b,
q ≤ ab < q + 1.
Portanto, q é o maior inteiro menor ou igual ao racional ab e é
chamado de parte inteira do número racional ab , sendo denotado
por
[
a
b
]
.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 12/21
Exemplos de parte inteira
Aproveitando alguns cálculos feitos anteriormente, temos[
19
5
]
=
[
5·3+4
5
]
=
[
3 + 45
]
= 3.
[−19
5
]
=
[
5·(−4)+1
5
]
=
[
−4 + 15
]
= −4.
Note que −4 < −3, 8 = −195 < −3.[
−32
5
]
=
[
5× (−7) + 3
5
]
=
[
−7 + 3
5
]
= −7.
Se a ∈ Z e α ∈ Q, com 0 ≤ α < 1, então [a + α] = a.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 13/21
Aplicação
Quantos múltiplos de 9 há entre 238 e 1247?
Entendemos que se algum dos números 238 ou 1247 for múltiplo
de 9, ele deve ser contado.
Solução
Às vezes, um problema se torna mais claro, quando generalizado.
Dados 0 < a < c, vamos contar quantos múltiplos de a existem
entre 1 e c.
Pela divisão euclidiana, temos que
c = aq + r , com 0 ≤ r < a.
Portanto, podemos escrever a lista dos múltiplos de a entre 1 e c
como segue:
a, 2a, . . . , (q − 1)a, qa.
Agora ficou fácil contar esses números: o seu número é q =
[
c
a
]
.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 14/21
Continuação
Agora, dados 0 < a < b < c , se quisermos contar quantos são os
múltiplos de a entre b e c, procedemos como segue:
De
[
c
a
]
, que é o número de múltiplos de a entre 1 e c ,
devemossubtrair
[
b−1
a
]
, que é o número de múltiplos de a
anteriores a b.
Assim, o número de múltiplos de a entre b e c é[c
a
]
−
[
b − 1
a
]
.
Portanto, a resposta para o nosso problema é:[
1247
9
]
−
[
238− 1
9
]
= 112.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 15/21
Par ou ı́mpar?
Desde os tempos de Pitágoras, os números inteiros são
classificados em pares e ı́mpares. Essa classificação pode ser
justificada pela divisão euclidiana.
Dado um número inteiro n ∈ Z qualquer, temos duas
possibilidades:
i) n é par: o resto da divisão de n por 2 é 0, isto é, existe q ∈ N tal
que n = 2q; ou
ii) n é ı́mpar: o resto da divisão de n por 2 é 1, ou seja, existe
q ∈ N tal que n = 2q + 1.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 16/21
Generalização: divisão por m ≥ 3
Mais geralmente, fixado um número natural m > 2, pode-se
sempre escrever um número qualquer n, de modo único, na forma
n = mk + r , onde k , r ∈ Z e 0 6 r < m.
Por exemplo,
todo número inteiro n pode ser escrito em uma, e somente
uma, das seguintes formas: 3k , 3k + 1, ou 3k + 2.
Ou ainda,
todo número inteiro n pode ser escrito em uma, e somente
uma, das seguintes formas: 4k , 4k + 1, 4k + 2, ou 4k + 3.
Este último fato, permite mostrar o resultado a seguir.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 17/21
Exerćıcio
Nenhum quadrado de um número inteiro é da forma 4k + 3.
Solução
De fato, seja a ∈ Z.
Se a = 4k, então a2 = 16k2 = 4k ′, onde k ′ = 4k2.
Se a = 4k + 1, então a2 = 16k2 + 8k + 1 = 4k ′ + 1,
onde k ′ = 4k2 + 2k.
Se a = 4k + 2, então a2 = 16k2 + 16k + 4 = 4k ′,
onde k ′ = 4k2 + 4k + 1.
Se a = 4k + 3, então a2 = 16k2 + 24k + 9 = 4k ′ + 1,
onde k ′ = 4k2 + 6k + 2.
Vamos aplicar este resultado para mostrar algo interessante.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 18/21
Exerćıcio
Nenhum número da forma a = 11 . . . 1 (n algarismos iguais a 1,
com n > 1) é um quadrado.
Solução
De fato, podemos escrever
a = b · 100 + 11 = 4(25 · b + 2) + 3,
onde b = 11 . . . 1 (n− 2 algarismos iguais a 1). Logo, a é da forma
4k + 3 e, portanto, não pode ser um quadrado.
Com esta técnica pode-se mostrar que nenhum número da forma
11 . . . 1 é soma de dois quadrados. Deixamos isto como exerćıcio.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 19/21
Exerćıcio
a) Quais são os números que, quando divididos por 7, deixam resto
igual à metade do quociente?
Solução
Seja a o número com a propriedade descrita acima. Pela divisão
euclidiana de a por 7 temos que existem inteiros q e r , tais que
a = 7q + r , com 0 ≤ r < 7. Como 0 ≤ r = q2 ≤ 6, então q é par,
com 0 ≤ q ≤ 12.
Os valores posśıveis de q, r e a estão na seguinte tabela:
q 0 2 4 6 8 10 12
r 0 1 2 3 4 5 6
a = 7q + r 0 15 30 45 60 75 90
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 20/21
Exerćıcio
b) (ENC: 2011) Seja N um número natural. Mostre que a divisão
de N2 por 6 nunca deixa resto 2.
Solução
Pela divisão euclidiana de N por 6, existem inteiros q e r tais que
N = 6q + r , com 0 ≤ r ≤ 5.
Portanto, N2 = 36q2 + 12qr + r2 = 6(6q2 + 2qr) + r2.
Assim, o resto que N2 deixa na divisão por 6 é o mesmo resto de
r2.
Analisaremos os valores de r2, na seguinte tabela:
r 0 1 2 3 4 5
r2 0 1 4 9 = 6 · 1 + 3 16 = 6 · 2 + 4 25 = 6 · 4 + 1
Logo, os restos posśıveis são 0, 1, 3 e 4.
PROFMAT - SBM Aritmética - Resumo 2 - Divisão Euclidiana slide 21/21
MA14 - Aritmética
Resumo 3
Sistemas de Numeração
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 4 - Seção 4.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Estes resumos contaram com a colaboração de Maria Lúcia T.
Villela.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 2/21
Sistemas de Numeração
Sabemos que existem infinitos números naturais.
Os primeiros tantos possuem até nomes. Por exemplo:
um, dois, três, . . . ,
cem, cento e um . . .
. . .
um trilhão, um trilhão e um . . .
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 3/21
É imposśıvel dar um nome para cada um dos números naturais,
mas é posśıvel de modo engenhoso dotar cada um deles de uma
representação com um pequeno número de śımbolos, por meio dos
chamados sistemas de numeração.
O sistema universalmente utilizado pelas pessoas comuns para
representar os números inteiros é o sistema decimal posicional.
Podemos nos restringir à representação dos números naturais,
pois todo número inteiro negativo é representado por um número
natural precedido pelo sinal − e zero tem seu próprio śımbolo que
é 0.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 4/21
Sistema decimal
No sistema decimal, todo número natural é representado por uma
sequência formada pelos algarismos
1, 2, 3, 4, 5, 6, 7, 8, 9,
acrescidos do śımbolo 0 (zero), que representa a ausência de
algarismo.
Por serem dez os algarismos, o sistema é chamado decimal.
O sistema é também chamado posicional, pois cada algarismo,
além do seu valor intŕınseco, possui um peso que lhe é atribúıdo
em função da posição que ele ocupa no número.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 5/21
Peso do algarismo
Esse peso, sempre uma potência de dez, varia do seguinte modo: o
algarismo da extrema direita tem peso 1; o seguinte, sempre da
direita para a esquerda, tem peso dez; o seguinte tem peso cem; o
seguinte tem peso mil, etc.
Portanto, os números de um a nove são representados pelos
algarismos de 1 a 9, correspondentes. O número dez é representado
por 10, o número cem por 100, o número mil por 1000.
Por exemplo, o número 12019, na base 10, é a representação de
1 · 104 + 2 · 103 + 0 · 102 + 1 · 10 + 9 = 1 · 104 + 2 · 103 + 1 · 10 + 9.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 6/21
Ordem de um algarismo/Classe de uma terna de ordens
Cada algarismo de um número possui uma ordem contada da
direita para a esquerda.
Assim, no número 12019, o primeiro 1 que aparece (não se
esqueça, sempre da direita para a esquerda) é de segunda ordem,
enquanto que o último é de quinta ordem. O 9 é de primeira
ordem, enquanto que o 2 é de quarta ordem.
Cada terna de ordens, também contadas da direita para a
esquerda, forma uma classe. As classes são, às vezes, separadas
umas das outras por meio de um ponto.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 7/21
Classes e ordens
Damos a seguir os nomes das primeiras classes e ordens:
Classe das Unidades
 unidades 1
a ordem
dezenas 2a ordem
centenas 3a ordem
Classe do Milhar
 unidades de milhar 4
a ordem
dezenas de milhar 5a ordem
centenas de milhar 6a ordem
Classe do Milhão
 unidades de milhão 7
a ordem
dezenas de milhão 8a ordem
centenas de milhão 9a ordem
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 8/21
Expansão na base b
Os sistemas de numeração posicionais baseiam-se no resultado a
seguir, que é uma aplicação da divisão euclidiana.
Teorema
Dados números inteiros a e b, com a > 0 e b > 1, existem números
inteiros n ≥ 0 e 0 ≤ r0, r1, . . . , rn < b, rn 6= 0, univocamente
determinados, tais que a = r0 + r1b + r2b
2 + · · ·+ rnbn.
A representação dada no teorema acima é chamada de expansão
relativa à base b.
Quando b = 10, essa expansão é chamada expansão decimal.
Quando b = 2, ela toma o nome de expansão binária.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 9/21
Demonstração
Aplicamos sucessivamente a divisão euclidiana, permitindo
determinar aexpansão de a na base b, como segue:
a = bq0 + r0, 0 ≤ r0 < b,
q0 = bq1 + r1, 0 ≤ r1 < b,
q1 = bq2 + r2, 0 ≤ r2 < b,
e assim por diante. Como a > q0 > q1 > · · · , deveremos, em um
certo ponto, ter qn−1 < b e, portanto, de
qn−1 = bqn + rn,
decorre que qn = 0, o que implica 0 = qn = qn+1 = qn+2 = · · · , e,
portanto, 0 = rn+1 = rn+2 = · · · .
Temos, então, que
a = r0 + r1b + · · ·+ rnbn.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 10/21
Exemplo 1
Vamos determinar a expansão na base b = 2 do número 53.
53 = 2 · (26)︸︷︷︸
q0
+ 1︸︷︷︸
r0
;
26 = 2 · (13)︸︷︷︸
q1
+ 0︸︷︷︸
r1
;
13 = 2 · 6︸︷︷︸
q2
+ 1︸︷︷︸
r2
;
6 = 2 · 3︸︷︷︸
q3
+ 0︸︷︷︸
r3
;
3 = 2 · 1︸︷︷︸
q4
+ 1︸︷︷︸
r4
;
1 = 2 · 0︸︷︷︸
q5
+ 1︸︷︷︸
r5
;
Logo, 53 = 1 + 0 · 2 + 1 · 22 + 0 · 23 + 1 · 24 + 1 · 25.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 11/21
Exemplo 2
Vamos determinar a expansão de a = 113 na base b = 3.
113 = 3 · (37)︸︷︷︸
q0
+ 2︸︷︷︸
r0
;
37 = 3 · (12)︸︷︷︸
q1
+ 1︸︷︷︸
r1
;
12 = 3 · 4︸︷︷︸
q2
+ 0︸︷︷︸
r2
;
4 = 3 · 1︸︷︷︸
q3
+ 1︸︷︷︸
r3
;
1 = 3 · 0︸︷︷︸
q4
+ 1︸︷︷︸
r4
.
Logo, 113 = 2 + 1 · 31 + 0 · 32 + 1 · 33 + 1 · 34.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 12/21
A expansão numa dada base b nos fornece um método para
representar os números naturais. Para tanto, escolha um conjunto
S de b śımbolos
S = { s0, s1, . . . , sb−1 },
com s0 = 0, para representar os números de 0 a b − 1.
Um número natural a na base b se escreve na forma
xnxn−1 . . . x1x0,
com x0, . . . , xn ∈ S , e n variando, dependendo de a, representando
o número
x0 + x1b + · · ·+ xnbn.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 13/21
No sistema decimal, isto é, de base b = 10, usa-se
S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Se a base b é tal que b 6 10, utilizam-se os śımbolos
0, 1, . . . , b − 1.
Se a base b é tal que b > 10, costuma-se usar os śımbolos de 0 a
9, acrescentando novos śımbolos para 10, . . . , b − 1.
No sistema de base b = 2, temos que
S = { 0, 1},
e todo número natural é representado por uma sequência de 0 e 1.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 14/21
Representação na base 2
O número 10 na base 2 representa o número 2 (na base 10).
Quando estivermos lidando com números em bases diferentes num
mesmo contexto, utilizaremos śımbolos como [a]b significando que
a é a representação de um número na base b. Portanto,
[10]2 = [2
1 + 0]10 = [2]10;
[11]2 = [2
1 + 1]10 = [3]10;
[100]2 = [2
2 + 0 · 2 + 0]10 = [4]10;
[101]2 = [2
2 + 1]10 = [5]10;
[110]2 = [2
2 + 2 + 0] = [6]10;
[111]2 = [2
2 + 2 + 1]10 = [7]10;
[1011]2 = [2
3 + 2 + 1]10 = [11]10.
O sistema na base 2 é utilizado nos computadores.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 15/21
Exemplo 3
a) Representar na base 2 o número cuja representação na base 10
é 53.
Segue do Exemplo 1 que
53 = 1 + 0 · 2 + 1 · 22 + 0 · 23 + 1 · 24 + 1 · 25,
então [53]10 = [110101]2.
b) Representar na base 3 o número cuja representação na base 10
é 113.
Segue do Exemplo 2 que
113 = 2 + 1 · 31 + 0 · 32 + 1 · 33 + 1 · 34,
então [113]10 = [11012]3.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 16/21
Exemplo 4
Representar na base 5 o número cuja representação na base 10 é
723.
Por divisão euclidiana sucessiva,
723 = 144 · 5 + 3,
144 = 28 · 5 + 4,
28 = 5 · 5 + 3,
5 = 1 · 5 + 0,
1 = 0 · 5 + 1.
Portanto,
723 = 3 + 4 · 5 + 3 · 52 + 0 · 53 + 1 · 54,
e, consequentemente, 723 na base 5 se representa por 10343.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 17/21
Exemplo 5
a) Representar na base b = 11 o número cuja representação na
base 10 é 3909.
Usaremos S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, α}, onde α é o śımbolo
para 10 = b − 1. Aplicando sucessivamente o algoritmo euclidiano,
temos
3909 = 4 + 3 · 11 + 10 · 112 + 2 · 113.
Logo, 3909 é representado na base 11 por 2α34.
b) Quais os números na base 10 representados na base b = 11 por
10, 100, 11 e 12?
representação na base 11 número decimal
10 0 + 1 · b = b = 11
100 0 + 0 · b + 1 · b2 = 112 = 121
11 1 + 1 · b = 1 + 11 = 12
12 2 + 1 · b = 2 + 11 = 13
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 18/21
Critérios de divisibilidade por 5 e por 10
Seja a = rn · · · r1r0 um número representado no sistema decimal.
Uma condição necessária e suficiente para que a seja diviśıvel por 5
(respectivamente por 10) é que r0 seja 0 ou 5 (respectivamente 0).
Demonstração
Sendo a = 10 · (rn · · · r1) + r0, temos que a é diviśıvel por 5 se, e
somente se, r0 é diviśıvel por 5, e, portanto, r0 = 0 ou r0 = 5. Por
outro lado, a é diviśıvel por 10 se, e somente se, r0 é diviśıvel por
10, o que somente ocorre quando r0 = 0.
�
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 19/21
Critérios de divisibilidade por 3 e por 9
Seja a = rn · · · r1r0 um número representado no sistema decimal.
Uma condição necessária e suficiente para que a seja diviśıvel por 3
(respectivamente por 9) é que rn + · · ·+ r1 + r0 seja diviśıvel por 3
(respectivamente por 9).
Demonstração
Temos que
a−(rn + · · ·+r1+r0) = rn10n + · · ·+r110+r0−(rn + · · ·+r1+r0) =
rn(10
n − 1) + · · ·+ r1(10− 1).
Sabemos que o termo à direita nas igualdades acima é diviśıvel por
9 (Exemplo na Unidade 2), logo, para algum número q, temos que
a = (rn + · · ·+ r1 + r0) + 9q,
de onde segue o resultado. �
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 20/21
Exerćıcio
Verifique que 9 não divide 8285748537 e 3 divide 8285748537.
Solução
Aplicaremos, sucessivamente, os critérios de divisibilidade por 9 e
por 3.
Temos que
8 + 2 + 8 + 5 + 7 + 4 + 8 + 5 + 3 + 7 = 57 e 5 + 7 = 12.
É claro que 9 6 | 12 e 3 | 12.
Portanto,
9 6 | 12 se, e somente se, 9 6 | 57 se, e somente se, 9 6 | 8285748537 e
e 3 | 12 se, e somente se, 3 | 57 se, e somente se, 3 | 8285748537.
PROFMAT - SBM Aritmética - Unidade 3 - Resumo - Sistemas de Numeração slide 21/21
MA14 - Aritmética
Unidade 4
Resumo
O Jogo de Nim
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 4 - Seção 4.2
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Estes resumos contaram com a colaboração de Maria Lúcia T.
Villela.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 2/13
Introdução
O Jogo de Nim faz parte de uma teoria, relativamente jovem,
chamada Teoria de Jogos. Vários jogos podem ser reduzidos a
esse, conforme veremos mais adiante em um exemplo.
O jogo de Nim consiste de N palitos separados em três grupos com
números distintos de elementos e colocados em cima de uma mesa,
no qual dois jogadores se alternam retirando, cada um na sua vez,
um número não nulo qualquer de palitos de apenas um dos grupos,
podendo retirar inclusive todos os palitos do grupo escolhido.
Ganha o jogo quem primeiro não deixar nenhum palito sobre a
mesa.
Cada estado do jogo pode ser representado por uma terna de
números, representando o número de palitos em cada grupo,
ordenados previamente como Grupo 1, Grupo 2 e Grupo 3,
começando com uma configuração inicial (n1, n2, n3), onde
n1 + n2 + n3 = N.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 3/13
Tomemos como exemplo a configuração inicial (3, 5, 7) e que os
jogadores sejam João (J) e Maria (M) e vejamos um exemplo de
uma partida:
(3, 5, 7)
J→ (2, 5, 7) M→ (2, 5, 0) J→ (2, 2, 0).
Neste ponto já dá para perceber que Maria não tem mais sáıda,
pois se ela retirar dois palitos de um grupo, João tira os dois
palitos que sobraram no outrogrupo e ganha o jogo. Se Maria tira
um palito de um grupo, João tira um palito do outro grupo e assim
Maria fica também sem sáıda. Portanto, João ganhou a partida.
A primeira jogada do João, bem como as seguintes, não foram
jogadas aleatórias, ele seguiu uma estratégia vencedora que
explicaremos a seguir.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 4/13
Voltemos à situação inicial da partida entre João e Maria em que
N = 15, n1 = 3, n2 = 5 e n3 = 7.
| | | | | | | | | | | | | | |
Neste caso particular, vamos estabelecer uma estratégia de tal
modo que, quem iniciar a partida fazendo uma boa abertura e
seguindo as regras que estabeleceremos, sempre vencerá.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 5/13
Para isto, a cada jogada, escreve-se o número de palitos de cada
grupo na base 2, colocando-os um em cada linha, de modo que os
algarismos das unidades se correspondam. Por exemplo, no ińıcio
da partida tem-se
Grupo 1 11
Grupo 2 101
Grupo 3 111
Somando os três números acima como se fosse na base 10,
obtemos o número 223, que chamaremos, a cada etapa, de chave
do jogo.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 6/13
O primeiro jogador poderá, então, com uma jogada, tornar todos
os algarismos da chave pares. Por exemplo, poderá retirar um
palito do grupo três, obtendo
Grupo 1 11
Grupo 2 101
Grupo 3 110
222
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 7/13
Agora, qualquer jogada que o segundo jogador efetuar transformará
a chave 222 numa chave com, pelo menos, um algarismo ı́mpar
(você pode verificar isto com a análise de todas as possibilidades).
Agora, mediante uma jogada conveniente, o primeiro jogador
poderá recolocar o jogo na situação em que todos os algarismos
sejam pares.
Uma situação em que todos os algarismos da chave são pares será
chamada de posição segura, enquanto que, quando pelo menos um
dos algarismos da chave é ı́mpar, será uma posição insegura.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 8/13
Pode-se mostrar, de modo bem elementar, que qualquer que seja a
configuração inicial do jogo, se um jogador encontra na sua vez
uma posição segura, qualquer que seja a jogada que faça, só
poderá chegar a uma posição insegura.
Mostra-se também que, de uma posição insegura, pode-se, com
uma jogada conveniente, sempre retornar a uma posição segura.
Finalmente, observando que quem chegar primeiro em 000 ganha o
jogo e que esta é uma posição segura, ganhará o jogo quem
sempre, após a sua vez de jogar, se mantiver em posições seguras.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 9/13
Em geral, nem sempre a configuração inicial do jogo será favorável
ao primeiro jogador. Por exemplo, o jogo com a configuração
inicial (3, 5, 6), nos dá a seguinte chave:
Grupo 1 011
Grupo 2 101
Grupo 3 110
222
Esta chave já coloca o primeiro jogador em desvantagem, pois
qualquer jogada que fizer, o deixará em posição insegura.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 10/13
Esta versão, bem como a sua estratégia, podem ser generalizadas
sem dificuldade para um número arbitrário de grupos com um
número arbitrário de palitos em cada grupo.
Vamos a seguir discutir um problema emprestado do livro de
Terence Tao (Resolvendo Problemas Matemáticos, Coleção
Professor de Matemática, SBM).
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 11/13
Um jogo consiste de um tablete de chocolate dividido em 6× 10
quadradinhos separados por sulcos e jogado por dois jogadores.
Cada jogador, na sua vez, quebra a barra de chocolate numa
horizontal ou numa vertical ao longo de todo um sulco e come
uma das partes. O jogo prossegue até que um dos jogadores é
obrigado a comer o último quadradinho que restar e perde o jogo.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 12/13
Vejamos como podemos reduzir este jogo a um jogo de Nim e
aproveitar a estratégia já estudada.
Cada sulco na horizontal é representado por um palito. Portanto,
os 5 sulcos na horizontal são representados por 5 palitos e formam
um dos dois grupos de um jogo de Nim. O outro grupo é formado
por 9 palitos representando os 9 sulcos na vertical.
Cada jogador, ao retirar um pedaço da barra de chocolate, está na
realidade retirando um certo número de sulcos na horizontal ou na
vertical, o que corresponde a retirar o mesmo número de palitos de
um dos grupos.
Ganha o jogo quem tirar o último palito, pois quando esse jogador
retirar o último palito, o que sobrou da barra de chocolate é um
pedaço sem sulcos, ou seja, um último quadradinho de chocolate
que o outro jogador terá que comer, perdendo a partida.
PROFMAT - SBM Aritmética - Unidade 4 - Resumo - Jogo de Nim slide 13/13
MA14 - Aritmética
Unidade 5
Resumo
Máximo Divisor Comum
Abramo Hefez
PROFMAT - SBM
Julho 2013
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 5 - Seção 5.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 2/19
Divisor Comum
Sejam a e b dois inteiros, distintos ou não. Um número inteiro d
será dito um divisor comum de a e b se d |a e d |b.
Por exemplo, os números ±1, ±2, ±3 e ±6 são os divisores
comuns de 12 e 18.
A definição a seguir foi essencialmente dada por Euclides nos
Elementos e se constitui em um dos pilares da sua aritmética.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 3/19
Definição: Máximo Divisor Comum
Um número inteiro d > 0 é um máximo divisor comum (mdc) de
dois inteiros a e b se possuir as seguintes propriedades:
i) d é um divisor comum de a e de b, e
ii) d é diviśıvel por todo divisor comum de a e b.
Exemplo
O máximo divisor comum de 12 e 18 é 6.
A condição (ii) acima pode ser reenunciada como segue:
ii′) Se c é um divisor comum de a e b, então c |d .
Em particular, se d e d ′ são dois mdc de um mesmo par de
números, então d | d ′ e d ′ | d , o que, juntamente com as
condições d ≥ 0 e d ′ ≥ 0 implicam d = d ′.
Ou seja, quando existe, o mdc de dois números é único.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 4/19
Veremos mais adiante que sempre existe o mdc de dois números
inteiros a e b e o denotaremos por (a, b).
Como o mdc de a e b não depende da ordem em que a e b são
tomados, temos que
(a, b) = (b, a).
Em alguns casos particulares, é facil verificar a existência do mdc.
Por exemplo, se a é um número inteiro tem-se claramente que
(0, a) = |a|, (1, a) = 1 e (a, a) = |a|.
Mais geralmente, para todo b ∈ Z, temos que
a|b ⇐⇒ (a, b) = |a|. (1)
Observação
Sejam a, b ∈ Z. Tem-se que (a, b) = 0⇐⇒ a = b = 0.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 5/19
A demonstração da existência do mdc de qualquer par de números
inteiros, não ambos nulos, é bem mais sutil.
Se d > 0 é um mdc de a e b não nulos e c é um divisor comum
desses números, então c divide d e, consequentemente, |c | divide
d . Portanto, c 6 |c | 6 d .
Isto mostra que, efetivamente, quando existe, o máximo divisor
comum de dois números, não ambos nulos, é o maior dentre todos
os divisores comuns desses números.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 6/19
Podeŕıamos, como se faz usualmente no Ensino Fundamental,
definir o máximo divisor comum de dois números a e b, não ambos
nulos, como o maior elemento do conjunto de todos os divisores
comuns desses números, o que de imediato garantiria a sua
existência.
De qualquer modo, seria necessárioprovar a propriedade (ii) da
definição de mdc, pois é ela que possibilita provar os resultados
subsequentes, e não o fato do mdc ser o maior dos divisores
comuns.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 7/19
Observe que dados a, b ∈ Z, se existir o mdc (a, b) de a e b, então
(a, b) = (−a, b) = (a,−b) = (−a,−b).
Assim, para efeito do cálculo do mdc de dois números, podemos
supô-los não negativos.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 8/19
Resultado fundamental para o Algoritmo de Euclides
Para provar a existência do máximo divisor comum de dois inteiros
não negativos, Euclides utiliza, essencialmente, o resultado abaixo.
Lema
Sejam a, b, n ∈ Z. Se existe (a, b − na), então (a, b) existe e
(a, b) = (a, b − na).
O Lema é efetivo para calcular mdc, conforme veremos nos
exemplos a seguir, e será fundamental para estabelecermos o
algoritmo de Euclides, que permitirá, com muita eficiência, calcular
o mdc de dois números naturais quaisquer.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 9/19
Exerćıcio
Vamos determinar o máximo divisor comum de 96525 e 90, usando
o Lema.
Solução
(90, 96 525) = (90, 96 525− 90× 1 000) = (90, 96 525− 90 000)
= (90, 6 525)
= (90, 6 525− 70× 90) = (90, 6 525− 6 300)
= (90, 225)
= (90, 225− 2× 90) = (90, 225− 180)
= (90, 45)
= (45, 90)
= 45.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 10/19
Exemplo 1
Dados a ∈ Z com a 6= 1 e m ∈ N, temos que(
am−1
a−1 , a− 1
)
= (a− 1,m).
Solução
A igualdade acima é trivialmente verificada se m = 1. Suponhamos
que m > 2. Chamando de d o primeiro membro da igualdade,
temos que
d = (am−1 + am−2 + · · ·+ a + 1, a− 1) =(
(am−1 − 1) + (am−2 − 1) + · · ·+ (a− 1) + m, a− 1
)
.
Como
a− 1|(am−1 − 1) + (am−2 − 1) + · · ·+ (a− 1),
segue-se, para algum n ∈ N, que
(am−1 − 1) + (am−2 − 1) + · · ·+ (a− 1) = n(a− 1).
Portanto, pelo Lema anterior tem-se que
d = (n(a− 1) + m, a− 1) = (a− 1, n(a− 1) + m) = (a− 1,m).
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 11/19
Exemplo 2
Determinemos os valores de a ∈ Z e n ∈ N para os quais a + 1
divide a2n + 1.
Solução
Note inicialmente que
a + 1|a2n + 1⇐⇒ (a + 1, a2n + 1) = |a + 1|.
Como a2n + 1 = (a2n − 1) + 2, e a + 1|a2n − 1, segue-se do Lema
anterior, para todo n, que
(a + 1, a2n + 1) = (a + 1, (a2n − 1) + 2) = (a + 1, 2).
Portanto, a + 1|a2n + 1, para algum n ∈ N, se, e somente se,
|a + 1| = (a + 1, 2), o que ocorre se, e somente se, a = 0, a = 1,
a = −2 ou a = −3 e n qualquer.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 12/19
Exemplo 3
Vamos, neste exemplo, determinar os valores de a ∈ Z e n ∈ N
para os quais a + 1 divide a2n+1 − 1.
Solução
Note que
(a + 1, a2n+1 − 1) = (a + 1, a(a2n − 1) + a− 1) = (a + 1, a− 1).
Portanto, a + 1|a2n+1 − 1, para algum n ∈ N, se, e somente se,
|a+1| = (a+1, a2n+1−1) = (a+1, a−1) = (a+1,−2) = (a+1, 2)
o que ocorre se, e somente se, a = 0, a = 1, a = −2 ou a = −3 e
n qualquer.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 13/19
Algoritmo de Euclides
Prova construtiva da existência do mdc dada por Euclides.
Dados a, b ∈ N, podemos supor a 6 b. Se a = 1 ou a = b, ou
ainda a|b, já vimos que (a, b) = a. Suponhamos, então, que
1 < a < b e que a 6 | b. Logo, pela divisão euclidiana, podemos
escrever
b = aq1 + r1, com 0 < r1 < a.
Temos duas possibilidades:
a) r1|a, e, em tal caso, por (1) e pelo Lema,
r1 = (a, r1) = (a, b − q1a) = (a, b),
e termina o algoritmo, ou
b) r1 6 | a, e, em tal caso, podemos efetuar a divisão de a por r1,
obtendo
a = r1q2 + r2, com 0 < r2 < r1.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 14/19
Novamente, temos duas possibilidades:
a′) r2|r1, e, em tal caso, novamente, por (1) e pelo Lema de
Euclides,
r2 = (r1, r2) = (r1, a− q2r1) = (r1, a) = (b − q1a, a) = (b, a) = (a, b),
e paramos, pois termina o algoritmo, ou
b′) r2 6 | r1, e, em tal caso, podemos efetuar a divisão de r1 por r2,
obtendo
r1 = r2q3 + r3, com 0 < r3 < r2.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 15/19
Este procedimento não pode continuar indefinidamente, pois
teŕıamos uma sequência de números naturais
a > r1 > r2 > · · · ,
que não possui menor elemento, o que não é posśıvel pela
Propriedade da Boa Ordenação.
Logo, para algum n, temos que rn|rn−1, o que implica que
(a, b) = rn. �
O algoritmo acima pode ser sintetizado e realizado na prática,
como mostramos a seguir.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 16/19
Inicialmente, efetuamos a divisão
b = aq1 + r1
e colocamos os números envolvidos
no diagrama ao lado.
q1
b a
r1
Continuamos efetuando a divisão
a = r1q2 + r2
e colocamos os números envolvidos
no diagrama ao lado.
q1 q2
b a r1
r1 r2
Prosseguindo, enquanto for posśıvel (até que para algum n > 2
rn | rn−1), teremos
q1 q2 q3 · · · qn−1 qn qn+1
b a r1 r2 · · · rn−2 rn−1 rn = (a, b)
r1 r2 r3 r4 · · · rn
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 17/19
Exemplo 4
Calculemos o mdc de 372 e 162:
2 3 2 1 2
372 162 48 18 12 6
48 18 12 6
Observe que, no exemplo acima, o Algoritmo de Euclides nos
fornece:
6 = 18− 1 · 12
12 = 48− 2 · 18
18 = 162− 3 · 48
48 = 372− 2 · 162
Donde se segue que
6 = 18− 1 · 12 = 18− 1 · (48− 2 · 18) = 3 · 18− 48 =
3 · (162− 3 · 48)− 48 = 3 · 162− 10 · 48 =
3 · 162− 10 · (372− 2 · 162) = 23 · 162− 10 · 372.
Temos, então, que
(372, 162) = 6 = 23 · 162 + (−10) · 372.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 18/19
Note que conseguimos, através do uso do Algoritmo de Euclides de
trás para frente, escrever 6 = (372, 162) como múltiplo de 162
mais um múltiplo de 372.
O Algoritmo de Euclides nos fornece, portanto, um meio prático de
escrever o mdc de dois números como soma de dois múltiplos dos
números em questão. Esta é uma propriedade geral do mdc que
redemonstraremos com todo rigor na próxima seção.
Quando utilizarmos o Algoritmo de Euclides para expressar (a, b)
na forma ma + nb, com m, n ∈ Z, nos referiremos a ele como
Algoritmo de Euclides Estendido.
PROFMAT - SBM Aritmética - Unidade 5 - Resumo - Máximo Divisor Comum slide 19/19
MA14 - Aritmética
Unidade 6
Resumo
Propriedades do mdc
Abramo Hefez
PROFMAT - SBM
Julho 2013
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 5 - Seção 5.2,
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 2/9
Sejam a, b ∈ Z. O conjunto a seguir desempenhará papel
importante
I (a, b) = {xa + yb; x , y ∈ Z}.
Note que se a e b não são simultaneamente nulos, então
I (a, b) ∩ N 6= ∅.
De fato, temos que a2 + b2 = a · a + b · b ∈ I (a, b) ∩ N.
A importância do conjunto I (a, b) pode ser medida pelo resultado
a seguir.
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 3/9
Teorema
Sejam a, b ∈ Z não ambos nulos. Se d = min I (a, b) ∩ N, então
i) d é o mdc de a e b; e
ii) I (a, b) = dZ (= {xd ; x ∈ Z}).
Esse teorema nos dá uma outra demonstração da existência do
mdc de dois números.
Note que essa demonstração, ao contrário da prova de Euclides,
não é construtiva, no sentido de que não nos fornece um meio
prático para achar o mdc dos dois números.
O teorema admite vários corolários.
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 4/9
Corolários
1. Quaisquer que sejam a, b ∈ Z, não ambos nulos, e n ∈ N,
(na, nb) = n(a, b).
2. Dados a, b ∈ Z, não ambos nulos, tem-se que(
a(a, b)
,
b
(a, b)
)
= 1.
Dois números inteiros a e b serão ditos primos entre si, ou
coprimos, se (a, b) = 1; ou seja, se o único divisor comum positivo
de ambos é 1.
3. Dois números inteiros a e b são primos entre si se, e somente
se, existem números inteiros m e n tais que ma + nb = 1.
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 5/9
Um Teorema Fundamental
A propriedade acima estabelece uma relação crucial entre as
estruturas aditiva e multiplicativa dos números naturais, o que
permite provar o importante resultado a seguir.
Teorema
Sejam a, b e c números inteiros.
a | b · c e (a, b) = 1 =⇒ a|c .
Corolário
Dados a, b, c ∈ Z, com b e c não ambos nulos, temos que
b|a e c |a ⇐⇒ bc
(b, c)
| a.
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 6/9
Generalização do conceito de mdc
Um número natural d será dito mdc de dados números inteiros
a1, . . . , an, não todos nulos, se possuir as seguintes propriedades:
i) d é um divisor comum de a1, . . . , an.
ii) Se c é um divisor comum de a1, . . . , an, então c|d .
O mdc, quando existe, é certamente único e será representado por
(a1, . . . , an).
Dados números inteiros a1, . . . , an, não todos nulos, existe o seu
mdc e pode ser calculado recursivamente através da fórmula:
(a1, . . . , an) = (a1, . . . , (an−1, an)).
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 7/9
Exemplos
(72, 138, 252) = (72, (138, 252)) = (72, 6) = 6.
1 1 4 1 3
252 138 114 24 18 6
114 24 18 6
(15, 72, 180) = (15, (72, 180)) = (15, 36) = 3.
2 2
180 72 36
36
e
2 2 2
36 15 6 3
6 3
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 8/9
Os inteiros a1, . . . , an serão ditos primos entre si, ou coprimos,
quando (a1, . . . , an) = 1.
Exemplo
(5, 12, 18) = (5, (12, 18)) = (5, 6) = 1.
(143, 175, 245) = (143, (175, 245)) = (143, 35) = 1.
1 2 2
245 175 70 35
70 35
e
4 11 1 2
143 35 3 2 1
3 2 1
PROFMAT - SBM Aritmética - Unidade 6 - Resumo - Propriedades do mdc slide 9/9
MA14 - Aritmética
Unidade 7
Resumo
Ḿınimo Múltiplo Comum
Abramo Hefez
PROFMAT - SBM
Julho 2013
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 5 - Seção 5.4
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 2/9
Ḿınimo Múltiplo Comum
Um número inteiro é um múltiplo comum de dois números inteiros
dados se ele é simultaneamente múltiplo de ambos os números.
Exemplo
Os números ab e 0 são sempre múltiplos comuns de a e b.
Um número inteiro m ≥ 0 é um ḿınimo múltiplo comum (mmc)
dos números inteiros a e b, quando vale:
(i) m é um múltiplo comum de a e b, e
(ii) se c é um múltiplo comum de a e b, então m|c .
Exemplo
12 é um múltiplo comum de 2 e 3, mas não é um mmc destes
números. O número 6 é um mmc de 2 e 3.
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 3/9
Se m e m′ são dois ḿınimos múltiplos comuns de a e b, então, do
item (ii) da definição acima, temos que m|m′ e m′|m. Como m e
m′ são números inteiros não negativos, temos que m = m′, o que
mostra que o ḿınimo múltiplo comum, se existe, é único.
Por outro lado, se m é o mmc de a e b e c é um múltiplo comum
de a e b, então m|c . Portanto, se c é positivo, temos que m 6 c ,
mostrando que m é o menor dos múltiplos comuns positivos de a e
b.
O ḿınimo múltiplo comum de a e b, se existe, é denotado por
[a, b].
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 4/9
Caso exista [a, b] é fácil mostrar que
[−a, b] = [a,−b] = [−a,−b] = [a, b].
Assim, para efeito do cálculo do mmc de dois números, podemos
sempre supô-los não negativos.
É também fácil verificar que
[a, b] = 0⇐⇒ a = 0 ou b = 0.
De fato, se [a, b] = 0, então 0 divide ab, que é múltiplo de a e b,
logo ab = 0 e, portanto a = 0 ou b = 0.
Reciprocamente, se a = 0 ou b = 0, então 0 é o único múltiplo
comum de a e b, logo [a, b] = 0.
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 5/9
Relação entre o mdc, o mmc e o produto de dois inteiros
Proposição
Dados dois números inteiros a e b, temos que [a, b] existe e
[a, b](a, b) = |ab|.
Em virtude da proposição acima, o ḿınimo múltiplo comum de
dois inteiros, ambos não nulos, pode ser encontrado por meio do
Algoritmo de Euclides para o cálculo do mdc, pois basta dividir o
módulo do produto dos dois números pelo seu mdc.
Corolário
Se a e b são números inteiros primos entre si, então [a, b] = |ab|.
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 6/9
Exemplo
Sejam b e m dois números naturais. Vamos mostrar que, na
sequência de números
b, 2b, 3b, . . . , mb,
existem exatamente (b, m) números diviśıveis por m.
De fato, os números da sequência diviśıveis por m são múltiplos de
b e m; logo, múltiplos de [b, m]. Esses são:
[b, m], 2[b, m], 3[b, m], . . . , (b, m)[b, m] (= mb).
Portanto, tem-se (b, m) números diviśıveis por m na sequência.
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 7/9
Generalização do conceito de mmc
Podemos estender a noção de mmc para vários números, como
faremos a seguir.
Diremos que um número natural m é um mmc dos inteiros não
nulos a1, . . . , an, se m é um múltiplo comum de a1, . . . , an, e, se
para todo múltiplo comum m′ desses números, tem-se que m|m′.
É facil ver que o mmc, se existe, é único, sendo denotado por
[a1, . . . , an].
Além disso, o mmc de vários inteiros não nulos é o menor múltiplo
comum positivo desses inteiros.
Proposição
Sejam a1, . . . , an números inteiros não nulos. Então existe o
número [a1, . . . , an] e
[a1, . . . , an−1, an] = [a1, . . . , [an−1, an]] .
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 8/9
Exemplo
Temos que
[−56, 16, 24] = [56, [16, 24]] = [56, 48] = 336,
pois
[16, 24] =
16× 24
(16, 24)
=
16× 24
8
= 2× 24 = 48 e
[56, 48] =
56× 48
(56, 48)
=
56× 48
8
= 56× 6 = 336.
PROFMAT - SBM Aritmética - Unidade 7 - Resumo - Ḿınimo Múltiplo Comum slide 9/9
MA14 - Aritmética
Unidade 8
Resumo
Equações Diofantinas Lineares
Abramo Hefez
PROFMAT - SBM
Julho 2013
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 6 - Seção 6.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 2/15
A resolução de vários problemas de aritmética recai na resolução,
em números inteiros, de equações do tipo
aX + bY = c,
com a, b, c ∈ Z.
Tais equações são chamadas equações diofantinas lineares em
homenagem a Diofanto de Alexandria (aprox. 300 d.C.).
Nem sempre estas equações possuem solução.
Exemplo
A equação
4X + 6Y = 3
não possui nenhuma solução x0, y0 em números inteiros pois, caso
contrário, teŕıamos 4x0 + 6y0 par e, portanto, nunca igual a 3.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 3/15
É, então, natural perguntar-se:
1) Em que condições tal equação possui soluções?
2) Caso as tenha, como determiná-las?
As respostas para estas perguntas são relativamente fáceis e serão
dadas nas duas proposições a seguir.
Proposição
Sejam a, b, c ∈ Z. A equação aX + bY = c admite solução em
números inteiros se, e somente se, (a, b) | c.
PROFMAT - SBMAritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 4/15
É imediato verificar que a equação aX + bY = c , com a 6= 0 ou
b 6= 0 e (a, b) | c é equivalente à equação
a1X + b1Y = c1,
onde
a1 =
a
(a, b)
, b1 =
b
(a, b)
e c1 =
c
(a, b)
.
Note que (a1, b1) = 1 e, portanto, podemos nos retringir às
equações do tipo
aX + bY = c , com (a, b) = 1,
que sempre têm soluções.
Mostraremos a seguir como as soluções de uma equação diofantina
como acima podem ser determinadas a partir de uma solução
particular qualquer x0, y0.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 5/15
Proposição
Seja x0, y0 uma solução da equação aX + bY = c, onde (a, b) = 1.
Então, as soluções x , y em Z da equação são
x = x0 + tb, y = y0 − ta; t ∈ Z.
Segue-se da proposição acima que a equação diofantina
aX + bY = c , com (a, b) = 1, admite infinitas soluções em Z.
A seguir, descreveremos um método para encontrar uma solução
particular de uma equação do tipo aX + bY = c , quando
(a, b) = 1.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 6/15
Solução particular de aX + bY = c , quando (a, b) = 1
Se |a|, |b| e |c | são números pequenos, uma solução pode ser
encontrada por inspeção.
Mais geralmente, o método descrito abaixo sempre permitirá achar
uma solução particular da equação.
Usando o algoritmo euclidiano estendido, é posśıvel determinar
m, n ∈ Z tais que
ma + nb = (a, b) = 1.
Multiplicando ambos os membros da igualdade acima por c ,
obtemos
cma + cnb = c .
Logo, x0 = cm e y0 = cn é uma solução particular da equação
aX + bY = c .
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 7/15
Exemplo: Resolvamos a equação 24X + 14Y = 18
A equação tem solução, pois (24, 14) = 2 e 2|18.
Dividindo ambos os membros da equação por 2 = (24, 14),
obtemos a equação equivalente 12X + 7Y = 9.
Vamos, em seguida, achar uma solução particular x0, y0 desta
última equação. Pelo algoritmo euclidiano, temos
12 = 7 · 1 + 5, 7 = 5 · 1 + 2, 5 = 2 · 2 + 1.
Substituindo as equações acima umas nas outras, obtemos
1 = 12 · 3− 7 · 5,
portanto,
9 = 12 · 27 + 7 · (−45).
Logo, x0 = 27 e y0 = −45 é solução particular da equação e,
consequentemente, as soluções são
x = 27 + t7, y = −45− t12; t ∈ Z.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 8/15
Equações Diofantinas sobre N
Algumas vezes é necessário resolver em N ∪ {0} equações
diofantinas da forma aX + bY = c, onde a, b, c ∈ N.
Sejam a, b ∈ N. Definimos o conjunto
S(a, b) = {xa + yb; x , y ∈ N ∪ {0}},
chamado de semigrupo gerado por a e b.
É claro que aX + bY = c , com (a, b) = 1, tem solução em
N ∪ {0} se, e somente se, c ∈ S(a, b).
Portanto, é de fundamental importância caracterizar os elementos
do conjunto S(a, b), ou do conjunto de lacunas de S(a, b):
L(a, b) = N \ S(a, b).
Pode-se provar que
L(a, b) = {ma− nb ∈ N; m, n ∈ N, m < b}.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 9/15
Teorema
A equação aX + bY = c, onde (a, b) = 1, tem solução em
números naturais se, e somente se,
c 6∈ L(a, b) = {ma− nb ∈ N; m, n ∈ N, m < b}.
Note que o conjunto L(a, b) é finito e o seu maior elemento é
maxL(a, b) = (b − 1)a− b.
Portanto, se
c > (b − 1)a− b + 1 = (b − 1)(a− 1),
a equação aX + bY = c admite solução nos naturais.
Se c = (b − 1)(a− 1)− 1, ela não admite solução.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 10/15
A única solução m, n da equação aX + bY = c , com m < b, é
uma solução minimal, no sentido de que se x , y é uma solução,
então x > m.
Com isto, podemos enunciar o resultado a seguir.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 11/15
Proposição
Suponha que a equação aX + bY = c, com (a, b) = 1, tenha
solução e seja x0 = m, y0 = n a solução minimal. As soluções x , y
da equação são dadas pelas fórmulas
x = m + tb, e y = n − ta, t ∈ N ∪ {0}, n − ta > 0.
Note que este tipo de equação tem, no máximo, um número finito
de soluções, correspondentes aos seguintes valores de t:
0, 1, . . . ,
[n
a
]
,
onde
[n
a
]
representa o quociente da divisão euclidiana de n por a,
ou seja a parte inteira de
n
a
.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 12/15
Exemplo
Vamos determinar para quais valores de c ∈ N a equação
11X + 7Y = c tem soluções em N ∪ {0}.
O conjunto de lacunas de S(11, 7) é o conjunto
L(11, 7) = {m11− n7 ∈ N, m, n ∈ N, m < 7}
= {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 17, 19, 20, 23, 24, 26, 27, 30,
31, 34, 37, 38, 41, 45, 48, 52, 59}.
Portanto, a equação 11X + 7Y = c admite solução em N∪ {0} se,
e somente se, c 6∈ L(11, 7).
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 13/15
Exemplo: Resolver a equação 11X + 7Y = 58 em N ∪ {0}
Como, de acordo com o Exemplo anterior, 58 6∈ L(11, 7), a
equação possui soluções.
Para determiná-las, considere o algoritmo euclidiano,
11 = 7 · 1 + 4, 7 = 4 · 1 + 3, 4 = 3 · 1 + 1
Logo,
1 = 4− 3 = 4− (7− 4) = 2 · 4− 7 = 2(11− 7)− 7 = 2 · 11− 3 · 7.
Portanto,
58 = (58 · 2)11− (58 · 3)7 = (4 + 16 · 7)11− 174 · 7 = 4 · 11 + 2 · 7.
Segue dáı que x0 = 4 e y0 = 2 é a solução minimal da equação.
Logo, as soluções são
x = 4 + t7, y = 2− t11,
que só têm sentido para t = 0, e, portanto, a equação só possui a
solução x0 = 4, y0 = 2.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 14/15
Para resolver equações como as acima, não é necessário usar toda
a técnica que desenvolvemos, pois os números envolvidos são
suficientemente pequenos para que seja viável achar as soluções
por inspeção.
No exemplo acima, bastaria testar os valores X = 0, 1, 2, 3, 4, 5 ou
6 para verificar que apenas x0 = 4 é posśıvel.
PROFMAT - SBM Aritmética - Unidade 8 - Resumo - Equações Diofantinas Lineares slide 15/15
MA14 - Aritmética
Unidade 10
Resumo
Expressões Binômias
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 6 - Seção 6.2
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 10 - Resumo - Expressões Binômias slide 2/7
Nesta unidade, mostra-se como calcular o mdc de pares de
números da forma an ± 1, onde a, n ∈ N, mediante o uso do Lema
e do Algoritmo de Euclides.
Enunciaremos a seguir os principais resultados da unidade.
Proposição
Se n,m, a ∈ N, com a > 2, então
(am − 1, an − 1) = ad − 1, onde d = (m, n).
Exemplo
(218 − 1, 215 − 1) = 23 − 1 = 7, pois 3 = (18, 15).
(325 − 1, 320 − 1) = 35 − 1, pois 5 = (25, 20).
PROFMAT - SBM Aritmética - Unidade 10 - Resumo - Expressões Binômias slide 3/7
Proposição
Sejam n,m ∈ N, com n|m e m
n
par. Se a ∈ N, então,
(am + 1, an + 1) =
{
1, se a é par
2, se a é ı́mpar
Exemplo
(218 + 1, 23 + 1) = 1, pois 3 | 18, 183 = 6 e a = 2 é par.
(524 + 1, 56 + 1) = 2, pois 6 | 24, 246 = 4 e a = 5 é ı́mpar.
PROFMAT - SBM Aritmética - Unidade 10 - Resumo - Expressões Binômias slide 4/7
Teorema
Se a, n,m ∈ N, com a > 2, então
(am − 1, an − 1) = a(m,n) − 1,
(am ± 1, an + 1) ∈
{
1, 2, a(m,n) + 1
}
.
PROFMAT - SBM Aritmética - Unidade 10 - Resumo - Expressões Binômias slide 5/7
Corolário 1.
Tem-se que
(am + 1, an + 1) =

a(n,m) + 1, se
[m, n]
(m, n)
é ı́mpar
2, se
[m, n]
(m, n)
é par e a é ı́mpar
1, se
[m, n]
(m, n)
e a são pares
Corolário 2. Se a ∈ N, tem-se que
(am − 1, an +1) =

a(n,m) + 1, se
m
(m, n)
é par e
n
(m, n)
é ı́mpar
2, caso contrário e a é ı́mpar
1, caso contrário e a é par
PROFMAT - SBM Aritmética - Unidade 10 - Resumo - Expressões Binômias slide 6/7
Exemplo (Corolário 1)
1. (220 + 1, 212 + 1) = 24 + 1 = 17,
pois 4 = (20, 12), 60 = [20, 12] e [20,12](20,12) =
60
4 = 15.
2. (216 + 1, 212 + 1) = 1 e (316 + 1, 312 + 1) = 2,
pois 4 = (16, 12), 48 = [16, 12] e [16,12](16,12) =
48
4 = 12.
Exemplo (Corolário 2)
1. (218 − 1, 215 + 1) = 23 + 1 e (318 − 1, 315 + 1) = 33 + 1,
pois, 3 = (18, 15), 183 = 6 é par e
15
3 = 5 é ı́mpar.
2. (218 − 1, 230 + 1) = 1 e (318 − 1, 330 + 1) = 2,
pois, 6 = (18, 30), 186 = 3 é ı́mpar.
PROFMAT - SBM Aritmética - Unidade 10 - Resumo - Expressões Binômias slide 7/7
MA14 - Aritmética
Unidade 11
Resumo
Números de Fibonacci
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 6 - Seção 6.3
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 11 - Resumo - Números de Fibonacci slide 2/7
Números de Fibonacci
Nesta seção, apresentamos algumas propriedades dos números de
Fibonacci (Caṕıtulo 2, Seção 2.3, Exemplo 2.14).
A sequência de Fibonacci é a sequência (un) de números naturais,
definida, por recorrência, pelas relações
un = un−1 + un−2, com u1 = u2 = 1.
Os elementos da sequência de Fibonacci são chamados de números
de Fibonacci.
Exemplo
Os 13 primeiros números de Fibonacci são
1 1 2 3 5 8 13 21 34 55 89 144 233
PROFMAT - SBM Aritmética - Unidade 11 - Resumo - Números de Fibonacci slide 3/7
Propriedades dos números de Fibonacci
Proposição
Para todo par de números naturais n e m, temos que
un+m = unum+1 + un−1um
Lema
Dois termos consecutivos da sequência de Fibonacci são coprimos.
Lema
Se n,m ∈ N são tais que n|m, então, un|um.
Teorema
Seja (un)n a sequência de Fibonacci; então,
(um, un) = u(m,n).
Corolário
Sejam m ≥ n > 2. Na sequência de Fibonacci, temos que un divide
um se, e somente se, n divide m.
PROFMAT - SBM Aritmética - Unidade 11 - Resumo - Números de Fibonacci slide 4/7
Exemplo
O resultado anterior nos permite estabelecer alguns critérios de
divisibilidade para os termos da sequência de Fibonacci.
Quais os termos um da sequência de Fibonacci diviśıveis por 3?
Basta notar que u4 = 3 e que
3|um ⇐⇒ u(4,m) = (u4, um) = (3, um) = 3 = u4,
e, portanto,
3|um ⇐⇒ (4,m) = 4⇐⇒ 4|m.
PROFMAT - SBM Aritmética - Unidade 11 - Resumo - Números de Fibonacci slide 5/7
Exerćıcio
1. Calcule (un, un+4).
Solução
Sabemos do Teorema que
(un, un+4) = u(n,n+4) = u(n,4).
Por outro lado,
(n, 4) =

4, se n = 4k
1, se n = 4k + 1 ou n = 4k + 3
2, se n = 4k + 2.
Logo,
(un, un+4) = u(n,4) =
{
3, se 4 | n
1, se 4 6 | n
PROFMAT - SBM Aritmética - Unidade 11 - Resumo - Números de Fibonacci slide 6/7
Exerćıcio
2. Mostre que 55 divide um se, e somente se, 10 divide m.
Solução
Como u10 = 55, então pelo Corolário do Teorema,
55 | um ⇐⇒ u10 | um ⇐⇒ 10 | m.
PROFMAT - SBM Aritmética - Unidade 11 - Resumo - Números de Fibonacci slide 7/7
MA14 - Aritmética
Unidade 12
Resumo
Teorema Fundamental Da Aritmética
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 7 - Seção 7.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 2/10
Números Primos
Um número natural maior do que 1 que só possui como divisores
positivos 1 e ele próprio é chamado de número primo.
Dados dois números primos p e q e um número inteiro a qualquer,
decorrem da definição acima os seguintes fatos:
I) Se p|q, então p = q.
II) Se p 6 | a, então (p, a) = 1.
Um número maior do que 1 e que não é primo será chamado
composto.
Portanto, se um número natural n > 1 é composto, existirá um
divisor natural n1 de n tal que 1 < n1 < n. Logo, existirá um
número natural n2 tal que
n = n1n2, com 1 < n1 < n e 1 < n2 < n.
Exemplo
2, 3, 5, 7, 11 e 13 são números primos, enquanto que 4, 6, 8, 9, 10
e 12 são compostos.
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 3/10
Do ponto de vista da estrutura multiplicativa dos naturais, os
números primos são os mais simples e ao mesmo tempo são
suficientes para gerar todos os números naturais, logo todos os
números inteiros não nulos, conforme veremos mais adiante no
Teorema Fundamental da Aritmética.
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 4/10
A seguir, estabelecemos um resultado fundamental de Euclides (Os
Elementos, Proposição 30, Livro VII).
Proposição (Lema de Euclides)
Sejam a, b, p ∈ Z, com p primo. Se p|ab, então p|a ou p|b.
Na realidade, a propriedade dos números primos descrita na
proposição acima, os caracteriza totalmente (Veja Problema
7.1.9).
Corolário
Se p, p1, . . . , pn são números primos e, se p|p1 · · · pn, então p = pi
para algum i = 1, . . . , n.
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 5/10
Teorema Fundamental da Aritmética
Teorema
Todo número natural maior do que 1 ou é primo ou se escreve de
modo único (a menos da ordem dos fatores) como um produto de
números primos.
Agrupando no teorema os fatores primos repetidos, se necessário, e
ordenando os primos em ordem crescente, temos o seguinte
enunciado:
Teorema
Dado um número inteiro n 6= 0, 1,−1, existem primos
p1 < · · · < pr e α1, . . . , αr ∈ N, univocamente determinados, tais
que
n = ±pα11 · · · p
αr
r .
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 6/10
Proposição
Seja n = pα11 · · · pαrr um número natural escrito na forma acima.
Se n′ é um divisor positivo de n, então
n′ = pβ11 · · · p
βr
r ,
onde 0 ≤ βi ≤ αi , para i = 1, . . . , r .
Denotando por d(n) o número de divisores positivos do número
natural n, temos que se n = pα11 · · · pαrr , onde p1, . . . , pr são
números primos e α1, . . . , αr ∈ N, então
d(n) = (α1 + 1)(α2 + 1) · · · (αr + 1).
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 7/10
MDC e MMC
A fatoração de números naturais em primos revela toda a estrutura
multiplicativa desses números, permitindo, entre muitas outras
coisas, determinar facilmente o mdc e o mmc de um conjunto
qualquer de números.
Teorema
Sejam a = ±pα11 · · · pαnn e b = ±p
β1
1 · · · p
βn
n . Pondo
γi = min{αi , βi}, δi = max{αi , βi}, i = 1, . . . , n,
tem-se que
(a, b) = pγ11 · · · p
γn
n e [a, b] = p
δ1
1 · · · p
δn
n .
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 8/10
Exemplo
Seja n > 4 um número natural, vamos provar que n é composto se,
e somente se, n|(n − 2)!.
Suponhamos n composto. Provaremos inicialmente que n|(n − 1)!.
De fato, suponha que n = n1n2 com 1 < n1 < n e 1 < n2 < n.
Se n1 6= n2, podemos supor que 1 < n1 < n2, e portanto,
(n − 1)! = 1 · · · n1 · · · n2 · · · (n − 1),
o que mostra que n|(n − 1)!, neste caso.
Suponhamos que n1 = n2 > 2. Logo,
(n − 1)! = 1 · · · n1 · · · 2n1 · · · (n − 1),
o que implica também que n(= n1n1) divide (n − 1)!.
Agora, note que (n, n − 1) = 1 e que n|(n − 2)!(n − 1); portanto,
n|(n − 2)!.
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 9/10
Exemplo - continuação
Reciprocamente, se n | (n − 2)!, n não pode ser primo,pois é
maior do que os fatores primos de (n − 1)!.
A propriedade acima pode ser generalizada como segue:
Se n > 4 é composto e p é o menor número primo que divide n,
então, n|(n − p)!
De fato, temos que
(n − 1, n) = (n − 2, n) = · · · = (n − (p − 1), n) = 1.
Logo, segue-se que
((n − 1)(n − 2) · · · (n − p + 1), n) = 1,
o que, em vista do fato de n|(n − 1)!, acarreta o resultado.
PROFMAT - SBM Aritmética - Unidade 12 - Resumo - Teorema Fundamental da Aritmética slide 10/10
MA14 - Aritmética
Unidade 13
Resumo
Pequeno Teorema de Fermat
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 7 - Seção 7.3
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 13 - Resumo - Pequeno Teorema de Fermat slide 2/6
A demonstração do Teorema de Fermat se baseia no lema a seguir.
Lema
Seja p um número primo. Os números
(
p
i
)
, onde 0 < i < p, são
todos diviśıveis por p.
Teorema (Pequeno Teorema de Fermat)
Dado um número primo p, tem-se que p divide o número ap − a,
para todo a ∈ Z.
PROFMAT - SBM Aritmética - Unidade 13 - Resumo - Pequeno Teorema de Fermat slide 3/6
Exemplo
Dado um número qualquer n ∈ N, tem-se que n9 e n, quando
escritos na base 10, têm o mesmo algarismo da unidade.
A afirmação acima é equivalente a 10|n9 − n.
Como n9 e n têm a mesma paridade, segue-se que n9 − n é par;
i.e, 2|n9 − n.
Por outro lado,
n9 − n = n(n4 − 1)(n4 + 1) = (n5 − n)(n4 + 1).
Logo, pelo Pequeno Teorema de Fermat, temos que 5|n5 − n e,
portanto, 5|n9 − n.
Tem-se, então, que 10|n9 − n.
PROFMAT - SBM Aritmética - Unidade 13 - Resumo - Pequeno Teorema de Fermat slide 4/6
Corolário
Se p é um número primo e se a é um número inteiro não diviśıvel
por p, então p divide ap−1 − 1.
O corolário acima é também chamado de Pequeno Teorema de
Fermat.
PROFMAT - SBM Aritmética - Unidade 13 - Resumo - Pequeno Teorema de Fermat slide 5/6
Exerćıcios Resolvidos
1. Mostre que 5 | a12 − 1, se a ∈ Z e (a, 5) = 1.
Solução
Como 5 | a4 − 1 e a4 − 1 | (a4)3 − 1 = a12 − 1 então, pela
transitividade da divisibilidade, 5 | a12 − 1.
2. Mostre que 7 | a6 − b6, se a e b são inteiros primos com 7.
Solução
Como 7 | a6 − 1 e 7 | b6 − 1 então, por propriedade da
divisibilidade, 7 |
(
(a6 − 1)− (b6 − 1)
)
= a6 − b6.
3. Mostre que 21 | a6 − b6, se a e b são inteiros primos com 21.
Solução
Neste caso, a e b são primos com 3 e 7. Pelo exerćıcio anterior,
7 | a6 − b6. Como 3 | a2 − 1 e 3 | b2 − 1 então, por propriedade da
divisibilidade, 3 |
(
(a2 − 1)− (b2 − 1)
)
= a2 − b2. Além disso,
a2 − b2 divide (a2)3 − (b2)3 = a6 − b6. Portanto, 3 | a6 − b6.
Logo, 21 | a6 − b6.
PROFMAT - SBM Aritmética - Unidade 13 - Resumo - Pequeno Teorema de Fermat slide 6/6
MA14 - Aritmética
Unidade 14
Revisão
Atividade Especial
Abramo Hefez
PROFMAT - SBM
Aviso
Esta unidade constitui-se na tarefa da resolução da Lista dos
Problemas suplementares do Caṕıtulo 7 de 7.S.1 a 7.S.14 do
livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
O material completo a ser revisado encontra-se no
Caṕıtulo 7, Seções 7.1 e 7.3,
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 14 - Revisão - Atividade Especial slide 2/1
MA14 - Aritmética
Unidade 15
Resumo
Primos de Fermat e de Mersenne
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 8 - Seção 8.1
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 15 - Resumo - Primos de Fermat e de Mersenne slide 2/7
Primos de Fermat
Os números de Fermat são os números da forma
Fn = 2
2n + 1.
Fermat achava que esses números eram todos primos.
De fato, F1 = 5, F2 = 17, F3 = 257, F4 = 65 537 são primos.
Em 1732, Euler mostrou que
F5 = 2
25 + 1 = 4 294 967 297 = 641 · 6 700 417,
portanto, composto, desfazendo assim esta crença de Fermat.
Os números de Fermat primos são chamados de primos de Fermat.
Até hoje, não se sabe se existem outros primos de Fermat além dos
quatro primeiros.
No Exemplo 6.18(a), como consequência do Corolário 6.17 do livro
texto, observamos que
(Fn,Fm) = 1, se n 6= m.
PROFMAT - SBM Aritmética - Unidade 15 - Resumo - Primos de Fermat e de Mersenne slide 3/7
Primos de Mersenne
Os números de Mersenne são os números da forma
Mp = 2
p − 1,
onde p é um número primo.
No intervalo 2 ≤ p ≤ 5 000 os números de Mersenne que são
primos, chamados de primos de Mersenne, correspondem aos
seguintes valores de p:
2, 3, 5, 7, 13, 19, 31, 61, 89, 107, 127, 521, 607, 1 279, 2 203,
2 281, 3 217, 4 253 e 4 423.
Até o presente momento, o maior primo de Mersenne conhecido é
M57 885 161, descoberto em janeiro de 2013 e que possui no sistema
decimal 17 425 170 d́ıgitos.
Anteriormente, em agosto de 2008, havia sido descoberto o primo
M43 112 609, que tinha no sistema decimal 12 978 189 d́ıgitos.
PROFMAT - SBM Aritmética - Unidade 15 - Resumo - Primos de Fermat e de Mersenne slide 4/7
Teorema de Dirichlet
Enunciaremos a seguir, sem demonstração, um resultado profundo
devido a Lejeune Dirichlet:
Teorema (Dirichlet)
Em uma PA de números naturais, com primeiro termo e razão
primos entre si, existem infinitos números primos.
A demonstração deste resultado é bem dif́ıcil e pertence à teoria
anaĺıtica dos números.
Nos limitamos no texto a demonstrar alguns casos particulares do
teorema. O primeiro caso particular é o seguinte:
PROFMAT - SBM Aritmética - Unidade 15 - Resumo - Primos de Fermat e de Mersenne slide 5/7
Proposição
Na progressão aritmética 3, 7, 11, 15, . . . , 4n + 3, . . . existem
infinitos números primos.
O que a proposição nos diz é que existem infinitos primos da forma
4n + 3.
A prova de que existem infinitos primos da forma 4n + 1 é um
pouco mais sutil.
Em outras seções provaremos outros casos particulares.
PROFMAT - SBM Aritmética - Unidade 15 - Resumo - Primos de Fermat e de Mersenne slide 6/7
Exerćıcio
Mostre que existem infinitos números primos da forma 6n + 5.
Solução
Note que todo número primo ı́mpar maior do que 3 é da forma
6n + 1 ou 6n + 5.
O conjunto Λ = {6n + 1; n ∈ N} é fechado multiplicativamente.
De fato,
(6n + 1)(6n′ + 1) = 6(6nn′ + n + n′) + 1.
Suponhamos, por absurdo, que haja apenas um número finito de
números primos 5 < p1 < · · · < pk da forma 6n + 5.
Portanto, o número a = 6(p1 · p2 · · · pk) + 5 não é diviśıvel por
nenhum dos números primos 5, p1, . . . , pk e, consequentemente,
sua decomposição em fatores primos só pode conter primos da
forma 6n + 1. Logo, a é da forma 6n + 1, o que é uma
contradição, pois é da forma 6n + 5.
PROFMAT - SBM Aritmética - Unidade 15 - Resumo - Primos de Fermat e de Mersenne slide 7/7
MA14 - Aritmética
Unidade 16
Resumo
Números Perfeitos
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o doḿınio do assunto.
O material completo a ser estudado encontra-se no
Caṕıtulo 8 - Seção 8.2
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM Aritmética - Unidade 16 - Resumo - Números Perfeitos slide 2/6
Números Perfeitos
Os números como 6 e 28, com a propriedade de serem iguais à
metade da soma de seus divisores, tiveram o poder de fascinar os
gregos antigos, que os chamaram de números perfeitos.
Até a Idade