Algebra A introdução a teoria dos números - André Contiero

Prévia do material em texto

“main”
2013/9/18
page 1i
i
i
i
i
i
i
i
Notas de aula de Introduc¸a˜o a` Teoria
dos Nu´meros
por Andre´ Contiero
18 de Setembro de 2013
“main”
2013/9/18
page 7i
i
i
i
i
i
i
i
Cap´ıtulo 1
Princ´ıpios
Princ´ıpio da Casa dos Pombos. Sejam kn+1 pombos e suponha
que existam n casinhas de pombos. Se quisermos alojar todos os
pombos nas casinhas, enta˜o existira´ uma casinha com pelo menos
k + 1 pombos.
Demonstrac¸a˜o. Se em todas casinhas aloja´ssemos no ma´ximo k
pombos, enta˜o ter´ıamos no ma´ximo kn pombos. Que e´ uma con-
tradic¸a˜o.
Exemplo 1.1. Considere o conjunto {1, 2, . . . , 2n}, com n ∈ N e
n ≥ 1. Se escolhermos n+ 1 nu´meros deste conjunto, enta˜o dentre
os escolhidos existira˜o nu´meros consecutivos.
De fato, considere os pares de nu´meros consecutivos {1, 2},
{3, 4}, . . . , {2n − 1, 2n}. Existem n destes pares. Como devemos
escolher n+ 1 nu´meros, pelo menos um par sera´ escolhido.
Princ´ıpio da Boa Ordenac¸a˜o. Seja A ⊆ N. Enta˜o existe n0 ∈ A
tal que n0 < n ∀n ∈ A \ {n0}.
7
“main”
2013/9/18
page 8i
i
i
i
i
i
i
i
8 [CAP. 1: PRINC´IPIOS
Exemplo 1.2. Mostre que toda func¸a˜o f : N → N mono´tona na˜o
crescente e´ constante a partir de um certo nu´mero natural.
Dizer que f : N → N e´ mono´tona na˜o crescente significa que
∀m ≤ n =⇒ f(m) ≥ f(n). Seja A = f(N) a imagem de f .
Logo existe i0 ∈ A menor que todos os outros elementos de A.
Claro que i0 = f(n0). Assim se n ≥ n0 enta˜o f(n) ≥ f(n0) = i0.
Por outro lado, como f e´ mono´tona na˜o crescente, para n ≥ n0,
i0 = f(n0) ≥ f(n). Assim f(n) = i0, ∀n ≥ n0.
Princ´ıpio de Induc¸a˜o Finita. Seja P(n) uma afirmac¸a˜o em N
envolvendo o nu´mero n. Suponha que consigamos verificar:
BI) P(n0) e´ verdadeira para certo n0 ∈ N;
PI) Assumindo P(n) verdadeira, enta˜o P(n + 1) tambe´m e´ ver-
dadeira para todo n ≥ n0.
Enta˜o P(n) e´ verdadeira para todo n ≥ n0.
Exemplo 1.3. Vamos mostrar que 1+ 2+3+ · · ·+ k = 1
2
k(k+1).
Faremos por induc¸a˜o. Note que neste caso P(k) e´ 1 + 2 + 3 +
· · ·+k = 1
2
k(k+1). Em geral, nos primeiros exemplos, e´ instrutivo
dividir a induc¸a˜o em treˆs partes, a saber, BI: Base de Induc¸a˜o, HI:
Hipo´tese de Induc¸a˜o e PI: Passo Indutivo, como a seguir.
BI) Claro que 1 = 1
2
1(1 + 1). Logo P(1) e´ verdadeira;
HI) Suponha que P(n) e´ verdadeira, ou seja, 1+2+3+ · · ·+n =
1
2
n(n+ 1).
PI) Vamos mostrar que P(n + 1) tambe´m e´ verdadeira, ou seja,
1 + 2 + · · · + n = 1
2
(n + 1)(n + 2). De fato, 1 + 2 + 3 +
“main”
2013/9/18
page 9i
i
i
i
i
i
i
i
9
· · ·+ n+ 1 = (1 + 2 + · · ·+ n) + (n+ 1). Mas a Hipo´tese de
Induc¸a˜o (HI) nos diz que 1+2+3+ · · ·+n = 1
2
n(n+1), assim
1+ 2+ 3+ · · ·+n+1 = 1
2
n(n+1)+n+1 = 1
2
(n+1)(n+2).
Logo o Princ´ıpio de Induc¸a˜o Finita nos assegura que 1 + 2 + 3 +
· · ·+ k = 1
2
k(k + 1) ∀ k ∈ N?
Existe uma prova muita mais elegante e incrivelmente simples
de que 1+2+3+ · · ·+ k = 1
2
k(k+1). Esta ideia da prova foi dada
por Gauss quando ele tinha apenas 9 anos de idade. Vamos e ela:
Exemplo 1.4. Denote por s = 1 + 2 + 3 + · · ·+ k, claro que
s = 1 + 2 + · · ·+ (k − 1) + k(1.1)
s = k + (k − 1) + . . .+ 2 + 1(1.2)
somando as equac¸o˜es (1.1) e (1.2) obtemos que
2s = (k + 1) + · · ·+ (k + 1) = k(k + 1)
Uma outra bonita aplicac¸a˜o do PIF e´ o seguinte resultado.
Exemplo 1.5. Seja A um conjunto com n elementos. Mostre que
o conjunto P(A) formado por todos os subconjuntos de A tem exa-
tamente 2n elementos. o conjunto P(A) e´ chamado de conjunto das
partes de A.
Faremos por induc¸a˜o em n.
BI) Claro que se n = 1, A = {x} e enta˜o P(A) = {∅ , A}. Lembre-
se que o vazio e´ um subconjunto de qualquer conjunto.
HI) Suponha que para qualquer conjunto A com k elementos e
1 ≤ k < n, o conjunto das partes de A tenha exatamente 2k
elementos;
“main”
2013/9/18
page 10i
i
i
i
i
i
i
i
10 [CAP. 1: PRINC´IPIOS
PI) Considere A = {x1, x2, . . . , xn} um conjunto com n elementos.
Tomando B = {x1, x2, . . . , xn−1}, a HI diz que ] (P(B)) =
2n−1. Por outro lado, P(A) = P(B) ∪ D, onde D = {C ∪
{xn} | C ∈ P(B)}. Assim
](P(A)) = ](P(B)) + ](D) = 2n−1 + 2n−1 = 2n
Uma variante do PFI e muito u´til em diversas aplicac¸o˜es e´:
Princ´ıpio de Induc¸a˜o Forte. Seja P(n) uma afirmac¸a˜o em N
envolvendo o nu´mero n. Suponha que consigamos verificar que
BI) P(n0) se´ verdadeira;
PI) Se assumirmos que P(k) e´ verdadeira para todo n0 ≤ k ≤ n
e isto implicar que P(n+ 1) tambe´m e´ verdadeira.
Enta˜o P(n) e´ verdadeira para todo n ≥ n0.
Observac¸a˜o 1.6. A abreviac¸a˜o PIF significara´ tanto o Princ´ıpio
de Induc¸a˜o Finita quanto o Princ´ıpio de Induc¸a˜o Forte.
Definic¸a˜o 1.7. A sequencia de Fibonacci (fn) e´ definida recursi-
vamente da seguinte forma:
1. f0 = 0, f1 = 1;
2. Para cada n ≥ 2, fn = fn−1 + fn−2.
Lema 1.8. Os termos da sequencia de Fibonacci satisfazem
fn =
αn − βn
α− β
onde α = 1
2
(1 +
√
5) e β = 1
2
(1−√5).
“main”
2013/9/18
page 11i
i
i
i
i
i
i
i
11
Demonstrac¸a˜o. A prova sera´ feita por induc¸a˜o em n.
BI) Claro que f0 = 0 =
α0−β0
α−β e f1 = 1 =
α−β
α−β ;
HI) Suponha que fk =
αk−βk
α−β , para cada 0 ≤ k < n;
PI) Sabemos que fn = fn−1+fn−2. Usando a HI podemos escrever
fn = fn−1 + fn−2 =
αn−1 − βn−1
α− β +
αn−2 − βn−2
α− β(1.3)
=
(αn−1 + αn−2)− (βn−1 + βn−2)
α− β(1.4)
Note que α e β sa˜o ra´ızes da equac¸a˜o x2− x− 1. Assim α2 =
α+ 1 e β2 = β + 1. Logo podemos concluir que αn = αn−1 +
αn−2 e βn = βn−1 + βn−2. Colocando estas duas informac¸o˜es
na equac¸a˜o (1.3) resulta que fn =
αn−βn
α−β .
Assim o Princ´ıpio de Induc¸a˜o Forte nos assegura o resultado.
Definic¸a˜o 1.9. Uma Progresso Aritme´tica (PA) e´ uma sequeˆncia
de nu´meros reais (an) com n ∈ N∗ tal que o primeiro termo a1 e´
dado e os demais termos da PA sa˜o definidos por
an+1 = an + r
onde r e´ um nu´mero real fixado chamado de raza˜o da PA.
Exemplo 1.10. Numa PA com primeiro termo a1 e raza˜o r vale
que:
a) an = a1 + (n− 1)r;
b) Se Sn = a1 + · · ·+ an. Enta˜o Sn = 12(a1 + an)n.
“main”
2013/9/18
page 12i
i
i
i
i
i
i
i
12 [CAP. 1: PRINC´IPIOS
Fac¸amos o item (a). Claro que a1 = a1+(1− 1)r. Suponha que
ak = a1 + (k − 1)r para 1 ≤ k ≤ n. Usando a definic¸a˜o de PA e o
passo de induc¸a˜o obtemos an+1 = an+r = a1+(n−1)r+r = a1+nr.
Logo a prova segue pelo PIF. Fac¸amos agora o item (b). Temos que
S1 = a1 =
1
2
(a1+a1). Suponha que Sk = a1+ · · ·+ak = 12(a1+ak)k
para 1 ≤ k ≤ n. Usando a definic¸a˜o de Sn, o passo de induc¸a˜o e o
item (a) obtemos
Sn+1 = a1 + . . .+ an + an+1 =
1
2
(a1 + an)n+ an+1
=
1
2
(a1 + an)n+ a1 + n r =
1
2
[(a1 + an)n+ 2a1 + 2nr]
=
1
2
[(n+ 1)a1 + a1 + nan + 2nr)]
=
1
2
[(n+ 1)a1 + a1 + nr + n(an + r)]
=
1
2
[(n+ 1)a1 + an+1 + nan+1]
=
1
2
(a1 + an+1)(n+ 1)
Definic¸a˜o 1.11. Um Progresso Geome´trica (PG) e´ uma sequeˆncia
de nu´meros reais (an) onde o primeiro termo a1 e´ dado e os demais
sa˜o definidos por
an+1 = an · q ∀n ≥ 2
onde q e´ um nu´mero real fixado, chamado de raza˜o da PG e distinto
de 0 e 1.
Exemplo 1.12. Considere um PG com primeiro termo a1 e raza˜o
q. Tem-se que:
a) an = a1 · qn−1;
b) Se Sn = a1 + . . . an. Mostre que Sn = a1
qn−1
q−1 .
“main”
2013/9/18
page 13i
i
i
i
i
i
i
i
13
Farei somente o item (b), o item (a) segue facilmente usando
o PIF. Note que S1 = a1 = a1 · q1−1−1q−1 . Suponha que Sn = q
n−1
q−1 .
Agora
Sn+1 = a1 + · · ·+ am + an+1 = a1 · q
n − 1
q − 1 + an+1
= a1 · q
n − 1
q − 1 + a1 · q
n = a1 · q
n+1 − 1
q − 1
Considere o polinoˆmio de grau n, na indeterminada x e com
coeficientes inteiros dado por (1 +X)n. Escreva este polinoˆmio da
seguinte forma:
(1 +X)n = a0 + a1X + a2X
2 + · · ·+ an−1Xn−1 + anXnDefinic¸a˜o 1.13. Os coeficientes do polinoˆmio acima sa˜o chamados
de nu´meros binomiais e doravante sera˜o denotados por ai =
(
n
i
)
.
Usaremos a convenc¸a˜o que se i > n, enta˜o
(
n
i
)
= 0.
Com a definic¸a˜o acima podemos escrever
(1.5)
(1+X)n =
(
n
0
)
+
(
n
1
)
X+
(
n
2
)
X2+· · ·+
(
n
n− 1
)
Xn−1+
(
n
n
)
Xn
e facilmente vemos que
(
n
0
)
= 1,
(
n
1
)
= 1 e
(
n
n
)
= 1.
Observac¸a˜o 1.14. Por enquanto os nu´meros
(
n
i
)
sa˜o apenas coefi-
cientes de um polinoˆmio. Todos sabemos os nu´meros binomiais sa˜o
definidos em termos de fatorial. Veremos isso nas pro´ximas linhas.
Relac¸a˜o de Stifel. Para cada 0 ≤ i ≤ n vale que(
n
i
)
+
(
n
i+ 1
)
=
(
n+ 1
i+ 1
)
“main”
2013/9/18
page 14i
i
i
i
i
i
i
i
14 [CAP. 1: PRINC´IPIOS
Antes da prova um esclarecimento. O nu´mero
(
n+1
i+1
)
e´ o coefi-
ciente do termo X i+1 do polinoˆmio (1 + X)n+1. Enquanto
(
n
i
)
e(
n
i+1
)
sa˜o, respectivamente, os coeficientes dos termos X i e X i+1 do
polinoˆmio (1 +X)n.
Demonstrac¸a˜o. Usando as definic¸o˜es podemos escrever(
n+ 1
0
)
+ · · ·+
(
n+ 1
n
)
Xn +
(
n+ 1
n+ 1
)
Xn+1 = (1 +X)n+1
mas, por outro lado, sabemos que (1 +X)(1 +X)n. Assim
(1 +X)n+1 =
(1 +X)
[(
n
0
)
+
(
n
1
)
X + · · ·+
(
n
n− 1
)
Xn−1 +
(
n
n
)
Xn
]
=
(
n
0
)
+
[(
n
0
)
+
(
n
1
)]
X+ · · ·+
[(
n
n− 1
)
+
(
n
n
)]
Xn+
(
n
n
)
Xn+1
Basta agora lembrar que dois polinoˆmios sa˜o iguais se, e somente
se, os respectivos coeficientes de mesmo grau sa˜o iguais.
Definic¸a˜o 1.15. Seja n um natural na˜o nulo. O fatorial de n,
denotado por n!, e´ definido por
n! = n(n− 1)(n− 2) . . . 2 · 1
Observac¸a˜o 1.16. Usaremos a convenc¸a˜o que 0! = 1.
Lema 1.17. Para cada 1 ≤ i ≤ n vale que
i!
(
n
i
)
= n(n− 1) · · · (n− i+ 1) = n!
(n− i)!
Demonstrac¸a˜o. A prova sera´ feita por induc¸a˜o. Vamos la´.
“main”
2013/9/18
page 15i
i
i
i
i
i
i
i
15
BI) Se n = 1, enta˜o 1!
(
1
1
)
= 1 · 1 = 1;
HI) Suponha que para cada 1 ≤ k ≤ n valha i!(k
i
)
= k!
(k−i)! ;
PI) Para cada i ≤ n a Relac¸a˜o de Stifel nos diz que
i!
(
n+ 1
i
)
= i(i− 1)!
(
n
i− 1
)
+ i!
(
n
i
)
.
Usando a HI podemos escrever
i(i− 1)!
(
n
i− 1
)
+ i!
(
n
i
)
= i
[
n!
(n− i+ 1)!
]
+
n!
(n− i)!
=
n! i+ (n− i+ 1)n!
(n− i+ 1)! =
n! i− n! i+ (n+ 1)n!
(n− i+ 1)! =
(n+ 1)!
(n− i+ 1)!
As informac¸o˜es das duas equac¸o˜es acima resultam que
i!
(
n+ 1
i
)
=
(n+ 1)!
(n− i+ 1)!
Observac¸a˜o 1.18. Do lema acima segue facilmente a forma do
nu´mero binomial dada atrave´s de fatorial, a saber(
n
i
)
=
n!
i!(n− i)!
Binoˆmio de Newton. Sejam a e b nu´meros reais e n um inteiro
positivo. Tem-se
(a+ b)n = an +
(
n
1
)
an−1 b+ · · ·+
(
n
n− 1
)
abn−1 + bn
“main”
2013/9/18
page 16i
i
i
i
i
i
i
i
16 [CAP. 1: PRINC´IPIOS
Demonstrac¸a˜o. Note que se a = 0 na˜o temos nada a fazer. Assuma
enta˜o que a 6= 0. Sabemos que (1+X)n = (n
0
)
+
(
n
1
)
X+· · ·+(n
n
)
Xn.
Substituindo X por b
a
podemos escrever
(a+ b)n = an
(
1 +
b
a
)n
= an
[(
n
0
)
+
(
n
1
)
b
a
+ · · ·+
(
n
n
)
b
a
n]
= an +
(
n
1
)
an−1 b+ · · ·+
(
n
n− 1
)
abn−1 + bn
“main”
2013/9/18
page 17i
i
i
i
i
i
i
i
[SEC. 1.1: EXERC´ICIOS 17
1.1 Exerc´ıcios
1. Vamos mostrar que todos os alunos da UFAL torcem para o
mesmo time. Claro que esta afirmac¸a˜o e´ verdadeira para o
conjunto com um u´nico aluno. Suponha que qualquer con-
junto de n alunos da UFAL torc¸am para o mesmo time. Con-
sidere um conjunto com n+1 alunos da UFAL. Tire um aluno
deste conjunto. Logo os n que ficaram torcem para o mesmo
time (esta e´ a hipo´tese de induc¸a˜o), assim como aquele que
ficou sozinho (e´ o caso para n=1). Conclu´ımos, por induc¸a˜o,
todos torcem para o mesmo time. Onde esta´ o erro?
2. Considere o conjunto {1, 2, 3, . . . , 2n} com n ≥ 1. Mostre que
se escolhermos n + 1 nu´meros deste conjunto, existira˜o dois
tais que um sera´ mu´ltiplo do outro.
3. Mostre que um conjunto com n inteiros quaisquer possui um
subconjunto na˜o vazio cujo soma dos seus elementos e´ di-
vis´ıvel por n.
4. Considere a sequeˆncia de nu´meros reais (an) onde a1 e´ dado
e os demais termos sa˜o definidos por
an+1 = q · an + r , ∀n ≥ 1
onde q e r sa˜o nu´mero reais fixados com q 6= 0, 1. Fac¸a os
seguintes itens:
(a) Mostre que an = a1 · qn−1 + qn−1−1q−1 r;
(b) Se Sn = a1 + · · · + an, mostre que Sn = qn−1−1(q−1)2 q · r −
qn−1
1−q a1 +
n−1
1−q r.
5. Mostre que:
“main”
2013/9/18
page 18i
i
i
i
i
i
i
i
18 [CAP. 1: PRINC´IPIOS
(a) 12 + 22 + · · ·+ n2 = 1
6
n(n+ 1)(2n+ 1);
(b) 13 + 23 + · · ·+ n3 = (1 + 2 + · · ·+ n)2;
(c) 13 + 23 + · · ·+ n3 = 1
4
n2(n+ 1)2;
(d) 1
1·2 +
1
2·3 + · · ·+ 1n(n+1) = nn+1 .
6. Mostre a Fo´rmula de DeMoivre. Sejam n ∈ N∗ e i ∈ C tal
que i2 = −1. Enta˜o (cos(θ) + i sin(θ))n = cos(nθ) + i sin(nθ))
7. Encontre e verifique a veracidade da expressa˜o geral para:
(a) 2 + 4 + 6 + · · ·+ 2n;
(b) 2 + 5 + 8 + · · ·+ (3n− 1);
(c) 1 + 3 + 5 + · · ·+ (2n+ 1);
(d) 2 + 4 + 8 + · · ·+ 2n;
(e) 1
2
+ 1
4
+ · · ·+ 1
2n
.
8. Sejam A e B dois conjuntos com n e k elementos respecti-
vamente. Mostre que o nu´mero de func¸o˜es f : A → B e´
kn.
9. Mostre que
n∑
k=1
k(k + 1) =
1
3
n(n+ 1)(n+ 2).
10. Assuma como definic¸a˜o que
(
n
i
)
= n!
i!(n−i)! . Use induc¸a˜o para
mostrar que
(
n
i
)
e´ um nu´mero inteiro.
11. Mostre que
sinx+ sin 2x+ . . .+ sinnx =
sin ( (n+1)x
2
) · sin (nx
2
)
sin x
2
.
12. Seja (fn) a sequeˆncia de Fibonacci. Mostre que:
“main”
2013/9/18
page 19i
i
i
i
i
i
i
i
[SEC. 1.1: EXERC´ICIOS 19
(a) f1 + f2 + fn = fn+2 − 1;
(b) fn+1 · fn−1 − f2n = (−1)n;
(c)
(
n
0
)
+
(
n−1
1
)
+
(
n−2
2
)
+
(
n−3
3
)
+ . . . = fn+1. Lembre-se que(
n
i
)
= 0 se i > n.
13. Mostre que para todo natural n ≥ 4 vale que:
(a) 2n < n!;
(b) 2n3 > 3n2 + 3n+ 1.
14. Mostre que n! > 3n, para n ≥ 7.
15. Mostre ou de um contra-exemplo para a seguinte afirmac¸a˜o:
∀ k ∈ N, ∃n0 ∈ N tal que k! > kn , ∀n ≥ n0
16. Mostre que(
n
0
)
+
(
n
1
)
+ · · ·+
(
n
n− 1
)
+
(
n
n
)
= 2n.
17. Sejam n e i inteiros positivos. Mostre que(
n
i
)
+
(
n+ 1
n
)
+ · · ·+
(
n+ i
n
)
=
(
n+ i+ 1
n+ 1
)
18. Sejam m,n, k inteiros positivos, mostre que:
k∑
i=0
(
m
i
)(
n
k − i
)
=
(
n+m
k
)
.
“main”
2013/9/18
page 20i
i
i
i
i
i
i
i
20 [CAP. 1: PRINC´IPIOS
19. Seja n um inteiro positivo, mostre que
n∑
i=0
(
n
i
)2
=
(
2n
n
)
.
20. Seja α um nu´mero irracional. Mostre que existem infinitos
racionais p
q
tais que ∣∣∣∣α− pq
∣∣∣∣ < 1q2
21. Encontre o nu´mero ma´ximo de regio˜es em que n retas dividem
um plano.
22. Mostre que toda sequencia com n2 + 1 nu´meros reais, possui
um subsequeˆncia crescente com n+ 1 termos ou uma decres-
cente com n+ 1 termos.
“main”
2013/9/18
page 21i
i
i
i
i
i
i
i
Cap´ıtulo 2
Divisa˜o em Z
Definic¸a˜o 2.1. Sejam a e b nu´meros inteiros, com a 6= 0. Dizemos
que a divide b, em s´ımbolos a|b, se existe q ∈ Z tal que
b = aq
Observac¸a˜o 2.2. Dizer que a divide b e´ o mesmo que dizer que
b e´ divis´ıvel por a ou que b e´ mu´ltiplo de a, ou ainda que a e´ um
divisor de b.
Exemplo 2.3.• 2|6, pois 6 = 2 · 3;
• −2|6, pois 6 = (−2) · (−3);
• 7| − 14 pois −14 = 7 · (−2);
• 1 divide qualquer nu´mero inteiro;
• 0 e´ divis´ıvel por qualquer nu´mero;
21
“main”
2013/9/18
page 22i
i
i
i
i
i
i
i
22 [CAP. 2: DIVISA˜O EM Z
Definic¸a˜o 2.4. Dizemos que um nu´mero e´ par se ele e´ divis´ıvel por
2.
Note que todo nu´mero par e´ da forma 2n com n ∈ Z.
Lema 2.5. Sejam a e b inteiros. As seguintes afirmac¸o˜es sa˜o equi-
valentes:
a) a|b;
b) −a|b;
c) a| − b;
d) −a| − b;
Demonstrac¸a˜o. Farei somente que (a) implica (b), as demais ficam
como exerc´ıcios. Se a|b, enta˜o b = aq, para algum q ∈ Z. Assim
b = (−a)(−q), logo −a|b.
Lema 2.6. Sejam a, b e c nu´meros inteiros tais que a 6= 0 e b 6= 0.
Se a|b e b|c, enta˜o a|c.
Demonstrac¸a˜o. Usando a definic¸a˜o, existem inteiros q e s tais que
b = a · q e c = b · s. Assim c = a · (q · s).
Segue diretamente da definic¸a˜o de divisa˜o o seguinte resultado
de limitac¸a˜o.
Lema 2.7. Sejam a, b ∈ Z com a 6= 0. a | b enta˜o b = 0 ou |a| ≤ |b|.
Demonstrac¸a˜o. De fato, como a | b, enta˜o b = aq para algum q ∈ Z.
Supondo b 6= 0, temos q| ≥ 1 e enta˜o |b| = |aq| = |a||q| ≥ |a|
Proposic¸a˜o 2.8. Se a|(b+ c) e a|b, enta˜o a|c.
“main”
2013/9/18
page 23i
i
i
i
i
i
i
i
23
Demonstrac¸a˜o. Do fato de a|(b+ c), segue que existe q ∈ Z tal que
b + c = a · q. Mas a|b, enta˜o existe r ∈ Z tal que b = a · r. Assim
a · q = b+ c = a · r + c, e enta˜o c = a · (q − r).
Observac¸a˜o 2.9. Na˜o e´ verdade que se a|(b + c) enta˜o a|b ou
a|c. Fac¸a voceˆ mesmo uma infinidade de contra-exemplos.
Exemplo 2.10. O nu´mero 2 na˜o divide nenhum nu´mero da forma
2n+ 1, com n ∈ Z.
De fato, se 2|2n + 1 como 2|2n enta˜o 2|1, o que e´ uma con-
tradic¸a˜o.
Definic¸a˜o 2.11. Um nu´mero que na˜o e´ divis´ıvel por 2 e´ dito ı´mpar.
Note que todo nu´mero ı´mpar e´ da forma 2n + 1 para algum
n ∈ Z.
Proposic¸a˜o 2.12. Sejam a, b, c ∈ Z com a 6= 0. Se a|b e a|c, enta˜o
para quaisquer x, y ∈ Z a|(bx+ cy).
Demonstrac¸a˜o. Da hipo´tese temos b = qa e c = ua para certos
q, u ∈ Z. Assim para quaisquer x, y ∈ Z, bx + cy = aqx + auy =
a(qx+ uy).
Exemplo 2.13. Seja a ∈ Z?. Vamos mostrar que a−1|an−1 para
todo n ∈ N.
De fato, pois
an − 1 = (a− 1)(an−1 + an−2 + . . .+ a+ 1)
O exemplo acima possui a seguinte simples generalizac¸a˜o.
“main”
2013/9/18
page 24i
i
i
i
i
i
i
i
24 [CAP. 2: DIVISA˜O EM Z
Exemplo 2.14. Sejam a, b ∈ Z. Enta˜o a − b divide an − bn, para
qualquer n ∈ N.
Basta notar que
an − bn = (a− b)(an−1 + ban−2 + b2an−3 + . . . bn−2a+ bn−1)
Use induc¸a˜o para tambe´m mostrar os dois exemplos acima.
Exemplo 2.15. Vale que 2|(a2 − a) ∀ a ∈ Z.
De fato, pois a2 − a = a(a − 1), e a − 1 e a sa˜o nu´mero conse-
cutivos, logo um deles e´ par.
Exemplo 2.16. Vale que 3|(a3 − a) ∀ a ∈ Z.
Analogamente ao exemplo anterior. a3 − a = a(a− 1)(a+ 1), e
a − 1, a, a + 1 sa˜o nu´mero consecutivos, logo um deles e´ mu´ltiplo
de treˆs..
Divisa˜o Euclidiana. Sejam a e b nu´meros inteiros tais que a 6= 0.
Existem inteiros q e r, unicamente determinados, tais que
b = a · q + r onde 0 ≤ r < |a|
O inteiro r e´ chamado resto da divisa˜o de b por a, enquanto que
q e´ chamado o quociente da divisa˜o de b por a.
Demonstrac¸a˜o. Separamos a prova da existeˆncia em dois casos. Pri-
meiramente suponhamos a > 0. Considere um inteiro q tal que
b − aq ≥ 0 mas b − a(q + 1) < 0. Definindo r = b − aq temos que
b = aq + r com 0 ≤ r < |a| = a.
Por outro lado, se a < 0. Enta˜o considere um inteiro tal que
b − aq ≥ 0 mas b − a(q − 1) < 0. Definindo r = b − aq temos que
b = aq + r com ≤ r < |a| = −a
“main”
2013/9/18
page 25i
i
i
i
i
i
i
i
25
Quanto a unicidade. Suponha que b = aq−r e b = aq1−r1 com
0 ≤ r < |a| e 0 ≤ r1 < |a|. Temos que r − r1 = a(q − q1), assim
a | (r−r1) donde conclu´ımos que r = r1. Assim b = aq+r = aq1+r,
implicando em q = q1.
Observac¸a˜o 2.17. O resto de uma divisa˜o e´ um inteiro na˜o nega-
tivo, ou seja, nunca um nu´mero negativo.
Exemplo 2.18.
• O resto da divisa˜o de 15 por 31 e´ 15, pois 15 = 31 · 0 + 15;
• O resto da divisa˜o de −15 por 31 e´ 16, pois −15 = 31 · (−1)+
16.
Exemplo 2.19. Vale que 5|(a5 − a) ∀ a ∈ Z.
Note que a5 − a = a(a2 − 1)(a2 + 1). Seja r o resto da divisa˜o
de a por 5, ou seja, a = 5q + r. Lembre-se que r ∈ {0, 1, 2, 3, 4}.
Analisaremos todos os casos poss´ıveis, isto e´, todos os poss´ıveis
restos.
i) Se r = 0, 5|a e enta˜o 5|(a5 − a);
ii) Se r = 1, 5|a2−1, pois a2−1 = (5q+1)2−1 e enta˜o 5|(a5−a);
iii) Se r = 2, 5|a2 + 1, pois a+1 = (5q + 2)+1 e enta˜o 5|(a5 − a);
iv) Se r = 3, 5|a2+1, pois a2+1 = (5q+3)2+1 e enta˜o 5|(a5−a);
v) Finalmente, se r = 4, 5|a2 − 1, pois a2 − 1 = (5q + 4) − 1 e
enta˜o 5|(a5 − a).
Portanto conclu´ımos que 5|(a5 − a) ∀ a ∈ Z.
“main”
2013/9/18
page 26i
i
i
i
i
i
i
i
26 [CAP. 2: DIVISA˜O EM Z
Exemplo 2.20. Vamos mostrar que existem infinitos nu´meros na-
turais n tais que 3 e 5 dividem, ao mesmo tempo, 11n2 + 6.
Primeiramente lembramos que um nu´mero nu´mero e´ divis´ıvel
por 3 e por 5 se, e somente se, ele e´ divis´ıvel por 15. Seja n um
inteiro da forma n = 15q + r, com q ∈ N e 0 ≤ r < 15. Enta˜o
11n2 + 6 = 11(15q + r)2 + 6 = 15q(11 · 15 · q + 2 · r) + r2 + 6
= 15qk + 11(r2 + 6)
onde k = 11 · 15 · q+2 · r. Se tomarmos r = 3, enta˜o para qualquer
q ∈ N, vale que
11n2 + 6 = 15qk + 9 + 6 = 15(qk + 1)
Conclu´ımos que para qualquer inteiro positivo da forma 15q + 3
com q ∈ N temos 15|11n2 + 6.
Definic¸a˜o 2.21. Um inteiro na˜o negativo b e´ dito um quadrado
perfeito se existe k ∈ Z tal que b = k2.
Exemplo 2.22. Vamos mostrar que se b e´ um quadrado perfeito
enta˜o b na˜o deixa resto 2 nem 5 na divisa˜o por 6.
De fato, se b e´ um quadrado perfeito enta˜o b = a2, para algum
a ∈ Z. Seja r o resto da divisa˜o de a por 6. Assim b = a2 =
(6q + r)2 = 36q2 + 12qr + r2 = 6(6q2 + 2qr) + r2 = 6q′ + r2. Note
que r ∈ {0, 1, 2, 3, 4, 5} e r2 ∈ {0, 1, 4, 9, 16, 25}. Mas 9 = 6 + 3,
16 = 12+4 e 25 = 24+1, donde b = 6q′′+ r′, onde r′ ∈ {0, 1, 3, 4}.
Exemplo 2.23. Considere n ∈ N\{0}. SejaA := {a1, a2, . . . , an} ⊂
N. Mostre que existem um subcobunto de A tal que a soma dos
seus elementos e´ divis´ıvel por n.
“main”
2013/9/18
page 27i
i
i
i
i
i
i
i
27
Exemplo 2.24. Seja I um inteiro positivo ı´mpar. Mostre que na˜o
existe uma func¸a˜o f : N→ N tal que f(f(n)) = n+ I, ∀n ∈ N.
Definic¸a˜o 2.25. Sejam a e b inteiros na˜o ambos nulos. O ma´ximo
divisor comum de a e b e´ o maior dentre todos os divisores comuns
de a e de b. Notac¸a˜o: mdc(a, b).
Observac¸a˜o 2.26. O mdc(a, b) sempre existe, pois:
(a) 1|a ∀ a ∈ Z \ {0};
(b) Se m|a enta˜o m ≤ |a|.
Lema 2.27. Sejam a b inteiros na˜o ambos nulos, enta˜o:
1. mdc(a, b) = mdc(b, a);
2. mdc(1, a) = 1;
3. mdc(a, b) = mdc(−a, b);
4. Se a|b enta˜o mdc(a, b) = |a|;
Demonstrac¸a˜o. As propriedades (1) e (2) seguem diretamente da
definic¸a˜o de mdc. A propriedade (4) segue da (3), lembrando que
o mdc e´ um inteiro positivo. Assim mostraremos a (3). Sejam
A o conjunto de todos os divisores comuns de a e b ; e B o con-
junto de todos os divisores comuns de −a e b. Sabemos que se
d|a se, e somente se, d|(−a). Assim A = B, e portanto o maior
inteiro positivo de A e´ igual ao maior inteiro positivo de B, ou seja,
mdc(a, b) = mdc(−a, b).
Definic¸a˜o 2.28. Dois inteiros sera˜o ditos primos entre si, se o mdc
entre eles for igual a 1.
“main”
2013/9/18
page 28i
i
i
i
i
i
i
i
28 [CAP. 2: DIVISA˜O EM Z
2.1 Teorema de Bachet-Be´zout
Teorema de Bachet–Be´zout. Sejam a e b inteiros na˜o nulos.
Enta˜o existem inteiros x e y tais que mdc(a, b) = ax+ by.
Demonstrac¸a˜o. Considere Ia,b ⊂ Z o conjunto
Ia,b := {m ∈ Z ; m = ax+ by com x, y ∈ Z}.
Seja d0 o o menor inteiro positivo em Ia,b (Verifique d0 que sempre
existe). Claramented0 = ax0 + by0. Vamos mostrar que d0 divide
qualquer elemento de I. Sejam ax + by um elemento qualquer de
Ia,b e r o resto de sua divisa˜o por d0, enta˜o
ax+ by = d0q + r = a(x0q) + b(y0q) + r
Donde conclu´ımos que r = a(x− x0q) + b(y − y0q). Assim r ∈ Ia,b,
mas 0 ≤ r < d0 e d0 e´ o menor inteiro positivo em Ia,b, logo r = 0.
Note agora que a, b ∈ Ia,b. Assim d0|a e d0|b, implicando
d0 ≤ mdc(a, b), pois por definic¸a˜o mdc(a, b) e´ o maior dos divi-
sores comuns de a e b. Por outro lado, como d0 = ax0 + by0, pela
Proposic¸a˜o (2.12), mdc(a, b)|d0, implicando mdc(a, b) ≤ d0.
Suplemento 1. Pela prova do teorema de Bachet-Be´zout, mdc(a, b)
e´ o menor inteiro positivo do conjunto Ia,b = {ax+ by ; x, y ∈ Z}
Corola´rio 2.29. Sejam a, b, d ∈ Z, com d > 0 e tais que d|a e d|b.
Enta˜o d = mdc(a, b) se, e somente se, para qualquer c ∈ Z tal que
c|a e c|b tem-se que c|d.
Demonstrac¸a˜o. Suponha d = mdc(a, b) e seja c ∈ Z tal que c|a e
c|b. Por Bachet–Be´zout, d = ax + by e pela Proposic¸a˜o (2.12) c|d.
Reciprocamente, ja´ sabemos que d e´ divisor comum de a e b. Agora,
para todo c ∈ Z tal que c|a e c|b temos que c|d enta˜o |c| ≤ d. Logo
d e´ o maior dos divisores comuns de a e b.
“main”
2013/9/18
page 29i
i
i
i
i
i
i
i
[SEC. 2.1: TEOREMA DE BACHET-BE´ZOUT 29
Corola´rio 2.30. Sejam a, b, c ∈ Z tais que a|bc e mdc(a, b) = 1,
enta˜o a|c.
Demonstrac¸a˜o. Pelo TBB temos que 1 = ax + by, multiplicando
por c esta igualdade, conclu´ımos que c = acx + bcy. Mas a|acx e
a|bcy, logo a|c.
Corola´rio 2.31. Sejam a, b ∈ Z na˜o ambos nulos. Enta˜o
mdc(na, nb) = nmdc(a, b) , ∀n ∈ N∗
Demonstrac¸a˜o. Basta notar que
Ina.nb = {nax+ nby ; x, y ∈ Z} = n{ax+ by ; x, y ∈ Z} = n Ia,b
e como n e´ um natural na˜o nulo, portanto maior que zero, o Suple-
mento 1 nos assegura o resultado.
Corola´rio 2.32. Sejam a, b ∈ Z na˜o ambos nulos. Enta˜o(
a
mdc(a, b)
,
b
mdc(a, b)
)
= 1
Demonstrac¸a˜o. Pelo corola´rio anterior temos
mdc(a, b)
(
a
mdc(a, b)
,
b
mdc(a, b)
)
=
(
mdc(a, b)
a
mdc(a, b)
, mdc(a, b)
b
mdc(a, b)
)
= mdc(a, b)
Corola´rio 2.33. Sejam a, b, c ∈ Z com a, b na˜o ambos nulos. A
equac¸a˜o aX + bY = c possui soluc¸a˜o inteira se, e somente se,
mdc(a, b)|c.
“main”
2013/9/18
page 30i
i
i
i
i
i
i
i
30 [CAP. 2: DIVISA˜O EM Z
Demonstrac¸a˜o. Dizer que x0, y0 ∈ Z e´ soluc¸a˜o de aX + bY = c,
significa que ax0 + by0 = c. Sabemos que mdc(a, b)|a e mdc(a, b)|b.
Logo pela Proposic¸a˜o (2.12) mdc(a, b)|ax0 + by0 = c.
Reciprocamente, se mdc(a, b)|c, enta˜o c = mdc(a, b) q para al-
gum q ∈ Z. Mas sabemos que mdc(a, b) = ax + by, assim c =
mdc(a, b) q = a(xq) + b(yq), ou seja, (x0, yo) e´ uma soluc¸a˜o inteira
da equac¸a˜o aX + bY = c.
Uma ferramenta muito u´til para o ca´lculo de mdc e´ o seguinte
lema.
Lema de Euclides (LE). Sejam a, b, q ∈ Z, enta˜o mdc(a, b) =
mdc(a, b+ aq).
Demonstrac¸a˜o. Temos que mdc(a, b)|a e mdc(a, b)|b, logo mdc(a, b)|a
e
mdc(a, b)|b+ aq, logo mdc(a, b)|mdc(a, b+ aq).
Por outro lado, mdc(a, b + aq)|a e mdc(a, b + aq)|b + aq, pela
Proposic¸a˜o (2.8) mdc(a, b+aq)|a e mdc(a, b+aq)|b, logo mdc(a, b+
aq)|mdc(a, b).
Exemplo 2.34. Vamos calcular o mdc entre os nu´meros 1201 e
4521.
A ideia ba´sica e´ aplicar diversas vezes o Lema de Euclides, ate´
conseguirmos nu´meros pequenos (em mo´dulo), onde nos sentimos
seguros.
mdc(1201, 4521) = mdc(1201, 4521− 4 · 1201) = mdc(1201,−283)
= mdc(283, 1201− 4 · 283) = mdc(283, 69) = mdc(283− 4 · 69, 69)
= mdc(7, 69) = 1
“main”
2013/9/18
page 31i
i
i
i
i
i
i
i
[SEC. 2.2: ALGORITMO DE EUCLIDES 31
Exemplo 2.35. Seja n ∈ Z. Calcule o mdc entre n2−1 e n2+n+1.
Novamente aplicaremos o LE diversas vezes.
mdc(n2 − 1, n2 + n+ 1) = mdc(n2 − 1, n2 + n+ 1− (n2 − 1))
= mdc(n2 − 1, n+ 2) = mdc(n2 − 1− n(n+ 2), n+ 2)
mdc(3, n+ 2) =
{
1 se 3 - n+ 2
3 se 3|n+ 2
Exemplo 2.36. Encontre todos os inteiros positivos n tais que
2n2 + 1 |n3 + 9n− 17 .
Usando as Proposic¸o˜es (2.12) e (2.8) e o Corola´rio (2.30) vemos
que
2n2 + 1 |n3 + 9n+ 1⇐⇒ 2n2 + 1 | 2(n3 + 9n+ 1)− n(2n2 + 1)
Assim o conjunto dos inteiros positivos tais que 2n2 + 1 |n3 +
9n − 17 e´ igual ao conjunto dos inteiros positivos tais que 2n2 +
1 | 17n− 34.
Sabemos que se 2n2 + 1 | 17n − 34, enta˜o 17n − 34 = 0 ou
|2n2 + 1| ≤ |17n − 34|. Explorando essas condic¸o˜es, encontramos
que 0 ≤ n ≤ 5, visto que para n > 5 temos 2n2 + 1 > 17n − 34,
e 17n − 34 = 0 somente para n = 2. Finalmente, atribuindo os
valores 1, 2, 3, 4, 5 encontramos que as soluc¸o˜es sa˜o n = 2 e n = 5.
2.2 Algoritmo de Euclides
Como pudermos notar, o Teorema de Bachet–Be´zout e´ de ex-
trema importaˆncia em teoria dos nu´meros. Contudo, a prova que
“main”
2013/9/18
page 32i
i
i
i
i
i
i
i
32 [CAP. 2: DIVISA˜O EM Z
exibimos acima na˜o e´ expl´ıcita, pois na˜o constro´i de forma al-
gor´ıtmica os inteiros x, y tais que mdc(a, b) = ax + by. Isso sera´
resolvido com o Algoritmo de Euclides.
Antes do enunciarmos o Algoritmo de Euclides faremos um
exemplo muito simples, e notaremos que o caso general sera´ mera
formalidade.
Exemplo 2.37. Dados os inteiros 66 e 385, queremos encontrar, de
maneira algor´ıtmica, inteiros x, y, bem como o mdc(66, 385), tais
que mdc(66, 385) = 66x+ 385y.
Vamos ao trabalho! Usando divisa˜o Euclidiana, podemos escre-
ver 385 = 66 · 5 + 55. Usando o Lema de Euclides temos
mdc(385, 66) = mdc(66, 55)
Podemos escrever ainda
(2.1) 55 = 385− 66 · 5
Novamente, divisa˜o Euclidiana, 66 = 55 + 11, donde
mdc(385, 66) = mdc(66, 55) = mdc(55, 11)
11 = 66− 55
E finalmente veˆ-se que 55 = 11 · 5 e mdc(385, 66) = mdc(55, 11) =
11. Temos que 11 = 66− 55, usando a equac¸a˜o (2.1), escrevemos
11 = 66− (385− 66 · 5) = 66 · 6 + 385(−1)
Algor´ıtmo de Euclides. Sejam a, b ∈ Z na˜o ambos nulos. Con-
sidere o resto da divisa˜o de b por a, b = aq0 + r0 com 0 ≤ r0 < |a|.
Pelo LE temos mdc(a, b) = mdc(r0, a). Temos dois casos a ana-
lisar. Primeiro se r0 = 0, enta˜o a|b e assim mdc(a, b) = a e
“main”
2013/9/18
page 33i
i
i
i
i
i
i
i
[SEC. 2.2: ALGORITMO DE EUCLIDES 33
a = a + b · 0. Segundo, se r0 6= 0. Assim aplicamos divisa˜o Eucli-
diana e LE novamente:
a = r0q1 + r1 com 0 ≤ r1 < r0
mdc(a, b) = mdc(a, r0) = mdc(r1, r0)
Novamente temos dois casos. Se r1 = 0, enta˜o mdc(a, b) = r0 e
r0 = a(−q0) + b
Caso contra´rio, r1 6= 0, e enta˜o aplicamos divisa˜o Euclidiana e LE.
r0 = q2r1 + r2 com 0 ≤ r2 < r1
mdc(a, b) = mdc(a, r0) = mdc(r1, r0) = mdc(r2, r1)
Se r2 = 0, enta˜o mdc(a, b) = r1, e assim
r1 = a− r0q1 = a− (a(−q0) + b)q1 = a(1 + q0q1) + b(−q1)
Caso contra´rio, r2 6= 0 e aplicamos divisa˜o Euclidiana e LE nova-
mente.
Afirmamos que existe um k ∈ N tal que rk+1 = 0. De fato, em
cada passo tal que ri 6= 0 obtemos um ri+1 tal que ri+1 < ri < · · · <
r1 < r0 < |a|. Logo, em algum momento rk+1 = 0.
Portanto, rk−1 = rkqk+1 + rk+1 = rkqk+1 e enta˜o
mdc(a, b) = mdc(a, r0) = mdc(r0, r1) = · · · = mdc(rk−1, rk) = rk
Mas rk−2 = rk−1qk + rk, donde
rk = rk−2 − rk−1qk
e substituindo os restos anteriores encontramos explicitamente x e
y tais que rk = mdc(a, b) = ax+ by.
“main”
2013/9/18
page 34i
i
i
i
i
i
i
i
34 [CAP. 2: DIVISA˜O EM Z
2.3 Bases
O inteiro 127 pode ser escrito da forma 127 = 102 + 2 · 10 + 7.
Esta a´ a representac¸a˜o usual de um natural, que e´ na base 10 e
com algarismos entre 0 e 9. Por outro lado, o nu´mero 127 tambe´m
pode ser escrito da forma 127 = 34 + 33 + 2 · 32 + 1. Diremos
que 1121 a representac¸a˜o de 127 na base 3. Note que recuperamos
integralmente 127 a partir de 1121 sabendo que trata-se de base 3.
Teorema 2.38. Sejam n e d inteiros na˜o negativos e d > 1. Enta˜o
existem inteiros na˜o negativos rk, rk−1, . . . , r1, r0, unicamente de-
terminados satisfazendo seguintes propriedades
1. 0 ≤ ri ≤ d− 1;2. n = rkd
k + rk−1dk−1 + · · ·+ r1d+ r0.
Demonstrac¸a˜o. Seja r0 o resto da divisa˜o de n por d, enta˜o n =
dq1 + r0, e 0 ≤ r0 ≤ d − 1. Usando novamente divisa˜o Euclidiana,
q1 = dq2+ r1, com 0 ≤ r1 ≤ d− 1. Afirmamos que existe um k ∈ N
tal que qk+1 = 0. De fato, note que em cada passo acrescentamos
um elemento numa sequeˆncia decrescente de naturais, a saber q1 >
q2 > · · · > qi. Logo para algum k devemos ter qk+1 = 0. Assim
n = dq1 + r0, q1 = dq2 + r1 , . . . , qk−1 = dqk + rk−1 e qk = d · 0 + rk,
com 0 ≤ ri ≤ d− 1, ∀ i. Substituindo q1 = dq2 + r1 em n obtemos
n = (dq1 + r1)d + r0 = q1d
2 + r1d + r0.Agora substitu´ımos q2 na
fo´rmula anterior e assim sucessivamente, ate´ qk. Mostramos assim
os itens (1) e (2).
Quanto a unicidade. Suponha que
n = rkd
k + · · ·+ r1d+ r0 = sldl + · · ·+ s1d+ s0
com 0 ≤ si, ri ≤ d − 1. Seja i o menor ı´ndice para o qual ri 6= si.
Assim ri + ri+1d
i+1 + · · · + rkdk = si + si+1di+1 + . . . sldl e enta˜o
“main”
2013/9/18
page 35i
i
i
i
i
i
i
i
[SEC. 2.4: ALGUNS CRITE´RIOS DE DIVISIBILIDADE 35
d|(ri − si) que e´ uma contradic¸a˜o, pois neste caso d ≤ |ri − si|
contrariando o item (1).
Definic¸a˜o 2.39. Sejam n e d inteiros na˜o negativos com d > 1.
Escrevendo n = rkd
k + rk−1dk−1 + · · ·+ r1d+ r0, como no teorema
acima, associamos a` n a sequeˆncia de naturais rkrk−1 . . . r1r0. Esta
sequeˆncia e´ chamada de representac¸a˜o de n na base d.
Observac¸a˜o 2.40. Note que a prova do Teorema acima indica
como obter cada ri usando divisa˜o Euclidiana.
Exceto menc¸a˜o contra´ria expl´ıcita, todos os nu´meros tomados
sera˜o escritos na base usual 10.
2.4 Alguns Crite´rios de Divisibilidade
Todos sabemos que um nu´mero e´ divis´ıvel por 2 se, e somente
se, ele e´ par. Passemos agora a crite´rios de divisibilidade um pouco
menos triviais que esse.
• Divisa˜o por 3 ou por 9
Seja n um inteiro maior que 1. Considere a representac¸a˜o de n
na base 10. Assim
n = rk10
k + . . . r110 + r0
enta˜o
n− (rk + rk−1 + · · ·+ r1 + r0) =
rk(10
k − 1) + rk−1(10k−1 − 1) + · · ·+ r1(10− 1)
Lembre-se que 9|10k − 1 ∀ k ∈ N. Provamos assim o seguinte
crite´rio:
“main”
2013/9/18
page 36i
i
i
i
i
i
i
i
36 [CAP. 2: DIVISA˜O EM Z
Lema 2.41. 3|n ou 9|n se, e somente se, 3|(rk + rk−1+ . . . r1+ r0)
ou 9|(rk + rk−1 + . . . r1 + r0), respectivamente.
• Divisa˜o por 5 ou por 10
Seja n um inteiro maior que 1. Considere a representac¸a˜o de n
na base 10. Assim
n = rk10
k + . . . r110 + r0 = 10(rk10
k−1 + · · ·+ r1) + r0
Logo vemos diretamente o seguinte crite´rio
Lema 2.42. Seja n um inteiro. Enta˜o 5|n ou 10|n se, e somente
se, 5|r0 ou 10|r0, respectivamente.
2.5 Teorema Fundamental da Aritme´tica
Definic¸a˜o 2.43. Seja p um inteiro maior que um. Dizemos que p
e´ primo se seus divisores positivos sa˜o somente 1 e p.
Facilmente listamos os primeiros nu´meros primos: 2,3,5,7,11,13,17, . . .
Pore´m, a tarefa pode ser tornar demasiado a´rdua, e em certos
momentos impratica´vel, se nos arriscarmos a continuar com tal
lista. Por exemplo, o nu´mero 2243112609 − 1 e´ primo, ele possui
12978189 d´ıgitos! Para informac¸o˜es sobre recordes de primos visite
http://primes.utm.edu.
Lema 2.44. Seja p um inteiro positivo. Enta˜o p e´ primo se, e
somente se, ∀ a ∈ Z tem-se mdc(a, p) =
{
1 ou
p
Demonstrac¸a˜o. O lema segue diretamente da seguinte observac¸a˜o.
Se d e´ um divisor de p, enta˜o mdc(d, p) = d.
“main”
2013/9/18
page 37i
i
i
i
i
i
i
i
[SEC. 2.5: TEOREMA FUNDAMENTAL DA ARITME´TICA 37
Lema 2.45. Sejam a, b ∈ Z e p um primo. Se p|ab enta˜o p|a ou
p|b.
Demonstrac¸a˜o. A prova segue do Corola´rio (2.30).
Nota-se logo a importaˆncia dos nu´meros primos com o seguinte
teorema.
Teorema Fundamental da Aritme´tica (TFA). Seja n um in-
teiro maior que 1. Existem primos p1, . . . , pk e inteiros positivos
α1, . . . , αk, unicamente determinados, tais que
n = pα11 . . . p
αk
k
Demonstrac¸a˜o. Faremos a prova por induc¸a˜o em n. O Caso n = 2
e´ completamente trivial. Assuma que todo inteiro positivo m com
2 ≤ m ≤ n possa ser escrito como produto de poteˆncias de primos.
Considere m = n + 1. Temos duas opc¸o˜es. Ou m + 1 e´ primo, e
assim na˜o ha´ nada a fazer, ou m+1 e´ composto. Neste u´ltimo caso,
existem inteiros a e b, maiores que 1 tais que m + 1 = a · b. Logo
a < n e b < n. Aplicando enta˜o a hipo´tese de induc¸a˜o para a e
para b, completamos a prova da existeˆncia.
Quanto a unicidade. Suponha que n = pα11 . . . p
αk
k = q
β1
1 . . . q
βs
s ,
com pi , qj (1 ≤ i ≤ k , 1 ≤ j ≤ s) nu´meros primos. Como p1 divide
n enta˜o p1 divide q
β1
1 . . . q
βs
s . Logo p1 = qi para algum i, suponha-
mos, sem perda de generalidade, que i = 1. Assim pα11 . . . p
αk
k =
pβ11 . . . q
βs
s , tomando a maior poteˆncia de p1 que divide n, obtemos
que α1 = β1. Olhamos enta˜o para p
α2
2 . . . p
αk
k = q
β2
2 . . . q
βs
s . Pro-
cedendo como anteriormente chegaremos que k = s, cada pi sera´
igual a algum qj e αi = βj.
“main”
2013/9/18
page 38i
i
i
i
i
i
i
i
38 [CAP. 2: DIVISA˜O EM Z
Vejamos alguns exemplos simples:
6 = 2 · 3 8 = 23 10 = 2 · 5
12 = 22 · 3 1001 = 7 · 11 · 13 16875 = 33 · 54
16891875 = 33 · 54 · 7 · 11 · 13 6903125 = 55 · 472
Observac¸a˜o 2.46. Note que se n = pα11 . . . p
αk
k e´ fatorac¸a˜o em pri-
mos de n, enta˜o n possui exatamente (α1+1) · · · (αk+1) divisores.
Exemplo 2.47.
• 6 = 2 · 3, tem exatamente 4 divisores, a saber, 1 = 2030,
2 = 2130, 3 = 2031 e 6 = 2131.
Exemplo 2.48. Existem inteiros positivos k e n tais que 12n14k
possui exatamente 165 divisores?
Primeiramente escrevemos 12n · 14k na forma do TFA, a saber
12n · 14k = (22 · 3)n · (2 · 7)k = 22n+k3n7k. Logo, 12n · 14k possui 165
divisores, se e somente se, a equac¸a˜o (2n + k + 1)(n + 1)(k + 1) =
165 = 11 · 5 · 3 possui soluc¸a˜o em N. Note que n = 4 e k = 2 e´
soluc¸a˜o da equac¸a˜o anterior.
Definic¸a˜o 2.49. Sejam a e b inteiros. O mı´nimo mu´ltiplo comum
entre a e b e´ menor inteiro positivo que e´ mu´ltiplo de a e de b.
Notac¸a˜o: mmc(a, b).
Observac¸a˜o 2.50. O mmc entre dois inteiros sempre existe. Pois
se a, b ∈ Z enta˜o |a| · |b| e´ mu´ltiplo de a e de b.
O Teorema Fundamental da Aritme´tica pode ser usado tambe´m
para os ca´lculos de mdc e mmc. Vejamos.
Exemplo 2.51.
“main”
2013/9/18
page 39i
i
i
i
i
i
i
i
[SEC. 2.5: TEOREMA FUNDAMENTAL DA ARITME´TICA 39
• Sabemos que 385 = 5 · 7 · 11, enquanto que 66 = 2 · 3 · 11.
Logo 11 e´ o u´nico primo comum em ambas a fatorac¸o˜es enta˜o
mdc(385, 66) = 11.
• Temos que 1260 = 22 · 32 · 5 · 7 e 21294 = 2 · 32 · 7 · 132. Os
primos comuns em ambas a fatorac¸o˜es sa˜o 2, 3 e 7. Tomando a
menor poteˆncia desses nu´meros que aparecem nas fatorac¸o˜es,
conclu´ımos que mdc(1260, 21294) = 2 · 32 · 7 = 126;
• Quanto ao mmc. Facilmente veˆ-se que mmc(385, 66) = 2 · 3 ·
5 · 7 · 11.
• mmc(1260, 21294) = 22 · 32 · 5 · 7 · 132.
Inspirados no exemplo acima, segue diretamente do TFA os se-
guintes corola´rios.
Corola´rio 2.52. Sejam a e b inteiros na˜o negativos e na˜o ambos
nulos. Se a = pα11 . . . p
αr
r · uγ11 . . . uγkk e b = pβ11 . . . pβrr · qθ11 . . . qθss e´ a
fatorac¸a˜o em primos de a e b respectivamente, com ui 6= qj ∀ i, j.
Enta˜o:
i) mdc(a, b) = p
min{α1,β1}
1 . . . p
min{αr,βr}
r ;
ii) mmc(a, b) = p
max{α1,β1}
1 . . . p
max{αr,βr}
r · uγ11 . . . uγkk · qθ11 . . . qθss .
Corola´rio 2.53. Sejam a, b ∈ Z na˜o ambos nulos. Enta˜o
mdc(a, b) ·mmc(a, b) = a · b
“main”
2013/9/18
page 40i
i
i
i
i
i
i
i
40 [CAP. 2: DIVISA˜O EM Z
2.6 Exerc´ıcios
1. Calcule o resto da divisa˜o de a por b nos seguintes casos:
(a) a = −17, b = 1;
(b) a = −16, b = −27;
(c) a = 16, b = 27;
(d) a = −16, b = 27.
2. Encontre o mdc entre a e b nos seguintescasos:
(a) a = 102 e b = 274;
(b) a = 1001 e b = 109;
3. Mostre que 215 − 1 e 210 + 1 sa˜o primos entre si.
4. Mostre que 7|a7 − a ∀ a ∈ Z.
5. Mostre ou deˆ um contra-exemplo para:
(a) 4|a4 − a ∀ a ∈ Z;
(b) 6|a6 − a ∀ a ∈ Z.
6. Mostre que se k e´ natural ı´mpar, enta˜o a+ b | ak + bk.
7. Mostre que (n− 1)2 |nk − 1 se, e somente se, n− 1|k.
8. Sejam m 6= n dois nu´meros naturais. Mostre que:
(a2
m
+ 1, a2
n
+ 1) =
{
1, se a e´ par,
2, se a e´ ı´mpar.
9. Sejam a, b ∈ N com (a, b) = 1. Mostre que se c > ab− a− b,
enta˜o a equac¸a˜o ax+ by = c admite soluc¸a˜o em N.
“main”
2013/9/18
page 41i
i
i
i
i
i
i
i
[SEC. 2.6: EXERC´ICIOS 41
10. Mostre que a frac¸a˜o 21n+4
14n+3
e´ irredut´ıvel para todo n ∈ N.
11. Determine todos os pares [m,n] de inteiros positivos para os
quais n
3+1
mn−1 e´ inteiro.
12. Mostre os seguintes itens para todo n ∈ N:
(a) 9 | 10n − 1;
(b) 3 | 10n − 7n;
(c) 8 | 32n − 1;
(d) 53 | 74n − 24n;
(e) 13 | 92n − 24n;
13. Mostre que existem infinitos nu´meros naturais para os quais
8n2 + 5 e´ divis´ıvel por 7 e 11.
14. Encontre mdc(a, b) nos seguintes casos:
(a) a = 637 e b = 3887;
(b) a = 7325 e b = 8485;
(c) a = 551 e b = 874.
15. Mostre que mdc(a, a+ b) | b ∀ a, b ∈ Z.
16. Seja n ∈ N, mostre que:
(a) mdc(n, 2n+ 1) = 1;
(b) mdc(2n+ 1, 9n+ 4) = 1;
(c) mdc(n! + 1, (n+ 1)! + 1) = 1;
17. Seja n ∈ N, com n > 1. Mostre que na seguinte sequeˆncia
(n + 1)! + 2, (n + 1)! + 3, . . . , (n + 1)! + n + 1 de nu´meros
naturais consecutivos na˜o existe nenhum nu´mero primo.
“main”
2013/9/18
page 42i
i
i
i
i
i
i
i
42 [CAP. 2: DIVISA˜O EM Z
18. Calcule:
(a) mdc
(
240 + 1
28 + 1
, 28 + 1
)
;
(b) mdc
(
250 + 1
210 + 1
, 210 + 1
)
.
19. Mostre que mdc(a, b) = mdc(−a, b) = mdc(a,−b) = mdc(−a,−b), ∀ a, b ∈
Z.
20. Deˆ um contra-exemplo ou prove a veracidade das seguintes
sentenc¸as:
(a) mdc(a, b) = mdc(a+ ka, b);
(b) mdc(2n+ 1, 9n+ 1) = 1;
(c) Se ab e´ um quarado perfeito, com a, b, c ∈ N, enta˜o a e
b tambe´m o sa˜o.
(d) Se dois nu´meros compostos sa˜o primos entre si, enta˜o
um deles e´ ı´mpar;
(e) O produto de treˆs inteiros na˜o nulos consecutivos e´ mu´ltiplo
de 6;
(f) A soma de treˆs inteiros na˜o nulos consecutivos e´ mu´ltiplo
de 3;
(g) Se d | a enta˜o d | a+ n ∀ n ∈ Z;
(h) mdc(a+ b, c+ a) = mdc(a+ b, c);
(i) mdc(a+ b, a) = a;
(j) Se d divide p1 . . . pk + 1 com cada pi primo, enta˜o d | 1.
21. Demonstrar que se mdc(a, 2n+1) = 2n e mdc(b, 2n+1) = 2n ,
enta˜o mdc(a+ b, 2n+1) = 2n+1.
“main”
2013/9/18
page 43i
i
i
i
i
i
i
i
[SEC. 2.6: EXERC´ICIOS 43
22. Demonstrar que se a, b, c, d, m e n sa˜o inteiros tais que
ad − bc = 1 e mn 6= 0, enta˜o mdc(am + bn, cm + dn) =
mdc(m,n).
23. Mostre que 232 + 1 e 24 + 1 sa˜o primos entre si.
24. Demonstrar que mdc(2a− 1, 2b− 1) = 2mdc(a,b)− 1 para todos
a, b ∈ N.
25. Encontre inteiros positivos tais que:
(a) n+ 1 |n3 − 1;
(b) 2n− 1 |n3 + 1;
(c) 1
m
+ 1
n
= 1
143
;
(d) 2n3 + 5 |n4 + n+ 1.
26. Mostre que: Se ab e´ um quarado perfeito, com (a, b) = 1,
enta˜o a e b tambe´m o sa˜o.
27. Mostre que:
(a) mmc(a, b) = ab se, e somente se, (a, b) = 1;
(b) mmc(na, nb) = n ·mmc(a, b) ∀n ∈ N;
(c)
(
mmc(a, b)
a
,
mmc(a, b)
b
)
= 1;
(d) mmc(a,mdc(b, c)) = mdc(mmc(a, b),mmc(a, c));
(e) mdc(a, b) = mmc(a, b)⇔ a = b;
28. Qual o menor natural n tal que 1000 |n!?
29. Sejam a, b ∈ Z e n ∈ N∗. Mostre que mdc(an, bn) = mdc(a, b)n.
30. Ache os poss´ıveis valores de m,n ∈ N tais que 9m10n tenha:
“main”
2013/9/18
page 44i
i
i
i
i
i
i
i
44 [CAP. 2: DIVISA˜O EM Z
(a) 27 divisores;
(b) 243 divisores.
31. Seja n > 4 um natural composto. Mostre que n|(n− 1)!.
32. Seja n um natural na˜o nulo. Mostre que se 2n − 1 for primo
enta˜o n tambe´m sera´ primo.
33. Mostre que n4 + 4 e´ composto se n > 1.
34. Seja a e b naturais tais que mdc(a, b) = 1. Suponha que
a2 − b2 seja um quadrado perfeito. Mostre que a + b ea − b
sa˜o quadrados perfeitos, ou cada um (a + b) e (a − b) e´ um
duas vezes um quadrado perfeito.
35. Sejam a, b, c, d inteiros ı´mpares tais que 0 < a < b < c < d
e ad = bc. Demonstre que se a + d = 2k e b + c = 2m para
inteiros k e m, enta˜o a = 1.
36. Seja um inteiro k > 1. Mostre que o nu´mero 1
2
+ 1
3
+ · · ·+ 1
k
nunca e´ um inteiro.
37. Sejam a, b inteiros positivos. Divida a2 + b2 por a+ b, denote
o quociente por q e o resto por r. Encontrar todos os a, b ∈ N
tais que q2 + r = 1977.