Propriedades dos inteiros
Teorema (Algoritmo da Divisão)
Sejam a e b números inteiros, com b > 0. Então existem números
inteiros q e r , únicos e tais que a = bq + r , com 0 ≤ r < b.
Demonstração. Existência:
Consideremos S = {a − bk | k ∈ Z ∧ a − bk ≥ 0}.
Se 0 ∈ S, então b divide a. Fazendo q = a/b e r = 0 temos o pretendido.
Suponhamos agora que 0 ∈
/ S. Como 0 ∈
/ S, temos que ∀k ∈ Z, a 6= bk, ou
seja, b não divide a, donde a 6= 0. Se a > 0, a − b · 0 ∈ S; se a < 0,
a − b(2a) = a(1 − 2b) ∈ S. Assim, pelo Princı́pio de Boa Ordenação, podemos
afirmar que S tem um elemento mı́nimo, digamos r = a − bq, para algum
q ∈ Z. Assim obtemos que a = bq + r e r ≥ 0 (por definição de S), faltando
provar que r < b.
Suponhamos que r > b, então a − b(q + 1) = a − bq − b = r − b > 0. Deste
modo a − b(q + 1) ∈ S e a − b(q + 1) < a − bq, o que não pode ser, pois a − bq
é o elemento mı́nimo de S. Portanto, r ≤ b. Se r = b, então b = a − bq, isto
é, a − b(q + 1) = 0. Assim 0 ∈ S o que contradiz a hipótese. Logo r < b.
Unicidade de q e de r :
Suponhamos que a = bq + r , com 0 ≤ r < b e a = bq 0 + r 0 , com 0 ≤ r 0 < b.
Podemos supor que r 0 ≥ r . Temos que bq + r = bq 0 + r 0 , ou seja,
b(q − q 0 ) = r 0 − r . Como b divide r 0 − r e 0 ≤ r 0 − r ≤ r 0 < b, temos que
r 0 − r = 0. Logo r 0 = r e consequentemente
q 0 = q.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
32 / 68
Propriedades dos inteiros
Os inteiros a e b referidos no teorema anterior designam-se por dividendo
e divisor, respectivamente. Os inteiros q e r designam-se,
respectivamente, por quociente e resto da divisão de a por b.
Exemplo
Para a = 27 e b = 6, o algoritmo da divisão dá 27 = 6 · 4 + 3.
O algoritmo da divisão, para a e b inteiros positivos, pode ser descrito da
forma seguinte.
Algoritmo (Algoritmo da divisão)
Input: dois números inteiros positivos a e b (a ≥ b)
q ← 0; r ← 0;
while (a − q ∗ b ≥ b) do
q ← q + 1;
r ← a − q ∗ b;
fim;
Output: dois números inteiros q e r tais que a = bq + r e 0 ≤ r < b
Álgebra (Curso de CC)
Ano lectivo 2005/2006
33 / 68
Propriedades dos inteiros
Exercı́cio
Escreva uma função GAP que efectue o algoritmo da divisão. Dados os
inteiros positivos a e b deve devolver os valores de q e de r numa lista da
forma [q, r ].
Crie uma outra função que permita testar a função acabada de construir
com valores gerados aleatoriamente (use a função RandomList).
No GAP as funções QuoInt e RemInt permitem calcular,
respectivamente, o quociente e o resto da divisão de dois números
inteiros positivos. A função QuotientRemainder devolve uma lista com
o quociente e o resto da divisão de dois números inteiros positivos. O
operador mod calcula o resto da divisão de dois números inteiros
quaisquer (sendo o divisor não nulo).
gap>
4
3
gap>
[ 4,
gap>
3
QuoInt(27,6); RemInt(27,6);
QuotientRemainder(27,6);
3 ]
27 mod 6;
Álgebra (Curso de CC)
Ano lectivo 2005/2006
34 / 68
Propriedades dos inteiros
Exercı́cio
Em Illinois (EUA) os últimos três dı́gitos da carta de condução são
determinados pela fórmula: 31(m − 1) + d + s, onde m é o número
correspondente ao mês de nascimento, d é o dia de nascimento e s vale 0
se for homem e 600 se for mulher.
Escreva um programa no GAP que, dados os três últimos dı́gitos de uma
carta de condução emitida em Illinois, determine o sexo, o mês e o dia de
nascimento do condutor.
Teste o programa para os seguintes casos: 972 = 31 · 11 + 31 (mulher
que nasceu em Dezembro, mês 12, no dia 31); 341 = 31 · 10 + 31
(número inválido); 001 = 31 · 0 + 1 (homem que nasceu em Janeiro, mês
1, no dia 1).
Álgebra (Curso de CC)
Ano lectivo 2005/2006
35 / 68
Propriedades dos inteiros
Definição (Máximo Divisor Comum)
O máximo divisor comum de dois inteiros a e b não simultaneamente
nulos é o maior de todos os divisores comuns a ambos. Vamos denotar
este inteiro por mdc(a, b).
Note-se que, se d divide a e b, então −d também divide a e b. Assim,
pretendendo encontrar o maior de todos os divisores comuns de dois
inteiros, basta considerar divisores positivos, como se afirma na primeira
parte da seguinte nota.
Nota
Sendo a e b inteiros não simultaneamente nulos,
(i) mdc(a, b) = max{k ∈ N | k|a ∧ k|b};
(ii) mdc(a, b) = mdc(b, a);
(iii) mdc(a, 0) =| a |.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
36 / 68
Propriedades dos inteiros
No GAP a função DivisorsInt dá uma lista dos divisores positivos de
um inteiro não nulo.
Exemplo
Determinação (pela definição) de mdc(16, 20) (fazendo uso do GAP):
gap>
[ 1,
gap>
[ 1,
gap>
[ 1,
gap>
4
D16:=DivisorsInt(16);
2, 4, 8, 16 ]
D20:=DivisorsInt(20);
2, 4, 5, 10, 20 ]
DC:=Intersection(D16,D20);
2, 4 ]
Maximum(DC);
Exercı́cio
Construa uma função GAP para determinar o máximo divisor comum de
dois números inteiros não simultaneamente nulos, com base na definição.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
37 / 68
Propriedades dos inteiros
Proposição (Euclides)
Sejam a e b inteiros positivos e seja a = qb + r , com q, r ∈ Z e
0 ≤ r < b. Então mdc(a, b) = mdc(b, r ).
Demonstração. Para provar que mdc(a, b) = mdc(b, r ) basta provar que
{k ∈ N | k|a ∧ k|b} = {k ∈ N | k|b ∧ k|r }.
⊆: Se k | a e k | b, para algum k ∈ N, então k | a − qb = r .
⊇: Se k | b e k | r = a − qb, para algum k ∈ N, então k | a − qb + qb = a.
Exemplo
Vamos determinar mdc(154, 105).
154 = 105 · 1 + 49
105 = 49 · 2 + 7
49 = 7 · 7 + 0
(mdc(154, 105) = mdc(105, 49))
(mdc(105, 49) = mdc(49, 7))
(mdc(49, 7) = mdc(7, 0))
Assim, mdc(154, 105) = mdc(105, 49) = mdc(49, 7) = mdc(7, 0) = 7.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
38 / 68
Propriedades dos inteiros
Este processo (designado por Algoritmo de Euclides) permite determinar
mdc(a, b), a e b inteiros positivos, realizando divisões sucessivas de
forma a encontrar uma sequência decrescente de inteiros
r1 > r2 > ... > rk tais que:
a = bq1 + r1
b = r1 q2 + r2
r1 = r2 q3 + r3
···
rk−2 = rk−1 qk + rk
rk−1 = rk qk+1 + 0
0 < r1
0 < r2
0 < r3
···
0 < rk
<b
< r1
< r2
< rk−1
mdc(a, b) é igual a rk , o resto que antecede o resto nulo.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
39 / 68
Propriedades dos inteiros
Algoritmo (Algoritmo de Euclides)
Input: dois números inteiros positivos a e b
r1 ← a; r2 ← b;
while r2 6= 0 do
r0 ← r1 ;
r1 ← r2 ;
r2 ← r0 mod r1 ;
end;
Output: r1 , o maximo divisor comum de a e b
Exercı́cio
Construa uma função GAP que, dados dois números inteiros positivos,
determine através do Algoritmo de Euclides o seu máximo divisor comum.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
40 / 68
Propriedades dos inteiros
Exemplo
Vamos aplicar o Algoritmo de Euclides para determinar mdc(3150, 495).
3150
495
180
135
=
=
=
=
495 · 6 + 180
180 · 2 + 135
135 · 1 + 45
45 · 3 + 0
Resulta que mdc(3150, 495) = 45.
As igualdades anteriores permitem escrever 45 como uma combinação
linear de 3150 e 495:
45 = mdc(3150, 495)
=
=
=
=
=
=
180 − 135 · 1
180 − 1 · (495 − 2 · 180)
3 · 180 − 1 · 495
3 · (3150 − 6 · 495) − 1 · 495
3 · 3150 − 19 · 495
3 · 3150 + (−19) · 495
Encontrámos inteiros x e y (x = 3 e y = −19) tais que
mdc(3150, 495) = x · 3150 + y · 495.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
41 / 68
Propriedades dos inteiros
Teorema (MDC como combinação linear)
Sejam a e b inteiros não simultaneamente nulos. Então existem inteiros
x e y tais que mdc(a, b) = xa + yb. Além disso, mdc(a, b) é o menor
inteiro positivo da forma xa + yb.
Demonstração. Seja S = {ma + nb | m, n inteiros e ma + nb > 0}. Como S é
não vazio (se uma escolha de m e n faz ma + nb < 0, então substitui-se m e n
por −m e −n, obtendo, assim, um elemento de S), o Princı́pio de Boa
Ordenação diz que S tem um elemento mı́nimo, digamos d = xa + yb, onde x
e y são inteiros.
Vejamos que d = mdc(a, b). O Algoritmo da Divisão permite escrever
a = dq + r , com 0 ≤ r < d. Vamos supor que r > 0. Assim,
r = a − dq = a − (xa + yb)q = a − xaq − ybq = (1 − xq)a + (−yq)b ∈ S,
contradizendo o facto de que d é o elemento mı́nimo de S. Logo r = 0 e d
divide a. De forma análoga prova-se que d divide b. Isto prova que d é um
divisor comum de a e b.
Resta provar que d é o menor divisor comum de a e b. Suponhamos que d 0 é
outro divisor comum de a e b. Então, para alguns g e h inteiros, a = d 0 g e
b = d 0 h. Assim, d = xa + yb = x(d 0 g ) + y (d 0 h) = d 0 (xg + yh), portanto d 0 é
um divisor de d. Logo, d é o maior de todos os divisores comuns a a e b.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
42 / 68
Propriedades dos inteiros
Algoritmo (Algoritmo de Euclides - versão alargada)
Input: dois números inteiros positivos a e b
r1 ← a; r2 ← b;
x1 ← 1; x2 ← 0;
y1 ← 0; y2 ← 1; while r2 6= 0 do
r0 ← r1 ; r1 ← r2 ;
x0 ← x1 ; x1 ← x2 ;
y0 ← y1 ; y1 ← y2 ;
q ← QuocienteInteiro(r0 , r1 );
r2 ← r0 − q ∗ r1 ;
x2 ← x0 − q ∗ x1 ;
y2 ← y0 − q ∗ y1 ;
end;
Output: inteiros x1 e y1 tais que r1 = mdc(a, b) = x1 a + y1 b
Álgebra (Curso de CC)
Ano lectivo 2005/2006
43 / 68
Propriedades dos inteiros
Existem no GAP as funções GcdInt e Gcdex para determinar o máximo
divisor comum de dois inteiros não simultaneamente nulos. Esta última,
encontra os números necessários para escrever o máximo divisor comum
como uma combinação linear.
gap> GcdInt(2520,154);
14
gap> Gcdex(2520,154);
rec(gcd:=14,coeff1:=3,coeff2:=-49,coeff3:=-11,coeff4:=180)
No output da função Gcdex, coeff1 e coeff2 são os inteiros x e y
necessários para escrever mdc(a, b) = xa + yb e coeff3 e coeff4 são
inteiros m e n tais que 0 = ma + nb. No caso do exemplo, o output
diz-nos que mdc(2520, 154) = 14, que
mdc(2520, 154) = 2520 · 3 + 154 · (−49) e, ainda, que
0 = 2520 · (−11) + 154 · 180.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
44 / 68
Propriedades dos inteiros
Teorema (Caracterização do máximo divisor comum)
Sejam a, b, d ∈ Z+ . As afirmações seguintes são equivalentes:
(i) d = mdc(a, b).
(ii) d é um divisor comum de a e b tal que todo o divisor comum de a e
b divide d.
(iii) d é o menor inteiro positivo da forma xa + yb, com x, y inteiros, isto
é, d = min{i ∈ N | ∃x, y ∈ Z : i = xa + yb}.
Demonstração. (i)⇒(ii) Seja d = mdc(a, b). Então d = xa + yb, para alguns
inteiros x e y . Se c é um divisor comum de a e b, então c | xa + yb = d.
(ii)⇒(i) Seja D um divisor comum de a e b tal que todo o divisor comum de a
e b divide D. Como mdc(a, b) é um divisor comum de a e b, então mdc(a, b)
divide D e, portanto, mdc(a, b) ≤ D. Por outro lado, D não pode ser maior
que o máximo divisor comum de a e b. Logo, D tem que ser igual a mdc(a, b).
(i)⇔(iii) Já foi provado no teorema anterior.
Na demonstração da proposição seguinte intervém (iii), isto é, o facto de
mdc(a, b) ser o menor inteiro positivo que se pode escrever como
combinação linear de a e b.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
45 / 68
Propriedades dos inteiros
Proposição
Sejam a e b inteiros positivos.
(i) Sendo n ∈ N, tem-se mdc(na, nb) = n · mdc(a, b).
(ii) Se d for um
divisor comum positivo de a e b, então
mdc da , db = d1 mdc(a, b).
Demonstração. (i) Existem x, y , r , s ∈ Z tais que
mdc(na, nb) = xna + ynb e mdc(a, b) = ra + sb.
Então, mdc(na, nb) = xna + ynb = n(xa + yb) ≥ n · mdc(a, b).
A outra desigualdade: n · mdc(a, b) = n(ra + sb) = nra + nsb ≥ mdc(na, nb).
(ii) Seja d um divisor
` positivo
´ comum `a a e´a b. Utilizando (i) temos que
mdc(a, b) = mdc d da , d db = d · mdc da , db .
Quando mdc(a, b) = 1, os inteiros a e b dizem-se primos entre si.
Proposição
Sejam a, b e c inteiros, com a e b primos entre si. Se a | bc, então a | c.
Demonstração. Tem-se bc = ka e ax + by = 1, para certos inteiros k, x, y .
Assim, c = c · 1 = c(ax + by ) = cax + cby = cax + kay = a(cx + ky ). Logo,
a | c.
Álgebra (Curso de CC)
Ano lectivo 2005/2006
46 / 68