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, relembramos 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 u¶ltimo
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 a 6
j 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 a 6
= 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. °
= q.
^ Sejam m, n, p e q inteiros positivos, com p e q primos e p 6
(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 pn qm ?
(c) Como podemos determinar o n¶
umero de divisores positivos de um inteiro dado? Como podemos list¶a-los (metodicamente)? Exempli¯que
tomando o inteiro 2 200.
. . Mostre que para cada n 2 N, 7j(32n+1 + 2n+2 ).
3. °
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 d 6
= 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 u
¶nicos.
A vers~ao mais u
¶til 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 d 6
= 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 u¶nicos.
2.4.1
Exemplos ilustrando o teorema 2.1
Antes de procedermos µa prova do teorema do algoritmo da divis~ao em Z, ilustraremos seu enunciado com exemplos simples. Entendemos que isto se faz necess¶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
resto ¡! 3
10
2
á quociente
Na divis~ao de ¡23 por 10 ser¶³amos tentados a fazer
¡23 10
¡3 ¡2
¶ claro que ¡23 = 10 ¢ (¡2) + (¡3), mas se quisermos o resto r nas
E
condi»c~oes do teorema 2.1 (r n~ao negativo e menor que o valor absoluto do divisor),
23
Um Mini-Curso de Aritm¶
etica dos Inteiros
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
¡24
4
0 ¡6
24 ¡4
0 ¡6
¡24 ¡4
0
6
Outros exemplos:
24 4
0 6
23 2
1 11
¡23
1
2
¡12
23
1
¡2
¡11
¡23 ¡2
1 ¡12
Os exemplos acima nos sugerem as adapta»co~es 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. Exist^encia 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 = dq 0 + r, com 0 · r < jdj, sendo q 0 = §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, respectivamente, d > 0 ou d < 0, logo n = d(§q) + 0.
Um Mini-Curso de Aritm¶
etica dos Inteiros
24
Se r 6
= 0, teremos
n =
=
=
=
¡jdjq ¡ r
¡jdjq ¡ jdj + jdj ¡ r
jdj(¡q ¡ 1) + (jdj ¡ r)
dq 0 + r0 ;
sendo q 0 = ¨(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 d 6
= 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 ¡ q2 j = jr2 ¡ r1 j
Sendo 0 · r1 ; r2 < jdj, temos ent~ao jr2 ¡ r1 j < jdj (prove isto, como
exerc¶³cio).
Da¶³,
jdj ¢ jq1 ¡ q2 j = jr2 ¡ r1 j < jdj ) jq1 ¡ q2 j < 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
2.5
25
M¶
aximo Divisor Comum
Se x e a s~ao inteiros, com a 6
= 0, e xja ent~ao jxj · jaj. De fato, como a = xc
para algum inteiro c e c 6
= 0 (pois a 6
= 0), temos jcj ¸ 1, e logo
jxj = jxj ¢ 1 · jxjjcj = jxcj = jaj ) jxj · jaj
Assim sendo, se a 6
= 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 a 6
= 0 ou b 6
= 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 a 6
= 0)
ou jxj · jbj (se b 6
= 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 a 6
= 0 ou b 6
= 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 a 6
= 0 ou b 6
= 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 a 6
= 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 a 6
= 0 ou b 6
= 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 a 6
= 0 ou b 6
= 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 a 6
= 0 ou b 6
= 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 = min L, 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 = m0 a + n0 b; para certos m0 ; n0 2 Z:
Ent~ao teremos
r =
=
=
=
Finalmente observamos:
a ¡ dq
a ¡ (m0 a + n0 b)q
(1 ¡ m0 q)a + (¡n0 q)b
m0 a + n0 b
27
Um Mini-Curso de Aritm¶
etica dos Inteiros
(1) r = m0 a + n0 b, com m0 ; n0 2 Z
(2) r = 0 ou 0 < r < d
(3) d = m0 a + n0 b ¶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 condi»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(m0 a + n0 b) ) 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 a 6
= 0 ou b 6
= 0, temos que
d = mdc (a; b), isto ¶e, min L = 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 b 6
= 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 2 M .
(ii) M ½ A:
Um Mini-Curso de Aritm¶
etica dos Inteiros
28
Seja y um elemento de M .
y 2 M ) 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 dados, temos:
8
< (1) d ¸ 0
d = mdc (a; b) ,
(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 a 6
= 0 ou b 6
= 0. Por (2), d 6
= 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. °
u^encia in¯nita de in^ Descreva, enumerando-os na forma de uma seqÄ
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
. . Mostre que existem in¯nitos pares de inteiros (r; s) satisfazendo
3. °
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»co~es. 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].
. . Mostre que se m e n s~ao inteiros primos entre si, ent~ao existem inteiros
4. °
x e y tais que
1
x
y
=
+
mn
m n
..
°
_ A partir deste fato, justi¯que o seguinte argumento:
Sendo m e n inteiros positivos primos entre si, se uma circunfer^encia 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Äu^encia ¯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
21
35
2
Um Mini-Curso de Aritm¶
etica dos Inteiros
30
Consideramos ent~ao o divisor 35 e o resto 21 dessa primeira divis~ao e efetuamos 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
7
14
1
Finalmente, chegamos µa divis~ao exata
14 7
0 2
Tendo chegado a um resto igual a zero, o algoritmo termina. O u¶ltimo
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 b 6
= 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Äu^encia 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+1
rk
¤
31
Um Mini-Curso de Aritm¶
etica dos Inteiros
e se rk = 0, a seqÄu^encia termina em rk . Ent~ao a seqÄu^encia 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
eS6
= ¿, 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
u^encia de¯nida
inteiros ambos positivos com a ¸ b e seja r1 ; r2 ; : : : ; rn ; rn+1 a seqÄ
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 =
=
=
=
=
=
=
2.5.3
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)
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
7
14
1
14 7
0 2
Um Mini-Curso de Aritm¶
etica dos Inteiros
32
As tr^es 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 tr^es 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
. . Em cada caso, calcule mdc (a; b) pelo algoritmo Euclidiano (divis~oes
1. °
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 a 6
= 0 ou b 6
= 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 p 6
= 0, p 6
= §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
p6
j 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 p 6
j a.
Se p 6
j 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(a1 a2 : : : 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 a1 a2 : : : ak ak+1 e suponhamos que pja1 a2 : : : ak ak+1 . Ent~ao pj(a1 a2 ¢ ¢ ¢ ak )ak+1 . Pela proposi»c~ao 2.4,
pj(a1 a2 ¢ ¢ ¢ 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 u¶nicos, 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.
Exist^encia 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 exist^encia da decomposi»c~ao de m em seus fatores primos.
Se m = 2, ent~ao m ¶e primo (prove). Temos ent~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.
Se m = 2, obviamente n~ao ser¶a poss¶³vel termos m = 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¡1 pn = q1 ¢ ¢ ¢ qs¡1 qs ,
temos que pn j(q1 ¢ ¢ ¢ qs ) e qs j(p1 ¢ ¢ ¢ pn ).
Pelo corol¶ario 2.4, temos que pn jqi e qs jpj 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¡1 pn = q1 ¢ ¢ ¢ qs¡1 qs 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 u¶nica.
Demonstra»c~ao. Pelo teorema fundamental da aritm¶etica, m ¶e um produto de fatores primos q1 ¢ ¢ ¢ qn , com q1 · : : : · qn (n ¸ 1). Agrupando-se os fatores primos
repetidos na forma de pot^encias de primos, temos a representa»c~ao enunciada neste
corol¶ario. Ademais, pelo teorema fundamental da aritm¶etica, tal representa»c~ao ¶e
u¶nica.
Corol¶
ario 2.6 Seja m um inteiro, m = p®1 1 ¢ ¢ ¢ 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¯1 1 ¢ ¢ ¢ 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¯1 1 ¢ ¢ ¢ 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®1 1 ¢ ¢ ¢ p®nn = p¯1 1 ¢ 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¯1 1 ¢ 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 ; ¯i g.
2.6.1
Problemas Complementares
..
1. °
umeros racionais) Usando o Teorema
_ (Admita familiaridade com os n¶
Fundamental da Aritm¶etica, mostre que se p > 0 ¶e primo ent~ao
p
p
(a) p ¶e irracional
(b) n p ¶e irracional, para cada n ¸ 3
. . Seja a um inteiro positivo. Mostre que se cada primo positivo p, com
2. °
p
p · a, n~ao ¶e fator de a, ent~ao a ¶e primo. [Sugest~ao: Mostre
p que se a > 0
n~ao ¶e primo, ent~ao a possui um fator primo p, com p · a. Para isso,
supondo que a n~ao ¶e primo, decomponha-o na forma a = p1 p2 : : : pn , com
p
n ¸ 2 e p1 ; : : : ; pn todos primos. Se, para cada ¶³ndice i tivermos pi > a,
ent~ao teremos a2 = p21 p22 : : : p2n > 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
Congru^
encia m¶
odulo m em Z
De¯ni»c~
ao 2.6 Dados tr^es inteiros a, b e m, dizemos que a ¶e congruente a b
m¶odulo m, e denotamos a ´ b (mod m) ou a ´ b se m divide a ¡ b.
m
Observa»c~
ao 2.4 Alternativamente, temos que dados tr^es 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 congru^encia m¶odulo m, de¯nida em Z conforme a de¯ni»c~ao 2.6, ¶e uma rela»c~ao de equival^encia em Z, ou seja,
satisfaz µas seguintes tr^es propriedades:
1. 8a 2 Z, a ´ a;
m
2. 8a; b 2 Z, se a ´
b ent~ao b ´
a;
m
m
beb´
c ent~ao a ´
c.
3. 8a; b; c 2 Z, se a ´
m
m
m
Demonstra»c~ao. Para cada a, cada b e cada c, todos inteiros, temos:
1. mj0 ) mj(a ¡ a) ) a ´
a
m
2. a ´
b ) mj(a ¡ b) ) mj ¡ (a ¡ b) ) mj(b ¡ a) ) b ´
a
m
m
3. a ´m b e b ´m c ) mj(a ¡ b) e mj(b ¡ c) ) mj[(a ¡ b) + (b ¡ c)] )
mj(a ¡ c) ) a ´
c
m
Proposi»c~
ao 2.9 (Compatibilidade de ´
com as opera»c~
oes em Z)
m
Seja m um inteiro ¯xado. Dados a; b; c e d inteiros, e n natural, tem-se:
1. a ´
b,a+c´
b+c
m
m
)
a´
b
m
2.
)a+c´
b+d
m
c´
d
m
Um Mini-Curso de Aritm¶
etica dos Inteiros
38
3. a ´
b ) ac ´
bc
m
m
)
a´b
m
4.
) ac ´
bd
m
d
c´
m
b ) an ´
bn
5. a ´
m
m
Demonstra»c~ao.
1. a ´
b , mj(a ¡ b) , mj[(a + c) ¡ (b + c)] , a + c ´
b+c
m
m
2.
b
a´
m
d
c´
m
)
) mj(a ¡ b) e mj(c ¡ d)
)
)
)
mj[(a ¡ b) + (c ¡ d)]
mj[(a + c) ¡ (b + d)]
a+c´b+d
m
3. a ´
b ) mj(a ¡ b) ) mj(a ¡ b)c ) mj(ac ¡ bc) ) ac ´
bc
m
m
)
(
)
a´
ac
´
b
bc
m
m
4.
)
) ac ´
bd
m
d
bd
c´
bc
´
m
m
5. A prova ¶e feita por indu»c~ao sobre n (exerc¶³cio para o leitor).
Observa»c~
ao 2.5 (Congru^
encias Irrelevantes)
1. Se m = 0, dados dois inteiros a e b,
a´
b,a´
b , 0j(a ¡ b) , a ¡ b = 0 , a = b
m
0
Assim, a rela»c~ao de congru^encia m¶odulo 0 coincide com a rela»c~ao de igualdade em Z.
2. Se m = 1, dados dois inteiros a e b,
b,a´
b , 1j(a ¡ b)
a´
m
1
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 congru^encias m¶odulo 0 e m¶odulo 1 s~ao
casos desinteressantes de congru^encia.
3. Dado m 2 Z e inteiros a e b,
a´
b , mj(a ¡ b) , (¡m)j(a ¡ b) , a ´
b
m
¡m
Assim, as congru^encias m¶odulo m e m¶odulo ¡m s~ao a mesma rela»c~ao de
congru^encia.
Em vista das tr^es observa»co~es feitas a partir dos itens 1, 2 e 3 acima, doravante trataremos de estudar a rela»c~ao de congru^encia m¶odulo m em Z
apenas para m ¸ 2.
Um Mini-Curso de Aritm¶
etica dos Inteiros
39
Proposi»c~
ao 2.10 (Congru^
encia 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 ´
r
m
2. Se a ´
s (s 2 Z) e 0 · s < m ent~ao s ¶e o resto da divis~ao de a por m.
m
3. a ´
b , os restos das divis~oes de a e b por m s~ao iguais.
m
Demonstra»c~ao.
1. a = mq + r, com q 2 Z ) a ¡ r = mq ) mj(a ¡ r) ) a ´
r.
m
2. Sendo a ´
s, temos a ¡ s = mq, para algum inteiro q.
m
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 u¶nicos.
3. Seja r o resto da divis~ao de a por m. Pelo item 1, a ´
r.
m
Como a ´ b, pelas propriedades da rela»c~ao de congru^encia m¶odulo m,
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 congru^
encias
Nesta se»c~ao daremos exemplos do emprego de congru^encias m¶odulo m no c¶alculo
de restos de divis~oes euclidianas. Note que no primeiro exemplo o dividendo considerado ¶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 ´
5
7
j¶a que 2364 deixa resto 5 quando dividido por 7.
2364 ´
5 ) 23642 ´
52 = 25 ´
4 :.: 23642 ´
4
7
7
7
7
Um Mini-Curso de Aritm¶
etica dos Inteiros
2364 ´
5
7
2
2364 ´
4
7
2364 ´ 5
7
23643 ´
6
7
40
)
) 23643 ´
5 ¢ 4 = 20 ´
6 :.: 23643 ´
6
7
7
7
)
) 23644 ´
5 ¢ 6 = 30 ´
2 :.: 23644 ´
2
7
7
7
E ainda
23644 ¢ 2364 ´
2 ¢ 5 = 10 ´
3
23645 ´
7
7
7
23646 ´
23645 ¢ 2364 ´
3 ¢ 5 = 15 ´
1, e esta ¶e uma boa not¶³cia!
7
7
7
Como 23646 ´
1, se escrevermos 638 564 = 6m + s, teremos
7
2364638 564 = 23646m+s
= 23646m ¢ 2364s
m
= (23646 ) ¢ 2364s
´
1m ¢ 2364s = 2364s
7
Dividindo 638 564 por 6, obtemos 638 564 = 6m + 2, logo s = 2 e ent~ao
2364638 564 ´
2364s = 23642 ´
4, e portanto o resto da divis~ao de 2364638 564
7
7
por 7 ¶e igual a 4.
Exemplo 2.3 Dado um n¶umero inteiro N > 0, seja
N = as as¡1 : : : a1 a0 = (as as¡1 : : : a1 a0 )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)s as por 11.
Considere a representa»c~ao decimal de N como acima. Em termos de congru^encia m¶odulo 11, podemos simpli¯car as pot^encias de 10 que aparecem na
representa»c~ao de N como segue.
Um Mini-Curso de Aritm¶
etica dos Inteiros
1 ´
11
10 ´
11
102 ´
11
103 ´
11
..
.
s
10 ´
11
41
1
¡1
(¡1)2 = 1
(¡1)3 = ¡1
(¡1)s
Sendo assim, utilizando as propriedades descritas no teorema 2.9, teremos:
a0 ´
11
a0
a1 ¢ 10 ´
11
a1 ¢ (¡1) = ¡a1
a3 ¢ 103 ´
11
..
.
as ¢ 10s ´
11
a3 ¢ (¡1)3 = ¡a3
a2 ¢ 102 ´
11
a2 ¢ (¡1)2 = a2
as ¢ (¡1)s
de onde, somando-se todas estas congru^encias membro a membro, chegamos a
a0 ¡ a1 + a2 ¡ : : : + (¡1)s as ,
as ¢ 10s + as¡1 ¢ 10s¡1 + ¢ ¢ ¢ + a1 ¢ 10 + a0 ´
11
ou seja,
N´
a0 ¡ a1 + a2 ¡ : : : + (¡1)s as .
11
Pelo teorema 2.10, N e a0 ¡ a1 + a2 ¡ : : : + (¡1)s as 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 = (as as¡1 : : : a1 a0 )10 ¶e divis¶³vel por 11 se e somente
se a soma alternada de seus algarismos, a0 ¡ a1 + a2 ¡ : : : + (¡1)s as , ¶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 ´
6, portanto o resto procurado ¶e 6.
11
2.8.1
Problemas Complementares
..
1. °
^ Encontre todos os inteiros x satisfazendo
42
Um Mini-Curso de Aritm¶
etica dos Inteiros
(a) 2x ´ x (mod 5)
(d) x2 ´ 1
(b) 2x ´ 4 (mod 6)
(c) 25 ´ 4
(mod x)
(mod 8) [Sugest~ao: escreva x = 4m + r, com 0 · r < 4]
(e) x2 ´ x (mod 4)
. . Seja n um inteiro positivo e seja n = (a a : : : a a a ) a sua repre2. °
s s¡1
2 1 0 10
s
senta»c~ao no sistema decimal, isto ¶e, n = as ¢10 +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 (a1 a0 )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 (a2 a1 a0 )10 ¶e divis¶³vel por 8 , 4a2 +
2a1 + a0 ¶e divis¶³vel por 8.
. . Considere n como no exerc¶³cio anterior. Mostre que o resto da divis~ao
3. °
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 congru^encias, estabele»ca crit¶erios de divisibilidade
(a) por 7
(b) por 13
(c) por 12
(d) por 16
. . Mostre que 22225555 + 55552222 ¶e divis¶³vel por 231. [Sugest~ao: Note
5. °
que 231 = 3 ¢ 7 ¢ 11. Mostre que o n¶umero dado ¶e divis¶³vel por 3, por 7 e
por 11].
. . Qual ¶e o algarismo das unidades do inteiro dado no problema anteri6. °
or? Quais s~ao seus dois u¶ltimos algarismos? [Sugest~ao: O algarismo das
unidades de um inteiro positivo ¶e o resto da divis~ao desse inteiro por 10.
Seus dois u¶ltimos algarismos constituem o resto da divis~ao dele por 100].
. . Veri¯que se 271958 ¡ 108878 + 101528 ¶e divis¶³vel por 26460.
7. °
..
8. °
_ Determine o algarismo das unidades de cada um dos seguintes inteiros:
9
97
8
77
(a) 78
(b) 9998
(c) 88
(d) 7777
c
c
[Observa»c~ao: A nota»c~ao ab signi¯ca a(b ) ].
. . Determine o resto da divis~ao de 10 + 1010 + 10102 + 10103 + ¢ ¢ ¢ + 101010
9. °
por 7.
. . Seja n um inteiro positivo e seja n = (a a : : : a a ) a sua repre10. °
s s¡1
1 0 10
senta»c~ao no sistema decimal. Mostre que n ¶e divis¶³vel por 7 se e somente
se o inteiro (as as¡1 : : : a2 a1 )10 ¡ 2a0 ¶e divis¶³vel por 7. [Sugest~ao: Sendo
N = (as as¡1 : : : a2 a1 )10 , temos, n = 10N + a0 . Veri¯que ent~ao que
n´
0 , 10N + a0 ´
0 , 20N + 2a0 ´
0 , N ¡ 2a0 ´
0]:
7
7
7
7
Um Mini-Curso de Aritm¶
etica dos Inteiros
43
. . Sejam p e q inteiros primos entre si. Mostre que as congru^encias
11. °
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.]