Mini-curso de álgebra - Lógica

Prévia do material em texto

2
Um Mini-Curso de Aritm¶etica dos
Inteiros
Neste cap¶³tulo reuniremos elementos b¶asicos da teoria dos n¶umeros, pr¶e-requisitos
indispens¶aveis a um primeiro curso de estruturas alg¶ebricas.
2.1 O Princ¶³pio do Menor Inteiro
Como primeiro resultado fundamental da aritm¶etica dos n¶umeros inteiros, relem-
bramos o Princ¶³pio do Menor Inteiro, teorema 1.2 do Cap¶³tulo 1. O Princ¶³pio do
Menor Inteiro estabelece que
Todo subconjunto n~ao vazio A do conjunto Z dos n¶umeros inteiros, limitado
inferiormente, possui um primeiro elemento, menor que os demais elementos de
A, a que chamaremos de m¶³nimo de A.
Estabelece tamb¶em que
Todo subconjunto B de Z, n~ao vazio, limitado superiormente, possui um ¶ultimo
elemento, maior que os demais elementos de B, a que chamaremos de m¶aximo de
B.
2.2 Valor Absoluto ou M¶odulo
Relembraremos tamb¶em o conceito de valor absoluto ou m¶odulo de um n¶umero
inteiro, j¶a de¯nido na se»c~ao 1.2.3 Problemas Complementares, cap¶³tulo 1.
De¯ni»c~ao 2.1 Para cada inteiro x, de¯ne-se o inteiro valor absoluto de x ou
m¶odulo de x, denotado por jxj, pela igualdade:
jxj =
½
x; se x ¸ 0
¡x; se x < 0
19
Um Mini-Curso de Aritm¶etica dos Inteiros 20
Deixaremos ao leitor, como exerc¶³cio, as provas das seguintes propriedades
do valor absoluto:
Proposi»c~ao 2.1 Para cada x, e cada y, x e y inteiros, tem-se
1. jxj ¸ 0; e jxj = 0, x = 0;
2. j¡xj = jxj;
3. jxyj = jxjjyj;
4. jx§ yj · jxj+ jyj;
5. jxj · y , ¡y · x · y
2.3 M¶ultiplos e Divisores
De¯ni»c~ao 2.2 Dados dois inteiros a e b, dizemos que
² a divide b, ou que
² a ¶e divisor de b, ou que
² a ¶e fator de b, ou ainda que
² b ¶e m¶ultiplo de a,
se existe um inteiro c, tal que b = a ¢ c.
Observa»c~ao 2.1 Se a e b s~ao inteiros, escrevemos ajb para denotar que a divide
b. Se a n~ao divide b, denotaremos a6j b.
Observa»c~ao 2.2 Ao denotar que a divide b, n~ao escreva a=b e nem tampouco
anb. Lembre-se que a=b denota a fra»c~ao de inteiros a sobre b no conjunto dos
n¶umeros racionais. J¶a anb, com a e b inteiros, ¶e nota»c~ao que carece de signi¯cado.
Exemplo 2.1
² 2j(¡6), pois ¡6 = 2 ¢ (¡3)
² Para cada inteiro a, aja, 1ja e aj0, pois, respectivamente, a = a ¢1 e 0 = a¢0
² 0j0 (zero divide zero !), pois 0 = 0 ¢ c, para qualquer inteiro c
² 0ja, a = 0. De fato, 0ja, a = 0 ¢ c = 0, para algum inteiro c
Um Mini-Curso de Aritm¶etica dos Inteiros 21
Proposi»c~ao 2.2 Para cada a, cada b, e cada c, todos inteiros,
1. aja
2. ajb e bja , a = §b
3. ajb e bjc ) ajc
4. ajb e ajc ) aj(mb§ nc); 8m;n 2 Z
5. ajb e aj(b§ c)) ajc
Demonstra»c~ao. Sejam a, b e c n¶umeros inteiros. Ent~ao
1. a = a ¢ 1) aja
2.
ajb e bja ) b = ax e a = by; para certos inteiros x e y
) a = by = (ax)y = a(xy)
Se a = 0, ent~ao b = ax = 0) a = b
Se a6= 0, ent~ao a = a(xy)) xy = 1) x = y = §1
Logo, a = by = b(§1) = §b.
Reciprocamente, a = §b) a = b(§1) e b = a(§1)) ajb e bja
3.
ajb e bjc ) existem x; y 2 Z; tais que b = ax e c = by
) c = by = (ax)y = a(xy)
) ajc
4. ajb e ajc) existem inteiros x e y, tais que b = ax e c = ay.
Logo, dados m;n 2 Z, mb + nc = m(ax) + n(ay) = a(mx + ny) )
aj(mb+ nc)
5. ajb e aj(b§ c)) aj[b¡ (b§ c)]) aj(§c)) ajc
2.3.1 Problemas Complementares
1. °^. . Liste todos os divisores positivos de
(a) 20 (b) 63 (c) ¡101
2. °^. . Sejam m, n, p e q inteiros positivos, com p e q primos e p6= q.
(a) Quantos e quais s~ao os divisores positivos de pn?
Um Mini-Curso de Aritm¶etica dos Inteiros 22
(b) Quantos e quais s~ao os divisores positivos de pnqm?
(c) Como podemos determinar o n¶umero de divisores positivos de um in-
teiro dado? Como podemos list¶a-los (metodicamente)? Exempli¯que
tomando o inteiro 2 200.
3. °. . Mostre que para cada n 2 N, 7j(32n+1 + 2n+2).
2.4 Algoritmo da Divis~ao Euclidiana
Primeiramente, relembraremos o teorema do algoritmo da divis~ao para os n¶umeros
naturais (teorema 1.5, p¶agina 12):
Teorema do Algoritmo da Divis~ao em N . Para cada inteiro n, e cada
inteiro d6= 0, existem inteiros q; r 2 N satisfazendo
n = d ¢ q + r e 0 · r < d
Al¶em disso, os inteiros q e r, nas condi»c~oes acima, s~ao ¶unicos.
A vers~ao mais ¶util desse teorema, para os inteiros, tem a seguinte forma:
Teorema 2.1 (Algoritmo da Divis~ao em Z) Para cada inteiro n, e cada inteiro
d, com d6= 0, existem inteiros q (quociente) e r (resto) satisfazendo:
n = dq + r e 0 · r < jdj
Al¶em disso, os inteiros q e r, nas condi»c~oes acima, s~ao ¶unicos.
2.4.1 Exemplos ilustrando o teorema 2.1
Antes de procedermos µa prova do teorema do algoritmo da divis~ao em Z, ilus-
traremos seu enunciado com exemplos simples. Entendemos que isto se faz ne-
cess¶ario pois o conceito de resto que este teorema de¯ne ¶e ligeiramente diferente
daquele ao qual estamos acostumados.
Na divis~ao euclidiana de 23 por 10, temos o \diagrama da chave"
23 10
resto ¡! 3 2 á quociente
Na divis~ao de ¡23 por 10 ser¶³amos tentados a fazer
¡23 10
¡3 ¡2
¶E claro que ¡23 = 10 ¢ (¡2) + (¡3), mas se quisermos o resto r nas
condi»c~oes do teorema 2.1 (r n~ao negativo e menor que o valor absoluto do divisor),
Um Mini-Curso de Aritm¶etica dos Inteiros 23
o quociente e o resto no diagrama acima s~ao inadequados. O diagrama correto
seria
¡23 10
7 ¡3
pois ¡23 = 10 ¢ (¡3) + 7 e 0 · 7 < j10j.
Variando os sinais do dividendo e do divisor, temos os seguintes exemplos:
23 10
3 2
¡23 10
7 ¡3
23 ¡10
3 ¡2
¡23 ¡10
7 3
Outros exemplos:
24 4
0 6
¡24 4
0 ¡6
24 ¡4
0 ¡6
¡24 ¡4
0 6
23 2
1 11
¡23 2
1 ¡12
23 ¡2
1 ¡11
¡23 ¡2
1 ¡12
Os exemplos acima nos sugerem as adapta»c~oes que devem ser feitas para
estabelecermos o algoritmo da divis~ao em Z a partir do algoritmo da divis~ao em
N.
Demonstra»c~ao. do teorema 2.1.
I. Existe^ncia de q e r.
(1o caso: n ¸ 0).
Como jdj > 0, pelo algoritmo da divis~ao em N, existem n¶umeros naturais q
e r satisfazendo
n = jdj ¢ q + r; 0 · r < jdj
Teremos ent~ao n = dq0 + r, com 0 · r < jdj, sendo q0 = §q conforme
tenhamos, respectivamente, d > 0 ou d < 0.
(2o caso: n < 0).
Como jnj > 0, pelo algoritmo da divis~ao em N, existem q; r 2 N satisfazendo
jnj = jdjq + r e 0 · r < jdj
Ent~ao temos
¡n = jdjq + r;
n = ¡jdjq ¡ r:
Se r = 0, teremos n = ¡jdjq = d(¨q), conforme tenhamos, respectiva-
mente, d > 0 ou d < 0, logo n = d(§q) + 0.
Um Mini-Curso de Aritm¶etica dos Inteiros 24
Se r6= 0, teremos
n = ¡jdjq ¡ r
= ¡jdjq ¡ jdj+ jdj ¡ r
= jdj(¡q ¡ 1) + (jdj ¡ r)
= dq0 + r0;
sendo q0 = ¨(q+ 1) (conforme se tenha, respectivamente, d > 0 ou d < 0)
e r0 = jdj ¡ r.
Note que 0 < r < jdj ) ¡jdj < ¡r < 0 ) ¡jdj+ jdj < ¡r + jdj < jdj )
0 < r0 < jdj
II. Unicidade de q e r.
Sejam n e d dois inteiros, com d6= 0, e suponhamos que existam inteiros
q1; q2; r1 e r2 satisfazendo
n = dq1 + r1 = dq2 + r2; com 0 · r1; r2 < jdj
Ent~ao
d(q1 ¡ q2) = r2 ¡ r1 ) jdj ¢ jq1 ¡ q2j = jr2 ¡ r1j
Sendo 0 · r1; r2 < jdj, temos ent~ao jr2 ¡ r1j < jdj (prove isto, como
exerc¶³cio).
Da¶³,
jdj ¢ jq1 ¡ q2j = jr2 ¡ r1j < jdj ) jq1 ¡ q2j < 1) q1 ¡ q2 = 0) q1 = q2
e ent~ao tamb¶em r1 = r2.
2.4.2 Problemas Complementares
1. °^. . Para cada par de inteiros n, d, encontre o quociente e o resto da divis~ao
Euclidiana de n por d (lembre-se de que 0 · r < jdj).
(a) n = 19, d = 5 (b) n = 5, d = 19 (c) n = ¡19, d = 5
(d) n = 19, d = ¡5
(e) n = ¡19, d = ¡5 (f) n = ¡13, d = ¡20 (g) n = 30, d = 3
(h) n = 0, d = ¡1000
2. °^. . Agora, utilizando uma calculadora, obtenha quociente e resto na divis~ao
de
(a) 26 482 627 por 23 837 (b) ¡728 439 por 3 373
Um Mini-Curso de Aritm¶etica dos Inteiros 25
2.5 M¶aximo Divisor Comum
Se x e a s~ao inteiros, com a6= 0, e xja ent~ao jxj · jaj. De fato, como a = xc
para algum inteiro c e c6= 0 (pois a6= 0), temos jcj ¸ 1, e logo
jxj = jxj ¢ 1 · jxjjcj = jxcj = jaj ) jxj · jaj
Assim sendo, se a6= 0, o conjunto D(a)dos inteiros divisores de a ¶e limitado
superiormente por jaj (note por¶em que se a = 0, ent~ao D(a) = D(0) = Z, pois
cada inteiro ¶e divisor de zero).
Agora, dados dois inteiros a e b, com a6= 0 ou b6= 0, existe pelo menos um
divisor comum de a e b, a saber, 1, j¶a que 1ja e 1jb. Al¶em disso, se x 2 Z ¶e um
divisor comum de ambos a e b ent~ao, pela observa»c~ao acima, jxj · jaj (se a6= 0)
ou jxj · jbj (se b6= 0). Assim sendo, o conjunto dos divisores comuns de a e b
¶e limitado superiormente (pelo maior dos inteiros jaj e jbj), e portanto possui um
m¶aximo d, sendo d ¸ 1, j¶a que 1ja e 1jb. A este inteiro d chamamos m¶aximo
divisor comum de a e b.
De¯ni»c~ao 2.3 Dados dois inteiros a e b, chama-se m¶aximo divisor comum de a
e b ao inteiro d satisfazendo:
1. d = 0, se a = b = 0
2. Se a6= 0 ou b6= 0, d ¶e caracterizado pelas seguintes duas propriedades:
(i) dja e djb
(ii) 8x 2 Z, xja e xjb) x · d
Observa»c~ao 2.3 Se d ¶e o m¶aximo divisor comum de a e b, denotamos
d = mdc (a; b)
De acordo com a nota»c~ao estabelecida acima, simbolicamente temos:
1. mdc (0; 0) = 0
2. Se a6= 0 ou b6= 0, ent~ao
mdc (a; b) = maxfx 2 Z j xja e xjbg
Proposi»c~ao 2.3 8a; b 2 Z
1. mdc (a; 0) = jaj
2. mdc (a; b) = mdc (jaj; jbj)
3. mdc (a; b) = mdc (b; a)
Um Mini-Curso de Aritm¶etica dos Inteiros 26
Demonstra»c~ao. A prova dos itens 2 e 3 ¶e imediata, j¶a que 8x 2 Z,
xja e xjb, xjb e xja, xjjaj e xjjbj
Prova do item 1:
Se a = 0, mdc (a; 0) = mdc (0; 0) = 0 = jaj.
Se a6= 0, seja d = jaj. Como a = §d = d(§1), temos que dja. Tamb¶em
dj0. Agora, para cada x 2 Z, xja e xj0) xja) x · jaj ) x · d.
Logo, pela de¯ni»c~ao de mdc, jaj = d = mdc (a; 0).
O seguinte teorema, provavelmente o primeiro teorema n~ao trivial de nossa
introdu»c~ao µa aritm¶etica dos inteiros, e bastante n~ao intuitivo, nos d¶a uma segunda
caracteriza»c~ao do m¶aximo divisor comum e ser¶a fundamental para estabelecermos
uma terceira (e mais utililizada) caracteriza»c~ao do m¶aximo divisor comum.
Teorema 2.2 Se a; b 2 Z, e a6= 0 ou b6= 0, ent~ao o m¶aximo divisor comum de
a e b ¶e a menor das combina»c~oes lineares positivas ma+ nb, com m e n inteiros.
Em outras palavras, se a6= 0 ou b6= 0, ent~ao
mdc (a; b) = minfx 2 Z j x > 0 e x = ma+ nb; com m;n 2 Zg
Demonstra»c~ao. Seja
L = fx 2 Z j x > 0 e x = ma+ nb; com m;n 2 Zg
L6= ¿, pois, sendo a6= 0 ou b6= 0, o inteiro jaj+ jbj ¶e elemento de L, pois
jaj+ jbj > 0 e jaj+ jbj = (§a) + (§b) = ma+ nb, sendo m = §1 e n = §1.
Al¶em disso, L ¶e um subconjunto de Z limitado inferiormente por 0.
Pelo Princ¶³pio do Menor Inteiro, teorema 1.2 do cap¶³tulo 1, existe um inteiro
d, tal que d = minL, isto ¶e, d 2 L e d · x; 8x 2 L.
Veremos agora que dja e djb:
Sendo d > 0, pelo algoritmo da divis~ao em Z, teorema 2.1, existem inteiros
q; r tais que
a = dq + r e 0 · r < d(= jdj)
Como d 2 L, d pode ser escrito na forma
d = m0a+ n0b; para certos m0; n0 2 Z:
Ent~ao teremos
r = a¡ dq
= a¡ (m0a+ n0b)q
= (1¡m0q)a+ (¡n0q)b
= m0a+ n0b
Finalmente observamos:
Um Mini-Curso de Aritm¶etica dos Inteiros 27
(1) r = m0a+ n0b, com m0; n0 2 Z
(2) r = 0 ou 0 < r < d
(3) d = m0a+n0b ¶e a menor combina»c~ao linear positiva da forma ma+nb, com
m e n inteiros.
Por (1), (2) e (3), temos r = 0 (Caso n~ao tenha entendido, leia novamente as con-
di»c~oes (1), (2) e (3) e repense sobre como elas podem ocorrer simultaneamente).
Como r = 0, temos ent~ao a = dq e assim dja.
Analogamente, podemos provar que djb (Complete os detalhes desta parte,
como exerc¶³cio).
Portanto
dja e djb (2.1)
Seja agora x um inteiro tal que xja e xjb. Pela proposi»c~ao 2.2, item 4,
xj(m0a+ n0b)) xjd) x · jdj = d. Assim estabelecemos tamb¶em que
8x 2 Z; xja e xjb) x · d (2.2)
Pelas propriedades (2.1) e (2.2) acima, como a6= 0 ou b6= 0, temos que
d = mdc (a; b), isto ¶e, minL = mdc (a; b).
Corol¶ario 2.1 Se a e b s~ao inteiros e d = mdc (a; b), ent~ao existem inteiros r e s
tais que d = ra+ sb.
Corol¶ario 2.2 Sejam a; b 2 Z e d = mdc (a; b). Sejam
A = fx 2 Z j x = ma+ nb; com m;n 2 Zg e
M = fy 2 Z j y = ¸d; com ¸ 2 Zg:
Ent~ao A =M , isto ¶e, as combina»c~oes lineares ma+nb, com m e n inteiros,
s~ao, na verdade, os inteiros m¶ultiplos de d.
Demonstra»c~ao. Se a = b = 0, temos d = 0 e A = M = f0g. Suponhamos ent~ao
a6= 0 ou b6= 0. Para provar que A =M , provaremos que A ½M e M ½ A.
(i) A ½M :
Seja x um elemento de A.
x 2 A) x = ma+ nb para certos inteiros m e n.
Sendo d = mdc (a; b), temos que dja e djb) dj(ma+nb)) djx) x = ¸d,
para algum inteiro ¸ ) x 2M .
(ii) M ½ A:
Um Mini-Curso de Aritm¶etica dos Inteiros 28
Seja y um elemento de M .
y 2M ) y = ¸d, para algum inteiro ¸.
Pelo teorema 2.2, d = ra + sb, para certos inteiros r; s. Logo, y = ¸d =
¸(ra+ sb) = (¸r)a+ (¸s)b ) y 2 A.
Por (i) e (ii), temos A =M .
Corol¶ario 2.3 (Caracteriza»c~ao habitual do mdc) Sendo a e b dois inteiros da-
dos, temos:
d = mdc (a; b),
8<
:
(1) d ¸ 0
(2) dja e djb
(3) 8x 2 Z; xja e xjb) xjd
Demonstra»c~ao.
())
Note que (1) e (2) j¶a s~ao propriedades estabelecidas do mdc. Assim s¶o nos
resta demonstrar que d = mdc (a; b) satisfaz µa condi»c~ao (3).
Pelo primeiro corol¶ario do teorema 2.2, d = ra+ sb para certos inteiros r e
s. Logo, para cada x 2 Z, se xja e xjb ent~ao xj(ra+ sb), logo xjd.
(()
Sejam a = b = 0 e suponhamos que d 2 Z satisfaz as condi»c~oes (1), (2)
e (3). Por (3), cada inteiro x que divide a e b deve tamb¶em dividir d. Agora,
x = 0 divide a e b, logo divide d. Mas 0jd , d = 0. Logo, pela de¯ni»c~ao 2.3,
d = mdc (a; b).
Suponhamos agora a6= 0 ou b6= 0. Por (2), d6= 0 e ent~ao, por (1) e (2),
d > 0.
Agora temos: se x 2 Z ¶e tal que xja e xjb. Pela condi»c~ao (3), temos ent~ao
que xjd, logo x · jdj = d.
Assim temos:
dja e djb e
8x 2 Z; xja e xjb) x · d.
Portanto, conforme a de¯ni»c~ao 2.3, d = mdc (a; b).
2.5.1 Problemas Complementares
1. °^. . Mostre que se a e b s~ao inteiros tais que ma + nb = ¡26 para certos
inteiros m e n ent~ao mdc (a; b) 2 f1; 2; 13; 26g.
2. °^. . Descreva, enumerando-os na forma de uma seqÄue^ncia in¯nita de in-
teiros, os elementos do conjunto
Um Mini-Curso de Aritm¶etica dos Inteiros 29
(a) A = f12m+ 18n j m;n 2 Zg
(b) B = f24m+ 18n+ 30p j m;n; p 2 Zg
3. °. . Mostre que existem in¯nitos pares de inteiros (r; s) satisfazendo
r ¢ 2 + s ¢ 3 = mdc (2; 3) = 1
[Sugest~ao: Mostre que a equa»c~ao
x ¢ 2 + y ¢ 3 = 0 (2.3)
tem um n¶umero in¯nito de solu»c~oes. Mostre que a equa»c~ao
r ¢ 2 + s ¢ 3 = 1 (2.4)
tem ao menos uma solu»c~ao. Mostre ent~ao que as solu»c~oes da equa»c~ao 2.4
s~ao da forma (x+r0; y+s0), onde (x; y) ¶e solu»c~ao da equa»c~ao 2.3 e (r0; s0)
¶e uma solu»c~ao particular da equa»c~ao da equa»c~ao 2.4].
4. °. . Mostre que se m e n s~ao inteiros primos entre si, ent~ao existem inteiros
x e y tais que
1
mn
=
x
m
+
y
n
°_. . A partir deste fato, justi¯que o seguinte argumento:
Sendo m e n inteiros positivos primos entre si, se uma circunfere^ncia pode
ser dividida, com o uso de r¶egua e compasso, em m arcos congruentes, e
tamb¶em em n arcos congruentes, ent~ao ela tamb¶em pode ser dividida, com
r¶egua e compasso, em mn arcos congruentes.
5. °_. . Mostre que se a, b e c s~ao inteiros, ent~ao
mdc (ac; bc) = jcj ¢mdc (a; b)
[Sugest~ao: Chame d = mdc (a; b). Lembre-se que existem inteiros r e s tais
que d = ra + sb. Ent~ao cd = r(ac) + s(bc). Da¶³, se xjac e xjbc (x 2 Z),
tem-se ent~ao que xjcd. O resto ¶e por sua conta].
2.5.2 O algoritmo Euclidiano para o c¶alculo do mdc
Estabeleceremos aqui um algoritmo para o c¶alculo de mdc (a; b), no caso em que
a e b s~ao inteiros ambos n~ao nulos, realizado atrav¶es de uma seqÄue^ncia ¯nita de
divis~oes Euclidianas. Antes de enunci¶a-lo ilustr¶a-lo-emos atrav¶es de um exemplo.
Considere o problema de calcular mdc (91; 35).
Come»camos fazendo
91 35
21 2
Um Mini-Cursode Aritm¶etica dos Inteiros 30
Consideramos ent~ao o divisor 35 e o resto 21 dessa primeira divis~ao e efetu-
amos a divis~ao Euclidiana de 35 por 21.
35 21
14 1
Agora repetimos o processo iniciado acima, isto ¶e, tomamos, na pr¶oxima
divis~ao, 21 como dividendo e 14 como divisor:
21 14
7 1
Finalmente, chegamos µa divis~ao exata
14 7
0 2
Tendo chegado a um resto igual a zero, o algoritmo termina. O ¶ultimo
resto n~ao nulo, das divis~oes sucessivas realizadas, ¶e o mdc procurado, ou seja,
mdc (91; 35) = 7.
Lema 2.1 Sejam a e b dois inteiros, com b 6= 0, e seja r o resto da divis~ao
Euclidiana de a por b. Ent~ao mdc (a; b) = mdc (b; r).
Demonstra»c~ao. Para demonstrar o resultado enunciado no lema, ¶e su¯ciente provar
que todo divisor de a e b ¶e tamb¶em divisor de b e r, e reciprocamente. Assim sendo,
o maior divisor de a e b coincidir¶a com o maior divisor de b e r. Note que esse
\maior divisor" existe, j¶a que b6= 0.
Temos, por hip¶otese, a = bq + r, logo r = a¡ bq.
Seja x um inteiro divisor de a e b. Ent~ao xja e xjb ) xj(a ¡ qb) ) xjr.
Logo, xjb e xjr.
Agora, seja x um inteiro divisor de b e r. Ent~ao xjb e xjr) xj(qb+r)) xja.
Logo, xjb e xja.
Lema 2.2 Sejam a e b inteiros ambos positivos com a ¸ b e de¯namos uma
seqÄue^ncia de inteiros n~ao negativos da seguinte forma:
² r1 = a;
² r2 = b;
² Para cada¶³ndice k, com k ¸ 2, se rk 6= 0, rk+1 ¶e o resto da divis~ao Euclidiana
de rk¡1 por rk:
rk¡1 rk
rk+1 ¤
Um Mini-Curso de Aritm¶etica dos Inteiros 31
e se rk = 0, a seqÄue^ncia termina em rk. Ent~ao a seqÄue^ncia r1; r2; : : : ¶e ¯nita e
termina num zero, ou seja, existe um indice n tal que r1 ¸ r2 > : : : > rn > 0 e
rn+1 = 0.
Demonstra»c~ao. Por hip¶otese, r1 ¸ r2 e, pela de¯ni»c~ao de rk+1, para k ¸ 2 temos
rk+1 < rk.
Considere o conjunto de n¶umeros naturais S = fr1; r2; : : :g. Como S ½ N
e S6= ¿, pelo princ¶³pio da boa ordem, S possui um m¶³nimo, o qual denotaremos
por rn+1. Pelo que foi observado acima, teremos rn+1 < rn < : : : < r2 · r1.
A¯rmamos que rn+1 = 0. Para justi¯car isto, basta observar que se rn+1 6= 0
ent~ao podemos de¯nir rn+2 2 S como sendo o resto da divis~ao de rn por rn+1.
Teremos ent~ao 0 · rn+2 < rn+1, contrariando o fato de rn+1 ser m¶³nimo de S.
Teorema 2.3 (Algoritmo Euclidiano para o c¶alculo do mdc) Sejam a e b
inteiros ambos positivos com a ¸ b e seja r1; r2; : : : ; rn; rn+1 a seqÄue^ncia de¯nida
pelo lema 2.2, sendo r1 ¸ r2 > : : : > rn > rn+1 = 0. Ent~ao rn = mdc (a; b).
Demonstra»c~ao. Para cada k ¸ 3, rk ¶e o resto da divis~ao de rk¡2 por rk¡1. Pelo
lema 2.1,
mdc (rk; rk¡1) = mdc (rk¡1; rk¡2)
Logo
rn = mdc (0; rn)
= mdc (rn+1; rn) (pois rn+1 = 0)
= mdc (rn; rn¡1) (pelo lema 1)
= : : :
= mdc (r3; r2)
= mdc (r2; r1)
= mdc (a; b)
2.5.3 Escrevendo mdc (a; b) = ra + sb, com r e s inteiros,
atrav¶es do algoritmo Euclidiano. Um exemplo.
No exemplo mostrado acima, mdc (91; 35) = 7 foi obtido mediante quatro divis~oes
sucessivas:
91 35
21 2
35 21
14 1
21 14
7 1
14 7
0 2
Um Mini-Curso de Aritm¶etica dos Inteiros 32
As tre^s primeiras divis~oes estabelecem
91 = 35 ¢ 2 + 21
35 = 21 + 14
21 = 14 ¢ 1 + 7
E ent~ao, isolando os restos, temos
21 = 91¡ 35 ¢ 2
14 = 35¡ 21 ¢ 1
7 = 21¡ 14 ¢ 1,
de onde ent~ao obtemos, passo a passo, cada um dos tre^s restos como combina»c~ao
linear de 91 e 35:
21 = 91¡ 35 ¢ 2, conforme j¶a estabelecido.
14 = 35¡ 21 ¢ 1
= 35¡ (91¡ 35 ¢ 2)
= (¡1) ¢ 91 + 3 ¢ 35
e ¯nalmente
7 = 21¡ 14 ¢ 1
= (91¡ 35 ¢ 2)¡ [(¡1) ¢ 91 + 3 ¢ 35] ¢ 1
= 2 ¢ 91 + (¡5) ¢ 35
ou seja,
7 = 2 ¢ 91 + (¡5) ¢ 35
obtendo-se assim 7 = mdc (91; 35) como combina»c~ao linear r ¢ 91 + s ¢ 35, com r
e s inteiros.
2.5.4 Problemas Complementares
1. °. . Em cada caso, calcule mdc (a; b) pelo algoritmo Euclidiano (divis~oes
sucessivas) e use as divis~oes sucessivas efetuadas para escrever mdc (a; b) na
forma ra+ sb, com r e s inteiros.
(a) a = 11, b = 15 (b) a = 180, b = 252 (c) a = 868, b = 378
(c) a = ¡21, b = 35 (d) a = ¡4148, b = 7864 (e) a = ¡60, b = ¡51
2.6 O Teorema Fundamental da Aritm¶etica
De¯ni»c~ao 2.4 Dados a e b inteiros, dizemos que a e b s~ao relativamente primos
ou primos entre si se mdc (a; b) = 1, ou seja, se a e b n~ao tem fatores positivos
comuns al¶em da unidade.
Um Mini-Curso de Aritm¶etica dos Inteiros 33
Proposi»c~ao 2.4 Dados dois inteiros a e b, a e b s~ao primos entre si se e somente
se existem inteiros r e s satisfazendo ra+ sb = 1.
Demonstra»c~ao. A prova ¶e uma aplica»c~ao imediata do teorema 2.2. Vale uma
igualdade ra+ sb = 1, com r e s inteiros, se e somente se a6= 0 ou b6= 0 e, al¶em
disso, 1 ¶e a menor combina»c~ao linear positiva de a e b, com coe¯cientes inteiros,
ou seja, se e somente se mdc (a; b) = 1.
Proposi»c~ao 2.5 Dados inteiros a, b e c, se a e b s~ao primos entre si e ajbc ent~ao
ajc.
Demonstra»c~ao. Como a e b s~ao primos entre si, pela proposi»c~ao 2.4 acima, ra+
sb = 1 para certos inteiros r e s.
Logo, rac+ sbc = c.
Assim, aj(rac) e aj(sbc) (pois ajbc). Logo aj(rac+ sbc), e portanto ajc.
Proposi»c~ao 2.6 Dados inteiros a, b e c, com a e b primos entre si, se ajc e bjc
ent~ao abjc.
Demonstra»c~ao. Por hip¶otese, ajc e bjc. Isto quer dizer que para certos inteiros x
e y, temos
c = ax e c = by
Como a e b s~ao primos entre si, pelo teorema 2.2, existem inteiros r e s tais
que ra+ sb = 1. Da¶³, rac + sbc = c. Logo,
ra(by) + sb(ax) = c) ab(ry + sx) = c) abjc
De¯ni»c~ao 2.5 Dizemos que um inteiro p ¶e primo se p6= 0, p6= §1 e os ¶unicos
inteiros divisores de p s~ao 1, p, ¡1 e ¡p.
Proposi»c~ao 2.7 Sendo a e p inteiros, se p ¶e primo e p n~ao divide a ent~ao a e p
s~ao relativamente primos.
Demonstra»c~ao. Sejam a e p tal como no enunciado da proposi»c~ao e seja d =
mdc (a; p).
Ent~ao d > 0, dja e djp. Como p ¶e primo, temos que d = 1 ou d = p. Mas
p6j a e dja, logo d = 1 e assim a e b s~ao primos entre si.
Teorema 2.4 Sejam a, b e p inteiros, com p primo. Se pjab ent~ao pja ou
pjb (podendo ser fator de ambos, a e b).
Um Mini-Curso de Aritm¶etica dos Inteiros 34
Demonstra»c~ao. Temos que pja ou p6j a.
Se p6j a, ent~ao, pela proposi»c~ao anterior, p e a s~ao relativamente primos.
Como pjab, pela proposi»c~ao 2.5, temos que pjb.
Corol¶ario 2.4 Sejam p; a1; : : : ; an n¶umeros inteiros com n ¸ 2 e p primo. Se
pj(a1a2 : : : an) ent~ao pjai para algum ¶³ndice i, i 2 f1; 2; : : : ; ng.
Prova por indu»c~ao sobre n.
Para n = 2, o corol¶ario ¶e verdadeiro pela proposi»c~ao 2.4.
Seja k um inteiro com k ¸ 2 e suponhamos que a a¯rma»c~ao do corol¶ario
seja verdadeira para n = k, isto ¶e, suponhamos que se p ¶e primo e p divide um
produto de k n¶umeros inteiros ent~ao p divide ao menos um dos fatores.
Consideremos ent~ao um produto de k + 1 inteiros a1a2 : : : akak+1 e supo-
nhamos que pja1a2 : : : akak+1. Ent~ao pj(a1a2 ¢ ¢ ¢ ak)ak+1. Pela proposi»c~ao 2.4,
pj(a1a2 ¢ ¢ ¢ ak) ou pjak+1. Logo, pjaj para algum j 2 f1; : : : ; kg (pela hip¶otese de
indu»c~ao) ou pjak+1, e assim a propriedade enunciada tamb¶em se aplica ao produto
de k + 1 inteiros.
Pelo primeiro principio de indu»c~ao ¯nita, o corol¶ario est¶a demonstrado.
Teorema 2.5 (Teorema Fundamental da Aritm¶etica) Para cada inteiro m,
com m ¸ 2, existe um conjunto de inteiros positivos e primos p1; : : : ; pn, com
n ¸ 1 e p1 · : : : · pn, tal que m = p1 ¢ ¢ ¢ ¢ ¢ pn. Al¶em disso, os fatores primos
p1; : : : ; pn, satisfazendo as condi»c~oes acima, s~ao ¶unicos, isto ¶e, se q1; : : : ; qs s~ao
tamb¶em primos positivos com q1 · : : : · qs e m = q1 ¢ ¢ ¢ ¢ ¢ qs, ent~ao n = s e,
al¶em disso, p1 = q1; : : : ; pn = qn.
Demonstra»c~ao.
Existe^ncia da decomposi»c~ao de m em fatores primos.
Provaremos, por indu»c~ao sobre m (pelo segundo princ¶³pio de indu»c~ao ¯nita),
a existe^ncia da decomposi»c~ao de m em seus fatores primos.
Se m = 2, ent~ao m ¶e primo (prove). Temosent~ao m = p1, com p1 primo
positivo.
Seja k ¸ 2 e suponhamos que se m ¶e um inteiro, com 2 · m · k, ent~ao m
¶e primo ou se decomp~oe como produto de fatores primos. Trataremos de provar
que ent~ao k + 1 tamb¶em ¶e primo ou se escreve como produto de fatores primos.
Se k + 1 ¶e primo, ent~ao nada mais temos a provar.
Se k + 1 n~ao ¶e primo (isto ¶e, se k + 1 ¶e composto), ent~ao existem inteiros
positivos a e b, com 1 < a < k + 1 e 1 < b < k + 1, tais que k + 1 se fatora na
forma k + 1 = a ¢ b.
Agora, como 1 < a · k e 1 < b · k, pela hip¶otese de indu»c~ao, cada um
dos inteiros a e b se decomp~oe como produto de fatores primos positivos.
Um Mini-Curso de Aritm¶etica dos Inteiros 35
Logo, como k + 1 = ab, k + 1 se decomp~oe como um produto de fatores
primos.
Assim sendo, cada inteiro m ¸ 2 ¶e primo ou se escreve como um produto
de primos. Arranjando-se convenientemente a ordem dos fatores, teremos
m = p1 ¢ ¢ ¢ pn; com p1; : : : ; pn primos positivos e p1 · : : : · pn
Unicidade da decomposi»c~ao de m em fatores primos.
Para a prova da unicidade dos fatores primos de m, utilizaremos novamente
o segundo princ¶³pio de indu»c~ao ¯nita.
Sem = 2, obviamente n~ao ser¶a poss¶³vel termosm = q1 ¢ ¢ ¢ qs, com q1; : : : ; qs
primos positivos e s ¸ 2, j¶a que 2 ¶e primo. S¶o nos resta a possibilidade s = 1,
tendo ent~ao 2 = q1. Assim, s¶o h¶a uma maneira de escrever 2 como \produto" de
fatores primos positivos.
Seja k ¸ 2 e suponhamos que para cada inteiro m, com 2 · m · k, s¶o h¶a
uma fatora»c~ao poss¶³vel de m como produto de primos positivos, se considerados
ordenadamente, como no enunciado do teorema. Mostraremos que o mesmo se
d¶a com rela»c~ao ao inteiro k + 1.
Suponhamos que k + 1 = p1 ¢ ¢ ¢ pn = q1 ¢ ¢ ¢ qs, com n; s ¸ 1, p1 · : : : · pn
e q1 · : : : · qs.
Se n = 1, ent~ao k+1 = p1 ¶e primo e, neste caso tamb¶em teremos s = 1, j¶a
que um primo n~ao pode ser um produto de dois ou mais primos. Ent~ao n = s = 1
e k + 1 = p1 = q1.
Se, por outro lado, s = 1, ent~ao, analogamente, teremos n = 1 e k + 1 =
p1 = q1.
Suponhamos ent~ao n ¸ 2 e s ¸ 2. Como p1 ¢ ¢ ¢ pn¡1pn = q1 ¢ ¢ ¢ qs¡1qs,
temos que pnj(q1 ¢ ¢ ¢ qs) e qsj(p1 ¢ ¢ ¢ pn).
Pelo corol¶ario 2.4, temos que pnjqi e qsjpj para certos ¶³ndices i; j, com
1 · i · s e 1 · j · n. Logo, pn · qi · qs · pj · pn, o que ent~ao acarreta
pn = qs.
Logo, p1 ¢ ¢ ¢ pn¡1pn = q1 ¢ ¢ ¢ qs¡1qs e pn = qs, e ent~ao
p1 ¢ ¢ ¢ pn¡1 = q1 ¢ ¢ ¢ qs¡1
Agora, 2 · p1 ¢ ¢ ¢ pn¡1 = q1 ¢ ¢ ¢ qs¡1 < k + 1, ou seja, 2 · p1 ¢ ¢ ¢ pn¡1 =
q1 ¢ ¢ ¢ qs¡1 · k.
Aplicando a hip¶otese de indu»c~ao, temos ent~ao que n ¡ 1 = s ¡ 1 e, al¶em
disso, p1 = q1, : : :, pn¡1 = qn¡1.
Logo, n = s e p1 = q1; : : : ; pn¡1 = qn¡1; pn = qn.
Assim sendo, a unicidade dos fatores primos de m ¶e v¶alida para cada m ¸ 2.
Um Mini-Curso de Aritm¶etica dos Inteiros 36
Corol¶ario 2.5 Para cada inteiro m, com m ¸ 2, existem primos positivos p1, : : :,
ps, com s ¸ 1 e p1 < : : : < ps se s ¸ 2, e inteiros positivos ®1; : : : ; ®s tal que
m = p1
®1 ¢ ¢ ¢ ps®s. Tal representa»c~ao de m ¶e ¶unica.
Demonstra»c~ao. Pelo teorema fundamental da aritm¶etica, m ¶e um produto de fa-
tores primos q1 ¢ ¢ ¢ qn, com q1 · : : : · qn (n ¸ 1). Agrupando-se os fatores primos
repetidos na forma de pote^ncias de primos, temos a representa»c~ao enunciada neste
corol¶ario. Ademais, pelo teorema fundamental da aritm¶etica, tal representa»c~ao ¶e
¶unica.
Corol¶ario 2.6 Sejam um inteiro,m = p®11 ¢ ¢ ¢ p®nn , com n ¸ 1 e p1; : : : ; pn primos
positivos com p1 < : : : < pn se n ¸ 2 e ®1; : : : ; ®n inteiros positivos. Sendo a um
inteiro, temos que a divide m se e somente se a = p¯11 ¢ ¢ ¢ p¯nn , para certos inteiros
n~ao negativos ¯1; : : : ; ¯n satisfazendo ¯1 · ®1; : : : ; ¯n · ®n.
Demonstra»c~ao. Se ajm, ent~ao m = a ¢ c para um certo inteiro positivo c. Assim,
os eventuais fatores primos de a (eventuais, pois podemos ter a = 1) s~ao fatores
primos de m. Ou seja, o conjunto de fatores primos de a ¶e um subconjunto dos
fatores primos de m.
Assim sendo, a = p¯11 ¢ ¢ ¢ p¯nn para certos inteiros n~ao negativos ¯1; : : : ; ¯n
(onde teremos ¯j = 0 se pj n~ao for fator de a). Claramente, para cada ¶³ndice j,
teremos ¯j · ®j, pois como p®11 ¢ ¢ ¢ p®nn = p¯11 ¢ p¯nn ¢ c, se ®j < ¯j para algum
¶³ndice j, teremos uma contradi»c~ao ao teorema fundamental da aritm¶etica.
Corol¶ario 2.7 Sejam a e b dois inteiros positivos. Ent~ao existem primos positivos
p1; : : : ; pn, com n ¸ 1 e p1 < : : : < pn se n ¸ 2, e inteiros n~ao negativos
®1; : : : ; ®n, ¯1; : : : ; ¯n, tais que a = p
®1
1 ¢ ¢ ¢ p®nn e b = p¯11 ¢ p¯nn . E a partir destas
representa»c~oes de a e b, teremos
mdc (a; b) = p°11 ¢ ¢ ¢ p°nn
onde, para cada ¶³ndice i, °i = minf®i; ¯ig.
2.6.1 Problemas Complementares
1. °_. . (Admita familiaridade com os n¶umeros racionais) Usando o Teorema
Fundamental da Aritm¶etica, mostre que se p > 0 ¶e primo ent~ao
(a)
p
p ¶e irracional (b) n
p
p ¶e irracional, para cada n ¸ 3
2. °. . Seja a um inteiro positivo. Mostre que se cada primo positivo p, com
p · pa, n~ao ¶e fator de a, ent~ao a ¶e primo. [Sugest~ao: Mostre que se a > 0
n~ao ¶e primo, ent~ao a possui um fator primo p, com p · pa. Para isso,
supondo que a n~ao ¶e primo, decomponha-o na forma a = p1p2 : : : pn, com
n ¸ 2 e p1; : : : ; pn todos primos. Se, para cada ¶³ndice i tivermos pi >
p
a,
ent~ao teremos a2 = p21p
2
2 : : : p
2
n > a ¢a : : : a ¸ a2, ou seja, teremos a2 > a2.]
Um Mini-Curso de Aritm¶etica dos Inteiros 37
3. °^. . Utilizando o resultado do problema anterior, veri¯que quais dos inteiros
dados ¶e primo:
(a) 247 (b) 251 (c) 531 (d) 539 (e) 541
2.7 Congrue^ncia m¶odulo m em Z
De¯ni»c~ao 2.6 Dados tre^s inteiros a, b e m, dizemos que a ¶e congruente a b
m¶odulo m, e denotamos a ´ b (mod m) ou a
m´
b se m divide a¡ b.
Observa»c~ao 2.4 Alternativamente, temos que dados tre^s inteiros a, b e m,
a ´ b (mod m)
, mj(a¡ b)
, a¡ b = q ¢m, para algum q 2 Z,
, a = b+ qm, para algum q 2 Z.
Proposi»c~ao 2.8 Sendo m um inteiro, a rela»c~ao de congrue^ncia m¶odulo m, de¯ni-
da em Z conforme a de¯ni»c~ao 2.6, ¶e uma rela»c~ao de equivale^ncia em Z, ou seja,
satisfaz µas seguintes tre^s propriedades:
1. 8a 2 Z, a
m´
a;
2. 8a; b 2 Z, se a
m´
b ent~ao b
m´
a;
3. 8a; b; c 2 Z, se a
m´
b e b
m´
c ent~ao a
m´
c.
Demonstra»c~ao. Para cada a, cada b e cada c, todos inteiros, temos:
1. mj0) mj(a¡ a)) a
m´
a
2. a
m´
b) mj(a¡ b)) mj ¡ (a¡ b)) mj(b¡ a)) b
m´
a
3. a
m´
b e b
m´
c ) mj(a ¡ b) e mj(b ¡ c) ) mj[(a ¡ b) + (b ¡ c)] )
mj(a¡ c)) a
m´
c
Proposi»c~ao 2.9 (Compatibilidade de
m´
com as opera»c~oes em Z)
Seja m um inteiro ¯xado. Dados a; b; c e d inteiros, e n natural, tem-se:
1. a
m´
b, a+ c
m´
b+ c
2.
a
m´
b
c
m´
d
)
) a+ c
m´
b+ d
Um Mini-Curso de Aritm¶etica dos Inteiros 38
3. a
m´
b) ac
m´
bc
4.
a
m´
b
c
m´
d
)
) ac
m´
bd
5. a
m´
b) an
m´
bn
Demonstra»c~ao.
1. a
m´
b, mj(a¡ b), mj[(a+ c)¡ (b+ c)], a+ c
m´
b+ c
2.
a
m´
b
c
m´
d
)
) mj(a¡ b) e mj(c¡ d)
) mj[(a¡ b) + (c¡ d)]
) mj[(a+ c)¡ (b+ d)]
) a+ c
m´
b+ d
3. a
m´
b) mj(a¡ b)) mj(a¡ b)c) mj(ac¡ bc)) ac
m´
bc
4.
a
m´
b
c
m´
d
)
)
(
ac
m´
bc
bc
m´
bd
)
) ac
m´
bd
5. A prova ¶e feita por indu»c~ao sobre n (exerc¶³cio para o leitor).
Observa»c~ao 2.5 (Congrue^ncias Irrelevantes)
1. Se m = 0, dados dois inteiros a e b,
a
m´
b, a
0´
b, 0j(a¡ b), a¡ b = 0, a = b
Assim, a rela»c~ao de congrue^ncia m¶odulo 0 coincide com a rela»c~ao de igual-
dade em Z.
2. Se m = 1, dados dois inteiros a e b,
a
m´
b, a
1´
b, 1j(a¡ b)
Como 1 divide qualquer inteiro, quaisquer dois inteiros a e b s~ao congruentes
m¶odulo 1.
Em vista dos itens 1 e 2 acima, as congrue^ncias m¶odulo 0 e m¶odulo 1 s~ao
casos desinteressantesde congrue^ncia.
3. Dado m 2 Z e inteiros a e b,
a
m´
b, mj(a¡ b), (¡m)j(a¡ b), a
¡´m
b
Assim, as congrue^ncias m¶odulo m e m¶odulo ¡m s~ao a mesma rela»c~ao de
congrue^ncia.
Em vista das tre^s observa»c~oes feitas a partir dos itens 1, 2 e 3 acima, do-
ravante trataremos de estudar a rela»c~ao de congrue^ncia m¶odulo m em Z
apenas para m ¸ 2.
Um Mini-Curso de Aritm¶etica dos Inteiros 39
Proposi»c~ao 2.10 (Congrue^ncia mod m e resto da divis~ao por m)
Sejam a, b e m inteiros com m ¸ 2. Ent~ao
1. Se r ¶e o resto da divis~ao de a por m ent~ao a
m´
r
2. Se a
m´
s (s 2 Z) e 0 · s < m ent~ao s ¶e o resto da divis~ao de a por m.
3. a
m´
b, os restos das divis~oes de a e b por m s~ao iguais.
Demonstra»c~ao.
1. a = mq + r, com q 2 Z) a¡ r = mq ) mj(a¡ r)) a
m´
r.
2. Sendo a
m´
s, temos a¡ s = mq, para algum inteiro q.
Da¶³, a = mq + s, com q e s inteiros e 0 · s < jmj = m. Pelo teorema do
algoritmo da divis~ao em Z, teorema 2.1, p¶agina 22, s ¶e o resto da divis~ao
de a por m, j¶a que o resto e o quociente dessa divis~ao s~ao ¶unicos.
3. Seja r o resto da divis~ao de a por m. Pelo item 1, a
m´
r.
Como a
m´
b, pelas propriedades da rela»c~ao de congrue^ncia m¶odulo m,
proposi»c~ao 2.8, teremos b
m´
r. Como 0 · r < m, pelo item 2 acima,
r ¶e o resto da divis~ao de b por m.
2.8 Determinando restos via congrue^ncias
Nesta se»c~ao daremos exemplos do emprego de congrue^ncias m¶odulo m no c¶alculo
de restos de divis~oes euclidianas. Note que no primeiro exemplo o dividendo con-
siderado ¶e t~ao grande que nos impede de computar o quociente da divis~ao.
Exemplo 2.2 Determinar o resto da divis~ao de 2364638 564 por 7.
Solu»c~ao
Em virtude da proposi»c~ao 2.10, basta determinar um inteiro r, com
0 · r < 7 satisfazendo 2364638 564 ´ r (mod 7).
Temos inicialmente
2364
7´
5
j¶a que 2364 deixa resto 5 quando dividido por 7.
2364
7´
5) 23642
7´
52 = 25
7´
4 :
.
: 23642
7´
4
Um Mini-Curso de Aritm¶etica dos Inteiros 40
2364
7´
5
23642
7´
4
)
) 23643
7´
5 ¢ 4 = 20
7´
6 :.: 23643
7´
6
2364
7´
5
23643
7´
6
)
) 23644
7´
5 ¢ 6 = 30
7´
2 :
.
: 23644
7´
2
E ainda
23645
7´
23644 ¢ 2364
7´
2 ¢ 5 = 10
7´
3
23646
7´
23645 ¢ 2364
7´
3 ¢ 5 = 15
7´
1, e esta ¶e uma boa not¶³cia!
Como 23646
7´
1, se escrevermos 638 564 = 6m+ s, teremos
2364638 564 = 23646m+s = 23646m ¢ 2364s
= (23646)
m ¢ 2364s
7´
1m ¢ 2364s = 2364s
Dividindo 638 564 por 6, obtemos 638 564 = 6m+ 2, logo s = 2 e ent~ao
2364638 564
7´
2364s = 23642
7´
4, e portanto o resto da divis~ao de 2364638 564
por 7 ¶e igual a 4.
Exemplo 2.3 Dado um n¶umero inteiro N > 0, seja
N = asas¡1 : : : a1a0 = (asas¡1 : : : a1a0)10
a sua representa»c~ao decimal, isto ¶e,
N = as ¢ 10s + as¡1 ¢ 10s¡1 + ¢ ¢ ¢+ a1 ¢ 10 + a0
com os \algarismos" as; as¡1; : : : ; a1; a0 todos no conjunto f0; 1; : : : ; 9g.
Por exemplo, quando escrevemos 46 728, estamos na verdade simbolizando
o n¶umero
(46728)10 = 40000 + 6000 + 700 + 20 + 8
= 4 ¢ 104 + 6 ¢ 103 + 7 ¢ 102 + 2 ¢ 10 + 8
Mostrar que o resto da divis~ao de N por 11 ¶e o resto da divis~ao do inteiro
a0 ¡ a1 + a2 ¡ : : :+ (¡1)sas por 11.
Considere a representa»c~ao decimal de N como acima. Em termos de con-
grue^ncia m¶odulo 11, podemos simpli¯car as pote^ncias de 10 que aparecem na
representa»c~ao de N como segue.
Um Mini-Curso de Aritm¶etica dos Inteiros 41
1
1´1
1
10
1´1
¡1
102
1´1
(¡1)2 = 1
103
1´1
(¡1)3 = ¡1
...
10s
1´1
(¡1)s
Sendo assim, utilizando as propriedades descritas no teorema 2.9, teremos:
a0
1´1
a0
a1 ¢ 10
1´1
a1 ¢ (¡1) = ¡a1
a2 ¢ 102
1´1
a2 ¢ (¡1)2 = a2
a3 ¢ 103
1´1
a3 ¢ (¡1)3 = ¡a3
...
as ¢ 10s
1´1
as ¢ (¡1)s
de onde, somando-se todas estas congrue^ncias membro a membro, chegamos a
as ¢ 10s + as¡1 ¢ 10s¡1 + ¢ ¢ ¢+ a1 ¢ 10 + a0
1´1
a0 ¡ a1 + a2 ¡ : : :+ (¡1)sas,
ou seja,
N
1´1
a0 ¡ a1 + a2 ¡ : : :+ (¡1)sas.
Pelo teorema 2.10, N e a0¡ a1+ a2¡ : : :+(¡1)sas deixam o mesmo resto
quando divididos por 11, que ¶e o que quer¶³amos demonstrar.
O resultado aqui obtido d¶a origem a um crit¶erio de divisibilidade por 11:
Um inteiro positivo N = (asas¡1 : : : a1a0)10 ¶e divis¶³vel por 11 se e somente
se a soma alternada de seus algarismos, a0¡a1+a2¡ : : :+(¡1)sas, ¶e divis¶³vel
por 11.
Por exemplo, qual seria o resto da divis~ao do inteiro
34 628 702 016 322 112 985 531
por 11?
Temos que 1¡ 3+ 5¡ 5 + 8¡ 9 + 2¡ 1 + 1+ 2¡ 2 + 3¡ 6+ 1¡ 0 + 2¡
0 + 7¡ 8 + 2¡ 6 + 4¡ 3 = ¡5
1´1
6, portanto o resto procurado ¶e 6.
2.8.1 Problemas Complementares
1. °^. . Encontre todos os inteiros x satisfazendo
Um Mini-Curso de Aritm¶etica dos Inteiros 42
(a) 2x ´ x (mod 5) (b) 2x ´ 4 (mod 6) (c) 25 ´ 4 (mod x)
(d) x2 ´ 1 (mod 8) [Sugest~ao: escreva x = 4m+ r, com 0 · r < 4]
(e) x2 ´ x (mod 4)
2. °. . Seja n um inteiro positivo e seja n = (asas¡1 : : : a2a1a0)10 a sua repre-
senta»c~ao no sistema decimal, isto ¶e, n = as¢10s+as¡1¢10s¡1+¢ ¢ ¢+a1¢10+a0,
com as; as¡1; : : : ; a1; a0 todos algarismos do conjunto f0; 1; : : : ; 9g.
Demonstre os seguintes crit¶erios de divisibilidade:
(a) n ¶e divis¶³vel por 3 , as + as¡1 + ¢ ¢ ¢+ a1 + a0 ¶e divis¶³vel por 3.
(b) n ¶e divis¶³vel por 4 , o n¶umero (a1a0)10 ¶e divis¶³vel por 4 , 2a1 + a0
¶e divis¶³vel por 4.
(c) n ¶e divis¶³vel por 9 , as + as¡1 + ¢ ¢ ¢+ a1 + a0 ¶e divis¶³vel por 9.
(d) n ¶e divis¶³vel por 8 , o n¶umero (a2a1a0)10 ¶e divis¶³vel por 8 , 4a2 +
2a1 + a0 ¶e divis¶³vel por 8.
3. °. . Considere n como no exerc¶³cio anterior. Mostre que o resto da divis~ao
de n por 6 ¶e o resto da divis~ao de 4(as+as¡1+ ¢ ¢ ¢ a1)+a0 por 6. Utilizando
este resultado, determine o resto da divis~ao de 123 456 789 987 654 321 por
6.
4. °_. . Utilizando congrue^ncias, estabele»ca crit¶erios de divisibilidade
(a) por 7 (b) por 13 (c) por 12 (d) por 16
5. °. . Mostre que 22225555 + 55552222 ¶e divis¶³vel por 231. [Sugest~ao: Note
que 231 = 3 ¢ 7 ¢ 11. Mostre que o n¶umero dado ¶e divis¶³vel por 3, por 7 e
por 11].
6. °. . Qual ¶e o algarismo das unidades do inteiro dado no problema anteri-
or? Quais s~ao seus dois ¶ultimos algarismos? [Sugest~ao: O algarismo das
unidades de um inteiro positivo ¶e o resto da divis~ao desse inteiro por 10.
Seus dois ¶ultimos algarismos constituem o resto da divis~ao dele por 100].
7. °. . Veri¯que se 271958 ¡ 108878 + 101528 ¶e divis¶³vel por 26460.
8. °_. . Determine o algarismo das unidades de cada um dos seguintes inteiros:
(a) 78
9
(b) 9998
97
(c) 88
8
(d) 7777
77
[Observa»c~ao: A nota»c~ao ab
c
signi¯ca a(b
c)].
9. °. . Determine o resto da divis~ao de 10+1010+10102 +10103 + ¢ ¢ ¢+101010
por 7.
10. °. . Seja n um inteiro positivo e seja n = (asas¡1 : : : a1a0)10 a sua repre-
senta»c~ao no sistema decimal. Mostre que n ¶e divis¶³vel por 7 se e somente
se o inteiro (asas¡1 : : : a2a1)10 ¡ 2a0 ¶e divis¶³vel por 7. [Sugest~ao: Sendo
N = (asas¡1 : : : a2a1)10, temos, n = 10N + a0. Veri¯que ent~ao que
n
7´
0, 10N + a0
7´
0, 20N + 2a0
7´
0, N ¡ 2a0
7´
0]:
Um Mini-Curso de Aritm¶etica dos Inteiros 43
11. °. . Sejam p e q inteiros primos entre si. Mostre que as congrue^ncias
x ´ a (mod p); x ´ b (mod q)
podem ser resolvidas simultaneamente para algum x 2 Z. [Sugest~ao: Sendo
p e q primos entre si, existem inteiros r e s tais que rp+ sq = 1.]