Embed Size (px)
Citation preview
UNIVERSIDADE DO ESTADO DO PARÁ
CENTRO DE CIÊNCIAS SOCIAIS E EDUCAÇÃO
DEPARTAMENTO DE MATEMÁTICA, ESTATÍSTICA E INFORMÁTICA.
LICENCIATURA EM MATEMÁTICA MODALIDADE A DISTÂNCIA
DISCIPLINA: TEORIA DOS NÚMEROS
CONTÉUDO PROGRAMÁTICO:
INTRODUÇÃO AO ESTUDO DA TEORIA DOS NÚMEROS:
UNIDADE I – NÚMEROS INTEIROS:
1.1 - Números inteiros.
1.2 - Propiedades dos inteiros;
1.3 - Valor absoluto de um inteiro;
1.4 - Questões Resolvidas e Propostas.
UNIDADE II – INDUÇÃO MATAMÁTICA:
2.1 - Elemento mínimo de um conjunto de inteiros.
2.2 - Princípio da boa ordenação;
2.3 - Princípio de indução finita;
2.4 - Indução matemática;
2.5 - Exemplos de demonstração por indução matemática e outras formas de indução
matemática;
2.6 - Questões Resolvidas e Propostas.
UNIDADE III – DIVISIBILIDADE:
3.1 - Relação de divisibilidade em Z.
3.2 - Conjunto dos divisores de um inteiro;
3.3 - Divisores comuns de dois inteiros;
3.4 - Algoritmo da divisão;
3.5 - Paridade de um inteiro;
3.6 - Questões Resolvidas e Propostas.
UNIDADE IV – MÁXIMO DIVISOR COMUM:
4.1 - Máximo divisor comum de dois inteiros.
4.2 - Existência e unicidade do mdc;
4.3 - Inteiros primo entre si;
4.4 - Caracterização do mdc de dois inteiros;
4.5 - Mdc de vários inteiros;
4.6 - Questões Resolvidas e Propostas.
UNIDADE V – ALGORITMO DE EUCLIDES MÍNIMO MÚLTIPLO COMUM:
5.1 - Algoritmo de EUCLIDES.
5.2 - Múltiplos comuns de dois inteiros;
5.3 - Mínimo múltiplo comum de dois inteiros;
5.4 - Relação entre o mdc e o mmc;
5.5 - Mmc de vários inteiros;
5.6 - Questões Resolvidas e Propostas.
UNIDADE VI – NÚMEROS PRIMOS:
6.1 - Números primos e compostos.
6.2 - Teorema fundamental da Aritmética;
6.3 - Formula que dão primos;
6.4 - Crivo de ERATÓSTENES;
6.5 - Primos gêmeos;
6.6 - Seqüências de inteiros consecutivos compostos;
6.7 - Conjectura de GOLDBACH;
6.8 - Método de fatoração de FERMAT;
6.9 - Questões Resolvidas e Propostas.
UNIDADE VII – EQUAÇÕES DIOFANTINAS LINEARES:
7.1 - Generalidades.
7.2 - Condição de existência de solução;
7.3 - Solução da equação ax + by = c;
7.4 - Questões Resolvidas e Propostas.
UNIDADE VIII – CONGRUÊNCIAS:
8.1 - Inteiros congruentes.
8.2 - Caracterização de Inteiros congruentes;
8.3 - Propriedades das congruências;
8.4 - Sistemas completos de restos;
8.5 - Questões Resolvidas e Propostas.
UNIDADE IX – CONGRUÊNCIAS LINEARES:
9.1 - Generalidades.
9.2 - Condição de existência de solução;
9.3 - Solução da congruência a x b(mod. m);
9.4 - Resolução de equações diofantinas lineares por congruências;
9.5 - Inverso de um inteiro;
9.6 - Questões Resolvidas e Propostas.
UNIDADE X – SISTEMAS DE CONGRUÊNCIAS LINEARES:
10.1 - Generalidades.
10.2 - Teorema do resto chinez;
10.3 - Questões Resolvidas e Propostas.
UNIDADE XI – TEOREMA DE FERMAT E WILSON:
11.1 - Teorema de Fermat.
11.2 - Teorema de Wilson;
11.3 - Questões Resolvidas e Propostas.
BIBLIOGRAFIA:
INTRODUÇÃO AO ESTUDO DA TEORIA DOS NÚMEROS
Embora existam diversos tipos de números em Matemática (reais, complexos, etc.), o nome
"Teoria dos Números" é tradicionalmente reservado para o estudo dos Números Inteiros, isto é, -3, -
2, -1, 0, 1, 2, 3, ... Também é usado o nome “Aritmético”, proveniente de arithmós, que em grego
significa “número".
A Teoria dos Números, a mais pura disciplina dentro da mais pura das Ciências a
Matemática e tem uma longa história, originando-se nas antigas civilizações da humanidade.
Listamos primeiro alguns nomes famosos de matemáticos que contribuirão para o estudo da teoria
dos números:
Pitágoras (569-500 a. C.)
Euclides (_ 350 a. C.)
Eratóstenes (276-196 a. C.)
Diofante (_ 250 d. C.)
Plutarco (_ 100 d. C.)
Marin Mersenne (1588-1648)
Pierre de Fermat (1601-1665)
Blaise Pascal (1623-1662)
Christian Goldbach (1690-1764)
Leonhard Euler (1707-1783)
Joseph Louis Lagrange (1736-1813)
John Wilson (1741-1793)
Adrien Marie Legendre (1752-1833)
Carl Friedrich Gauss (1777-1855)
Augustin Louis Cauchy (1789-1857)
Peter Gustav Dirichlet (1805-1859)
P. L. Tchebychef (1821-1894)
Frederick Nelson Cole (1861-1927)
Axel Thue (1863-1922)
Jacques Salomon Hadamard (1865-1963)
Charles de la Vallé e Poussin (1866-1962)
Dentre outros....
A teoria dos números veio a ocupar-se com uma classe mais vasta de problemas que
surgiram naturalmente do estudo dos números inteiros. A teoria dos números pode ser subdividida
em vários campos, de acordo com os métodos que são usados e das questões que são investigadas, a
saber:
1) Teoria elementar dos números: utiliza somente os métodos elementares da aritmética para a
verificação e comprovação das propriedades essenciais do conjunto dos números inteiros e em
particular as propriedades dos números primos.
2) Teoria analítica dos números: utiliza a análise real e análise complexa, especialmente para
estudar as propriedades dos números primos.
3) Teoria algébrica dos números: utiliza álgebra abstrata e estuda os números algébricos.
4) Teoria geométrica dos números: utiliza métodos geométricos, algébricos e analíticos.
Nesta notas faremos o estudo da primeira Teoria, um conceito chave em Teoria elementar
dos Números é o conceito de divisibilidade. Enquanto nos números reais, por exemplo, pode-se
dividir qualquer número por outro (não nulo), obtendo como resultado um número real, nos inteiros
é diferente. Um inteiro a só é divisível pelo inteiro b quando existir um inteiro c tal que a = bc.
Nesse caso, diz-se também que b é um divisor de a, ou que b divide a, ou ainda que a é múltiplo de
b. Por exemplo, 8 é divisível por 2, mas não é por 3. Mesmo que a não seja divisível por b, pode-se
sempre encontrar, de modo único, inteiros c (quociente) e r (resto) tais que a = bc + r.
Todo inteiro a é divisível por 1, -1, a, -a. Estes são os divisores triviais de a. Um inteiro é
dito primo quando só possui os divisores triviais. Um inteiro de valor absoluto maior que 1 e que
não seja primo (isto é, possua divisores não triviais) é dito composto. Por exemplo: São primos: 2, -
2, 3, -3, 17, .... São compostos 6 = 2x3, -8 = (-2) x 4, ... Os números 0, 1 e –1 não são primos nem
compostos. Euclides foi o primeiro a demonstrar que existe uma infinidade de números primos.
O máximo divisor comum dos inteiros não nulos a e b tem a propriedade de ser múltiplo de
qualquer divisor comum de a e b e pode ser encontrado pelo algoritmo de Euclides. Quando o
máximo divisor comum de a e b for 1, então seus únicos divisores comuns são 1 e –1. Nesse caso, a
e b são ditos primos entre si, ou relativamente primos. Por exemplo, 9 e 14 são primos entre si.
As propriedades mais cruciais dos números inteiros, e que não têm similares nos reais ou nos
complexos, são o Princípio da Boa Ordenação, segundo o qual qualquer conjunto não vazio de
inteiros limitado inferiormente possui um elemento mínimo, e o Princípio de Indução, segundo o
qual se uma propriedade P(n), referente ao inteiro n, for verdadeira para n = a, e a veracidade de
P(n) acarretar a veracidade de P(n + 1), então P(n) é verdadeira para todo inteiro maior que ou igual
a a.
A partir das propriedades usuais da adição e da multiplicação de inteiros, da relação <, e do
Princípio da Boa Ordenação (ou do de Indução, que lhe é equivalente), é possível construir toda a
Teoria dos Números. Um de seus resultados mais importantes é o Teorema Fundamental da
Aritmética, segundo o qual todo inteiro (diferente de 0, 1 e –1) pode ser escrito de modo único
como um produto de fatores primos.
Uma das características da Teoria dos Números é que ela inclui problemas extremamente
simples de enunciar e ao mesmo tempo incrivelmente difíceis de resolver. Um exemplo é a
conjectura de Feuerbach: "todo número par é a soma de dois números primos"; ninguém até hoje
conseguiu decidir se isto é verdadeiro ou falso. Outro exemplo é o famoso Último Teorema de
Fermat: "Dado um inteiro n maior que 2, é impossível encontrar inteiros não nulos x, y, z tais que xn
+ yn
= zn". Este teorema, enunciado no século XVII por Fermat, que só foi demonstrado em 1995,
por Wiles.
Gauss, o "príncipe dos matemáticos", dizia que a Matemática era a rainha das ciências, e a
Aritmética, a rainha das Matemáticas. Gauss desenvolveu muita a Teoria dos Números. Aos 22
anos, em 1799, publicou em latim suas "Investigações Aritméticas", onde introduziu o importante
conceito de congruência para números inteiros.
O matemático inglês Hardy, grande especialista em Teoria dos Números, orgulhava-se, em
1940, de que "nenhuma descoberta sua havia feito, nem provavelmente viria a fazer, direta ou
indiretamente, alguma diferença para o conforto da humanidade". No entanto, 50 anos depois, um
obscuro matemático americano descobriria uma falha no recém lançado processador Pentium, ao
realizar cálculos "inúteis" sobre primos gêmeos (números primos que diferem de 2).
Mas já no próprio momento em que Hardy escrevia aquela frase, durante a segunda guerra
mundial, três americanos desenvolviam um sistema de código secreto, chamado SRA, baseado nas
dificuldades insuperáveis para descobrir os fatores primos de um número muito grande. Criava-se
um novo ramo a Criptografia, a ciência dos códigos, fortemente baseado em Teoria dos Números.
Com o advento dos computadores e da computação algébrica, a Criptografia ganhou um novo
impulso. Neste momento, a proliferação de senhas bancárias e de cartões de crédito, bem como a
crescente necessidade de criptografar dados confidenciais que inundam a Internet, faz da
Criptografia um dos ramos mais em moda da Matemática aplicada. E um dos mais úteis, para
desespero póstumo de Hardy.
UNIDADE I – NÚMEROS INTEIROS
1 - Introdução:
A noção de número está, através dos tempos, associada a todos os tipos de atividades
humanas. A primeira concepção de número data do período paleolítico. Poucos progressos se
fizeram neste campo até se dar a transição para o período neolítico, durante o qual já existia uma
atividade comercial importante entre diversas povoações. Esta atividade promoveu a formação de
linguagens, cujas palavras exprimiam coisas muito concretas e poucas abstrações, mas onde já havia
lugar para alguns termos numéricos simples. Estes termos numéricos destinavam-se apenas a
estabelecer a distinção entre um, dois e muitos. Depois de durante milênios ter utilizado os números
para contar, medir, calcular, o homem começou a especular sobre a natureza e propriedades dos
próprios números. Desta curiosidade nasceu a Teoria dos Números, um dos ramos mais profundos
da matemática.
A Teoria dos Números nasceu cerca de 600 anos antes de Cristo quando Pitágoras e os seus
discípulos começaram a estudar as propriedades dos números inteiros. Os pitagóricos rendiam
verdadeiro culto místico ao conceito de número, considerando-o como essência das coisas.
Acreditavam que tudo no universo estava relacionado com números inteiros ou razões de números
inteiros (em linguagem atual, números racionais). Aliás, na antiguidade a designação número
aplicava-se só aos inteiros maiores do que um. Esta crença foi profundamente abalada quando
usaram o Teorema de Pitágoras para calcular a medida da diagonal de um quadrado unitário. Com
efeito, a diagonal divide o quadrado em dois triângulos retângulos isósceles cujos catetos têm
comprimento um e assim, pelo teorema de Pitágoras, a medida da hipotenusa é igual à raiz quadrada
de dois, que não pode ser expresso como quociente de inteiros.
Ao descobrirem que a diagonal de um quadrado de lado 1 não era uma razão entre dois
inteiros (em linguagem atual, que a raiz quadrada de 2 é um número irracional) os Pitagóricos
consideraram quebrada a harmonia do universo, já que não podiam aceitar a raiz quadrada de dois
como um número, mas não podiam negar que esta raiz era a medida da diagonal de um quadrado
unitário. Convencidos de que os deuses os castigariam caso divulgassem aquilo que lhes parecia
uma imperfeição divina, tentaram ocultar a sua descoberta. Segundo reza a lenda, o primeiro
membro da seita pitagórica que divulgou esta descoberta morreu afogado.
Este fato teve grandes repercussões na história da ciência que se fizeram sentir até finais do
século XIX. De cada vez que as necessidades do cálculo levavam a introduzir novos entes
numéricos gerava-se uma enorme desconfiança à sua volta, o que levava a atribuir-lhes designações
curiosas. Assim, os números irracionais eram designados por números inexprimíveis e por números
incalculáveis. Durante muitos séculos os números reais (fracionarias ou racionais e irracionais)
foram apenas concebidos como medidas de grandezas e só nos finais do século XIX, principalmente
por obra dos matemáticos alemães Dedekind e Cantor, se construiu uma teoria dos números reais
independente da geometria.
1.1 - Números Inteiros Noções Fundamentais:
Os números inteiros ou apenas os inteiros são: , 3, 2, 2,0,1, 2,3, .
Cujo conjunto representa-se pela letra , isto é: , 3, 2, 2,0,1,2,3, , deste conjunto
destacam-se os seguintes subconjuntos:
1) Conjunto dos inteiro não nulos ( 0) . = x / x 0 1, 2, 3, 4,z .
2) Conjunto dos inteiro não negativos ( 0) . = x / x 0 0,1,2,3,z .
3) Conjunto dos inteiro não positivos ( 0) . = x / x 0 0, 1, 2, 3,z .
4) Conjunto dos inteiro positivos ( 0) . = x / x 0 1,2,3,4,z .
4) Conjunto dos inteiro positivos ( 0) . = x / x 0 1, 2, 3, 4,z .
Os inteiros positivos são também denominados inteiros naturais e por isso o conjunto dos inteiros
positivos é habitualmente designados pela letra *
+ = .
1.2 - Propriedades dos Inteiros:
O conjunto Z dos inteiros munidos das operações de adição (+) e multiplicação ( ) possui as
propriedades fundamentais que a seguir enumeramos, onde a, b e c são inteiros quaisquer, isto é,
elementos de z:
1) Lei comutativa para multiplicação e adição: a + b = b + a e ab = ba .
2) Lei associativa para multiplicação e adição: a + b + c = a + b + c e (ab)c = a(bc) .
3) Existência da identidade para adição e multiplicação: 0 + a = a e a 1 = 1 a = a .
4) Existência do inverso em relação à adição, -a, para todo inteiro a: a + (- a) = (-a) + a = 0 .
5) Lei distributiva: a b + c = ab + ac .
6) Lei do cancelamento da multiplicação 0 a = 0 e se ab = 0, então a = 0 ou b = 0 .
Também existe uma “relação de ordem” entre os inteiros, representada pelo sinal “< (menor que)”
que possui as seguintes propriedades:
7) Se a 0, então a < 0 ou 0 < a .
8) Se a b, e b < c então, a < c .
9) Se a b, então a + c < b + c .
10) Se a b, então 0 < c, então ac < bc .
11) Se a b, então c < 0, então bc < ac .
12) (Lei da Tricotomia) Para quaisquer inteiros a e b, vale exatamente uma das seguintes
afirmações: a < b, a = b ou a > b .
13) Suponha que a b , e seja c um inteiro qualquer. Entãoa + c b+c
ac bc se c > 0, mas ac bc, se c < 0.
Destas propriedades podem ser deduzidas muitas outras propriedades dos inteiros.
1.3 - Valor absoluto de um Inteiro:
Definição: Chama-se valor absoluto de um inteiro a, o inteiro que se indica por a , tal que:
a se a oa
-a se a o
A partir da definição de a , para todo inteiro a, temos:
2 2
2
a 0
a a
- a a
a a
a a
.
Teoremas: Se a e b são dois inteiros, quaisquer então:
1) a 0 e a 0 se a = 0 .
2) a a a .
3) ab a b .
4) a b a b .
5) a + b a ± b .
Questões Resolvidas
01) Calcular a soma dos “n” primeiros inteiros positivos.
Solução: Vamos escrever a soma dos n primeiros números inteiros positivos em ordem crescente e
a mesma soma em ordem decrescente, temos:
S = 1 + 2 + 3 + 4 + ........ + n – 3 + n – 2 + n – 1 + n
S = n + n – 1 + n – 2 + n – 3 + ........ + 4 + 3 + 2 + 1
Somando as duas igualdades:
2S = (n + 1) + (n + 1) + (n + 1) + (n + 1) + .............. + (n + 1) + (n + 1) + (n + 1) + (n + 1)
Observe que serão n parcelas iguais a (n + 1). Portanto, 2S = n(n + 1) S = n(n + 1)/2.
02) Calcular o inteiro positivo n, sabendo que 3n+2
2n+3
= 2592.
Solução: Decompondo 2592, obtém-se 34.2
5. Portanto, n + 2 = 4 n = 2, ou 5 = n + 3 n = 2.
Pois a forma de decomposição em fatores primos é única.
03) Achar um inteiro positivo de dois algarismos que seja igual ao quádruplo da soma dos seus
algarismos.
Solução: Um número de algarismos a e b, na base 10 é expresso por 10a + b.
Portanto, 10a + b = 4(a + b) 6a = 3b b = 2a. Ou seja, qualquer número de dois algarismos,
onde o algarismo das unidades é o dobro do algarismo das unidades. Assim, temos: 12, 24, 36, etc.
04) Achar o menor e o maior inteiro positivo de n algarismos.
Solução: Menor: 1º algarismo igual a 1 e os demais (n – 1) iguais a zero. Portanto, 1 x 10 n – 1
.
Maior: todos os n algarismos iguais a 9, ou 1 seguido de n zeros menos 1 1.10n – 1
Observação: Considerando, n = 5. Menor 10000 = 1.105 – 1
= 1.104
Maior 99999 = 100000 – 1 = 1.105 – 1.
05) Achar todas as soluções inteiras e positivas da equação: x2 – y
2 = 88.
Solução: x2 – y
2 = 88 (x + y) (x – y) = 88. Como x e y são inteiros positivos, (x + y) e (x – y)
são dois números inteiros cujo produto é 88. Assim, (1) x + y = 88 e x – y = 1; (2) x + y = 44 e x – y
= 2; (3) x + y = 22 e x – y = 4; (4) x + y = 11 e x – y = 8. Cada par de duas equações formam um
sistema. Para resolver o sistema basta somar as duas equações, o que resultaria em 2x = soma dos
números. Como essa soma tem que ser par (x é inteiro), resulta apenas as possibilidades 2 e 3.
Portanto, 2x = 46 x = 23 e y = 44 – 23 = 21 ou 2x = 26 x = 13 e y = 22 – 13 = 9.
Resposta: (x = 23, y = 21) e (x = 13, y = 9).
06) O produto de um inteiro positivo de três algarismos por 7 termina à direita por 638. Achar esse
inteiro.
Solução: Para facilitar o raciocínio, construamos a tabela de multiplicação por 7.
7 x 1 = 7, 7 x 2 = 14, 7 x 3 = 21, 7 x 4 = 28, 7 x 5 = 35, 7 x 6 = 42, 7 x 7 = 49, 7 x 8 = 56, 7 x 9 =
63. Como o algarismo das unidades é 8, o único valor possível para o algarismos das unidades do
número é 4. Ao efetuar a multiplicação do algarismo das unidades, que é 4 por 8, vão duas unidades
para a casa das dezenas. Assim, o algarismo das dezenas deve ser tal que ao multiplicar por 7 e
somar 2, resulte num final igual a 3. Portanto, o algarismo das dezenas é 3, pois 7 x 3 + 2 = 23. Da
mesma forma vão duas unidades para a casa das centenas. O algarismo aí deve ser de forma que, ao
somar 2 (vindo das dezenas) resulte em 6. Portanto, deve ser um múltiplo de 7 terminado em 4. Isto
permite concluir que o algarismo das centenas é 2 , pois 2 x 7 + 2 = 16.
Portanto, o número é 234.
07) Um livro tem 1235 páginas. Determinar o número de vezes que o algarismo 1 aparece na
numeração da páginas deste livro.
Solução: De 1 a 100, o algarismo 1 aparece 10 vezes nas unidades (1, 11, 21,... 91) e 10 vezes nas
dezenas (10, 11, 12, ...19). Portanto a cada centena o algarismo 1 aparece 20 vezes. Em 1235 temos
12 centenas. Portanto o algarismo 1 aparecerá 20 x 12 = 240 vezes na posição das unidades e
dezenas. De 100 a 200, o algarismo 1 aparece 100 vezes na posição das centenas. Isto se repete de
1100 a 1200. Portanto, 200 vezes na posição das centenas.
De 1200 a 1236, o algarismo 1 aparece 4 vezes nas unidades e 10 vezes nas dezenas. Totalizando 14
vezes. De 1000 a 1235, o algarismo 1 aparece 236 vezes na posição dos milhares.
Portanto: 240 + 200 + 14 + 236 = 690 vezes.
08) Achar o inteiro que deve ser somado a cada um dos inteiros 2, 6 e 14 para que, nesta ordem,
formem uma proporção contínua.
Solução: Uma proporção contínua é aquela que tem os meios ou os extremos iguais. Pela definição
podemos ter (a) (2 + x)/(6 + x) = (6 + x)/(14 + x) ou (2 + x)/(6 + x) = (14 + x)/(2 + x). Na situação
(a), (6 + x) 6 + x) = (2 + x) (14 + x) => 36 + 12x + 2x = 28 + 16x + 2x 4x = 8 x = 2. Na
situação (b) (2 + x) (2 + x) = (6 + x) (14 + x) 4 + 4x + 2x = 84 + 20x + 2x 16x = - 80
x = - 5.
R: 2 ou –5.
09) Achar o menor inteiro cujo produto por 21 é um inteiro formado apenas por 4 algarismo.
Solução: O número é o menor múltiplo de 21 maior que 1000.
Portanto: 1000 = 47 x 21 + 13. Portanto, o número é 48 x 21 = 1008.
10) Escreve-se a seqüência natural dos inteiros positivos, sem separar os algarismos:
123456789101112131415...
Determinar:
(a) O 435º algarismo.
Solução: De 1 a 9 são escritos 9 algarismos. De 10 a 99, são dois algarismos em cada número 2
x 90 = 180 algarismos. Portanto, até 100 são escritos: 9 + 180 + 3 = 192.
Para chegar ao algarismo que ocupa o 435º lugar serão necessários mais 435 – 192 = 243
algarismos. Como a partir de 100 são usados 3 algarismos teríamos 243 3 = 81 números após o
100. Portanto, o número é 181 e o algarismo que ocupa a posição é o 1.
(b) O 1756º algarismo.
Solução: Da mesma forma 1756 – 192 = 1564 1564 3 = 521 e sobra 1 algarismo. Portanto
teríamos até a 100 + 521 = 621. Como sobra 1 algarismo, o próximo é o 6 do número 622.
(c) O 12387º algarismo.
Solução: Até 1000 seriam 9 + 90 x 2 + 900 x 3 + 4 = 2889.
12387 – 2889 = 9498 9498 4 = 2374 e sobram dois algarismo. Portanto, o último número
inteiro é 1000 + 2374 = 3374. A sobra de dois algarismos implica que o último algarismo será 3, o
segundo algarismo de 3375.
11) Mostrar que o produto de dois fatores entre 10 e 20 é o décuplo da soma do primeiro com as
unidades do segundo mais o produto das unidades dos dois.
Solução: Sejam os números 10 + b e 10 + c, com 0 < b < 10 e 0 < c < 10. Nestas condições 10 + b e
10 + c estarão compreendidos entre 10 e 20 e b e c serão os algarismos das unidades.
Efetuando o produto temos: (10 + b) (10 + b) = 100 + 10b + 10c + bc = 10[(10 + b) + c] + bc.
(10 + b) + c é a soma do primeiro com as unidades do segundo, bc é o produto dos dois e 10[(10 +
b) + c] é o décuplo da soma do primeiro com as unidades do segundo.
Questões Propostas
01) Calcule o inteiro positivo n, sabendo-se que: 3n + 3
n+1 + 3
n+2 + 3
n+3 = 1080.
R: n = 3.
02) Decompor o inteiro 575 numa soma de cinco inteiros ímpares consecutivos.
R: 109, 113, 115, 117, 119.
03) Achar todas as soluções inteiras e positivas da equação (x + 1) (y + 2) = 2xy.
R: os valores são (x = 2, y = 6), (x = 3, y =4) e (x = 5, y = 3).
04) Verificar se o quadrado de um inteiro pode terminar em 2, 3, 7 ou 8.
R: Portanto, não pode terminar em 2, 3, 7 ou 8.
05) A soma dos quadrados de dois inteiros é 3332 e um deles é o quádruplo do outro. Achar os dois
inteiros.
R: 14 e 56.
06) A média aritmética de dois inteiros positivos é 5 e a média geométrica é 4. Achar os dois
inteiros.
R: 8 e 2.
07) Calcular a soma dos três maiores números inteiros de, respectivamente, três, quatro e cinco
algarismos.
R: 110997.
08) Determinar a diferença entre o maior número inteiro com seis algarismos diferentes e o menor
inteiro com cinco algarismos também diferentes.
R: 977420.
09) Mostrar que o produto de quatro algarismos consecutivos, aumentado de 1, é um quadrado
perfeito.
10) Sejam a e b dois inteiros. Demonstrar:
(a) Max (a, b) = (a + b + |a – b|)/2.
(b) Min (a, b) = (a + b – |a – b|)/2.
11) Achar cinco inteiros positivos consecutivos cuja soma dos quadrados é igual a 2010.
R: 18, 19, 20, 21 e 22.
12) Escreve-se a seqüência natural dos inteiros positivos pares, sem separar os algarismos:
24681012141618...
Determinar o 2574º algarismo que se escreve.
R: algarismo é o 6.
13) Os inteiros a e b são tais que –1 < a < 3 e –2 < b < 0. Mostrar que –1 < a – b < 5.
R: – 1 < a – b < 5.
14) Os inteiros a e b são tais que -2 < a < 2 e - 2 < b < 2. Mostrar que –4 < a – b < 4.
R: –4 < a – b < 4.
15) Achar o menor inteiro positivo que multiplicado por 33 dá um produto cujos algarismos são
todos 7.
R: 777777: 33 = 23569.
16) No planeta Mong o número de horas por dia é igual a número de dias por semana, que é igual ao
número de semanas por mês, que é igual ao número de meses por ano. Sabendo que em Mong há
4096 horas por ano, quantas semanas há por mês?
R:
17) A soma de três números naturais consecutivos é igual ao produto desses três números. A soma
dos quadrados desses números é:
R:
18) Sejam a, b e c inteiros e positivos. Entre as opções abaixo, a expressão que não pode representar
o número 24 é:
a) ab3 b) a
2b
3 c) a
cb
c d) ab
2c
3 e) a
cb
cc
c
19) Efetuando as operações indicadas na expressão abaixo obtemos um número de quatro
algarismos. Qual é a soma dos algarismos desse número: 2007 2005
2006 2004
2 22006
2 2.
R:
20) Qual é a soma dos algarismo do número: 2 3 4 2005 2006
2 3 2004 2005
2 2 2 2 2
2 2 2 2 2 ?
R:
21) Quantos são os possíveis valores inteiros de x para que x 99
x 19 seja um número inteiro?
R: 20.
22) Um pai tem 33 anos e seu filho, 7 anos. Depois de quantos anos a idade do pai será o triplo da
idade do filho?
R: 6.
UNIDADE II – INDUÇÃO MATEMÁTICA
2.1 - Introdução:
O Princípio da Indução é um eficiente instrumento para a demonstração de fatos referentes
aos números naturais. Por isso deve-se adquirir prática em sua utilização. Por outro lado, é
importante também conhecer seu significado e sua posição dentro do arcabouço da Matemática.
Entender o Princípio da Indução é praticamente o mesmo que entender os números naturais.
Apresentamos abaixo uma breve exposição sobre os números naturais, onde o Princípio da
Indução se insere adequadamente e mostra sua força teórica antes de ser utilizado na lista de
exercícios propostos ao final.
2.2 - A Seqüência dos Números Naturais:
Os números naturais constituem um modelo matemático, uma escala padrão, que nos
permite a operação de contagem. A seqüência desses números é uma livre e antiga criação do
espírito humano. Comparar conjuntos de objetos com essa escala abstrata ideal é o processo que
torna mais precisa a noção de quantidade; esse processo (a contagem) pressupõe, portanto o
conhecimento da seqüência numérica. Sabemos que os números naturais são 1, 2, 3, 4, 5,… A
totalidade desses números constitui um conjunto, que indicaremos com o símbolo N e que
chamaremos de conjunto dos naturais. Portanto N = {1, 2, 3, 4, 5,…}.
Evidentemente, o que acabamos de dizer só faz sentido quando já se sabe o que é um
número natural. Façamos de conta que esse conceito nos é desconhecido e procuremos investigar o
que há de essencial na seqüência 1, 2, 3, 4, 5… .
Deve-se a Giussepe Peano (1858 - 1932) a constatação de que se pode elaborar toda a teoria
dos números naturais a partir de quatro fatos básicos, conhecidos atualmente como os axiomas de
Peano. Noutras palavras, o conjunto N dos números naturais possui quatro propriedades
fundamentais, das quais resultam, como conseqüências lógicas, todas as afirmações verdadeiras que
se podem fazer sobre esses números.
2.3 - Elemento Mínimo:
Definição 1.1 - Seja A um conjunto de inteiros. Chama-se elemento mínimo de A um elemento a
A tal que a x para todo x A. Notação: a = min A.
min A = a se, e somente se, (a A e ( x A) a x).
Teorema: Se a é elemento mínimo de A, então este elemento é único.
2.4 - Princípio da Boa Ordenação (PBO).
Todo conjunto não vazio A, de inteiros não negativos, possui elemento mínimo.
A Z+, A , existe min A.
2.5 - Indução Matemática:
Teorema: Seja P(n) uma proposição associada a cada inteiro positivo n e que satisfaz às duas
seguintes condições:
1) P(1) é verdadeira.
2) Para todo inteiro k, se P(k) é verdadeira, então P(k + 1) também é verdadeira. Nestas condições,
a proposição P(n) é verdadeira para todo inteiro positivo n.
2.6 - Princípio da Indução Finita (PIF).
Teorema: Seja S um subconjunto do conjunto N dos inteiros positivos (S N) que satisfaz as duas
seguintes propriedades:
1) 1 pertence a S (1 S).
2) Para todo inteiro positivo k, se k S, então (k + 1) S;
3) Nestas condições, S é o conjunto N dos inteiros positivos: S = N.
2.7 - Outra Forma da Indução Matemática:
Teorema: Seja r um número inteiro positivo fixo e seja P(n) uma proposição associada a cada
inteiro n r e que satisfaça às duas seguintes condições:
1) P(r) é verdadeira.
2) Para todo inteiro k r, se P(k) é verdadeiro, então P(k + 1) é verdadeiro;
3) Nestas condições, P(n) é verdadeira para todo inteiro n r.
Questões Resolvidas
01) Demonstrar por "indução matemática", as questões abaixo:
1) 12 + 2
2 + 3
2 + ... + n
2 =
6
)1n2)(1n(n n N.
Solução: P(1) é verdadeira, pois 12 =
6
3.2.1. Suponhamos que para P(k) é verdadeira:
12 + 2
2 + 3
2 + ... + k
2 =
6
)1k2)(1k(k. Somando (k + 1)
2 a ambos os membros:
12 + 2
2 + 3
2 + ... + k
2 + (1 + k)
2 =
6
)1k2)(1k(k + (k + 1)
2
= 6
)1k(6)1k2)(1k(k 2
= 6
)1k(6)1k2(k)1k(
= 6
)6k6kk2)(1k( 2
=6
)3k2)(2k)(1k( Logo P(k + 1) é verdadeira.
2) 13 + 2
3 + 3
3 + ... + n
3 =
4
)1n(n 22
n N.
Solução: P(1) é verdadeira, pois 13 =
4
)11(1 22
. Suponhamos que para P(k) é verdadeira:
13 + 2
3 + 3
3 + ... + k
3 =
4
)1k(k 22
Somando (k + 1)3 a ambos os membros
13 + 2
3 + 3
3 + ... + k
3 + (k + 1)
3 =
4
)1k(k 22
+ (k + 1)3
= 4
)1k(4)1k(k 322
= 4
)1k(4k)1k( 22
= 4
)4k4k()1k( 22
= 4
)2k()1k( 22
Logo P(k + 1) é verdadeira.
3) 12 + 3
2 + 5
2 + ... + (2n – 1)
2 =
3
)1n4(n 2
n N.
Solução: P(1) é verdadeira, pois 12 =
3
)11.4(1 2
Suponhamos que para P(k) é verdadeira:
12 + 3
2 + 5
2 + ... + (2k – 1)
2 =
3
)1k4(k 2
Somando (2k + 1)2 a ambos os membros
12 + 3
2 + 5
2 + ... + (2k – 1)
2 + (2k + 1)
2 =
3
)1k4(k 2
+ (2k + 1)2
= 3
)1k2(3)1k2)(1k2(k 2
= 3
)1k2(3)1k2(k)1k2(
= 3
)3k5k2)(1k2( 2
= 3
)3k2)(1k)(1k2(
= 3
)3k2)(1k2)(1k( Logo P(k + 1) é verdadeira.
4) 13 + 3
3 + 5
3 + ... + (2n –1)
3 = n
2(2n
2 – 1)
Solução: P(1) é verdadeira, pois 13 = 1
2(2.1
2 – 1). Suponhamos que para P(k) é verdadeira:
13 + 3
3 + 5
3 + ... + (2k –1)
3 = k
2(2k
2 – 1). Somando (2k + 1)
3 a ambos os membros
13 + 3
3 + 5
3 + ... + (2k –1)
3 + (2k + 1)
3 = k
2(2k
2 – 1) + (2k + 1)
3
= 2k4 – k
2 + 8k
3 + 12k
2 + 6k + 1
= 2k4 + 8k
3 + 11k
2 + 6k + 1
= (k + 1)(2k3 + 6k
2 + 5k + 1)
= (k + 1)(k + 1)(2k2 + 4k + 1)
= (k + 1)2(2(k + 1)
2 – 1) Logo P(k + 1) é verdadeira.
5) 1.2 + 2.3 + 3.4 + ... + n(n + 1) = 3
)2n)(1n(n.
Solução: P(1) é verdadeira, pois 1(1 + 1)= 1(1 + 1)(1 + 2)/3
Suponhamos que para P(k) é verdadeira: 1.2 + 2.3 + 3.4 + ... + k(k + 1) = 3
)2k)(1k(k
Somando (k + 1)(k + 2) a ambos os membros:
1.2 + 2.3 + 3.4 + ... + k(k + 1) + (k + 1)(k + 2) = 3
)2k)(1k(k + (k + 1)(k + 2)
= 3
)2k)(1k(3)2k)(1k(k
= 3
)3k)(2k)(1k( Logo P(k + 1) é verdadeira.
6) a + aq + aq2 + ... + aq
n =
1q
)1q(a 1n
, q 1.
Solução: P(1) é verdadeira, pois a + aq = 1q
)1q(a 11
Suponhamos que para P(k) verdadeira.
a + aq + aq2 + ... + aq
k =
1q
)1q(a 1k
Somando aqk+1
a ambos os membros
a + aq + aq2 + ... + aq
k + aq
k+1 =
1q
)1q(a 1k
+ aqk+1
= 1q
)1q(aq)1q(a 1k1k
= 1q
)1q(q1qa 1k1k
= 1q
)qq1q(a 1k2k1k
= 1q
)1q(a 2k
Logo P(k + 1) é verdadeira.
02) Demonstrar por “indução matemática”:
1) 2n < 2
n+1 n N.
Solução: P(1) é verdadeira, pois 21 < 2
1+1. Suponhamos que para P(k) é verdadeira:
2k < 2
k+1 Multiplicando por 2 ambos os membros
2.2k < 2.2
k+1 ou 2
k+1 < 2
k+2 logo, P(k + 1) é verdadeira.
2) n ! > n2 n 4.
Solução: P(4) é verdadeira, pois 4! > 42 ou 24 > 16. Suponhamos que para P(k) é verdadeira:
k! > k2 Multiplicando por k + 1 ambos os membros
k!(k + 1) > k2(k + 1) ou (k + 1)! > k
3 + k
2 como k
3 > k
2 e k
2 > 2k + 1 temos
(k + 1)! > k2 + 2k + 1 ou (k + 1)! > (k + 1)
2 Logo P(k + 1) é verdadeira.
3) 2n > n
2 n 5.
Solução: P(5) é verdadeira, pois 25 > 5
2. Suponhamos que para P(k) é verdadeira:
2k > k
2 Multiplicando por 2 ambos os membros
2.2k > 2.k
2 ou 2
k+1 > k
2 + k
2 > k
2 + 2k + 1 (pois k
2 > 2k + 1) ou 2
k+1 > (k + 1)
2.
Logo P(k + 1) é verdadeira.
4) 24 | (52n
– 1) n N.
Solução: P(1) é verdadeira, pois 24 | (52.1
– 1) Suponhamos que para P(k) é verdadeira,
24 | (52k
– 1). Logo 52k
– 1 = 24t ou 52k
= 24t + 1
Multiplicando ambos os membros por 52.5
2.5
2k = 5
2 (24t + 1) = 5
2.24t + 25 = 5
2.24t + 24 + 1
52k+2
= 24(25t + 1) + 1 ou 52(k+1)
– 1 = 24q
onde q = 24t + 1 ou 24 | (52(k+1)
–1).
5) 5 | (8n – 3
n) n N.
Solução: P(1) é verdadeira, pois 5 | (81 – 3
1) Suponhamos que para P(k) verdadeira
5 | (8k – 3
k) Logo 8
k – 3
k = 5t, onde t é um número inteiro. Vamos mostrar que P(k + 1) é
verdadeira: 8k+1
– 3k+1
= 8.8k – 3.3
k = 8.8
k – (8.3
k – 5.3
k)
= 8.8k – 8.3
k + 5.3
k
= 8(8k – 3
k) + 5.3
k
= 8.5t + 5.3
k
= 5(8t + 3k) fazendo 8t + 3
k = q
= 5q Logo 5 | (8k+1
– 3k+1
).
6) 4n > n
4 n 5.
Solução: P(5) é verdadeira, pois 45 > 5
4 Suponhamos que para P(k) verdadeira, k > 5
4k > k
4 Multiplicando por 4 ambos os membros
4.4k > 4k
4 ou 4
k+1 > k
4 + 3k
4 Vamos usar a desigualdade n
4 > 4n
3 + 6n
2 + 4n + 1
4k+1
> k4 + 3k
4 > k
4 + 4k
3 + 6k
2 + 4k + 1 ou 4
k+1 > (k + 1)
4 Logo P(k + 1) é verdadeira
7) Demonstrar que 10n + 1
– 9n – 10 é um múltiplo de 81 para todo inteiro positivo n.
Solução: P(1) é verdadeira, pois 81 | (101+1
– 9 1 – 10) ou 81 | 81.
Suponhamos que para P(k) verdadeira: 81 | (10k+1
– 9k – 10) Logo 10k+1
– 9k – 10 = 81t
Multiplicando ambos os membros por 10.
10.10k+1
– 10.9k – 10.10 = 10.81t
10k+2
– 9k – 81k = 10.81t + 102
10k+2
– 9k – 9 = 10.81t + 102 + 81k – 9
10k+2
– 9(k + 1) – 10 = 10.81t + 102 + 81k – 9 – 10
10k+2
– 9(k + 1) – 10 = 10.81t + 81k + 81
10k+2
– 9(k + 1) – 10 = 81(10t + k + 1)
10k+2
– 9(k + 1) – 10 = 81q fazendo 10t + k + 1 = q Logo 81 | [10k+2
– 9(k + 1) – 10 }].
8) Demonstrar que 15
n7
5
n
3
n 53
é um inteiro positivo para todo n N.
Solução: 15
n7
5
n
3
n 53
= 15
n7n3n5 53, isto é: 15 | (5n
3 + 3n
5 + 7n) n N.
P(1) é verdadeira, pois 15 | (5 13 + 3 1
5 + 7 1) ou 15 | 15.
Suponhamos que para P(k) verdadeira: 15 | (5k3 + 3k
5 + 7k) ou 5k
3 + 3k
5 + 7k = 15t. Vamos
mostrar que.
P(k + 1) é verdadeira. Somando a expressão 15k4 + 30k
3 + 45k
2 + 30k + 15 a ambos os membros da
igualdade acima, temos:
5k3 + 3k
5 + 7k + 15k
4 + 30k
3 + 45k
2 + 30k + 15 = 15t + 15k
4 + 30k
3 + 45k
2 + 30k + 15.
Arranjando os termos convenientemente, temos:
5k3 + 15k
2 + 15k + 5 + 3k
5 + 15k
4 + 30k
3 + 30k
2 + 15k + 3 + 7k + 7 = 15(t + k
4 + 2k
3 + 3k
2 + 2k +
1).
5(k3 + 3k
2 + 3k + 1) + 3(k
5 + 5k
4 + 10k
3 + 10k
2 + 5k + 1) + 7(k + 1) = 15(t + k
4 + 2k
3 +3k
2 + 2k +
1).
5(k + 1)3 + 3(k + 1)
5 + 7(k + 1) = 15q fazendo t + k
4 + 2k
3 +3k
2 + 2k + 1 = q Assim.
15 | [5(k + 1)3 + 3(k + 1)
5 + 7(k + 1)] o que queríamos provar.
Questões Propostas
01) Demonstrar por “indução matemática”, as questões abaixo:
1) 1 + 3 + 5 + ... + (2n –1) = n2 n . 10)
2n
1...
9
1
4
11 2 –
n
1, n .
2) 1 2 n n
1 1 1 11 n
2 2 2 2 . 11)
1 2 n n
2 2 2 11 , n
3 3 3 3 .
3) n + 1
2 n 1 r1 r r r , n
1 r . 12)
n(n 1)1 2 3 n , n
2 .
4) (n 1)(4 + 3n)
2 5 8 (2 3n) , n2
. 13) 0 1 2 n 1 n2 2 2 2 2 1, n .
5) 2 2 2 2 n(n 1)(2n + 1)1 2 3 n , n
6 . 14)
2
3 3 3 3 n(n 1)1 2 3 n n
2 .
6) 6 | n(n +1)(n + 2) n . 15) 4
3 3 3 3 n1 2 3 n , n
4 .
7) 2 | (n2 + n) n . 16) n(1 a) 1 na, n , a , a 1.
8) 1 1 1 1 n
, n1 2 2 3 3 4 n (n+1) n 1
17) 3 | (22n
–1) n .
9) 1 1 1
(1 1) 1 1 1 n 1, n2 3 n
.18) 3 | (n3 + 2n) n .
02) Usando o principio da "indução matemática", demonstrar:
1) O número de diagonais de um polígono convexo de n lados é: n
n(n 3)d
2.
2) A soma das medidas dos ângulos internos de um polígono convexo de n lados é: 0
nS (n 2) 180 .
3) Se A é um conjunto finito com n elementos, então (A) , conjunto das partes de A, tem 2n
elementos.
4) Prove que a soma de uma PG ou razão q de n termos e primeiro termo a1 é dado por n
1n
a (q 1)S
q 1.
5) Prove que uma P.G. de primeiro termo a1 e razão q o produto (Pn) dos n primeiros termos é dado
por n(n - 1)
n 2n 1P a q , n 1.
6) Prove que numa PA. de primeiro termo a1 e razão r a soma (Sn) dos n primeiros termos é dado
por n 1
n(n 1)S na r
2.
7) Para n+ nr , θ e n 0, mostre que r (cosθ + isen θ) r (cosnθ + isen nθ) , onde i
2 = -1.
8) Sendo z um número complexo não-nulo e n 0 , mostre que n n( ) ( )z z .
9) Prove que numa o termo geral da P. A. é dado pela formula n 1a a (n 1)r .
10) Prove que 0 1 nn n n-1 n n
n n n(a + b) a a b b , para n .C C C
11) Seja cosθ senθ
Asen θ cosθ
. Determine An, para n 1.
12) Para x e n 1, mostre que sen nx n sen x .
13) Demonstrar a lei de De Morgan (A B) ' A' B' , sobre n conjuntos.
UNIDADE III – DIVISIBILIDADE
3.1 - Introdução:
Sabemos, desde a escola básica, que quando um número inteiro e dividido por um segundo
número inteiro não nulo, o quociente pode ou não ser um numero inteiro. Esta observação nos leva
a seguinte definição.
3.2 - Divisibilidade:
Definição 3.2 - Sejam a e b dois inteiros, com a 0. Diz-se que a divide b se, e somente se, existe
um inteiro q tal que b = aq.
Se a divide b também se diz que a é divisor de b, que b é múltiplo de a, que a é um fator de b ou que
b é divisível por a.
Notação: “a | b” (a 0 divide b e portanto, a notação “a | b” significa que a 0 não divide b).
A relação “a divide b (a | b)” denomina-se relação de divisibilidade em .
Observação: Se a | b, então –a | b.
Teorema 3.1: Quaisquer que sejam os inteiros a, b e c tem-se:
(1) a | 0, a 0, 1 | a e a | a, a 0.
(2) Se a | 1, então a = 1.
(3) Se a | b e se c | d, então ac | bd.
(4) Se a | b e se b | c, então a | c.
(5) Se a | b e se b | a, então a = b.
(6) Se a | b com b 0, então | a | | b |.
(7) Se a | b e se a | c, então a |(bx + cy) para todos x e y em .
3.3 - Conjunto de divisores de um inteiro:
D(a) = {x *| x | a}.
3.4 - Divisores comuns de dois inteiros:
Definição 3.3: Chama-se divisor comum de dois inteiros a e b todo inteiro d 0 tal que d | a e d | b.
Notação: D(a, b) = {x * | x | a e x | b}
Propriedade; D(a, b) = D(a) D(b).
Obs.: D(a, b) ; D(0, 0) = *.
3.5 - Algoritmo da Divisão:
Teorema 3.2: Se a e b são dois inteiros, com b > 0, então existem e são únicos os inteiros q e r que
satisfazem às condições: a = bq + r e 0 r < b.
Corolário 3.2: Se a e b são dois inteiros com b 0, existem e são únicos os inteiros q e r que
satisfazem às condições: a = bq + r, 0 r < | b |.
3.6 - Paridade de um Inteiro:
Na divisão de um inteiro qualquer a por b = 2 os possíveis restos são r = 1 e r = 0. Se r = 0 então, o
inteiro a = 2q é denominado par; e se r = 1, então o inteiro a = 2q + 1 é denominado ímpar.
Questões Resolvidas
01) Mostrar que, se a é um inteiro qualquer, então um dos inteiros a, a + 2, a + 4 é divisível por 3.
Solução: Quando dividimos um inteiro a qualquer por 3 , os restos são 0, 1 ou 2.
Assim a = 3q ou a = 3q + 1 ou a = 3q + 2.
Se a = 3q, então 3 | a
Se a = 3q + 1, a + 2 = 3q + 1 + 2 ou a + 2 = 3(q + 1) então 3 | (a + 2).
Se a = 3q + 2, a + 4 = 3q + 2 + 4 ou a + 4 = 3(q + 2) então 3 | (a + 4).
02) Sendo a um inteiro qualquer, mostrar:
a) 2 | a(a + 1).
Solução: Como a e a + 1 são inteiros consecutivos, então um dos dois é par, sendo o outro ímpar;
então a(a + 1) = 2k1(2k2 + 1) onde 2k1 representa o número par e 2k2 + 1 representa o número ímpar.
Assim 2 | a(a + 1).
03) 3 | a(a + 1)(a + 2).
Solução: Dividindo a por 3, temos três hipóteses. a = 3q ou a = 3q + 1 ou a = 3q + 2
Se a = 3q então 3 | a e por conseguinte 3 | a(a + 1)(a + 2)
Se a = 3q + 1 então a + 2 = 3q + 1 + 2 ou a + 2 = 3(q + 1); logo 3 | (a + 2) e por conseguinte 3 | a(a
+1)(a + 2)
Se a = 3q + 2 então a + 1 = 3q + 2 + 1 ou a + 1 = 3(q + 1); logo 3 | (a + 1) e por conseguinte 3 | a(a
+ 1)(a + 2)
04) Mostrar que todo inteiro ímpar é da forma 4k + 1 ou 4k + 3.
Solução: Quando dividimos um inteiro por 4 os restos possíveis são: 0, 1, 2 ou 3. Se o número for
ímpar, os restos só poderão ser 1 ou 3 e, assim, n = 4k + 1 ou n = 4k + 3 onde n é o número ímpar.
05) Mostrar que o quadrado de um inteiro qualquer é da forma 3k ou 3k + 1.
Solução: Dividindo um inteiro por três, obtemos os restos 0, 1 ou 2. Sendo assim podemos
escrever: a = 3k1, a = 3k1 + 1 ou a = 3k1 + 2, onde a é um inteiro qualquer
Se a = 3k1, a2 = 9 k1
2 ou a
2 = 3(3k1
2). Fazendo 3k1
2 = k, temos a = 3k
Se a= 3k1 + 1, a2 = 9k1
2 + 6k1 + 1 ou a
2 = 3(3k1
2 +2k1) + 1. Fazendo 3k1
2 +2k1 = k temos a
2 = 3k + 1
Se a = 3k1 + 2, a2 = 9k1
2 + 12k1 + 4 ou a
2 = 9k1
2 + 12k1 + 3 + 1; assim
a2 = 3(3k1
2 +4k1 + 1) + 1. Fazendo 3k1
2 +4k1 + 1 = k temos a
2 = 3k + 1.
06) Mostrar que n n n( )( )1 2 1
6 é um inteiro qualquer que seja o inteiro positivo n.
Solução: Devemos provar que n(n + 1)(2n + 1) é múltiplo de 6.
Como n e n + 1 são inteiros consecutivos, então um dos dois é par, logo múltiplo de 2.
Vamos mostrar que um dos números n, n + 1, 2n + 1 é múltiplo de 3.
Se n não for múltiplo de 3, então n = 3q + 1 ou n = 3q + 2.
Se n = 3q + 1, 2n + 1 = 6q + 2 + 1 ou 2n + 1 = 3(2q + 1). Logo 2n + 1 é múltiplo de 3.
Se n = 3q + 2, n + 1 = 3q + 2 + 1 ou n + 1 = 3(q + 1). Logo n + 1 é múltiplo de 3.
Então podemos concluir que um dos três números n, n + 1, 2n + 1 é múltiplo de 3.
Podemos, então, escrever: n(n + 1)(2n + 1) = 2t13t2t3, substituindo o fator múltiplo de 2 por 2t1 e o
fator múltiplo de 3 por 3t2, sendo t3 outro inteiro qualquer. Concluímos que n(n + 1)(2n + 1) = 6t1t2t3
é múltiplo de 6, como queríamos demonstrar.
Demonstrar:
07) Se a é um inteiro ímpar, então 24 | a(a2 – 1).
Solução: a(a2 –1) = a(a – 1)(a + 1). Como a é ímpar, a = 2t + 1, a – 1 = 2t e a + 1 = 2t + 2.
Então a(a2 – 1) = (2t + 1)2t(2t + 2) ou a(a
2 – 1) = (2t + 1) 2t2(t + 1) ou a(a
2 – 1) = 4t(t + 1)(2t + 1).t(t
+ 1)(2t + 1) é múltiplo de 6.
Portanto a(a2 – 1) = 4.6 k ou a(a
2 – 1) = 24 k; concluímos que 24 | a(a
2 – 1).
08) Se a e b são inteiros ímpares, então 8 | (a2 – b
2).
Solução: a2 – b
2 = (a - b)(a + b). Como a e b são ímpares a = 2q + 1 e b = 2k + 1. Onde q e k são
inteiros quaisquer. Então: a2 – b
2 = 2q + 1 – (2k + 1) (2q + 1 + 2k + 1)
a2 – b
2 = (2q – 2k)(2q + 2k + 2) ou a
2 – b
2 = 2(q – k)2(q + k + 1) ou
a2 – b
2 = 4(q – k)(q + k + 1). Quaisquer que sejam as paridades de q e k, q – k e q + k tem a mesma
paridade: deste modo q - k e q + k + 1 têm paridades diferentes, isto é, um é par e o outro ímpar.
Assim (q – k)(q + k + 1) = 2t(2t + 1). Substituindo na expressão acima, obtemos: a2 – b
2 = 4.2t(2t +
1) ou a2 – b
2 = 8t(2t + 1) e logo 8 | (a
2 – b
2 ).
09) Mostrar que a diferença entre os cubos de dois inteiros consecutivos nunca é divisível por 2.
Solução: Sejam os inteiros consecutivos n e n + 1. Achemos a diferença entre os cubos destes
números:
(n + 1)3 – n
3 = n
3 + 3n
2 + 3n + 1 – n
3
= 3n2 + 3n + 1
= 3n(n + 1) + 1. Como n e n + 1 são consecutivos, um dos dois é par e, portanto, o
produto 3n(n + 1) é também par e 3n(n + 1) + 1 é ímpar. Logo não é divisível por 2.
10) Na divisão do inteiro a = 427 por um inteiro positivo b o quociente é 12 e o resto é r. Achar o
divisor b e o resto r.
Solução:: De acordo com o algoritmo da divisão 427 = 12b + r, 0 r b ; onde 427 é o dividendo,
b o divisor , 12 o quociente e r o resto. Desta igualdade tiramos:
427 –12b = r e daí 0 427 –12b < b. Somando 12b aos três membros da desigualdade, obtemos:
12b 427 < 13b. Da desigualdade 12b 427, tiramos b 35, 5 ou b 35.
Da desigualdade 427 < 13b tiramos b > 32,8 ou b 33. Assim os valores para b são os inteiros no
intervalo 33,35 ou 33, 34 e 35.
Para b = 33, r = 427 – 12 x 33 = 31. Para b = 34, r = 427 – 12 x 34 = 19. Para b = 35, r = 427 – 12
x 35 = 7.
11) Achar um inteiro de quatro algarismos, quadrado perfeito, divisível por 27 e terminado em 6.
Solução: Se a, b, c ... são fatores primos, os expoentes desses fatores devem ser par.
Como 27 = 33, deve-se ter pelo menos mais um 3 como fator. Portanto, o número deve ser múltiplo
de 27 x 3 ou de 81. Para que o número termine em 6, devemos multiplicar 81 por um quadrado
(pois 81 já é quadrado), terminado em 6, pois 81 termina em 1. Assim, temos as possibilidades 81 x
16 = 1296 e 81 x 36 = 2916.
Se o número tivesse 6 fatores iguais a 3, ele deveria ser múltiplo de 729. Para que terminasse
em 6, deveriamos ter 729 x a, com a terminado em 4. Como os menores quadrados terminados em
quatro são 4 e 64, teríamo: 729 x 4 = 2916 e 729 x 64 = 46656 que tem 5 algarismos. Para 8 fatores
iguais a 3, o número deveria ser múltiplo de 6561 = 38. Para que o número terminasse em 6,
deveriamos ter 6561 x a, com a terminado em 4. Como os menores quadrados terminados em quatro
são 4 e 64, teríamos 6561 x 4 = 26244 que contém cinco algarismos. Para 10 fatores iguais a 3,
teríamos 310 > 10000, que terá mais de 4 algarismos.
Portanto, os únicos números são 1296 e 2916.
12) Demonstrar que se m e n são inteiros ímpares, então 8 | (m4 + n
4 – 2).
Solução: se m e n são ímpares, podemos escrever: m = 2k + 1 e n = 2k’ + 1.
Temos então: m4 + n
4 - 2 = (2k + 1)
4 + (2k’ + 1)
4 – 2 = [(2k)
4 + 4(2k)
3 + 6(2k)
2 + 4(2k) + 1] +
[(2k’)4 + 4(2k')
3 + 6(2k’)
2 + 4(2k’)+1] – 2 = 16(k
4 + k’
4) + 32(k
3 – k’
3) + 24(k
2 + k’
2) + 8(k + k’) +
2 – 2 = 8[2(k4 + k’
4) + 4(k
3 – k’
3) + 3(k
2 + k’
2) + (k + k’)]. Como 2(k
4 + k’
4) + 4(k
3 – k’
3) + 3(k
2 +
k’2) + (k + k’)]. É um inteiro (multiplicação e adição de inteiros), podemos escrever: m
4 + n
4 - 2 =
8q, q inteiro 8 | (m4 + n
4 – 2).
Questões Propostas
01) Mostrar que, se a | b, então (-a) | b e a | (-b) e (-a) | (-b).
02) Sejam a, b e c inteiros. Mostrar:
a) se a | b, então a | bc.
b) Se a | b e se a | c, então a2 | bc.
c) a | b se, e somente se, ac | bc, (c 0).
03) Mostrar que um inteiro qualquer da forma 6k + 5 também é da forma 3k + 2.
04) Mostrar que o cubo de um inteiro qualquer é de uma das formas: 9k, 9k + 1 e 9k + 8.
05) Mostrar que, se a | (2x – 3y) e se a | (4x – 5y), então a | y.
06) Determinar os inteiros positivos que divididos por 17 deixam um resto igual ao quadrado do
quociente. R: 18, 38, 60 e 84.
07) Na divisão do inteiro 525 por um inteiro positivo o resto é 27. Achar os inteiros que podem ser
o divisor e o quociente. R: b = 498 e q = 1; b = 249 e q = 2; b = 166 e q = 3 e b = 83 e q = 6.
08) Na divisão de dois inteiros positivos o quociente é 16 e o resto o maior possível. Achar os dois
inteiros, sabendo que a sua soma é 341. R: a = 322, b = 19.
09) Achar os inteiros positivos menores que 150 e que divididos por 39 deixam um resto igual ao
quociente. R: q = 1, 2, 3 e a = 40, 80, 120.
10) Seja d um divisor de n (d | n). Mostrar que cd | n se, e somente se, c | n
d.
11) Mostrar que para todo inteiro n, existem inteiros k e r tais que n = 3k + r e r = –1, 0, 1.
12) Mostrar que todo inteiro ímpar, quadrado perfeito, é da forma 4n + 1.
13) Na divisão de 392 por 45, determinar:
a) o maior inteiro que se pode somar ao dividendo sem alterar o quociente. R: 12.
b) o maior inteiro que se pode subtrair do dividendo sem alterar o quociente. R: 32.
14) Numa divisão de dois inteiros, o quociente é 16 e o resto 167. Determinar o maior inteiro que se
pode somar ao dividendo e ao divisor sem alterar o quociente. R: 11.
15) Achar o maior inteiro de quatro algarismos divisível por 13 e o menor inteiro de cinco
algarismos divisível por 15.
R: maior 9997 e o menor é 10.005.
UNIDADE IV – MÁXIMO DIVISOR COMUM - M. D. C
4.1 - Introdução:
Fazem parte do ensino fundamental, entre outras, as noções de Máximo Divisor Comum
(MDC), Mínimo Múltiplo Comum (MMC), Números primos e Fatoração, que compõem uma
parcela significativa da Teoria Elementar dos Números. No caso específico M.D.C, pretendemos
mostrar a relevância destes através da abordagem de exercícios para o aprofundamento teórico e
após o estudo do M.M.C veremos aplicações de forma contextualizada.
4.2 - Máximo Divisor Comum:
Definição 4.1 - Dados dois ou mais números inteiros não nulos denominamos máximo divisor
comum destes números ao maior número inteiro que é divisor simultaneamente de todos os
números dados. O mdc é o maior elemento da intersecção dos conjuntos dos divisores positivos dos
números dados.
Definição 4.2 - Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0). Chama-se
máximo divisor comum de a e b o inteiro positivo d (d > 0) que satisfaz às condições:
1) d | a e d | b.
2) Se c | a e c | b, então c d.
Notação: d = mdc(a, b).
4.3 - Existência e Unicidade do MDC:
Teorema 4.1 - Se a e b são inteiros não conjuntamente nulos (a 0 ou b 0), então existe e é único
o mdc(a,b); além disso, existem inteiros x e y tais que mdc(a, b) = ax + by, isto é, o mdc(a, b) é uma
combinação linear de a e b.
Teorema 4.2 - Se a e b são dois inteiros não conjuntamente nulos (a 0 ou b 0), então o conjunto
de todos os múltiplos do mdc(a, b) = d é T = {ax + by | x,y Z}.
4.4 - Inteiros Primos entre si:
Definição 4.3 - Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0). Diz-se que a e b
são primos entre si se, e somente se, o mdc(a, b) = 1.
Teorema 4.3 - Dois inteiros a e b, não conjuntamente nulos (a 0 ou b 0), são primos entre si se,
e somente se, existe inteiros x e y tais que ax + by = 1.
Corolário 4.1 - Se o mdc(a, b) = d, então mdc a b
,d d
= 1.
Corolário 4.2 - Se a | b e se mdc(b, c) = 1, então o mdc(a, c) = 1.
Corolário 4.3 - Se a | c, se b | c e se mdc(a, b) = 1, então ab | c.
Corolário 4.4 - Se mdc(a, b) = 1 = mdc(a, c), então o mdc(a, bc) = 1.
Corolário 4.5 - Se mdc(a, bc) = 1, então mdc(a, b) = 1 = mdc(a, c).
Teorema 4.4 - (de Euclides) Se a | bc e se o mdc(a, b) = 1 então a | c.
4.5 - Caracterização do MDC de dois Inteiros:
Teorema 4.5 - Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0). Um inteiro
positivo d (d > 0) é o mdc(a, b) se, e somente se, satisfaz às condições:
1) d | a e d | b.
2) Se c | a e c | b, então c | d.
4.6 - Caracterização do MDC de dois Inteiros:
O conceito de máximo divisor comum, definido para dois inteiros a e b, estende-se de maneira
natural a mais de dois inteiros. No caso de três inteiros a, b e c, não todos nulos, o mdc (a, b, c) é o
inteiro positivo d (d > 0) que, satisfaz às condições:
1) d | a, d | b e d | c.
2) Se e | a, se e | b e se e | b, então e d.
4.7 - MDC de Vários Inteiros:
Teorema 4.6 - O mdc(a,b,c) = mdc(mdc(a,b), c).
Questões Resolvidas
01) Determinar:
(a) mdc(11, 99).
Solução: 99: 11 = 9, resto zero mdc(11,99) = 11
R: 11.
(b) mdc(-21, 14).
Solução: mdc(-21, 14) = mdc(21, 14)
21: 14 = 1 resto 7.
14:7 = 2, resto zero mdc(-21, 14) = 7
R: 7.
(c) mdc(17, 18).
Solução: 18: 17 = 1, resto 1
17: 1 = 17 resto 0 mdc(17, 18) = 1.
R: 1.
02) Achar o menor inteiro positivo c da forma c = 22x + 55y onde x e y são dois inteiros.
Solução: Como o menor inteiro da forma 22x + 55y é o mdc(22, 55) então c = 11.
03) Calcular mdc(n, n + 2), sendo n um inteiro par.
Solução: Seja d = mdc(n, n+2). Então d | n e d | (n+2). Como d | n e d | (n+2), então, d | 2 e portanto,
d = 1 ou d = 2 e como n é par a resposta será d = 2 (o maior dos divisores).
04) Calcular mdc(n, n + 2), sendo n um inteiro ímpar.
Solução: Seja d = mdc(n, n+2). Então, usando o mesmo raciocínio anterior, d = 1 ou d = 2. Mas
como n é ímpar, concluímos que d = 1.
05) Sendo n um inteiro qualquer, calcular o mdc(n, n + 1)
Solução: Seja d = mdc(n, n+1). Então d | n e d | (n+1). Como d | n e d | (n+1), então d | 1. Logo d =
1.
Sejam a, b e c inteiros. Demonstrar:
06) Existem inteiros x e y tais que c = ax + by se, e somente se, mdc(a, b) | c.
Solução: Demonstraremos primeiramente, a ida:
Seja d = mdc(a, b). Então d | a e d | b e logo d | (ax + by) quaisquer que sejam os inteiros x e y.
Portanto d | c, desde que c = ax + by por hipótese.
Solução: Demonstraremos agora a volta:
Seja d = mdc(a, b). Como d | c, temos c = dq. Sendo d o mdc(a, b) existem inteiros x’ e y
’ tais que d
= ax’ + by
’. Substituindo este valor na igualdade c = dq obtemos: c = (ax
’ + by
’ )q. Daí tiramos valor
c = a(x’q) + b(y
’q). Fazendo x
’q = x e y
’q = y temos c = ax + by.
07) Se existem inteiros x e y tais que ax + by = mdc(a, b), então o mdc(x, y) = 1
Solução: Seja d = mdc(a, b). Então existem inteiros x e y tais que d = ax + by, onde d | a e d |b.
Dividindo ambos os membros por d ( d > 0), obtemos: a b
x yd d
= 1 Como d | a e d | b as
expressões entre parêntesis são inteiras, que representaremos por k1 e k2 obtendo assim: xk1 + yk2 =
1, donde concluímos que mdc(x, y) = 1.
Determinar inteiros positivos a e b sabendo:
08) a + b = 63 e o mdc(a, b) = 9.
Solução: Se 9 = mdc(a, b), temos que 9 | a e 9 | b ou a = 9q1 e b = 9q2. Substituindo estes valores na
igualdade a + b = 63 temos: 9q1 + 9q2 = 63; daí, dividindo por 9 obtemos:
q1 + q2 = 7. Como q1 e q2 são primos entre si, devemos procurar inteiros positivos primos entre si
que somem 7. Temos os seguintes valores:
q1 = 1 e q2 = 6; q1 = 2 e q2 = 5 e q1 = 3 e q2 = 4. Assim obtemos para a e b os seguintes valores:
a = 9 e b = 54; a = 18 e b = 45 e a = 27 e b = 36.
09) ab = 756 e o mdc(a, b) = 6.
Solução: Se 6 = mdc(a, b) temos que 6 | a e 6 | b ou a = 6q1 e b = 6q2. Substituindo na igualdade a b
= 756, temos 6q16q2 = 756. Daí obtemos que q1q2 = 21. Do mesmo modo, como q1 e q2 são primos
entre si, devemos encontrar inteiros positivos cujo produto dê 21. Os valores são: q1 = 1 e q2 = 21 e
q1 = 3 e q2 = 7. Destes valores tiramos os valores de a e b: a = 6 e b = 126 e a = 18 e b = 42.
10) Demonstrar que, se n = abc + 1, então o mdc (n, a) = mdc(n, b) = mdc(n, c) = 1.
Solução: Provemos que mdc(n, a) = 1. O mesmo pode ser feito para b e c.
Seja d = mdc(n, a). Então d | n e d | a. Podemos dizer, portanto, que d | abc, múltiplo de a. Como d |
n e d | abc, então d | 1, pois n – abc = 1. Logo d = 1.
11) O mdc(a, 4) = 2 = mdc(b, 4). Demonstrar que o mdc(a + b, 4) = 4.
Solução: Temos mdc(a, 4) = 2 e mdc(b, 4) = 2. Concluímos que a e b são números pares e não são
múltiplos de 4 , pois se o fossem, 2 não seria o mdc entre eles. Logo o resto da divisão de a e b por 4
é 2. Assim a = 4q1 + 2 e b = 4q2 + 2. Somando membro a membro estas desigualdades, temos a + b
= 4q1 + 2 + 4q2 + 2 ou a + b = 4 (q1 + q2 + 1). Logo, 4 | (a + b) e por conseguinte mdc(a + b, 4) = 4.
12) Sendo a e b dois inteiros não conjuntamente nulos (a 0 ou b 0), mostrar:
mdc(a, b) = mdc(-a, b) = mdc(a, -b) = mdc(-a, -b).
Solução: Se c | a então a = qc. Temos que - a = (-q)c c | (-a) todo divisor de a é divisor de (-a)
maior divisor de a é também o maior divisor de –a. O mesmo ocorre com b e –b. Portanto,
podemos concluir que o maior divisor comum de (a e b), é também de (–a e b), de (a e –b) e o de (-
a, -b). Assim, mdc(a, b) = mdc(-a, b) = mdc(a, -b) = mdc(-a, -b).
13) Demonstrar que mdc(mdc(a, b), b) = mdc(a, b).
Solução: A definição do mdc de três números mdc(a, b, c) = mdc(mdc(a, b), c), quaisquer que
sejam a, b e c. Fazendo c = b, temos mdc(mdc(a, b), b) = mdc(a, b, b) = mdc(a, mdc(b, b)) = mdc(a,
b) pois mdc(b, b) = b.
14) Demonstrar que o mdc(n + k, k) = 1 se e somente se o mdc(n, k) = 1.
Solução: Se mdc(n + k, k) = 1, então existem os inteiros x e y, tais que (n + k)x+ ky = 1 nx +
k(a + b) = 1 (n, k) = 1.
Por outro lado, se mdc(n, k) = 1, então existem a e b tais que na + kb = 1. Fazendo a = x e b = x + y,
teremos nx + k(x + y) = 1 (n + k)x + ky = 1 mdc(n + k), k) = 1.
15) Calcular o mdc(a + b, a – b) sabendo que a e b são inteiros primos entre si.
Solução:
Se a e b são primos entre si, não podem ser ambos pares, pois o mdc seria 2 ou múltiplo de 2.
Portanto, a e b são ambos ímpares ou são de paridades diferentes.
(1º caso) a e b com paridades diferentes – (a = 2k + 1 b = 2k’)
Temos então:
a + b = 2k + 1 + 2k’ = 2(k + k’) + 1 = 2n + 1 a + b é ímpar.
a – b = 2k + 1 – 2k’ = 2(k – k’) + 1 = 2m + 1 a – b é ímpar.
Portanto, o mdc(a + b, a – b) é um número ímpar.
Seja então mdc(a + b, a – b) = 2k + 1 existem x e y tais que (a + b)x + (a – b)y = 2k + 1
[(a + b)/(2k+1)]x + [(a – b)/(2k + 1)]y = 1 (a + b)/(2k + 1) e (a – b)/(k + 1) são primos entre si.
Fazendo r = (a + b)/(2k + 1) e s = (a – b)/(2k + 1), resulta: a + b = r(2k + 1) (i) e a – b = s(2k + 1)
(ii).Como (a + b), (a – b) e (2k + 1) são ímpares, r e s também são ímpares.
Além disso r e s ímpares, r + s e r – s são pares.
Somando membro a membro as igualdades (i) e (ii), resulta:
(1) 2a = (2k + 1)(r + s) a = (2k + 1)[(r + s)/2] pois s + r é par (inteiro), portanto 2 | (r + s).
Assim, existe o inteiro (r + s)/2, tal que a = (2k + 1)[(r + s)/2) 2k + 1 | a.
Subtraindo membro a membro as igualdades (i) e (ii),
(2) 2b = (2k + 1)(r – s) b = (2k + 1)[(r – s)/2]. (r – s) é par. Portanto, (r – s)/2 é inteiro.
Assim, existe o inteiro (r – s)/2, tal que b = (2k + 1)[(r – s)/2] 2k + 1 | b.
Ora, a e b são primos entre si. Portanto, o único divisor comum é 2k + 1. Disto permite-se escrever
2k + 1 = 1 1 = mdc(a + b, a – b).
(2º caso) a e b são ímpares a = 2k + 1 e b = 2k’ + 1.
Temos, então:
(a + b) = 2k + 1 + 2k’ + 1 (a + b) = 2(k + k’ + 1)
(a – b) = 2k + 1 – 2k’ – 1 = 2(k – k’)
Das igualdades acima, concluímos que (a + b) e (a – b) são pares. Portanto, o mdc é da forma 2k.
Assim, existem x e y, tais que: (a + b)x + (a – b)y = 2k r = (a + b)/2k e s = (a – b)/2k são primos
entre si. (a + b) = 2kr (i) e (a – b) = 2ks (ii).
Somando membro a membro, 2a = 2k(r + s) a = k(r + s) k | a.
Subtraindo membro a membro, 2b = 2k(r – s) b = k(r – s) k | b.
Como a e b são primos entre si, o único divisor comum de a e b é 1. Portanto, k = 1 e Mdc(a + b, a –
b) = 2k mdc(a + b, a – b) =2.1 = 2.
Portanto, se a e b são primos então mdc(a + b, a – b) é 1 ou 2.
16) O mdc de dois inteiros positivos é 10 e o maior deles é 120. Determinar o outro inteiro.
Solução: Seja a o outro número. “a” deve ser um múltiplo de 10 que não divide 120. Como o maior
dos números e 120, a deve ser menor que 120. Os múltiplos de 10 que não dividem 120 são: 50, 70,
90 e 110.
17) O mdc(a, b) = p, sendo p um primo. Achar os possíveis valores do:
( a ) mdc(a2, b).
Solução: Sejam a = p.a1.a2.a3 ...an, onde p, a1, a2, a3, ... an são os fatores primos de a e b =
p.b1.b2.b3...bn, onde p, b1, b2, b3, ...bn são os fatores primos de b. Assim, a2 = p.p.a1.a2.a2.a3a3...an.an
que a2 e b são divisíveis ao mesmo tempo apenas por p. mdc(a
2, b) = p.
( b ) mdc(a3, b) = p, mesma conclusão acima.
( c ) mdc(a2, b
3) = p
2. Pois aparecem 2 fatores iguais a p em a
2 e 3 fatores iguais a p em b
3.
18) Sejam a e k inteiros não conjuntamente nulos. Demonstrar que mdc(a, a + k) | k.
Solução: Seja m o mdc(a, a + k). Assim, existem os inteiros x e y tais que: a = mx e a + k = my.
Subtraindo primeira igualdade da segunda resulta: (a + k) – a = my – mx k = m(y – x). Como x e
y são inteiros, y - x é inteiro. Portanto, existe o inteiro (y – x) tal que k = m(y – x) m | k ou
mdc(a, a + k) | k.
19) Seja o quadrado abaixo em que cada lado mede 3 cm. Quantos quadradinhos de 1cm² cabem no
quadrado?
R: 9 quadradinhos.
Com o mesmo quadrado acima, obter o valor de 3². R: 3² = 9.
20) De quantos cubinhos de 1cm de lado, isto é, um centímetro cúbico, precisaremos para construir
um cubo com 3cm de comprimento, 3cm de largura e 3cm de altura?
R: 27 cubinhos.
Questões Propostas
01)Achar os elementos do conjunto A = {1, 2, 3, 4, 5} que são primos com 8. R: 1, 3 e 5.
02) Sabendo que o mdc(a, 0) = 13, achar todos os valores do inteiro a. R: 13
03) Sendo n um inteiro qualquer, calcular o mdc(n, n + 1). R: 1.
04) Sendo n um inteiro qualquer, achar os possíveis valores do máximo divisor comum dos inteiros
n e n + 10. R: 1, 2, 5, 10.
05) Sendo n um inteiro qualquer, calcular o mdc(n – 1, n2 + n + 1). R: 1 ou 3.
06) Sejam a, b e c inteiros. Demonstrar:
( a ) se o mdc(a, b) = 1 então o mdc(ac, b) = mdc(b, c) Portanto, todo divisor de d é divisor de ac.
( b ) Se o mdc(a, b) = 1 e se c | (a + b), então o mdc(a, c) = 1 e o mdc(b, c) = 1.
( c ) se b | c, então o mdc(a, b) = mdc(a + c, b).
( d ) Se mdc(a, b) = 1, então mdc(am
, bn) = 1, onde m e n são inteiros positivos.
07) Achar o maior inteiro positivo pelo qual se devem dividir os inteiros 160, 198 e 370 para que os
restos sejam respectivamente 7, 11 e 13. R: 17.
08) Os restos das divisões dos inteiros 4933 e 4435 por um inteiro positivo n são respectivamente
37 e 19. Achar o inteiro n. R: n = 96 ou n = 48.
09) Demonstrar que, se a | bc e se mdc(a, b) = d, então a | cd.
10) Demonstrar que, se a | c, se b | c e se o mdc(a, b) = d então ab | cd.
11) Demonstrar que se mdc(a, b) = 1 e se mdc(a,c) = d,então mdc(a, bc) = d.
12) O inteiro ímpar d é um divisor de a + b e de a – b. Demontrar que d também é um divisor do
mdc(a, b).
13) Os inteiros positivos m e n são tais que o mdc(m, n) = d. Mostrar que o mdc(2m
– 1, 2n – 1) = 2
d
– 1.
14) Demonstrar que mdc(a, b) = mdc(a, b, a + b).
15) Demonstrar que mdc(a, b) = mdc(a, b, ax + by), quaisquer que seja os inteiros x e y.
16) Demonstrar que se o mdc(a, b) = d então o mdc(a2, b
2) = d
2.
17) Demonstrar que mdc(a, b) = mdc(a, c) implica mdc(a2, b
2) = mdc(a
2, c
2).
18) Demonstrar que mdc(a, b) = mdc(a, c) implica mdc(a, b) = mdc(a, b, c).
19) Demonstrar que mdc(a, b, c) = mdc(mdc(a, b), mdc(a, c).
20) Sejam a e b inteiros positivos tais que ab é um quadrado perfeito e o mdc(a, b) = 1. Demonstrar
que a e b são quadrados perfeitos.
21) Demonstrar que mdc( a + b, a – b) > mdc(a, b).
22) Sejam a, b, c, d (b d) inteiros tais que mdc(a, b) = mdc(c, d) = 1. Mostrar que a soma a/b + c/d
não é um inteiro.
23) Determinar os inteiros positivos a e b, sabendo que a2
– b2 = 7344 e mdc(a, b) = 12.
R: a = 312 e b = 300, ou a = 120 e b = 84.
24) Dividindo-se dois inteiros positivos pelo seu mdc, a soma dos quocientes é 8. Determinar os
dois inteiros, sabendo-se que sua soma é 384. R: 48 e 336 ou 144 e 240.
25) Três rolos de arame farpado têm, respectivamente, 168 m, 264m e 312 m. Deseja-se cortá-los
em partes de comprimentos iguais, de maneira que cada parte seja a maior possível. Qual o
comprimento e o número de partes? R: 24 m e 31 partes.
26) Um terreno retangular de 221 m por 117 m será cercado. Em toda a volta deste cercado serão
plantadas árvores igualmente espaçadas. Qual o maior espaço possível entre as árvores? R: 13 m.
27) Em uma excursão ao parque do Caraça, em Minas Gerais, viajaram dois ônibus um com 42
pessoas e outro com 30. Os guias queriam organizar grupos com o mesmo número de pessoas, mas
sem misturar as pessoas que vieram nos dias ônibus. Eles queriam também que esse número de
pessoas por grupo fosse o maior possível. Quantos grupos e de pessoas, foram formadas em cada
ônibus?
R: Foram formados 12 grupos de 6 pessoas sendo 7 grupos no 1º ônibus e 5 grupos no 2º ônibus.
28) Uma tecelagem fabrica peças de tecidos em três metragens diferentes: 45m, 60m e 105m.
Desejando cortar as peças em partes de mesmo comprimento e que esteja e que este seja o maior
possível, qual deverá ser o comprimento de cada parte? Em quantas partes cada peça será cortada?
R: Cada parte deverá ter 15m de comprimento. A peça 45m será cortada em 3 partes, a peça de 60m
será cortada em 4 partes e a peça de 105m em 7 partes.
29) De um aeroporto, partem todos os dias, 3 aviões que fazem rotas internacionais. O primeiro
avião faz a rota de ida e volta em 4 dias, o segundo em 5 dias e o terceiro em 10 dias. Se num certo
dia os três aviões partem simultaneamente, depois de quantos dias esses aviões partirão novamente
no mesmo dia?
R: 20 dias.
UNIDADE V – ALGORITMO DE EUCLIDES: MÍNIMO MÚLTIMPLO COMUM – M.M.C
5.1 - Introdução:
Fazem parte do ensino fundamental, entre outras, as noções de Máximo Divisor Comum
(MDC), Mínimo Múltiplo Comum (MMC), Números primos e Fatoração, que compõem uma
parcela significativa da Teoria Elementar dos Números. No caso específico M.M.C, pretende-se
mostrar a relevância destes através da abordagem de temas atuais onde aparecem e sua conexão com
outras áreas do conhecimento. Com isso, visamos a contextualização e a interdisciplinaridade,
ambas importantes para que o aluno veja a matemática como uma aliada na vida prática e sua
relação com outras disciplinas. Neste sentido, busca-se que o aluno perceba que os números e a
álgebra formam um sistema de códigos ligados especialmente a diversas aplicações.
Definição 5.1 - Dados dois ou mais números inteiros não nulos denominamos mínimo múltiplo
comum destes números dados ao menor número inteiro positivo que é múltiplo simultaneamente te
todos os números dados. O mmc é o menor elemento da intersecção dos conjuntos dos múltiplos
positivos dos números dados.
Lema: 5.2 - Se a = bq + r, então mdc(a, b) = mdc(b, r):
5.3 - Algoritmo de Euclides: Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0)
cujo máximo divisor comum se deseja determinar.
1) Se a 0, então mdc(a,0) = |a|.
2) Se a 0, então mdc(a,a) = |a|.
3) Se b | a, então o mdc(a,b) = |b|.
4) Se a não divide b e b não divide a, então a = bq + r e mdc(a, b) = mdc(b, r).
Dispositivo prático para o cálculo do Máximo divisor comum de dois inteiros positivos a e b é
denominado Algoritmo de Euclides.
q1 q2 q3 qn qn - 1
a b r1 r2 rn - 1 rn
r1 r2 r2 r4 0
Teorema 5.1 - Se k > 0, então o mdc(ka, kb) = k mdc(a, b).
Corolário 5.1 - Para todo k 0, o mdc(ka, kb) = |k| mdc(a, b).
5.4 - Múltiplos Comuns de dois Inteiros:
M(a) = {x Z | a | x} = {aq | q Z}.
M(1) = M(–1) = Z.
Definição 5.2 - Sejam a e b dois inteiros diferentes de zero (a 0 e b 0). Chama-se múltiplo
comum de a e b todo inteiro x tal que a | x e b | x. M(a, b) = M(a) M(b).
5.5 - Mínimo Múltiplo Comum:
Definição 5.3 - Sejam a e b dois inteiros diferentes de zero (a 0 e b 0). Chama-se mínimo
múltiplo comum de a e b o inteiro positivo m (m > 0) que satisfaz às condições:
1. a | m e b | m.
2. se a | c e b | c, com c > 0, então m c.
Notação: m = mmc(a, b).
Observação: a) mmc(a, b) ab. b) Se a | b, então mmc(a, b) = |b|.
5.6 - MMC de Vários inteiros:
O conceito de mínimo múltiplo comum, definido para dois inteiros a e b, estende-se de
maneira natural a mais de dois inteiros. No caso de três inteiros a, b e c, diferentes de zero, o
m.m.c(a, b, c) é o inteiro positivo m(m > 0) que satisfaz às condições:
1) a | m, b | m e c | m.
2) Se a | e, b | e, e se c | e, com e > 0, então m e.
5.7 - Relação Entre o MDC e o MMC:
Teorema 5.2 - Para todo par de inteiros positivos a e b subsiste a relação mdc(a, b) mmc(a, b) = ab.
Corolário 5.2 - Para todo par de inteiros positivos a e b, o mmc(a, b) = ab se, e somente se mdc(a,
b) = 1.
5.7 - Regra Prática para obtenção do MDC e MMC de Vários inteiros:
Podemos determinar o mdc e o mmc de dois ou mais números inteiros positivos procedendo
do seguinte modo:
1º) Fatoramos os números, decompondo-se em fatores primos positivos;
2º) Calculamos o mdc multiplicando os fatores comuns aos números, tomando cada fator uma só
vez e com o menor expoente que ele apresenta nas decomposições dos números dados;
3º) Calculamos o mmc multiplicando os fatores comuns e os não comuns aos números, tomando
cada fator uma só vez e com o maior expoente que ele apresenta nas decomposições dos números
dados;
Exemplo: Dados as seguintes decomposições de inteiros a = 32.19.71
2, b = 2.3
5.19.61 e c =
24.19
2.71, determine:
a) MDC(a, b) = 32.19
b) MMC(a, b) = 24. 3
5.19
2.61.71
2
c) MMC(a, c) = 24. 3
2.19
2.71
2
d) MDC(a, b, c) = 19
e) MDC(b, c) = 2.19
Questões Resolvidas
01) Usando o algoritmo de Euclides, achar os inteiros x e y que verifiquem cada uma das seguintes
igualdades:
a) mdc(56, 72) = 56x + 72y
mdc(56, 72) = 8 8 = 56x + 72y
72 = 56.1 + 16
56 = 16.3 + 8
16 = 8.2 + 0
b) mdc(24, 138) = 24x + 138y
138 = 24.5 + 18
24 = 18.1 + 6
18 = 6.3 + 0 (mdc = 6)
02) Achar inteiros x, y e z que verifiquem as seguintes igualdades:
1) 11x + 19y + 3z = 1
2) 56x + 6y + 32z = 2
3) 6x + 3y + 15z = 9
4) 14x + 7y + 21z = 4
Solução:
01) Achando o mdc(11, 19)
1 1 2 1 2
19 11 8 3 2 1
8 3 2 1 0
Usando o algoritmo da divisão, podemos escrever:
19 = 11 x 1 + 8
11 = 8 x 1 + 3
8 = 3 x 2 + 2
3 = 2 x 1 + 1
2 = 1 x 2
Desprezando a última igualdade, eliminemos os restos, a partir da penúltima igualdade:
1 = 3 – 2
1 = 3 – (8 – 3 x 2)
1 = 3 x 3 – 8
1 = (11 – 8) x 3 – 8
1 = 11 x 3 – 8 x 4
1 = 11 x 3 – (19 – 11) x 4
1 = 11 x 7 – 19 x 4
Tomando a penúltima igualdade;
8 = 56 – 16.3. Tirando o valor de 16 na primeira igualdade e
substituindo na penúltima:
8 = 56 – (72 – 56.1).3 8 = 56 + 56.3 – 72.3
8 = 56.4 + 72(-3). Portanto, x = 4 e y = -3.
6 = 24 – 18.1
6 = 24 – (138 – 24.5).1
6 = 24 + 24.5 – 138.1
6 = 24.6 + 138(-1) x = 6 e y = -1
Achemos agora o mdc(3, 1). Como mdc(3, 1) = 1, vamos escrever este mdc em função de 3 e 1:
1 = 3 x 1 + 1 x (-2). Agora substituamos o valor de 1, dado na igualdade acima, nesta última
igualdade:
1 = 3 x 1 + (11 x 7 – 19 x 4) (–2)
1 = 3 x 1 + 11 (–14) + 19 x 8 ou 1 = 11 (–14) + 19(8) + 3(1). Logo x = –14, y = 8 e z = 1.
02) 56x + 6y + 32z = 2. Achando o mdc(56, 32)
Usando o algoritmo da divisão, podemos escrever:
56 = 32.1 + 24
32 = 24.1 + 8
24 = 8.3 Desprezando a última igualdade e eliminando os restos a partir da penúltima:
8 = 32 – 24
8 = 32 – (56 – 32)
8 = 32.2 + 56(–1)
(1) Achemos o mdc(8, 6)
1 3
8 6 2
2 0
Usando o algoritmo da divisão, podemos escrever:
8 = 6 + 2
2 = 8 + 6(–1) Agora, substituamos o valor de 8 na expressão (1)
2 = 32(2) + 56(–1) + 6(–1)
2 = 56(–1) + 6(–1) + 32(2) .Logo, x = –1, y = –1 e z = 2.
03) 6x + 3y + 15z = 9
Achando o mdc(15, 6)
Usando o algoritmo da divisão, podemos escrever:
15 = 6.2 + 3
3 = 15(1) + 6(–2)
(1) Achemos o mdc(3, 3).Como o mdc(3, 3) = 3,vamos escrever 3 como combinação de 3 e 3: 3 =
3(2) + 3(–1) Substituamos o valor de 3 encontrado na igualdade (1) nesta última igualdade:
3 = 3(2) + [15(1) + 6(–2)](–1)
3 = 3(2) + 15(–1) + 6(2). Como escrever 9 como combinação linear de x, y e z, devemos multiplicar
por 3 esta última igualdade, obtendo:
1 1 3
56 32 24 8
24 8 0
2 2
15 6 3
3 0
9 = 3(6) + 15(–3) + 6(6)
9 = 6(6) + 3(6) + 15(–3). Logo, x = 6, y = 6 e z = –3
04) 14x + 7y + 21z = 4
Como o mdc(14, 7, 21) = 7 e 7 não divide 4, então a equação não tem solução inteira.
Calcular:
5) mmc (45, 21).
6) mmc (83, 68).
7) mmc (120, 110).
Solução:
5) Como o mdc(45, 21) = 3, então, 3.mmc(45, 21) = 45.21. Logo, mmc(45, 21) = 315.
6) Como mdc(83, 68) = 1, então, 1.MMC(83, 68) = 8.8. Logo, mmc(83, 68) = 5644.
7) Como mdc(120, 110) = 10 , então, 10.mmc(210, 110) – 210.110. Logo, mmc(210, 110) = 1320
08) O mdc de dois inteiros positivos a e b é 8 e na sua determinação pelo algoritmo de Euclides os
quocientes sucessivamente obtidos foram 2, 1, 1 e 4. Calcular a e b.
Resolução: Temos o seguinte esquema:
2 1 1 4
8
Sabemos que se o mdc é 8, o último resto é zero e o penúltimo é 8. Assim, temos:
2 1 1 4
8
8 0
Como 8 é o divisor, 4 o quociente e zero o resto, achamos o dividendo desta divisão:
4 x 8 + 0 = 32. Logo o número anterior a oito é 32. Deste modo 32 será o outro resto
Temos o seguinte esquema:
2 1 1 4
32 8
32 8 0
Tendo 32 para divisor, 1 para quociente e 8 para resto, o próximo dividendo será:
32 x 1 + 8 = 40. De modo semelhante, encontramos os outros números:
2 1 1 4
184 72 40 32 8
40 32 8 0
Logo a = 184 e b = 72.
09) Usando o algoritmo de Euclides, determinar:
a) mdc(624, 504, 90).
Solução:
Pelo processo anterior acha-se o mdc(624, 504) que é 24. A seguir acha-se o mdc(24, 90) que é 6.
R: 6.
Determinar os inteiros positivos a e b sabendo:
10) ab = 4032 e o mmc(a, b) = 336.
11) mdc(a, b) = 8 e o mmc(a, b) = 560.
Soluções:
10) Como mmc(a, b) = 336, temos 336 = a k1 e 336 = b k2 .Multiplicando membro a membro estas
duas igualdades, temos: 336 x 336 = a b k1 k2. Substituindo o valor de a b = 4032 nesta última
igualdade, temos: 112896 = 4032 k1 k2 ou k1 k2 = 28. Assim, como k1 e k2 são primos entre si,
devemos procurar dois inteiros primos entre si, cujo produto é 28. Encontramos k1 = 1 e k2 = 28, k1
= 4 e k2 = 7. Com estes valores temos a = 336 e b = 12 e a = 84 e b = 48.
11) Temos: mdc(a, b) mmc(a, b) = a b. Então a b = 8 560. Temos, portanto um problema já
resolvido sobre mdc. A resposta será: a = 8, b = 560; a = 16, b = 280; a = 40, b = 112; a = 56, b =
80.
12) Se a soma de dois números é 320 e o mínimo múltiplo comum entre eles é 600, quais são esses
números? Qual é o máximo divisor comum entre eles?
Solução: Se X e Y são os números procurados, eles devem ser divisores de 600, logo devem
pertencer ao conjunto D(600):
R: {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 25, 30, 75, 100, 120, 150, 200, 300, 600}.
Pares de números deste conjunto que somam 320, são: 300 e 20 ou 200 e 120. O primeiro par não
serve, pois MMC (300, 20) = 300. Os números que servem são X = 200 e Y = 120, pois MMC (200,
120) = 600 e MDC (200, 120) = 40.
13) Se a diferença entre dois números naturais é 126 e o máximo divisor comum entre eles é 18,
quais são esses números?
Solução: Se X e Y são os números procurados, eles devem ser múltiplos de 18 e podem ser escritos
na forma X = 18a e Y = 18b onde a e b devem ser determinados. Assim: 18a - 18b = 126, de onde
segue que 18(a - b) = 18×7, o que é equivalente a: a - b = 7. Tomando a = 8 e b = 1 teremos X = 144
e Y = 18.
14) Se a soma de dois números naturais é 420 e o máximo divisor comum entre eles é 60, quais são
esses números?
Solução: Sejam X e Y os números procurados. Se MDC(X, Y)=60, os números X e Y devem ser
múltiplos de 60, logo podem ser escritos na forma X = 60a e Y = 60b onde a e b são números
inteiros positivos. Assim: 60a + 60b = 420, o que garante que a + b = 7. Devemos escolher números
naturais tal que a + b = 7, e assim, temos várias opções.
Se a = 6 e b = 1 então X =360 e Y = 60 Se a = 5 e b = 2 então X = 300 e Y = 120
Se a = 4 e b = 3 então X = 240 e Y = 180 Se a = 3 e b = 4 então X = 180 e Y = 240
Se a = 2 e b = 5 então X = 120 e Y = 300 Se a = 1 e b = 6 então X = 60 e Y = 360
Questões Propostas
01) Usando o algoritmo de Euclides, determinar o mdc (306, 657).
02) Usando o algoritmo de Euclides, determinar:
a) mdc(285, 675, 405). R: 5.
b) mdc(209, 299, 102). R:- 1.
c) mdc(69, 398, 253). R: 23.
03) Usando o algoritmo de Euclides, achar inteiros x e y que verifiquem a seguinte igualdade:
mdc(56, 72) = 56x + 72y.
04) Achar inteiros x e y que verifiquem a seguinte igualdade:
a) 78x + 32y = 2 e) 238x + 51y = 3
b) 104x + 91y = 13 f) 52x + 13y = 1
c) 31x + 19y = 7 g) 145x + 58y = 87
d) 42x + 26y = 16 h) 17x + 5y = -2
05) Achar inteiros x, y e z que verifiquem a igualdade 198x + 288y + 512z = mdc(198, 288, 512).
R: x = -5, y = -217, z = 124.
06) Calcular as soluções de todos os itens abaixo podendo ser obtidas a partir da propriedade
mdc(a,b).mmc(a, b) = a.b.
a) mmc(83, 68) R: 5644 b) mmc( 120, 110) R: 1320
c) mmc(86, 71) R: 6106 d) mmc(224, 192) R: 1344
e) mmc(1287, 507) R: 16731 f) mmc(143, 227) R: 32461
g) mmc(306, 657) R: 22338
07) Determinar a e b se, a + b = 589 e mmc a b
a b
( , )
mdc( , )84 .
R: a = 57 e b = 532; a = 217 e b = 372.
08) Demonstrar que se a e b são inteiros positivos tais que o mdc(a, b) = mmc(a, b) então a = b.
09) Sendo a e b inteiros positivos, demonstrar quo o mdc(a, b) sempre divide o mmc(a, b).
10) Quais os dois menores números pelos quais devemos dividir 252 e 234 para que os quocientes
obtidos sejam iguais?
R: 7 e 9.
11) Quais os números compreendidos entre 100 e 300 divisiveis ao mesmo tempo por 6, 9 e 15?
R: 180 e 270.
12) Quais os dois números de três algarismo divisiveis ao mesmo tempo por 8, 9 e 10?
R: 360 e 720.
13) Quais os dois menores números pelos quais devemos multiplicar 30 e 54 para que os produtos
obtidos seja iguais?
R: 9 e 5.
14) Calcular o número que, dividido por 12, 40 e 60 deixa sempre o mesmo resto 5?
R: 125.
15) A editora do livro “Matemática” recebeu pedidos de três livrarias sendo que um pedido de 1300
livros, o segundo pedido de 1950 livros e o terceiro pedido de 3900 livros. A editora deseja remeter
em n pacotes iguais de tal forma que n seja o menor possível. Calcule o valor de n.
R: 650 livros em cada pacote, num total de 11 pacotes.
16) Três peças de tecido medem respectivamente, 180m, 252m e 324m. Pretende-se dividir em
retalhos de igual comprimento. Qual deverá ser esse comprimento de modo que o número de
retalhos seja o menor possível? Em quantos pedaços as peças serão dividas?
R: O comprimento é de 36 m e o número de peças serão de 5, 7 e 9 pedaços.
17) Duas rodas dentadas se engrenam uma a outra, a primeira tem 48 dentes e demora 4 segundos
em cada volta, a segunda tem 104 dentes. Colocam-se em movimento e se pergunta ao cabo de
quanto tempo, se encontram na mesma posição inicial? R: 52 segundos.
18) Dois ciclistas correm sobre uma pista circular, partindo ao mesmo tempo de uma mesma linha.
O primeiro realiza uma volta completa, em 30 minutos e o segundo em 36 minutos. Quantas voltas
deverão dar cada um, para que tornem a encontrar-se, sobre a linha de partida? R: 6 e 5.
19) Um remédio deve ser tomado diariamente em intervalos regulares. O fabricante quer que a
duração desses intervalos seja um número inteiro de horas (como 3 horas, por exemplo, e nunca três
horas e meia). Além disso, o fabricante quer que os horários em que se deve tomar o remédio não
mudem de um dia para outro. Existem várias possibilidades para a duração dos intervalos que
satisfazem essas exigências do fabricante. Quais são elas?
R: D(24) 1, 2, 3, 4, 6, 8, 12, 24 .
20) Os planetas Júpiter, Saturno e Urano têm período de translação em torno do Sol de
aproximadamente 12, 30 e 84 anos, respectivamente. Quanto tempo decorrerá, depois de uma
observação, para que eles voltem a ocupar simultaneamente as mesmas posições em que se
encontram no momento de observação? R: 420 anos.
21) Duas pessoas fazendo seus exercícios diários partem de um mesmo ponto e contornam,
andando, uma pista oval que circula um jardim. Uma dessas pessoas andando de forma mais
acelerada dá uma volta completa na pista em 12 min, enquanto a outra, andando mais devagar, leva
20 min para completar a volta. Depois de quantos minutos essas duas pessoas voltarão a se
encontrar no ponto de partida? R: 60 minutos ou 1 hora.
22) Em um certo pais as eleições para presidente ocorrem de 6 em 6 anos e para senador de 4 em 4
anos. Em 1992 essas eleições coincidiram. Dê os anos das quatro próximas vezes em que elas
voltaram a coincidir. R: 2004, 2016, 2028, 2040.
23) José é daquelas pessoas que gostam de complicar as coisas. Quando lhe perguntam a sua idade,
ele responde “Tenho mais de 40 anos, menos de 50 e minha idade é um múltiplo de 3 e de 8”. Qual
é a idade do José?
R: 48 anos.
24) De uma rodoviária, parte um ônibus da empresa X a cada 20 minutos e um da empresa Y a cada
45 minutos. Supondo que esses dois ônibus partem juntos às 8 horas da manhã, depois de quanto
tempo os ônibus das duas empresas partiram juntos novamente?
R: 180 minutos ou 3 horas.
25) Numa estação rodoviária, os ônibus para a cidade A partem de 6 em 6 horas, e para a cidade B,
de 8 em 8 horas. Numa ocasião, um ônibus para a cidade A partiu junto com outro para cidade B.
Quanto tempo depois isso acontecerá de novo?
R: 24 horas.
26) Da Praça da República partem, às 6 horas da manhã, dois bondes das linhas X e Y, iniciando o
serviço do transporte de passageiros. Sabendo-se que o bonde X volta ao ponto de partida ao cabo
de 50 minutos, e o Y, ao cabo de 45 minutos, pergunta-se a que horas os dois bondes partirão
novamente juntos da praça da República?
27) Tenho três réguas divididas em partes iguais. Cada parte da primeira tem 3 mm, da segunda, 5
mm, e da terceira, 12 mm. Coloco as três réguas uma do lado da outra, de modo que as suas
extremidades coincidam. Quais são os traços de divisão das três réguas que coincidem?
Questões Propostas Envolvendo M.D.C e M.M.C
01) Determine s e t inteiros tais que MDC (a, b) = sa + tb para os seguintes pares de inteiros:
a) a = 145; b = 72 R: s = 1 e t = -2.
b) a = 896; b = 143 R: s = 64 e t = -401.
c) a = -123; b = 32 R: s = 13 e t = 50.
d) a = -75; b = -15 R: s = 0 e t = 1.
e) a = 102; b = 49 R: s = -12 e t = 25.
f) a = 138; b = 24 R: s = -1 e t = 6.
02) Classifique cada afirmação abaixo em Verdadeira ou Falsa, justificando:
a) MDC de dois números naturais expressos por n e 2 + 1 é sempre 1, para qualquer natural n. (V).
b) Considere a e b números naturais. Então MDC(a, ab + 1) = 2. (F).
c) MDC de dois números naturais é sempre um divisor do MMC destes mesmos números. Se a e b
são relativamente primos, MMC(a, b) = |a.b|. (V).
03) Seja a N :
Determine o mdc(a, a 1) . R: d = 1.
Quais as possibilidades para o mdc(a, a 2) ? R: d = (1, 2).
Quais as possibilidades para o mdc (a, a 6)? R: d = (1, 2, 3, 6).
Quais as possibilidades para o mdc(a, 3a 5) ? R: d = (1, 5).
04) Determine todos os números de três algarismos divisíveis por 8, 11 e 12, simultaneamente.
R: 264, 528 e 792.
05) Encontre todos os possíveis pares de números naturais cujo produto é 3600 e cujo mmc é 1200.
R: a = 3 e b = 1200 ou a = 48 e b = 75.
06) Determine dois números cuja soma é 120 e o mmc é 144.
R: a = 12 e b = 108 ou a = 24 e b = 96.
07) Achar o menor número natural que satisfaça simultaneamente as condições:
a) quando dividido por 2 tem resto 1. R: 3.
b) quando dividido por 3 tem resto 2. R: 5.
c) quando dividido por 4 tem resto 3. R: 7.
d) quando dividido por 5 tem resto 4. R: 9.
e) quando dividido por 6 tem resto 5. R: 11.
f) quando dividido por 7 tem resto 6. R: 13.
g) quando dividido por 8 tem resto 7. R: 15.
h) quando dividido por 9 tem resto 8. R: 17.
08) Determine todos os possíveis números naturais n tais que:
a) mmc(n, 54) = 54 R: D(54) 1, 2, 3, 6, 9, 18, 27, 54
b) mmc(n, 26) = 26 R: D(26) 1, 2, 13, 26
09) O mmc dois números naturais a e b é igual a 1260 e quando dividimos este mmc pelos números
a e b o produto dos quocientes obtidos é igual a 90. Determine todos os números naturais a e b
satisfazendo esta condição.
R: a = 1260 e b = 14, a = 630 e b = 28 e a = 252 e b = 70.
10) O mmc dois números naturais é 300. Dividimos este mmc por a e b, os quocientes obtidos são
tais que o seu produto vale 50. Determinem todos os pares de números a e b que satisfazem estas
condições.
R: a = 300 e b = 6 e a = 150 e b = 12.
11) Prove que o produto de três números consecutivos é divisível por 6.
12) Se o resto da divisão de um número primo por 3 é 1, mostre que na divisão deste número por 6
o resto também é 1.
13) Prove: se o resto da divisão de um número inteiro n por 6 é 5, então o resto da divisão de n por 3
é 2.
14) Considere a e b números naturais não primos entre si, cujo produto é 420. Determine mdc(a, b).
R: 2.
15) Sejam m = 26.3
3.5
2, n = 2
r.3
s.5
t e p = 2
5.5
4.7
3. Escreva as condições que devem satisfazer r, s e t
para que n seja divisor comum de m e p.
R: r = 5, s = 0 e t = 2.
16) Seja 411752 43x , 264 31173y e 263 474152z . Determine:
a) mdc (x,y) . R: 417
b) mdc (x,z) . R: 2.5
c) mdc (x,y,z) . R: 2.41
d) mmc(x,y,z) . R: 23.3
4.5
3.17
6.31
2.41.47
2
e) mmc(x,y) . R: 2.34.5
3.17
6.31
2.41
f) mmc(x,z) . R: 23.5
3.17
4.41
6.47
2
17) Encontre mdc (a,b) e mmc(a,b) , através da decomposição em fatores primos:
1) a = 20.600, b = 3.300. R: mdc (a, b) = 22.5
2 e mmc (a, b) = 2
3.3.5
2.11.103.
2) a = 147.875, b = 166.725. R: mdc (a, b) = 52.13 e mmc (a, b) = 5
3.7.13
2.19.
18) Encontre os valores de x para os quais mdc(20 + x, x) = 4.
R: os valores de x deverão ser divisível por 4.
19) Um professor dá aulas numa 7ª série, de 30 alunos, e numa 8ª série, de 18 alunos. Em cada sala,
ele formou grupos, e de todos os grupos (tanto na 7ª como na 8ª) tinham o mesmo número de
alunos. Qual é o maior número de alunos que cada grupo pode ter?
R: Cada grupo pode ter no máximo 6 alunos.
20) Na minha escola, há 180 alunos na 5ª série, 168 na 6ª série, 144 na 7ª série e 120 na 8ª. Para
uma feira de ciências, todas esses alunos serão organizados em grupos com o mesmo número de
elementos, sem misturar alunos de série diferentes.
a) Qual o número máximo de alunos que pode haver em cada grupo?
R: Pode ter no máximo 12 pessoas.
b) Quantos grupos serão formadas em cada uma das séries?
R: 15 grupos na 5ª série; 14 grupos na 6ª série; 12 grupos na 7ª série e 10 grupos na 8ª série.
21) Um país tem eleições para presidente de 5 em 5 anos, e para governador de 4 em 4 anos. Em
1998, essas duas eleições coincidiram. Dê os anos das três próximas vezes em que elas voltarão a
coincidir.
R: 2018, 2038 e 2058.
22) Um país tem eleições para presidente de 4 em 4 anos, e para senador de 6 em 6 anos. Em 1997,
houve eleições para presidente, e em 1988 para senador. As eleições poderão cair alguma vez no
mesmo ano? Explique sua resposta. R: não.
23) Muitos cometas nos visitam de tempos em tempos. Um certo cometa passa pela terra de 12 em
12 anos. Outro passa de 32 em 32 anos. Em 1913, os dois passaram por aqui. Qual é a próxima
ocasião em que os dois passarão pela Terra no mesmo ano?
R: 2009.
24) Um cometa A passa pela terra de 26 em 26 anos. O cometa B passa de 32 em 32 anos. Ambos
visitaram a Terra em 1930. Pergunta-se:
a) Qual será a próxima ocasião em que os dois visitarão a Terra no mesmo ano? R: 2346.
b) Depois de 1930, quantas serão as passagens do cometa a até que os dois visitem a Terra ao
mesmo ano? R: 16 passagens o cometa A e 13 passagens o cometa B.
25) Alguns cometam visitam a Terra periodicamente. Um cometa A visita terra de 12 em 12 anos. O
cometa B passa de 32 em 32 anos. Ambos visitaram a Terra em 1910. Qual é a próxima ocasião em
que os dois passarão pela Terra no mesmo ano? R: 2006.
26) Uma árvore de Natal tem três tipos de luzes. As vermelhas acendem a cada 8 segundos, as
verdes a cada 10 segundos e as amarelas a cada 12 segundos. Se elas acenderem todas juntas num
determinado momento, depois de quantos segundos ascenderão juntas novamente? R: 120
segundos.
27) Numa competição, partiram juntos dois ciclistas. O primeiro leva 20 segundos para dar uma
volta completa na pista e o segundo leva 18 segundos. Eles estarão juntos novamente depois de
quantos segundos? R: 180 segundos.
28) Uma certa Irmã recebe periodicamente a visita de seus três filhos, Sérgio a visita a cada 15 dias,
Marta a cada 20 dias e Rodrigo a cada 24 dias. Como hoje é dia de seu aniversário, os três filhos
foram vê-la. Daqui a quantos dias coincidira a visita dos três filhos? R: 120 dias.
29) No terminal de ônibus ABCD, chegam ônibus da Vila Romana a cada 30 minutos e da Vila
Inglesa a cada 40 minutos. De quanto em quanto tempo os horários dos ônibus coincidem?
R: 120 minutos.
30) Uma avenida mede 4500 metros. A partir do inicio da avenida, a cada 250 metros há uma
parada de ônibus, e a cada 225 metros uma para de bonde. Pergunta-se:
a) A que distância do inicio da avenida ocorre a primeira coincidência das paradas de ônibus e de
bonde? R: 2250m.
b) Quantos são os pontos comuns de paradas de ônibus e de bonde? R: 2 paradas comuns.
31) Durante um evento, o organizador pretende distribuir, como brindes, a alguns dos participantes,
caixas (kits), com o mesmo conteúdo, formado de camisetas e chaveiros. Sabe-se que ele possui
exatamente 200 camisetas e 120 chaveiros.
a) Decomponha os números 200 e 120 em fatores primos? R: 200 = 23.5
2 e 120 = 2.3.5
b) Determine os números máximos de caixas, com o mesmo conteúdo, que o organizador
conseguirá formar utilizando todos os chaveiros e camisetas disponíveis? R: 40.
32) (UnB) Quatro pessoas saem de uma praça a caminhar numa mesma hora. Elas repetirão várias
vezes o mesmo percurso, e seus percursos duram respectivamente, 5 min, 9 min, 10 min e 15 min.
Após quantos minutos elas estarão juntas na praça pela primeira vez? R: 90.
33) (UFRJ) Uma escola deseja distribuir cadernos entre os seus 480 alunos, de forma que cada um
deles receba o mesmo número de cadernos e não haja sobras. Os cadernos são adquiridos pela
escola em pacotes de uma dúzia e meia cada. Determine o número de pacotes que a escola deve
adquirir para que cada aluno receba a menor quantidade possível de cadernos. R: 80.
34) (UNICAMP) Três líquidos diferentes, A, B e C, devem ser distribuídos em barris iguais. Há 108
litros do líquido A, 96 litros do B e 72 litros do C. Para que o número de barris seja o menor
possível, qual deve ser a capacidade de cada barril? Quantos barris serão necessários para conter
cada um dos líquidos? R: 12 litros, números de barris: 9, 8 ou 6.
35) (PUC) Dois livros, um dos quais tem 256 páginas e o outro com 160 páginas, são formados por
fascículos com o mesmo número de páginas (superior a 10 e inferior a 50). Cada fascículo pode ter?
R: Pode ter 32 páginas.
36) (PUC) Um lojista dispõe de três peças de um mesmo tecido, cujos comprimentos são 48 m, 60
m e 80 m. Nas três peças, o tecido tem a mesma largura. Ele deseja vender o tecido em retalhos
iguais, cada um tendo a largura das peças e o maior comprimento possível, de modo a utilizar todo a
tecido das peças. Quantos retalhos ele deverá obter? R: 47.
37) (UNESP) Três cidades brasileiras, A, B e C, realizam grandes festas; de 5 em 5 meses em A, de
8 em 8 em B e 12 em 12 meses em C. Essas festas coincidiram em setembro de 1982. Coincidirão
novamente em? R: Setembro 1992.
38) (UFES) Três vergalhões, medindo 400 cm, 480 cm e 720 cm, devem ser cortados em pedaços
iguais, de maior tamanho possível, de modo que cada um deles tenha, por medida, um número
inteiro de centímetros. Desse modo, serão obtidos. Quantos pedaços? R: 20 pedaços.
39) (UFMG) As medidas tomadas sobre as divisas de um campo de formato triangular são 595 m,
459 m e 340 m. O proprietário deseja plantar cajueiros nessas divisas, de tal modo que as distancia
entre eles sejam iguais e as maiores possíveis. Se há um cajueiro em cada canto do campo, a
quantidade de cajueiros necessária ao plantio é? R: 82.
40) (UFRN) Para as festas natalinas, uma fábrica de doces lançará uma caixa de chocolates. O
número de chocolates poderá ser dividido igualmente (sem fracioná-las) entre 2, 3, 4, 5 e 6 pessoas,
não havendo sobra. O menor número de chocolates que essa caixa deverá conter será: R: 60.
41) (UFCE) Dois relógios tocam uma música periodicamente, um deles a cada 60 segundos e o
outro a cada 62 segundos. Se ambos tocassem (simultaneamente) ás 10 horas, que horas estarão
marcando os relógios quando voltarão a tocar juntos (simultaneamente) pela primeira vez após as 10
horas? R: 10 horas e 31 minutos.
42) (UFMG) Numa república hipotética, o presidente deve permanecer 4 anos em seu cargo; os
senadores, 6 anos e os deputados, 3 anos. Nessa república, houve eleição para os três cargos em
1989. A próxima eleição simultânea para esses três cargos ocorrerá, novamente, em: R: 2001.
43) (VUNESP) Uma concessionária vendeu no mês de outubro n carros do tipo A e m carros do
tipo B, totalizando 216 carros. Sabendo-se que o número de carros vendidos de cada tipo foi maior
do que 20, que foram vendidos menos carros do tipo A do que do tipo B, isto é, n < m, e que
MDC(n, m) = 18, os valores de n e m são, respectivamente: R: 90, 126.
44) (UFMG) De uma praça partem, ás 6 horas da manha, dois ônibus A e B. Sabe-se que o ônibus A
volta a ponto de partida a cada 50 minutos, e o ônibus B, a cada 45 minutos. O primeiro horário,
após as 6 horas, em que os ônibus partirão juntos é: R: 13 horas e 30 minutos.
45) (U. E. Londrina - PR) Existem para doação a escolas, 2000 ingressos de um espetáculo e 1575
de outro. Cada escola deve receber ingressos para somente um dos espetáculos e todas as escolas
devem receber a mesma quantidade de ingressos. Distribuindo-se todos os ingressos, o número
mínimo de escolas que podem ser contemplados nessa doação é: R: 143.
46) (U. E. Londrina - PR) Para levar os alunos de certa escola a um museu, pretende-se formar
grupos que tenham iguais quantidades de alunos e de modo que em cada grupo todos sejam do
mesmo sexo. Se nessa estudam 1350 rapazes e 1224 garotas e cada grupo deverá ser acompanhado
de um único professor, o número mínimo de professores necessários para acompanhar todos os
grupos nessa visita é: R: 143.
47) (UFMG) Entre algumas famílias de um bairro, foi distribuídos um total de 144 cadernos, 192
lápis e 216 borrachas. Essa distribuição foi feita de modo que o maior número possível de famílias
fosse contemplado e todas recebessem o mesmo número de cadernos, o mesmo número de lápis e o
mesmo número de borrachas, sem haver sobra de qualquer material. Nesse caso, o número de
cadernos que cada família ganhou foi de: R: 6.
48) (UE-RJ) Dois sinais luminosos fecham juntos num determinado instante. Um deles permanece
10 segundos fechado e 40 segundos aberto, enquanto o outro permanece 10 segundos fechado e 30
segundos abertos. O número mínimo de segundos necessários, a partir daquele instante, para que os
dois sinais voltem a fechar juntos outra vez é de: R: 200.
49) (UE-RJ) o número de fitas de vídeo que Marcela possui está compreendido entre 100 e 150.
Grupando-as de 12 em 12, de 15 em 15 ou de 20 em 20, sempre resta uma fita. A soma dos três
algarismo do número total de fitas que ela possui é igual a: R: 4.
50) (UFMG) Três atletas correm numa pista circular e gastam, respectivamente, 2,4 min, 2,0 min e
1,6 min, para completar uma volta na pista. Eles partem do mesmo local e no mesmo instante. Após
algum tempo, os três atletas se encontram, pela primeira vez, no local da largada. Nesse momento, o
atleta mais veloz estará completando: R: 15 voltas.
51) (Cesgranrio-RJ) Certo botânico desenvolveu em laboratório 3 variedades de uma mesma planta
V1, V2 e V3, que se desenvolvem cada uma a seu tempo, de acordo com a tabela abaixo. Plantando-
se as 3 variedades no mesmo dia, confiando-se na exatidão, não ocorrendo nenhum fato que
modifique os critérios da experiência tabulada e levando-se em conta que, a cada dia de colheita,
outra semente da mesma variedade será plantada, o número mínimo de sementes necessário para
que a colheita das três variedades ocorra simultaneamente será:
Variedades Tempo de germinação (em
semanas após o plantio)
Tempo de floração (em semanas
após a germinação)
Tempo para única colheita (em
semanas após a floração)
V1 4 3 1
V2 2 3 1
V3 1 2 1
R: 24
52) Numa escola pretende-se distribuir, em partes iguais, 36 puzzles e 90 livros pelas bibliotecas
das varias turmas. Qual o número Maximo de turmas que a escola pode ter, para que essa
distribuição possa ser feita? Para esse numero Maximo, quantos puzzles e quantos livros receberão
cada biblioteca de turma? R:
53) Três amigas, a Ana, a Patrícia e a Lena tiveram folga dos respectivos empregos no sábado
passado. Sabendo que a Ana tem folga a um sábado de 6 em 6 semanas, a Patrícia de 3 em 3
semanas e a Lena de 4 em 4 semanas, quantas semanas vão passar até que as três amigas estejam de
folga, em simultâneo, a um sábado? R:
54) Duas rodas gigantes começam girar, num mesmo instante, com uma pessoa na posição mais
baixa em cada uma. A primeira dá uma volta em 30 segundos e a segunda dá uma volta em 35
segundos. As duas pessoas estarão ambas novamente na posição mais baixa após: R:
55) Três cidades A, B e C, realizam grandes festas: de 5 em 5 meses em A, de 8 em 8 meses em B e
de 12 em 12 meses em C. Essas festas coincidiram em setembro de 1982. Coincidirão novamente
em: R:
UNIDADE VI – NÚMEROS PRIMOS
6.1 - Introdução:
No ano de 2002 três matemáticos indianos descobriram um algoritmo de primariedade, que
informa se um dado número é primo ou não. Essa descoberta divulgada pela imprensa causou uma
preocupação mundial devido os códigos criptográficos que utilizam os números primos.
Já tinha lido sobre criptografia e sabia da sua importância para a proteção das informações, o
que despertou o meu interesse sobre o alcance desta descoberta, e na medida que a pesquisa se
desenvolvia outros movimentos em torno dos números primos apareciam, envolvendo desde
matemáticos e técnicos de computação profissionais até usuários de computadores domésticos.
O número é a entidade mais importante da Matemática estando na origem de diversos ramos
desta ciência. Entre os seres vivos, o homem é um dos poucos que possui senso numérico. Por isso,
desde os primórdios da raça humana os números já estavam presentes, tendo surgido para auxiliar o
homem a controlar quantidades a partir do contraste entre pouco e muito, resultando na criação dos
primeiros sistemas de contagem. Juntamente com a linguagem, a escrita e outras habilidades, o
número está no conjunto das criações humanas em que se baseou o desenvolvimento das nossas
sociedades. Nesta unidade, falaremos sobre números, mas de um tipo especial os números primos. É
um assunto em que muitos especialistas em segurança eletrônica de dados tem conhecimento, e a
grande maioria das pessoas não sabem que a inviolabilidade dos seus dados pessoais depende em
parte destes números. Os números primos, um conhecimento sem aplicação desde as civilizações
mais antigas, são a base dos códigos de segurança de informação para computadores. Como estamos
vivendo, segundo alguns historiadores e sociólogos na "Era da Informação" pode-se perceber sua
importância para a nossa vida diária, embora não apareçam de forma explícita. A propósito,
podemos citar a frase do matemático Nicolai Lobachevsky (1793-1856) "Não há ramo da
Matemática, por abstrato que seja, que não possa um dia vir a ser aplicado nos fenômenos do
mundo real".
Os primos são apresentados pela primeira vez aos alunos na 5a série e depois são quase
esquecidos. No nível médio, apesar do aluno estar mais amadurecido para a Matemática, eles não
reaparecem, embora pudessem ajudar na fixação do conteúdo específico, assim como devido ao
fascínio que exercem por conta das curiosidades e mistérios que os envolvem, despertar no aluno o
gosto por problemas da Teoria dos Números. Cabe ressaltar, que os números primos tem ganhado
importância por causa das aplicações na criptografia, deixando de ser uma mera curiosidade.
Desta forma, um papel de destaque está reservado para o conhecimento matemático, já que
ele é a "porta de entrada" para o mundo tecnológico. Segundo Ubiratan D' Ambrosio (1996)" a
educação para a cidadania, que é um dos grandes objetivos da educação de hoje, exige uma
apreciação do conhecimento moderno, impregnado de ciência e tecnologia".
Os números primos são um exemplo para os alunos, de como podemos a partir de uma
definição antiga e relativamente simples, construir uma teoria que foi sendo enriquecida ao longo do
tempo de outros conhecimentos, culminando no seu aproveitamento em aplicações tecnológicas de
última geração.
6.2 - Números Primos:
Definição 6.1 - Dizemos que um número inteiro positivo p maior que 1 é primo, se, e somente se, p
possui exatamente dois divisores positivos distintos, ou seja, 1, p .
Exemplo: O número 2 é primo, pois os divisores positivos de 2 são 1, 2 . E mais, 2 é o único
número primo par, pois se existe primo par maior que 2, seria da forma N = 2q (q 1). Portanto, 1, 2
e q são divisores de N, o que torna absurdo, pois N é primo. Um inteiro maior que 1 e que não é
primo diz-se composto.
Teorema 6.1: Se um número primo p não divide um inteiro a, então a e p são primos entre si.
Corolário 6.1: Se p é um primo tal que p | ab, então p | a ou p | b.
Corolário 6.2: Se p é um primo tal que p | a1a2a3 ... an, então existe um índice k, com 1 k n tal
que p | ak..
Corolário 6.3: Se os inteiros p, q1,q2 ,..., qn são todos primos e se p | q1q2 ... qn, então existe um
índice k, com 1 k n tal que p = qk..
Teorema 6.2: - Todo inteiro composto possui um divisor primo.
6.3 - Teorema Fundamental da Aritmética:
Teorema 6.3 Todo inteiro positivo n > 1 é igual a um produto de fatores primos.
Corolário 6.4: A decomposição de um inteiro positivo n > 1 como produto de fatores primos é
única, a menos da ordem dos fatores.
Corolário 6.5: Todo inteiro positivo b > 1 admite uma única decomposição da forma n =
r21 k
r
k
2
k
1 p...pp onde, para i =1,2,..., r cada ki é um inteiro positivo e cada pi é um primo, com p1 < p2 <
... < pr, denominada decomposição canônica do inteiro positivo n > 1.
Exemplo 6.1: Definir mdc e mmc dos números 588 e 936 pela decomposição canônica.
Teorema 6.4 - (de Euclides) - Há um número infinito de primos.
Teorema 6.5 - Se um inteiro positivo a > 1 é composto, então a possui um divisor primo p a .
6.4 - Crivo de Erastóstenes:
A construção de uma tabela de primos que não um dado inteiro n faz-se usando o processo
conhecido pelo nome de crivo de Erastóstenes, e que consiste no seguinte: escrevem-se na ordem
natural todos os inteiros desde 2 até n e, em seguida, eliminam-se todos os inteiros composto que
são múltiplos dos primos p tais que p n , isto é, 2p, 3p, 4p.
6.5 - Primo Gêmeos:
Definição 6.2 – Chama-se primos gêmeos de dois inteiros positivos ímpares e consecutivos que são
ambos primos.
Exemplos: 3 e 5; 5 e 7; 11 e 13; 17 e 19; 29 e 31.
Não se sabe até hoje se há um número infinito de pares de primos gêmeos muito grandes,
tais como:
140.737.488.353.507 e 140.737.488.353.509
140.737.488.353.699 e 140.737.488.353.701
Um fato interessante é a existência de apenas um terno de inteiros positivos ímpares e
consecutivos que são todos primos: 3, 5 e 7.
6.4 - Seqüência de Inteiros Consecutivos Compostos:
Teorema 6.5 - Existem seqüências de n inteiros positivos consecutivos e compostos, qualquer que
seja o inteiro positivo n. A seqüência é a seguinte: (n + 1)! + 2, (n + 1)! + 3, ... , (n + 1)! + (n + 1).
Os seus n termos são inteiros positivos consecutivos, e cada um deles é composto, porque (n + 1)! +
J. é divisível por j se 2 j n 1.
Exemplo:
Suponha n = 4, obtemos a seqüência.
5! + 2, 5! + 3, 5! + 4, 5! + 5
Cujos termos são 4 inteiros positivos consecutivos, cada um dos quais é composto, pois, temos:
5! + 2 = 122 = 2.61 5! + 3 = 123 = 3.41
5! + 4 = 124 = 4.31 5! + 5 = 125 = 5.25
Outra seqüências de 4 inteiros positivos consecutivos e composto existem, tais como:
24, 25, 26, 27 32, 33, 34, 35
54, 55, 56, 57 74, 75, 76, 77
Nota: Chama-se: Números primos: primeiros ou indecomponíveis e Números não primos:
secundários ou compostos.
Questões Resolvidos
01) Achar todos os primos que são iguais a um quadrado perfeito menos 1.
Solução: Seja p este primo. Então, p = n2 – 1 ou p = (n – 1)(n + 1). Como p é primo seus fatores só
podem ser 1 e p. Assim temos: n – 1 = 1 e n + 1 = p. Daí, concluímos que n = 2 e p = 3 que é o
primo pedido.
02) Achar todos os primos que são iguais a um cubo perfeito menos 1.
Solução: Seja p este número primo. Então p = n3 – 1 ou p = (n – 1)(n
2 + n + 1). Como p é primo
seus únicos fatores são 1 e p. Temos n – 1 = 1 e n2 + n + 1 = p. Daí tiramos n = 2 e p = 7.
03) Determinar todos os inteiros positivos tais que n, n + 2 e n + 4 são todos primos.
Solução: que se n é um inteiro qualquer, um dos inteiros n, n + 2 e n + 4 é divisível por 3. Sendo
assim só existe a possibilidade da seqüência ser 3, 5 e 7.
04) Determinar todos os primos p tais que 3p + 1 é um quadrado perfeito.
Solução: Temos 3p + 1 = n2 ou 3p = n
2 – 1 ou 3p = (n – 1)(n + 1). Como p é primo a decomposição
do primeiro membro deve ser igual a do segundo. Assim 3 = n – 1 e p = n + 1. Daí, n = 4 e p = 5.
05) Achar uma seqüência de 100 inteiros positivos consecutivos e compostos.
Solução: (100 + 1)! + 2, (100 + 1)! + 3, ... , (100 + 1)! + 101.
06) Mostrar que todo primo, exceto 2 e 3, é da forma 6k – 1 ou 6k + 1, onde k é um inteiro positivo.
Solução: Como o número primo não é divisível por 6, e estão excluídos os primos 2 e 3, os restos
da divisão deste primo por 6, só poderão ser 1 ou 5. Assim p = 6 q + 1 ou p = 6q + 5. A primeira
igualdade já está na forma exigida, fazendo q = k; e se p = 6q + 5, basta somarmos e subtrairmos um
ao segundo membro, obtendo: p = 6q + 5 + 1 –1 ou p = 6q + 6 – 1 ou p = 6(q + 1) – 1 o que dá p =
6k –1, fazendo q + 1 = k.
07) Achar o menor inteiro positivo pelo qual se deve dividir 3720, para se obter um quadrado
perfeito.
Solução: Achando a decomposição canônica de 3720 temos: 3720 = 23 x 3 x 5 x 31.
Para que um número seja um quadrado perfeito os expoentes de seus fatores primos, têm de ser par.
Então o menor número que deve dividir o 3720 será 2 x 3 x 5 x 31 = 930.
08) Achar todos os primos que são divisores de 50!
Solução: São todos os primos menores que 50, pois 50! = 1 x 2 x 3 x ... x 49 x 50
Logo 2, 3, 5, 7, ... , 47.
09) Mostrar que todo inteiro da forma n4 + 4, com n > 1 é composto.
Solução: Vamos decompor o número em um produto de fatores maiores que um
n4 + 4 = n
4 + 4 + 4n
2 – 4n
2 (somando e subtraindo 4n
2 para formar um quadrado perfeito)
n4 + 4 = (n
2 + 2)
2 – 4n
2 (fatoremos a diferença entre dois quadrados)
n4 + 4 = (n
2 + 2 + 2n)(n2
+ 2 – 2n). Sendo n > 1 os dois fatores são maiores que 1.
10) Mostrar que, se n > 4, é composto, então n divide (n – 1)!.
Solução: Como n é composto, ele pode ser decomposto como produto de dois inteiros a e b: n = a b
, com 1 < a < n e 1 < b < n. Suponhamos que a b e consideremos a < b. Temos: 1 < a < b < n, ou 1
< a < b n – 1. Logo (n – 1)! = 1.2.a.b. (n–1) sendo a e b fatores de (n–1)!. Deste modo ab = n
divide (n–1)!. Se a = b, n = a2 e como n > 4, temos a
2 > 4 ou a > 2 e a
2 > 2 a ou 2 a < n = a
2. Assim 2
a n – 1 e como a < 2 a, a e 2 a são fatores de (n–1)! Logo: (n–1)! = 1.2.3...a ...2 a ... (n–1).
Portanto a2 é um fator de (n–1)!. E assim, a
2 = n divide (n–1)!
11) Demonstrar que o inteiro positivo a > 1 é um quadrado perfeito se e somente se todos os
expoentes dos fatores primos da sua decomposição canônica são inteiros pares.
Solução: Seja a é um quadrado perfeito então a tem a forma n2. Se n = n1
k1.n2
k2.n3
k3. ... nn
kn, onde
n1k1
.n2k2
.n3k3
. ... nnkn
é a decomposição canônica em fatores primos de n, teremos n2 = (n1
k1.n2
k2.n3
k3.
... nnkn
)2 = n1
2k1.n2
2k2.n3
2k3. ... nn
2kn. Como todos os expoentes são da forma 2k, conclui-se que todos
os expoentes são pares. Seja então ni um fator primo de n cujo expoente não seja par. Neste caso, o
fator teria expoente da forma 2k + 1. Ora, ni2k
+ 1 = ni2k
. ni. ni2k
tem expoente para, portanto está de
acordo com o que foi dito anteriormente. Para que fosse quadrado, ni deveria ter dois fatores primos
iguais. Como ni é primo isto não é possível. Portanto, todo número é quadrado perfeito, se e
somente se, todos os expoentes dos fatores primos na decomposição canônica for par.
12) Demonstrar que, se o inteiro n é composto, então 2n – 1
também é composto.
Solução: Evidentemente se trata de n positivo, pois se n < 0, n – 1 é negativo e 2n – 1
não será um
inteiro. Assim, para n > 0 e n composto, n > 3. Teremos então n – 1 > 2 2n – 1
= 2k, k = n – 1 > 2
inteiro: k – 2 > 0 (k – 1) > 0. Ora, 2n – 1
= 2k = 2(2
k – 1) que é múltiplo de 2 (não se esqueça que k
– 1 > 0) 2n – 1
é composto.
13) Mostrar que são primos gêmeos:
( a ) 1949 e 1951
Solução: Primos gêmeos são dois primos que são ímpares consecutivos. 1949 e 1951 são dois
ímpares consecutivos. Devemos verificar se ambos são primos. 1949 e 1951. Como ambos não são
divisíveis por 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43, os dois são primos. Portanto são
primos gêmeos.
Questões Propostas
01) Achar os cinco menores primos da forma n2 – 2.
R: 2, 7, 23, 47 e 79.
02) Achar três primos ímpares cuja soma seja:
( a ) 81.
R: (3, 5, 73)
( b ) 125.
R: (5, 13, 107)
03) Achar todos os pares de primos p e q, tais que p – q = 3.
R: p = 5 e q = 2.
04) Determinar se são primos os números.
( a ) 169 R: é composto.
( b ) 197 R: é primo
( c ) 239 R: é primo
( d ) 473 R: é composto
05) Achar a decomposição canônica do inteiro 5040.
R: 24 . 3
2. 5 . 7
06) Achar o mdc(a, b) e mmc(a, b) sabendo a = 230
. 521
. 19 . 233 e b = 2
6 . 3 . 7
4 . 11
2 . 19
5. 23
7.
R: Mdc(a, b) = 26 . 19. 23
3 e (a, b) = 2
30.3.5
21.7
4.11
2.19
5.23
7.
07) Mostrar que são primos gêmeos:
( a ) 1997 e 1999.
R: são primos gêmeos.
08) Achar todos os primos gêmeos entre 400 e 500.
R:- 491 e 421, 461 e 463.
09) Achar uma sequência de quatro inteiros positivos consecutivos e compostos.
R: 5! + 2, 5! + 3, 5! + 4, 5! + 5
10) Verificar a conjectura de Goldbach para os seguintes inteiros pares:
( a ) 32
( b ) 100
( c ) 456
( d ) 1024
11) Verificar que todo par entre 4 e 100 é a soma de dois primos.
12) Achar o menor inteiro positivo n tal que 2n2 + 29 é um inteiro composto.
R: 1
13) Mostar que a soma de inteiros positivos ímpares e consecutivos é sempre um inteiro composto.
14) Usando a decomposição canônica dos inteiros 507 e 1287, achar o mdc(507, 1287) e o
mmc(507, 1287).
R: mdc = 39 e mmc = 16731.
15) Mostrar que o único primo da forma n3 – 1 é 7.
R: o único n3 – 1 primo é 7.
16) Mostrar que todo inteiro da forma 8n + 1, com n > 1, é composto.
17) Mostrar que se n2 + 2 é primo então 3 | n.
18) Mostrar, mediante um exemplo, que a seguinte conjectura é falsa:
“Todo inteiro positivo pode-se escrever sob a forma a2 + p, onde o inteiro a > 0 e p é um inteiro
primo ou 1”.
19) Demonstrar as seguintes propriedades:
( a ) Todo primo da forma 3n + 1 é também da forma 6m + 1.
( b ) Todo inteiro da forma 3n + 2 tem um fator primo desta forma.
( c ) Se p > 5 é um primo, então p2 + 2 é composto.
( d ) Se p é um primo e se p | an, então p
n | a
n.
( e ) Todo inteiro n > 11 pode ser expresso como a soma de dois inteiros compostos.
( f ) Se p > q > 5 e se p e q são ambos primos, então 24 | p2 – q
2.
( g ) Se p 5 é um primo ímpar, então p2 – 1 ou p
2 + 1 é divisível por 10.
20) Verificar que todo inteiro pode escrever-se sob a forma 2km, onde o inteiro k > 0 e m é um
inteiro ímpar.
21) Demonstrar que, se o inteiro n > 2, então existe um primo p tal que n < p < n!.
22) Demonstrar que todo primo ímpar é da forma 4k + 1 ou 4k – 1, onde k é um inteiro positivo.
UNIDADE VII – EQUAÇÕES DIOFANTINAS
7.1 - Introdução:
Diofante foi um grande matemático que dedicou - se à resolução de problemas. Sua mais
importante obra foi a Aritmética, uma coleção de 13 livros nos quais o autor reuniu cerca de 150
problemas resolvidos através de operações numéricas, nas quais demonstra seu alto grau de
habilidade e engenho. Também chamado de “pai da álgebra”, devido a sua contribuição na
introdução de notações algébricas, Diofante utilizou abreviações para a subtração, a igualdade e a
incógnita.
Epitáfio de Diofante:
Bastante curioso é o epitáfio de Diofante, matemático grego da Antiguidade, que viveu 200
anos a.C. Encontramos na Antologia Grega um problema que é apresentado sob a forma de epitáfio:
Eis o túmulo que encerra Diofante, maravilha de contemplar. Com um artifício aritmético a
pedra ensina a sua idade. Deus concedeu-lhe passar a sexta parte de sua vida na juventude; um
duodécimo na adolescência; um sétimo em seguida, foi passado num casamento estéril. Decorreram
mais cinco anos, depois do que lhe nasceu um filho. Mas este filho desgraçado e, no entanto, bem
amado! apenas tinha atingido a metade da idade que viveu seu pai, morreu. Quatro anos ainda,
mitigando sua própria dor com o estudo da ciência dos números, passou-os Diofante, antes de
chegar ao termo de sua existência. Em linguagem algébrica o epigrama da Antologia seria traduzido
pela equação: x x x x
+ + + 5 + + 4 x6 12 7 2
, na qual x representa o número de anos que viveu
Diofante.
Resolvendo essa equação, achamos x = 84. Trata-se, afinal, de uma equação muito simples
do 1º grau com uma incógnita vamos verificar alguns exemplos:
Considere o seguinte problema (1): Se um trabalhador recebe 510 reais em tíquetes de
alimentação, com valores de 20 reais ou 50 reais cada tíquetes, de quantas formais pode ser formado
o carnê de tíquetes desse trabalhador.
Solução:
Se x denota a quantidade de tíquetes de 20 reais e y denota a quantidade de tíquete de 50
reais então a equação 20x 50y 510 , deve ser satisfeita e o problema é resolvido determinando-se
todas as soluções todas as soluções inteiras não negativas desta equação.
Considere o seguinte problema (2): Se o custo de postagem de uma encomenda é e de 85
centavos e devemos usar selos de 6 centavos e de 15 centavos, como devemos combinar os selos na
postagem.
Solução:
Se x denota a quantidade de selos de 6 centavos e se y denota a quantidade de 15 centavos
então a equação 6x 15y 85 , deve ser satisfeita e o problema é resolvido determinando-se todas
as soluções todas as soluções inteiras não negativas desta equação. Desta forma passamos estudar
nesta unidade a resolução das equações diofantinas e suas aplicações.
7.2 - Equações Diofantinas:
Definição 7.1: Equação diofantina linear, é uma equação da forma ax + by = c em que a, b, c, são
números inteiros. Uma solução de uma equação diofantina linear é um par de inteiros x0, y0 que
satisfaz a equação.
Exemplos 7.1: 3x + 6y = 18 soluções 4 e 1, –6 e 6, 10 e –2 etc...
2x + 4y = 7 não tem solução, pois o primeiro membro será sempre par e o segundo membro é ímpar.
7.3 - Condição de Existência de Solução:
Teorema 7.1 - A equação diofantina linear ax + by = c tem solução se, e somente se, d = mdc (a, b)
divide c.
7.4 - Soluções da Equação ax + by = c:
Teorema 7.2 - Se d = mdc(a, b) divide c (d | c), e se o par de inteiros x0, y0 é uma solução particular
da equação diofantina linear ax + by = c, então todas as outras soluções desta equação são dadas
pela fórmula: x = x0 + b
d t e y = y0 –
a
d t onde t é um inteiro arbitrário.
Corolário 7.1 - Se o mdc(a, b) = 1 e se (x0, y0) é uma solução particular da equação diofantina ax +
by = c, então todas as outras soluções desta equação são dadas pelas fórmulas: x = x0 + bt e y = y0 –
at onde t é um inteiro arbitrário.
Questões Resolvidas
Determinar todas as soluções inteiras das seguintes equações diofantinas lineares:
01) 56x + 72y = 40
Solução: Determinemos o mdc (72, 56).
Como o mdc (56, 72) = 8 divide 40, a equação possui solução. Usando o algoritmo da divisão,
temos:
72 = 56 x 1 + 16
56 = 16 x 3 + 8
16 = 8 x 2
Vamos escrever o mdc 8 como combinação linear de 56 e 72.
8 = 56 – 16 x 3 = 56 – (72 – 56) x 3 = 56 x 4 – 72 x 3 = 56(4) + 72 (–3)
Como queremos resolver a equação 56x + 72y = 40 multipliquemos a última igualdade acima por 5
40 = 56(20) + 72(–15).Logo xo = 20 e yo = –15, dando a solução geral:
x = 20 + (72/8)t e y = –15 – (56/8)t ou x = 20 + 9t e y = –15 – 7t.
02) 24x + 138y = 18
Solução: Determinemos o mdc (138, 24).
Usando o algoritmo da divisão, temos:
138 = 24 x 5 + 18
24 = 18 x 1 + 6
18 = 6 x 3
Vamos escrever o mdc 6, como combinação linear de 24 e 138
6 = 24 – 18 = 24 – (138 – 24 x 5) = 24 x 6 – 138 = 24(6) + 138(–1)
Como queremos resolver a equação 24x + 138y = 18, multipliquemos a igualdade acima por 3
18 = 24(18) + 138(–3): Logo xo = 18 e yo = –3, dando a solução geral: x = 18 + (138/6)t e y = –3 –
(24/6)t ou x = 18 + 23t e y = –3 – 4t.
3) 221x + 91y = 117
Solução: Determinemos o mdc (221, 91).
Como o mdc (221, 91) = 13 divide 117, a equação possui solução.
Usando o algoritmo da divisão, temos:
221 = 91 x 2 + 39
91 = 39 x 2 + 13
39 = 13 x 3
Vamos escrever o mdc 13 como combinação linear de 221 e 91
13 = 91 – 39 x 2 = 91 – (221 – 91 x 2) x 2 = 91 x 5 – 221 x 2 = 221(–2) + 91(5)
Como queremos resolver a equação 221x + 91y = 117, multipliquemos a igualdade acima por 9.
117 = 221(–18) + 91(45). Logo xo = –18 e yo = 45 dando a solução geral:
x = –18 + (91/13)t e y = 45 – (221/13)t ou x = –18 + 7t e y = 45 – 17t.
04) 84x – 438y = 156
Solução: Determinemos o mdc (438, 84).
Como o mdc (438, 84) = 6 divide 156, a equação possui solução.
Usando o algoritmo da divisão, temos:
438 = 84 x 5 + 18
84 = 18 x 4 + 12
18 = 12 x 1 + 6
12 = 6 x 2
Vamos escrever o mdc 6 como combinação linear de 84 e –438
6 = 18 – 12 = 18 – (84 – 18 x 4) = 18 x 5 – 84 = (438 – 84 x 5) x 5 – 84 = 438 x 5 – 84 x 26 ou 6 =
84(–26) – 438(–5)
Como queremos resolver a equação 84x – 438y = 156 multipliquemos a igualdade acima por 26.
156 = 84(–676) - 438(–130). Logo xo = –676 e yo = –130, dando a solução geral:
x = –676 –(438/6)t e y = –130 –(84/6)t ou x = –676 –73t e y = –130 – 14t.
05) 57x – 99y = 77
Solução: Determinemos o mdc (57, 99).
Como o mdc (57, 99) = 3 não divide 77, a equação não possui solução.
06) 11x + 30y = 31
Solução: Determinemos o mdc (11, 30).
Como o mdc (11, 30) = 1 divide 31, a equação possui solução.
Usando o algoritmo da divisão, temos:
30 = 11 x 2 + 8
11 = 8 x 1 + 3
8 = 3 x 2 + 2
3 = 2 x 1 + 1
2 = 1 x 2
Vamos escrever o mdc 1 como combinação linear de 11 e 30.
1 = 3 – 2 = 3 – (8 – 3 x 2) = 3 x 3 – 8 = (11 – 8) x 3 – 8 =11 x 3 – 8 x 4 =
= 11 x 3 – (30 –11 x 2) x 4
1 = 11 x 11 – 30 x 4 = 11(11) + 30(–4)
Como queremos resolver a equação 11x + 30y = 31 multipliquemos a igualdade acima por 31
31 = 11(341) + 30(–124). Logo xo = 341 e yo = –124, dando a solução geral:
x = 341 + 30t e y = –124 – 11t.
07) 27x – 18y = 54
Solução: Determinemos o mdc (27, 18).
Como o mdc.(27, 18) = 9 divide 54, a equação possui solução. Usando o algoritmo da divisão,
temos:
27 = 18 x 1 + 9
18 = 9 x 2
Vamos escrever o mdc 9 como combinação linear de 27 e –18.
9 = 27 – 18 = 27(1) – 18(1)
Como queremos resolver a equação 27x – 18y = 54 multipliquemos a igualdade acima por 6
54 = 27(6) – 18(6). Logo xo = 6 e yo = 6 dando a solução geral:
x = 6 – (18/9)t e y = 6 – (27/9)t ou x = 6 – 2t e y = 6 – 3t.
08) 13x – 7y = 21
Solução: Determinemos o mdc (13, 7).
Como o mdc (13, 7) = 1 divide 21, a equação possui solução. Usando o algoritmo da divisão, temos:
13 = 7 x 1 + 6
7 = 6 x 1 + 1
6 = 1 x 6
Vamos escrever o mdc 6 como combinação linear de 13 e -7.
1= 7 – 6 = 7 – (13 – 7) = 7 x 2 – 13 = 13(–1) – 7(–2)
Como queremos resolver a equação 13x – 7y = 21 multipliquemos a igualdade acima por 21
21 = 13(–21) – 7(–42). Logo xo = –21 e yo = –42, dando a solução geral:
x = –21 –7t e y = –42 – 13t
09) 44x + 66y = 11
Solução: Determinemos o mdc (66, 44).
Como o mdc (44, 66) = 22 não divide 11, a equação não possui solução.
10) 21x – 12y = 72
Solução: Determinemos o mdc (21, 12).
Como o mdc (21, 12) = 3 divide 72, a equação possui solução. Usando o algoritmo da divisão,
temos:
21 = 12 x 1 + 9
12 = 9 x 1 + 3
9 = 3 x 3
Vamos escrever o mdc 3 como combinação linear de 21 e -12.
3 = 12 – 9 = 12 – (21 – 12) = 12 x 2 – 21 = 21 (–1) – 12(–2)
Como queremos resolver a equação 21x – 12y = 72 multipliquemos a última igualdade acima por 24
72 = 21 (–24) – 12(–48). Logo xo = –24 e yo = –48, dando a solução geral:
x = –24 – (12/3)t e y = –48 – (21/3)t ou x = –24 –4t e y = –48 – 7t.
02) Determinar todas as soluções inteiras e positivas das seguintes equações diofantinas lineares
01) 5x – 11y = 29
Solução: A equação geral desta equação é: x = –58 – 11t e y = –29 –5t
Como queremos as soluções positivas, devemos ter: –58 – 11t > 0 e –29 – 5t > 0
Da 1a. desigualdade, tiramos: t < –5,27 ou t –6 e da 2
a, t < –5,8 ou t –6. Sendo assim, a solução
será t –6, dando uma infinidade de soluções positivas.
02) 32x + 55y = 771
Solução: A solução geral desta equação é: x = –9252 + 55t e y = 5397 – 32t
Como queremos as soluções positivas, devemos ter: –9252 + 55t > 0 e 5397 – 32t > 0
Da primeira desigualdade, tiramos: t > 168,21 ou t 169
Da segunda desigualdade, tiramos: t < 168,5 ou t 168. Então, não há soluções positivas.
03) 58x – 87y = 290
Solução: A solução geral desta equação é: x = –10 –3t e y = –10 – 2t
Como queremos as soluções positivas, devemos ter: –10 – 3t > 0 e –10 – 2t > 0
Da primeira desigualdade, tiramos: t < –3,33 ou t – 4
Da segunda desigualdade, tiramos: t < – 5 ou t – 6. Logo todos os valores de t no intervalo t –
6, satisfazem o problema.
04) 62x + 11y = 788
Solução: A solução geral desta equação é: x = –2364 + 11t e y = 13396 – 62t
Como queremos as soluções positivas, devemos ter: –2364 + 11t > 0 e 13396 – 62t > 0
Da primeira desigualdade tiramos: t > 214,9 ou t 215
Da segunda desigualdade tiramos: t < 216,06 ou t 216. Logo os valores de t que satisfazem as
duas condições são: t = 215 e t = 216.
Quando t = 215, x = 1 e y = 66 e quando t = 216, x = 12 e y = 4.
05) 30x + 17y = 300
Solução: A solução geral desta equação é: x = 1200 + 17t e y = –2100 – 30t
Como queremos as soluções positivas, devemos ter: 1200 + 17t > 0 e –2100 –30t > 0
Da primeira desigualdade tiramos: t > –70,58 ou t – 70
Da segunda desigualdade tiramos: t < –70 ou t – 71. Portanto não há soluções positivas.
06) 54x + 21y = 906
Solução: A solução geral desta equação é: x = 604 + 7t e y = –1510 – 18t
Como queremos as soluções positivas, devemos ter: 604 + 7t > 0 e–1510 – 18t > 0
Da primeira desigualdade tiramos: t > – 86,28 ou t – 86
Da segunda desigualdade tiramos: t < – 83,88 ou t – 84, o que nos dá o intervalo –86,–84 ou
t = –86, t = –85 e t = –84 dando os valores:
Para t = –86, x = 2 e y = 38
Para t = –85, x = 9 e y = 20
Para t = –84, x = 16 e y = 2
07) 123x + 360y = 99
Solução: A solução geral desta equação é: x = 1353 + 120t e y = –462 – 41t
Como queremos as soluções positivas, devemos ter: 1353 + 120t > 0 e –462 – 41t > 0
Da primeira desigualdade tiramos: t > –11,27 ou t –11
Da segunda desigualdade tiramos: t < –11, 26 ou t -12. Portanto a equação não possui soluções
positivas.
08) 158x – 57y = 7
Solução: A solução geral desta equação é: x = –154 – 57t e y = –427 – 158t
Como queremos as soluções positivas, devemos ter: –154 – 57t > 0 e –427 – 158t > 0
Da primeira desigualdade tiramos: t < – 2,7 ou t – 3
Da segunda desigualdade tiramos: t < - 2,7 ou t - 3. Então todos os valores de t - 3 satisfazem o
problema, dando infinitas soluções positivas.
Questões Propostas
01) Determinar todas as soluções inteiras e positivas das seguintes equações diofantinas lineares:
01) 90x - 28y = 22 R: x = 13, y = 41.
02) 40x - 65y = 135 R: x = 5, y = 1.
03) 18x - 20y = -8 R: x = 4, y = 4.
04) 8x - 13y = 23 R: Não existem soluções positivas.
05) 3x + 4y = 20 R: x = 4, y = 2.
06) 50x - 56y = 74 R: x = 25, y = 21.
07) 8x - 13y = 23 R: x = 11, y = 5.
08) 5x - 2y = 2 R: x = 2, y = 4.
09) 24x + 138y = 18 R: Não existem soluções positivas.
10) 93x + 81y = 3 R: Não existem soluções positivas.
11) 43x + 128y = 1 R: Não existem soluções positivas.
12) 16x + 7y = 601 R: x = 3, y = 79 e x = 31, y = 15.
13) 47x + 29y = 1288 R: x = 20, y = 12.
14) 30x + 17y = 201 R: x = 5, y = 3.
15) 17x + 13y = 100 R: Não existem soluções positivas.
16) 12x + 18y = 50 R: Não admite solução.
17) 60x + 18y = 67 R: Não admite solução.
18) 1402x + 1969y = 1 R: Não existem soluções positivas.
19) 102x + 1001y = 533 R: Não existem soluções positivas.
20) 33x + 25y = 0 R: x = 0, y = 0.
21) 56x + 634y = 168 R: x = 0, y = 2.
22) 5x + 7y = 14 R:
25) 172x + 20y = 1000 R:
26) 18x + 5y = 48 R:
27) 39x + 26y = 105 R:
28) 14x + 22y = 50 R:
02) Encontre as soluções das seguintes equações diofantinas:
01) 2x - 10y + 35z = 0 R: x = 0, y = 0 e z = 0.
02) 2x + 3y + 5z = 7 R: x = 7, y = -14 e z = 7.
03) 1521x + 1955y + 455z = 221 R: x = 7956, y = -84.442 e z = 336.141.
04) 101x - 102y + 103z = 1 R: x = 1, y = -100 e z = -100.
05) 12x + 21y + 9z + 15w = 9 R: x = 2, y = -1, z = -1 e w = 1.
03) Determinar o menor inteiro positivo que dividido por 8 e por 15 deixa os restos 6 e 13,
respectivamente. R: 188.
04) Exprimir 100 como soma de dois inteiros positivos de modo que o primeiro seja divisível por 7
e o segundo seja divisível por 11. R: 56 e 44.
05) Determinar as duas menores frações positivas que tenham 13 e 17 para denominadores e cuja
soma seja igual a 305|221. R: 8|13 e 13|17.
06) Determine duas frações cujos denominadores sejam 12 e 16 e cuja soma seja 10|48.
R: 1|12 e 2|16.
07) Demonstrar que se a e b são inteiros positivos primos entre si, então a equação diofantina ax –
by = c, têm um número infinito de soluções inteiras e positivas.
08) Um grupo de pessoas gastou 1000 dólares num hotel. Sabendo-se que apenas alguns dos
homens estavam acompanhados pelas esposas e que cada homem gastou 19 dólares e cada mulher
gastou 13 dólares, pede-se determinar quantas mulheres e quantos homens estavam no hotel?
R: 41 homens e 17 mulheres.
09) Ache o inteiro estritamente positivo com a seguinte propriedade da resto 6 quando dividido por
11 e resto 3 quando dividido por 7?. R: 17.
10) Determine todos os múltiplos de 11 e de 9 cuja a soma é igual a:
a) 79. R: não existe. b) 80. R: 36 e 44. c) 270. R: 99 e 171; 72 e 198.
11) Determine o menor inteiro positivo que tem restos 11 e 35 quando dividido respectivamente por
37 e 48. R: 899.
12) O valor da entrada de um cinema e R$ 8,00 e da meia entrada R$ 5,00. Qual é o menor número
de pessoas que pode assistir a uma sessão de maneira que a arrecadação da bilheteria seja R$
500,00.
R: Este problema não tem uma única solução. As soluções possíveis são: x = 5 e y = 92 ou x = 60 e
y = 4.
13) Ao entrar num bosque alguns viajantes avistaram 37 montes de maça. Após serem retiradas 17
frutas, o restante foi dividido igualmente entre 79 pessoas. Quantas frutas coube a cada pessoa?
R: 4 para cada pessoa.
14) Dispondo de 100 reais, quais são as quantias que se podem gastar comprando selos de R$ 5,00 e
de R$ 7,00. R: x = 6 e y = 10.
15) Numa criação de coelhos e galinhas contaram-se 400 pés. Quantas são as galinhas e quantos são
os coelhos, sabendo que a diferença entre esses dois números seja a menor possível?
R: 99 coelhos e 2 galinhas.
16) Um grupo de pessoas gastou 690 dólares num hotel. Sabendo-se que apenas alguns dos homens
estavam acompanhados pelas esposas e que cada homem gastou 18 dólares e cada mulher gastou 15
dólares, pede-se determinar quantas mulheres e quantos homens estavam no hotel.
R: Este problema não tem uma única solução. As soluções possíveis são: 25 homens e 16 mulheres
ou 30 homens e 10 mulheres ou 35 homens e 4 mulheres.
17) Um teatro vende ingressos e cobra R$ 18,00 por adulto e R$ 7,50 por criança. Numa noite,
arrecada R$ 900,00. Quantos adultos e crianças assistiram ao espetáculo, sabendo que eram mais
adultos do que criança?
R: Este problema não tem uma única solução. As soluções possíveis são: x = 0 e y = 50 ou x = 12 e
y = 45 ou x = 24 e y = 40.
18) Uma agência de correios possui apenas selos de 14 centavos e de 21 centavos. Determine as
combinações desses selos que podem ser feitas para postar cartas dos seguintes valores postais:
(a) R$ 3,50
R:
(b) R$ 4,00
R: Não admite solução
(c) R$ 7,77
R: Varias soluções por ter o valor de entre 37 t 55 .
19) Com R$ 5,49 podemos comprar maças, a 18 centavos cada, e perras, a 33 centavos cada. Qual e
o numero mínimo de frutas que podem ser compradas?
R: 18 frutas.
20) Um estudante, viajando da Europa aos Estados Unidos, troca seus francos suíços e francos
franceses por dólares. Ele recebe US$ 17,06 tendo recebido US$ 0,19 (19 cents') por cada francos
francês e US$ 0,59 por cada francos suíços. Quanto de cada moeda ele possuía?
R: Francos Francês 7,03 e Francos Suíços 17,03.
21) De que modos e possível combinar 50 moedas, misturando moedas de 1, de 10 e de 25
centavos, de modo a totalizar 3 reais?
R: x = 1, y = -3 e z = 7.
22) Temos duas balanças: uma que marca pesos múltiplos de 10 e outra que marca pesos múltiplos
de 13. Como é que com essas balanças podemos pesar 107 gramas?
R: x = 12, y = 9.
23) Apenas com a utilização de dois relógios que só dão intervalos de tempo de 5 e de 11 minutos
como podemos cozer um ovo durante 3 minutos?
R: Não existem soluções positivas.
x x x x x x x x x
1 4 7 10 13 16 19 22 25
y y y y y y y y y
16 14 12 10 8 6 4 2 0
24) Numa papelaria vendem-se dois tipos de canetas por 110 e 70 reais respectivamente. Ao fim de
um dia a importância total recebida pela venda dessas canetas foi 6570 reais. Qual é o menor
numero possível de canetas vendidas? E qual o maior?
R: Qual é o menor numero possível de canetas 63. E qual o maior 91.
25) Subindo uma escada de dois em dois degraus, sobra um degrau. Subindo a mesma escada de três
em três degraus, sobram dois degraus. Determine quantos degraus possui a escada, sabendo que o
seu número e múltiplo de 7 e esta compreendido entre 30 e 100.
R: 35
26) Se um trabalhador recebe 510 reais em tíquetes de alimentação, com valores de 20 reais ou 50
reais cada tíquetes, de quantas formais pode ser formado o carnê de tíquetes desse trabalhador.
R: carnê com 3 tíquetes de R$ 20,00 reais e 9 tíquetes de R$ 50,00, com 8 tíquetes de R$ 20,00 reais
e 7 tíquetes de R$ 50,00, com 13 tíquetes de R$ 20,00 reais e 5 tíquetes de R$ 50,00, com 18
tíquetes de R$ 20,00 reais e 3 tíquetes de R$ 50,00, com 23 tíquetes de R$ 20,00 reais e 1 tíquetes
de R$ 50,00.
UNIDADE VIII – CONGRUÊNCIAS
8.1 - Introdução:
O conceito de congruência, bem como a notação através da qual essa noção tornou um dos
instrumentos mais poderosos da teoria dos números, foi introduzido por Karl Friedrich Gauss (1777
– 1855), em sua obra Disquisitions arithmeticae em 1801.
Para dar uma idéia da noção de congruência consideremos a seguinte questão, talvez ingênua
mas ilustrativa: Se hoje é sexta-feira, que dia da semana será daqui a 1520 dias?
Para organizar o raciocínio, indiquemos por o dia de hoje (sexta - feira), e por 1 o dia de
amanha (sábado), e assim por diante. A partir dessa escolha, podemos construir a seguinte tabela:
Sexta Sábado Domingo Segunda Terça Quarta Quinta
0 1 2 3 4 5 6
7 8 9 10 11 12 13
Nossa questão agora se resume em saber que coluna se encontra o número 1520. Para isso
basta observar que dois números da seqüência 0, 1, 2, , estão na mesma coluna se, e somente
se, sua diferença é divisível por 7. Suponhamos que o número 1520 se encontre na coluna
encabeçada pelo número a (0 a 6) , logo 1520 - a = 7q.
Para algum inteiro positivo q. donde obtemos 1520 = 7q + a, com (0 a 6) , Ora, pela
unicidade do resto na divisão euclidiana, segue dessa igualdade que o resto da divisão de 1520 por
7. é portanto 1520 = 217 7 + 1, desta forma conclui-se que o resto é 1 e que portanto 1520 esta na
segunda coluna. Logo, daqui a 1520 dias será um sábado.
8.2 - Congruências:
Definição 8.1 - Sejam a e b inteiros quaisquer e seja m um inteiro positivo fixo. Diz-se que a é
congruente a b módulo m se, e somente se, m divide a diferença a – b. Em outros termos a é
congruente a b módulo m se, e somente se, existe um inteiro k tal que a – b = km.
Notação: a b (mod m) Simbolicamente: a b (mod m) se, e somente se, m | ( a – b ).
Exemplos 8.1 - 3 24 (mod 7); –31 11 (mod 6); –15 –63 (mod 8).
Definição 8.2 - Se m não divide a diferença a – b, então, diz-se que a, é incongruente a b módulo m.
Notação: a b (mod m).
Observações:
1) Dois inteiros quaisquer são congruentes módulo 1.
2) Dois inteiros são congruentes módulo 2, se ambos são pares ou ambos ímpares.
3) a 0 (mod m) se, e somente se, m | a.
Exemplos 8.2:
1) Mostrar que n 7 (mod 12) então, n 3 (mod 4) n Z.
2) Mostrar que n2 0 (mod 4) ou n
2 1 (mod 4) n Z.
8.3 - Caracterização de Inteiros Congruentes:
Teorema 8.1 - Dois inteiros a e b são congruentes módulo m se, e somente se, a e b deixam o
mesmo resto quando divididos por m.
8.4 - Propriedades das Congruências:
Teorema 8.2- Seja m um inteiro positivo fixo (m > 0) e sejam a, b e c inteiros quaisquer. Subsistem
as propriedades:
1) a a (mod m).
2) Se a b (mod m), então b a (mod m).
3) Se a b (mod m) e se b c(mod m), então a c (mod m)
Teorema 8.3 - Seja m um inteiro positivo fixo (m > 0) e sejam a, b dois inteiros quaisquer.
Subsistem as seguintes propriedades:
1) Se a b (mod m) e se n | m, com n > 0, então a b (mod n).
2) Se a b (mod m) e se c > 0, então ac bc (mod mc).
3) Se a b (mod m) e se a, b, m são todos divisíveis pelo inteiro d > 0, então d
b
d
a mmod
d.
Teorema 8.4 - Seja m um inteiro positivo fixo (m > 0) e sejam a, b, c, d inteiros quaisquer.
Subsistem as seguintes propriedades:
1) Se a b (mod m) e se c d (mod m), então a + c b + d (mod m) e ac bd (mod m).
2) Se a b (mod m), então a + c b + c (mod m) e ac bc (mod m).
3) Se a b (mod m), então an b
n (mod m) para todo inteiro positivo n.
Exemplos 8.3 - Mostrar que:
a) Se a b (mod m), então –a –b (mod m).
b) Se a + b c (mod m) então a c – b (mod m).
Teorema 8.5 - Se ac bc (mod m) e se o mdc(c, m) = d, então a bm
modd
.
Corolário 8.1 - Se ac bc (mod m) e se o mdc (c, m) = 1, então a b (mod m).
Corolário 8.2 - Se ac bc (mod p), com p primo, e se p não divide c, então a b (mod p).
8.4 - Sistemas Completos de Restos:
Definição 8.3 - Chama-se sistema completo de restos módulo m todo conjunto S = {r1, r2,..., rm} de
m inteiros tal que um inteiro qualquer a é congruente módulo m a um único elemento de S.
Exemplos 8.3 - {1, 2, 3}, {0, 1, 2}, { –1, 0, 1}, {1, 5, 9} são sistemas completo de restos módulo 3.
Teorema 8.6 - O conjunto S = {0, 1, 2, ..., n–1 } é um sistema completo de restos módulo m.
Corolário 8.3 - Se S = {r1, r2,..., rm} é um sistema completo de restos módulo m, então os elementos
de S são congruentes módulo m aos inteiros 0, 1, 2, ... , m – 1, tomados numa certa ordem.
Questões Resolvidas
01) Achar o menor inteiro positivo que represente a soma:
( a ) 5 + 3 + 2 + 1 + 8 (mod. 7).
Solução: 5 + 2 0 (mod.7), 3 + 1 4 (mod. 7) 8 1 (mod. 7).
Portanto 5 + 3 + 2 + 1 + 8 0 + 4 + 1 5 (mod. 7)
R: 5
( b ) 2 + 3 – 1 + 7 – 2 (mod.4).
Solução: 2 + 3 1 (mod. 4) e -1 + 7 – 2 = 4 0 (mod. 4).
Portanto: 2 + 3 – 1 + 7 – 2 1 + 0 1 (mod. 4)
R. 1
02) Sabendo que 1066 1776 (mod m), achar todos os possíveis valores do módulo m.
Solução: Como m | (1066 – 1776) devemos achar todos os divisores positivos de –710.
Logo os divisores positivos de –710 são: 1, 2, 5, 10, 71, 142, 355 e 710.
03) Exprimir que “n é ímpar” de três outras maneiras.
Solução:
01) n 1 (mod. 2)
02) n - 1 (mod. 2)
03) n = 2k + 1
04) n = 2k – 1
04) Mostrar que todo primo (exceto 2) é congruente módulo 4 a 1 ou 3.
Solução: Se p é primo, diferente de 2, então ele é ímpar. Dividindo p por 4 obtemos os restos 1 ou
3. Assim p = 4q + 1 ou p = 4q + 3. Na primeira igualdade p – 1 = 4q, então p 1 (mod 4) e na
segunda igualdade p – 3 = 4q , dando p 3 (mod 4).
05) Mostrar que 1110
1 (mod 100).
Solução: 112 21 (mod 100); 11
4 21
2 41 (mod 100); 11
8 41
2 81 (mod 100)
1110
= 112. 11
8 21 . 81 1 (mod 100).
06) Mostrar que todo primo (exceto 2 e 3) é congruente módulo 6 a 1 ou 5.
Solução: Se p é um primo diferente de 2 e 3, então ao dividirmos p por 6, obtemos os restos 1 ou 5.
Assim p 1 (mod 6) ou p 5 (mod 6).
07) Mostrar que 41 divide 220
– 1.
Solução: Devemos mostrar que 220
1 (mod 41).
26 23 (mod 41); 2
4 16 (mod 41); 2
10= 2
6 . 2
4 23 . 16 40 (mod 41)
220
402 1 (mod 41).
08) Mostrar que 89 | (244
- 1).
Solução: Devemos mostrar que 244
1 (mod 89)
27 39 (mod 89); 2
4 16 (mod 89); 2
11 = 2
7 . 2
4 39 . 16 1 (mod 89)
244
= (211
)4 1 (mod 89).
09) Mostrar que 97 | (248
– 1).
Solução: Devemos mostrar que 248
1 (mod 97).
27 31 (mod 97); 2
5 32 (mod 97); 2
12 = 2
7 . 2
5 31 . 32 22 (mod 97)
248
= (212
)4 22
4 (mod 97); 22
2 96 -1 (mod 97); 22
4 = (22
2)2 (-1)
2 (mod 97)
Logo 248
1 (mod 97).
10) Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 4:
a) {–2, –1, 0, 1}.
Solução: –2 2; –1 3; 0 0; 1 1 (mod 4). Portanto é um sistema completo de restos módulo 4.
b) {0, 4, 8, 12}.
Solução: 0 0; 4 0; 8 0; 12 0 (mod 4). Portanto não é um sistema completo de restos
módulo 4.
c) {–13, 4, 17, 18}.
Solução: –13 3; 4 0; 17 1; 18 2 (mod 4). Portanto é um sistema completo de restos módulo
4.
( d ) -5, 0, 6, 22 .
Solução:
-5 = 4(-2) + 3 3, 0 0; 6 = 4.1 + 2 2; 22 = 4.5 + 2
O conjunto é equivalente a {0, 2, 3}. Portanto, não é um conjunto completo.
R: São conjuntos completos os das letras a e c.
Questões Propostas
01) Achar todos os inteiros x tais que 0 15x e 3x 6 (mod 15).
R: x = 2; x = 7 e x = 12.
02) Achar todos os inteiros x tais que 1 100x e x 7 (mod 17).
R:7, 24, 41, 58, 75 e 92.
03) Sabendo que k 1 (mod 4), mostrar que 6k + 5 3 (mod 4).
04) Achar os restos das divisões de 250
e 4165
por 7.
R: 4 e 6.
Demonstrar as seguintes proposições:
05) Se a é um inteiro ímpar, então a2 1 (mod 8).
06) Se a é um inteiro qualquer, então a3 0, 1 ou 8 (mod 9).
07) Se a é um inteiro qualquer, então a3 a (mod 6).
08) Mostrar, mediante um exemplo, que a2 b
2 (mod.m) não implica a b (mod.m).
09) Demonstrar que, se a b (mod. m) então mdc(a, m) = mdc(b, m).
10) Mostrar, mediante um exemplo, que ak b
k (mod. m) e k j não implica a
j b
j.
11) Achar os restos das seguintes divisões:
1) 245
por 7. R: r = 1.
2) 11100
por 100. R: r = 1.
3) 310
.425+6
8 por 5. R: r = 1.
4) 52.4841+28
5 por 3. R: r = 0.
5) 710
por 51. R: r = 19.
6) 2100
por 11. R: r = 1.
7) 734
por 51. R: r = 49.
8) 14256
por 17. R: r = 1.
9) 521
por 127. R: r = 126.
10) 1212
por 5. R: r = 3.
11) (116 + 1717
)21
por 8. R: r = 5.
12) 1316
-225
.515
por 3. R: r = 0.
13) 23728
por 13. R: r = 13.
14) 563
por 29. R: r = 28.
12) Mostrar que 2347 | (2 1) :
13) Para todo n N, Mostrar que:
1) 1016n
–1 é divisível por 70. R: r = 1.
2) 198n
–1 é divisível por 17. R: r = 1.
14) Achar os restos da divisão por 7 do número:
1) 2 3 10010 10 10 1010 + 10 + 10 +........+ 10 . R: r = 4.
2) 16 + 2
6+.......+100
6. R: r = 2.
3) 17 + 2
7+.......+100
7. R: r = 3.
4) 22225555
+ 55552222
. R: r = 0.
15) Achar os restos da divisão por 4 do número:
1) 1 + 2 + 22+........+2
19. R: r = 3.
2) 15 + 2
5+.......+100
5. R: r = 0.
16) Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 6.
a) {1, 2, 3, 4, 5}.
R: Não é, porque possui somente 5 elementos.
b) {0, 5, 10, 15, 20, 25}.
R: Portanto é um sistema completo de restos módulo 6.
c) {–4, –3, –2, –1, 0, 1}.
R: Portanto é um sistema completo de restos módulo 6.
d) {17, –4, 6, 7, 10, 3}.
R: Portanto é um sistema completo de restos módulo 6.
17) Achar um sistema completo de restos {p1, p2, ... p7} módulo 7, tal que todo pi é primo.
R: r = {2, 3, 5, 7, 11, 13, 28}.
18) Achar um sistema completo de restos módulo 7 formado só de múltiplos não negativos de 4.
R: r = { 36, 40, 44, 48, 52, 56, 60}.
19) Encontrar um sistema completo de restos módulo 11 formado somente por múltiplo de 6.
R: r: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 .
20) Encontrar um sistema completo de restos módulo 7 onde todos os elementos são primos:
R: r: 0, 1, 2, 3, 4, 5, 6 .
21) Dado um primo p é sempre possível encontrar um sistema completo de restos módulo p
formado só por primos? Justificar. Sua resposta. R:
UNIDADE XI – CONGRUÊNCIAS LINEARES
9.1 - Introdução:
Usamos congruências rotineiramente em nossa vida. Por exemplo, na contagem das horas,
fazemos uso de congruência modulo 12 ou modulo 24. Na contagem de minutos e segundos,
usamos congruência modulo 60. Nos calendários, na contagem dos dias da semana fazemos uso, de
certa forma, da congruência modulo, e na contagem dos meses, empregamos congruência modulo
12. Os hodômetros dos carros, usados para marcar quilômetros rodados, geralmente trabalham
modulo 100.000. Veremos nesta unidade como resolve congruências lineares e aplicando na
resolução de equações diofantinas.
9.2 - Congruências Lineares:
Definição 9.1: Chama-se congruência linear toda equação da forma ax b (mod m), onde a e b são
inteiros quaisquer e m um inteiro positivo. Todo inteiro x0 tal que ax0 b (mod m) diz-se uma
solução da congruência linear.
Observação 9.1 - Se x0 é uma solução da congruência linear ax b (mod m), então todos os
inteiros x0 + km, onde k é um inteiro arbitrário, também são soluções da congruência linear.
Observação 9.2 - Duas soluções x0 e x1 da congruência ax b (mod m) congruente módulo m isto
é, x0 x1 (mod m) não são consideradas soluções distintas. O número de soluções da congruência é
dado pelo número de soluções mutuamente incongruente módulo m.
9.3 - Condição de Existência de Soluções:
Teorema 9.1 - A congruência linear ax b (mod m) tem solução se, e somente se, d divide b, sendo
d = mdc(a, m). logo 0 0 0 0ax b my ou ax my = b .
9.4 - Soluções da Congruência ax b (mod m):
Teorema 9.2 - Se d divide b, sendo d = mdc(a, m), então a congruência linear ax b (mod m) tem
precisamente d soluções mutuamente incongruentes módulo m, dada pela fórmula:
x = xo + m
dt, 0 t d – 1.
Corolário 9.1 - Se o mdc(a, m) = 1, então a congruência linear ax b (mod m) tem uma única
solução módulo m.
9.5 - Resolução de Equações Diofantinas Lineares por Congruências:
Uma equação diofantina linear, é uma equação da forma ax + by = c em que a, b, c, são números
inteiros. e de acordo com o Teorema 7.1 A equação diofantina linear ax + by = c tem solução se, e
somente se, d = mdc (a, b) divide c. Uma solução de uma equação diofantina linear é um par de
inteiros x0, y0 que satisfaz a equação, então:
ax0 + by0 = c e ax0 - c = - by
o que implica: ax0 b (mod m), Assim sendo, para obter uma solução particular da equação
diofantina linear, basta determinar uma solução qualquer x = x0 da congruência linear ax c (mod
b), e substituir este valor x0 de x na equação ax + by = c afim de encontrar o valor correspondente y0
de y, isto é, tal que ax0 + by0 = c. Obviamente, também se pode obter uma solução particular da
equação diofantina linear, determinando uma solução qualquer y = y0 da congruência linear. bx c
(mod a).
Questões Resolvidas
01) Resolver as seguintes congruências lineares:
a) 2x 1 (mod 17).
Solução: O mdc(2, 17) = 1 e 1 | 1, logo a congruência possui uma solução.
2x 1 (mod 17); 1 2.9 (mod 17); 2x 2.9 (mod 17); x 9 (mod 17)
b) 3x 1 (mod 17).
Solução: O mdc(3, 17) = 1 e 1 | 1, logo a congruência possui uma solução.
3x 1 (mod 17); 1 3.6 (mod 17); 3x 3.6 (mod 17); x 6 (mod 17)
c) 3x 6 (mod 18).
Solução: O mdc(3, 18) = 3, e 3 | 6, logo a congruência possui três soluções. Dividindo por 3 a
congruência dada, obtemos: x 2 (mod 6) Assim a solução geral é x = 2 + 6t, t = 0, 1 e 2 dando x =
2, x = 8 e x = 14
d) 25x 15 (mod 29).
Solução: O mdc(25, 29) = 1 e 1 | 15, logo a congruência possui uma solução
25x 15 (mod 29) dividindo por 5, temos: 5x 3 (mod 29); 3 5.18 (mod 29)
5x 5.18 (mod 29); x 18 (mod 29)
e) 5x 2 (mod 26).
Solução: O mdc(5, 26) = 1, logo a congruência possui uma solução
5x 2 (mod 26); 2 5.16 (mod 26); 5x 5.16 (mod 26); x 16 (mod 26)
f) 6x 15 (mod 21).
Solução: O mdc(6, 21) = 3 e 3 | 15, logo a congruência possui três soluções
6x 15 (mod 21). Dividindo por 3, temos : 2x 5 (mod 7); 5 2.6 (mod 7)
2x 2.6 (mod 7); x 6 (mod 7). A solução geral é: x = 6 + 7t, t = 0, 1 e 2, dando:
x = 6, x= 13 e x = 20
g) 36x 8 (mod 102).
Solução: O mdc(36, 102) = 6 e como 6 não divide 8, a congruência não possui solução.
02) Resolver por congruência as seguintes equações diofantinas lineares.
a) 12x + 25y = 331.
Solução: O mdc(12, 25) = 1 e 1 | 331, logo a equação diofantina possui solução
12x – 331 = 25(-y) daí, 12x 331 (mod 25); 331 12.13 (mod 25)
12x 12.13 (mod 25); x 13 (mod 25). Assim x0 = 13 é uma solução particular da equação
diofantina linear. Substituindo este valor na equação diofantina, obtemos:
12.13 + 25y = 331; 25y = 331 - 156; 25y = 175; y0 = 7
A solução geral é: x = 13 + 25t, y = 7 – 12t.
b) 5x – 53y = 17.
Solução: O mdc(5, 53) = 1 e 1 | 17, logo a equação diofantina possui solução
5x – 17 = 53y daí, 5x 17 (mod 53); 17 5.14 (mod 53); 5x 5.14 (mod 53)
x 14 (mod 53). Assim x0 = 14 é uma solução particular da equação diofantina linear. Substituindo
este valor na equação diofantina, obtemos:
5.14 – 53y = 17; –53y = 17 - 70; – 53y = – 53; y0 = 1. A solução geral é: x = 14 – 53t, y = 1 – 5t.
c) 7x + 6y = 9.
Solução: O mdc(7, 6) = 1 e 1 | 9, logo a equação diofantina possui solução
7x - 9 = 6(–y) daí, 7x 9 (mod 6); 9 7.3 (mod 6); 7x 7.3 (mod 6)
x 3 (mod 6). Assim x0 = 3 é uma solução particular da equação diofantina linear. Substituindo este
valor na equação diofantina, obtemos: 7.3 + 6y = 9.
6y = 9 – 21; 6y = – 12; y0 = –2. A solução geral é: x = 3 + 6t, y = –2 – 7t.
03) Determinar o número de soluções de cada uma das seguintes congruências lineares:
(a ) 3x 6 (mod. 15)
Mdc(3, 15) = 3.
Como 6 é múltiplo de 3, a equação tem duas soluções.
( b ) 4x 8 (mod. 15)
Mdc(4, 15) = 1. 8 é múltiplo de 1. Portanto, a equação tem 1 solução.
( c ) 5x 10 (mod. 15)
mdc(5, 15) = 5. Como 10 é múltiplo de 5, a equação tem 2 soluções.
( d ) 6x = 11 (mod. 15)
mdc(6, 15) = 3. Como 11 não é múltiplo de 3, a equação não tem solução.
Questões Propostas
01) Resolver as seguintes congruências lineares:
1) 34x 60(mod 98) R: x 45 e 94 (mod 98).
2) 8x 16(mod 12) R: x 2, 5, 8, e 11 (mod. 12).
3) 14x 36(mod 48) R: x 6 ou 30 (mod. 48).
4) 5x 3(mod 24) R: x 4 (mod. 24).
5) 3x 5(mod 7) R: x 4 (mod. 7).
6) 23x 7(mod19) R: x 16 (mod. 19).
7) 7x 5(mod18) R: x 13 (mod. 18).
8) 25x 15(mod120) R: x 15, 39, 63, 87 e 111 (mod. 120).
9) 14x 36(mod 48) R: x 30 e 61 (mod. 48).
10) 5x 15(mod12) R: x 3 (mod. 12).
11) 3x 9(mod 24) R: x 3, 11, e 19 (mod. 24).
02) Resolver por congruência as seguintes equações diofantinas lineares.
( a ) 4x + 51y = 9 R: x = 15 + 51t e y = -1 – 4t.
( b ) 7x + 6y = 9 R: x = 3 + 6t e y = - 2 – 7t
( c ) 11x + 27y = 4 R: x = 20 + 27t e y = -8 – 11t
( d ) 79x – 131y = 6 R: x = 42 - 131t e y = 24 - 75t
( e ) 39x + 26y = 104 R: x = 2t e y = 37 + 61t
( f ) 61x – 11y = 81 R: x = 8 - 11t e y = 37 - 61t
( g ) 65x + 77y = 200 R: x = 9 + 77t e y = -5 – 65t
( h ) 51x + 85y = 1037 R: x = 2 + 5t e y = 11 – 3t
03) Determinar o número de soluções que pode ter uma congruência linear cujo módulo é 20.
R: 1, 2, 4, 5, 10 ou 20 soluções pois estes são os divisores de 20.
04) Demonstrar que se d = mdc (a, m) e se d | b, então as congruências lineares ax b (mod. m) e
(a|d)x (b|d) (mod. m|d) têm precisamente as mesmas soluções.
05) Encontrar todas as soluções de cada uma das seguintes congruências lineares:
1) 5x 3(mod 7) R: x = 15 + 51t e y = -1 – 4t
2) 13x 14(mod 29) R:
3) 15x 9(mod 25) R:
4) 37x 16(mod 19) R:
5) 5x 20(mod 15) R:
6) 3x 1(mod 25) R:
7) 9x 1(mod 65) R:
8) 6x 10 (mod 22) R:
9) 14x 1(mod 77) R:
10) 15x 9 (mod 12) R:
11) 6x 10 (mod 22) R:
12) 9x 12 (mod 21) R:
UNIDADE X – SISTEMAS CONGRUÊNCIAS LINEARES
10.1 - Introdução:
No século um, o matemático chinês chamado Sun-Tsu se perguntou? Que número ser a esse de
forma que quando dividido por 3, o resto é 2; quando dividido por 5, o resto é 3, e quando dividido
por 7, o resto é 2?. A pergunta é Qual é a solução para o seguinte sistema de congruências?
x 2 (mod 3)
x 3 (mod 5)
x 2 (mod 7)
Definição 10.1 - Um sistema de congruências lineares é um sistema da forma abaixo:
1 1 1
2 2 2
r r r
A x B (mod m )
A x B (mod m )
A x B (mod m )
Arx Br (mod mr) onde Ai, i = 1,2, ..., r são inteiros supostamente não nulos. Uma solução
do sistema é um inteiro x0 que é solução de cada uma das congruências que dele fazem partes.
Exemplo 10.1: 3x 1 (mod 5) 2x 3 (mod 9).
Teorema 10.1 - Um sistema x a1 (mod m1); x a2 (mod m2) admite solução se, e somente se, a1 –
a2 é divisível por d = mdc(m1, m2). Neste caso, se x0 é uma solução particular do sistema e se m =
mmc(m1, m2) então x = x0 (mod m) é sua solução geral.
Corolário 10.1 - Um sistema de congruências lineares x a1 (mod m1); x a2 (mod m2); ... ; x ar
(mod mr) admite solução se, e somente se, ai – aj é divisível por dij = mdc(mi, mj). Nesse caso se x0
é uma solução particular, então a solução geral do sistema é dada por x x0 (mod m) onde m =
mmc(m1, m2, ... , mr).
Exemplo 10.2: x 1 (mod 5); x 3 (mod 4); x 9 (mod 6).
Teorema 10.2 - (do Resto Chinês): Sejam m1, m2,..., mr números inteiros maiores que zero e tais
que mdc(mi, mj) = 1, i j. Façamos m = m1m2...mr e sejam b1, b2, ... , br, respectivamente, soluções
das congruências lineares jm
my 1 (mod mj). Então o sistema x a1 (mod m1); x a2 (mod m2); ...
; x ar (mod mr) admite soluções para quaisquer a1, a2, ... , ar e sua solução geral é dada por:
1 1 2 2 r r
1 2 r
M M Mx a b a b ... a b (mod m).
m m m
Este algoritmo, utilizado para resolver sistemas de congruências lineares, é muito antigo e foi
inventado, independentemente, pelos chineses e pelos gregos, para resolver problemas de
astronomia. O algoritmo chinês do resto tem este nome porque um dos primeiros lugares em que
aparece foi no livro Manual de aritmética do mestre Sun-Tsu, escrito entre 287 d.C. e 473 d.C.
Exemplo: x 1 (mod 2); x 2 (mod 3); x 3 (mod 5).
Questões Resolvidas
01) Resolver os seguintes sistemas de congruências lineares:
a) x 1 (mod 2), x 1 (mod 3).
Solução: Como o mdc(2, 3) = 1 o sistema possui solução.
A solução geral da 1a. é x = 1 + 2a, substituindo este valor na 2a, obtemos
1 + 2 a 1 (mod 3); 2 a 0 (mod 3); a 0 (mod 3). Logo a = 3b; substituindo este valor em x = 1 +
2a, temos x = 1 + 2(3b), dando x = 1 + 6b que é a solução geral do sistema ou x 1(mod 6) .
b) x 5 (mod 12), x 7 (mod 19).
Solução: Como mdc(12, 19) = 1 o sistema possui solução. A solução geral da 1a. é
x = 5 + 12a; substituindo este valor na 2a, obtemos: 5 + 12 a 7 (mod 19); 12 a 2 (mod 19); 6
a 1 (mod 19); 1 6.16 (mod 19) 6; a 6.16 (mod 19); a 16 (mod 19). A solução geral é a = 16 +
19b; substituindo este valor em x = 5 + 12 a, temos x = 5 + 12(16 + 19b), dando x = 197 + 228b,
que é a solução do sistema ou x 197(mod 228) .
02) Resolver os seguintes sistemas de congruências lineares:
a) x 3 (mod 5), x 5 (mod 7), x 7 (mod 11).
Solução: Como mdc(5, 7) = mdc(5, 11) = mdc(7, 11) = 1 o sistema possui solução.
A solução geral da 1a. é x = 3 + 5 a, substituindo este valor na 2a, obtemos
3 + 5 a 5 (mod 7); 5 a 2 (mod 7); 2 5.6 (mod 7); 5 a 5.6 (mod 7)
a 6 (mod 7) dando a solução geral a = 6 + 7b; substituindo este valor em x = 3 + 5 a temos: x = 3 +
5(6 + 7b) = 33 + 35b. Substituindo este valor na 3a equação, temos:
33 + 35b 7 (mod 11); 35b –26 (mod 11); 35b 2b (mod 11); 2b –26 (mod 11).
b –13 (mod 11) dando a solução b = –13 + 11c. Substituindo este valor na expressão
x = 33 + 35 b, temos x = 33 + 35(–13 + 11c) = –422 + 385c que é a solução geral do sistema
x 348(mod 385) .
b) x 1 (mod 5), x 5 (mod 7), x 7 (mod 11).
Solução: Como o mdc(5, 7) = mdc(5, 11) = mdc(7, 11) = 1 o sistema possui solução.
A solução geral da 1a congruência é: x = 1 + 5 a.; substituindo este valor na 2a., obtemos
1 + 5 a 5 (mod 7); 5 a 4 (mod 7); 4 5.5 (mod 7); 5 a 5.5 (mod 7)
a 5 (mod 7), dando a solução geral a = 5 + 7b; substituindo este valor em x = 1 + 5 a, obtemos x =
1 + 5(5 + 7b) = 26 + 35b; substituindo este valor na 3a congruência, temos:
26 + 35b 7 (mod 11); 35b –19 (mod 11); –19 35.7 (mod 11).
35b 35.7 (mod 11); b 7 (mod 11), dando a solução geral b = 7 + 11c; substituindo este valor em
x = 26 + 35b, x = 26 + 35(7 + 11c) = 271 + 385c que é a solução geral do sistema ou
x 271(mod 385) .
c) x 5 (mod 6), x 4 (mod 11), x 3 (mod 17).
Solução: Como o mdc(6, 11) = mdc(6, 17) = mdc(11, 17) = 1 o sistema possui solução.
A solução geral da 1a congruência é: x = 5 + 6 a, substituindo este valor na 2a congruência,
obtemos: 5 + 6 a 4 (mod 11); 6 a –1 (mod 11); –1 6.9 (mod 11).
6 a 6.9 (mod 11); a 9 (mod 11), dando a solução geral a = 9 + 11b; substituindo este valor em x
= 5 + 6 a, obtemos: x = 5 + 6(9 + 11b) = 59 + 66b; substituindo este valor na 3a congruência, temos:
59 + 66b 3 (mod 17); 66b –56 (mod 17); dividindo por 2, temos: 33b –28 (mod 17); –
28 33.11 (mod 17); 33b 33.11 (mod 17); b 11 (mod 17), dando a solução geral b = 11 + 17c,
substituindo este valor em x = 59 + 66b, temos: x = 59 + 66(11 + 17c) = 785 + 1122c que é a
solução geral do sistema ou x 785(mod 1122) .
d) x 5 (mod 11), x 14 (mod 29), x 15 (mod 31).
Solução: Como o mdc(11, 29) = mdc(11, 31) = mdc(29, 31) = 1 o sistema possui solução.
A solução geral da 1a congruência é: x = 5 + 11 a, substituindo este valor na 2a congruência,
obtemos 5 + 11 a 14 (mod 29); 11 a 9 (mod 29); 9 11.14 (mod 29); 11 a 11.14 (mod 29);
a 14 (mod 29), dando a solução geral a = 14 + 29b substituindo este valor em x = 5 + 11 a, temos:
x = 5 + 11(14 + 29b); x = 159 + 319b, substituindo este valor na 3a congruência, temos: 159 +
319b 15 (mod 31); 319b –144 (mod 31); –144 319.15 (mod 31); 319b 319.15 (mod 31);
b 15 (mod 31), dando a solução geral b = 15 + 31c; substituindo este valor em x = 159 + 319b,
temos: x = 159 + 319(15 + 31c); x = 4944 + 9889c que é a solução geral do sistema ou
x 4944(mod 9889) .
e) x 7 (mod 9), x 10 (mod 4), x 1 (mod 7).
Solução: Como o mdc(9, 4) = mdc(9, 7) = mdc(4, 7) = 1 o sistema possui solução.
A solução geral da 1a congruência é: x = 7 + 9a, substituindo este valor na 2a congruência, obtemos
7 + 9a 10 (mod 4); 9a 3 (mod 4); 3a 1 (mod 4); 1 3.3 (mod 4); 3 a 3.3 (mod 4); a 3 (mod
4), dando a solução geral a = 3 + 4b; substituindo este valor em x =7 + 9 a, temos x = 7 + 9(3 + 4b)
= 34 + 36b; substituindo este valor na 3a congruência, temos: 34 + 36b 1 (mod 7); 36b –33 (mod
7); –33 36.2 (mod 7); 36b 36.2 (mod 7); b 2 (mod 7), dando a solução geral b = 2 + 7c,
substituindo este valor em x = 34 + 36b, temos x = 34 + 36(2 + 7c); x = 106 + 252c, que é a solução
geral do sistema ou x 106(mod 252) .
f) x 28 (mod 29), x 30 (mod 31), x 10 (mod 11).
Solução: Como o mdc( 29, 31) = mdc(29, 11) = mdc(31, 11) = 1 o sistema possui solução.
A solução geral da 1a congruência é: x = 28 + 29 a, substituindo este valor na 2a congruência,
obtemos: 28 + 29 a 30 (mod 31); 29 a 2 (mod 31); 2 –29 (mod 31); 29 a –29 (mod 31); a –1
(mod 31), dando a solução geral a = –1 + 31b; substituindo este valor em x = 28 + 29 a, temos: x =
28 + 29(–1 + 31b); x = –1 + 899b; substituindo este valor na 3a congruência, temos: –1 + 899b 10
(mod 11); 899b 11 (mod 11); 11 899.11 (mod 11); 899b 899.11 (mod 11); b 11 (mod 11);
dando a solução geral b = 11 + 11c; substituindo este valor em x = –1 + 899b, temos x = –1 +
899(11 + 11c) = 9888 + 9889c, que é a solução geral do sistema ou x -1(mod 9889) .
g) x a (mod 3), x b (mod 5), x c (mod 8).
Solução: Como o mdc(3, 5) = mdc(3, 8) = mdc(5, 8) = 1 o sistema possui solução.
Vamos resolver este sistema pelo método do resto chinês. Temos m1 = 3, m2 = 5 e m3 = 8, sendo m
= 3.5.8 = 120.
m/m1 = 5.8 = 40, m/m2 = 3.8 = 24, m/m3 = 3.5 = 15. Vamos resolver as seguintes congruências
lineares: 40b1 1 (mod 3); 24b2 1 (mod 5); 15b3 1 (mod 8); 40b1 1 (mod 3), b1 = 1; 24b2 1
(mod 5); b2 = –1; 15b3 1 (mod 8); b3 = –1. Com a1 = a, a2 = b e a3 = c, que é a solução geral do
sistema x 40a – 24b – 15c (mod 120).
03) Resolver o seguinte sistema de congruência:
1) 5x 11 (mod 17), 3x 19 (mod 32), 11x 6 (mod 37).
Solução: Como o mdc(17, 32) = mdc(17, 37) = mdc(32, 37) = 1 o sistema possui solução.
De 5x 11 (mod 17), x 9 (mod 17)
De 3x 19 (mod 32), x 17 (mod 32)
De 11x 6 (mod 37), x 14 (mod 37), assim temos o seguinte sistema:
x 9 (mod 17), x 17 (mod 32), x 14 (mod 37)
Usando o método do resto chinês: a1 = 9, a2 = 17, a3 = 14, m1 = 17, m2 = 32, m3 = 37 e m = m1m2m3
= 17.32.37 = 20128. m/m1 = 32.37 = 1184, m/m2 = 17.37 = 629, m/m3 = 17.32 = 544.
Então 1184b1 1 (mod 17), 629b2 1 (mod 32) e 544b3 1 (mod 37). De onde concluímos: b1 = 14,
b2 = 29 e b3 = 10. A solução geral será: x 12.113 (mod 20.128).
2) 2x 1 (mod 5), 3x 9 (mod 6), 4x 1 (mod 7), 5x 9 (mod 11).
Solução: Como o mdc(5, 6) = mdc(5, 7) = mdc(5, 11) = mdc(6, 7) = mdc(6, 11) = mdc(7, 11) = 1 o
sistema possui solução.
De 2x 1 (mod 5), x 3 (mod 5).
De 3x 9 (mod 6), x 3 (mod 2).
De 4x 1 (mod 7), x 2 (mod 7).
De 5x 9 (mod 11), x 4 (mod 11).
Vamos resolver pelo método do resto chinês: a1 = 3, a2 = 3, a3 = 2, a4 = 4, m1= 5 , m2 = 2, m3 = 7,
m4 = 11.
m = m1 m2 m3 m4 = 5.2.7.11 = 770.
1
m
m = 2.7.11 = 154, 154b1 1 (mod 5), b1 = - 1.
2
m
m = 5.7.11 = 385, 385b2 1 (mod 2), b2 = 1.
3
m
m = 5.2.11 = 110, 110b3 1 (mod 7), b3 = 3.
4
m
m = 5.2.7 = 70, 70b4 1 (mod 11), b4 = 3.
A solução é: x 3.(–1).154 + 3.1.385 + 2.3.110 + 4.3.70 (mod 770) ou x 653 (mod 770).
4) Resolver os seguintes sistemas de congruências lineares:
1) x 8 (mod 9), x 2 (mod 3), x 5 (mod 7).
Solução: Como o mdc(9, 3) = 3 e 3 | (8 - 2), mdc(9, 7) = mdc(3, 7) = 1 o sistema possui solução.
A solução geral da 1a congruência é: x = 8 + 9 a , substituindo este valor na 2a congruência,
obtemos: 8 + 9 a 2 (mod 3); 9 a –6 (mod 3); 3 a - 2 (mod 1); a 1 (mod 7), dando a solução
geral a = 1 + b; substituindo este valor em x = 8 + 9 a, temos: x = 8 + 9(1 + b) = 17 + 9b;
substituindo este valor na 3a congruência, temos:
17 + 9b 5 (mod 7); 9b –12 (mod 7); 3b – 4 (mod 7); – 4 3 (mod 7); 3b 3 (mod 7); b 1
(mod 7); dando a solução geral b = 1 + 7c; substituindo este valor em x = 17 + 9b, temos x = 17 +
9(1 + 7c) = 26 + 63c que é a solução geral do sistema.
2) x 4 (mod 6), x 13 (mod 15), x 8 (mod 14), x 1 (mod 7).
Solução: Como o mdc(6, 15) = 3 e 3 | (13 - 4), mdc(6, 14) = 2 e 2 | (8 – 4), mdc(6, 7) = mdc(15, 14)
= mdc(15, 7) = 1 e mdc(14, 7) = 7 e 7 | (8 – 1) o sistema possui solução.
A solução geral da 1a congruência é: x = 4 + 6 a; substituindo este valor na 2a congruência,
obtemos: 4 + 6 a 13 (mod 15); 6 a 9 (mod 15); 2 a 3 (mod 5); 3 8 (mod 5); 2 a 8 (mod 5);
a 4 (mod 5); dando a solução geral a = 4 + 5b; substituindo este valor em x = 4 + 6 a, temos x = 4
+ 6(4 + 5b) = 28 + 30b; substituindo este valor na 3a congruência, temos: 28 + 30b 8 (mod 14);
30b –20 (mod 14); 3b – 2 (mod 7); – 2 12 (mod 7); 3b 12 (mod 7); b 4 (mod 7); dando a
solução geral b = 4 + 7c; substituindo este valor em x =28 + 30b, temos: x = 28 + 30(4 + 7c).
x = 148 + 210c; substituindo este valor na 4a congruência, temos: 148 + 210c 1 (mod 7); 210c –
147 (mod 7); 30c –21 (mod 1); –21 30 (mod 1); 30c 30 (mod 1); c 1 (mod 1); dando a
solução geral c = 1 + d; substituindo este valor em x =148 + 210c; temos: x = 148 + 210(1 + d) =
358 + 210c que é a solução geral do sistema.
3) x 0 (mod 3), x 1 (mod 4), 17x 9 (mod 23)
Solução: Como o mdc(3, 4) = mdc(3, 23) = mdc(4, 23) = 1 o sistema possui solução.
A congruência 17x 9 (mod 23) pode ser transformada em x 10 (mod 23)
A solução geral da 1a congruência é: x = 3 a; substituindo este valor na 2a congruência, obtemos 3
a 1 (mod 4); 1 9 (mod 4); 3 a 9 (mod 4); a 3 (mod 4); dando a solução geral a = 3 + 4b;
substituindo este valor em x =3 a, temos; x = 3(3 + 4b); x = 9 + 12b; substituindo este valor na 3a
congruência, temos: 9 + 12b 10 (mod 23); 12b 1 (mod 23); 1 12.2 (mod 23); 12b 12.2 (mod
23); b 2 (mod 23); dando a solução geral b = 2 + 23c; substituindo este valor em x = 9 + 12b,
temos: x = 9 + 12(2 + 23c) = 33 + 276c que é a solução geral do sistema.
Questões Propostas
01) Resolver os seguintes sistemas de congruências lineares:
01)
3x 1(mod 7)
5x 2(mod11)
4x 3(mod13)
R: x 810(mod 1001) 11)
x 1(mod 10)
x 4(mod 11)
x 6(mod 13)
R: x 851(mod 1430)
02)
x 8(mod 9)
x 2(mod 3)
x 5(mod 7)
R: x 26(mod 63) 12)
x 2 (mod 5)
x 3 (mod 6)
x 8 (mod 9)
R:
03)
x 1(mod 3)
x 2(mod 5)
x 3(mod 7)
R: x 52(mod 105) 13)
x 1 (mod 4)
x 3 (mod 6)
x 6 (mod 9)
R:
04)
x 2(mod11)
x 4(mod12)
x 5(mod13)
R: x 772(mod 1716) 14)
x 7 (mod 15)
x 4 (mod 32)
x 7 (mod 11)
R:
05)
x 3(mod11)
x 5(mod19)
x 10(mod 29)
R: x 4128(mod 6061) 15)
21x 15(mod 45)
27x 33(mod 48)
22x 18(mod 46)
R:
06)
x 5(mod 7)
x 1(mod 9)
x 6(mod10)
R: x 26(mod 630) 16)
x 2(mod 3)
x 3(mod 5)
x 2(mod 7)
R
07)
x 1(mod 2)
x 2(mod 3)
x 5(mod 7)
R: x 5(mod 42) 17)
x 8(mod5)
x 5(mod3)
x 11(mod 7)
x 2(mod 4)
R: x 158(mod 420)
08)
2x 1(mod 5)
3x 2(mod 7)
5x 7(mod11)
R: x 283(mod 385) 18)
x 2(mod 3)
x 3(mod 4)
x 4(mod 5)
x 5(mod 6)
R: x 119(mod 360)
09)
x 7(mod11)
3x 5(mod13)
7x 4(mod 5)
R: x 227(mod 715) 19)
x 1(mod 3)
x 3(mod 5)
x 5(mod8)
x 7(mod11)
R:
10)
x 3(mod10)
x 11(mod13)
x 15(mod17)
R: x 1103(mod 2210) 20)
x 2(mod 4)
x 3(mod5)
x 4(mod 7)
x 5(mod9)
R
02) Determinar o menor inteiro positivo múltiplo de 7 que tem para resto 1, quando dividido por 2,
3, 4 e 5.
R:
03) Determine os números inteiros cujos restos da divisão por 3, 4 e 5 são, respectivamente, 1, 2 e 3.
R:
04) Determine um certo inteiros entre 1 e 1200 tem como restos 1, 2 e 6 quando dividindo
respectivamente por 9, 11 e 13. Determiná-lo. R:
05) Um Coronel do Corpo de Bombeiros depois de assumir o comando da corporação quis saber
qual era o efetivo do Comando Geral para esse objetivo mandou o Ajudante Geral dispor o efetivo
sucessivamente em colunas de:
07 indivíduos, tendo sobrado 06 indivíduos;
11 indivíduos, tendo sobrado 05 indivíduos;
13 indivíduos, tendo sobrado 03 indivíduos;
Sabendo que o efetivo do Comando Geral, tem menos de 1000 de militares Determine quantos
militares constituem o efetivo.
R = 874 militares efetivo.
06) Um Coronel depois de destacado para comandar um regimento do Exército quis saber qual era o
efetivo desse regimento para esse objetivo mandou-os dispor sucessivamente em colunas de:
37 indivíduos, tendo sobrado 01 indivíduos;
32 indivíduos, tendo sobrado 04 indivíduos;
27 indivíduos, tendo sobrado 01 indivíduos;
Sabendo que um regimento, tem menos de 10.000 de militares. Determine quantos militares
constituem esse regimento.
R = 4996 militares efetivo.
07) Um bando de 17 piratas, ao tentar dividir igualmente entre si as moedas de uma arca, verificou
que haveria uma sobra de 3 moedas. Seguiu-se uma discussão, na qual um pirata foi morto. Na nova
tentativa de divisão já com um pirata a menos, verificou-se que haveria uma sobra de 10 moedas.
Nova confusão, e mais um pirata foi morto. Então, por fim, eles conseguiram dividir igualmente as
moedas entre si. Qual o menor número de moedas que arca poderia conter?
R= 3930 moedas.
08) Dois satélites S1 e S2 em órbita sobre a terra passam periodicamente sobre salvador. Sabendo-se
que S1 gasta 32 horas para completar sua órbita e que S2 gasta 23 horas, e que hoje S1 foi visto às 11
horas da manha e S2 foi visto às 10 horas da manha determine quando S1 e S2 serão vistos
simultaneamente sobre salvador.
R: Às 03:00 horas serão vistos simultaneamente.
09) Três satélites passarão sobre uma cidade esta noite. O primeiro à 01 h da madrugada, o segundo
às 04 hs e o terceiro às 08 hs da manhã. Cada satélite tem um período diferente. O primeiro leva 13
hs para completar uma volta ao redor da terra; o segundo 15 h/s e o terceiro 19 h/s. Determine
quantas horas decorrerão a partir da meia-noite até que os três satélites passem ao mesmo tempo
sobre a cidade?
R: 10 horas.
10) Uma senhora estava caminhando para um mercado quando um cavalo se bateu com a sua cesta
de ovos. O cavaleiro queria pagar os danos e perguntou para a senhora quantos ovos haviam na
cesta. Ela não se lembrava exatamente da quantidade, mas sabia que se tirasse os ovos da cesta de
três em três, sobravam dois ovos. Se tirasse de 5 em 5, sobravam 3 ovos e de 7 em 7 sobravam 2.
Qual seria a menor quantidade de ovos que ela poderia ter?
R: Pelo menos 23 ovos.
11) Um casal resolveu ir fazer uma viagem à volta do mundo. Sabendo que partiram no dia 01 de
março de um ano bissexto num domingo que chegariam no dia 6 de março, Segunda-feira e que
demoraram menos de 4 anos para fazer a viagem. Determine quantos dias demorou a viagem?
R:
12) Num cesto ha mais de 200 e menos de 600 ovos. Sabe-se que, se os ovos forem retirados 2 de
cada vez, no fim resta 1 ovo; se forem retirados 3 de cada vez, restam 2; se forem retirados 4 de
cada vez, restam 3; se forem retirados 5 de cada vez, restam 4; se forem retirados 6 de cada vez,
restam 5; e, se forem retirados 7 de cada vez, o cesto fica vazio. Quantos ovos estão no cesto?
R:
13) Três marinheiros sobreviveram a um naufrágio e foram ter a uma ilha onde vivia um macaco.
Comeram alguns cocos e resolveram apanhar mais alguns para comerem nos dias seguintes. Ao
anoitecer, imediatamente antes de irem dormir, constataram que tinham apanhado menos de 100
cocos. A meio da noite, um dos marinheiros acordou e, como não confiava nos companheiros,
decidiu guardar a parte dele. Assim, tentou dividir o monte dos cocos em três montes, todos com
igual número de cocos. Ao fazer isto sobrou um coco que ele deu ao macaco. Enterrou a parte dele e
foi dormir. Um segundo marinheiro acordou e, pelo mesmo motivo, decidiu também enterrar a parte
dele. Dividiu o monte em três montes iguais, tendo dado ao macaco um coco que, também neste
caso, sobrou. Enterrou a parte dele e foi dormir. Passado algum tempo o terceiro marinheiro
acordou e fez exatamente aquilo que haviam feito os outros dois anteriormente. Na manha seguinte
os três marinheiros dividiram novamente o monte de cocos em três partes e voltou a sobrar um coco
que deram ao macaco. Quantos cocos havia inicialmente no monte? Com quantos cocos ficou cada
um dos marinheiros?
R:
14) Um grupo de 17 macacos guarda suas bananas em 11 cestas de igual conteúdo e em uma 12ª
cesta contendo 6 bananas. Eles podem dividir o total de suas bananas em 17 grupos iguais. Qual é o
menor número de bananas que eles podem possuir?
R:
15) Generais Chineses contavam o número de soldados sobreviventes de uma batalha alinhando-os
sucessivamente em filas de determinados tamanhos, contando cada vez o número de soldados
restantes e calculando o total de sobreviventes à partir desses dados. Um general tinha inicialmente
1200 soldados antes de uma batalha; após a batalha, ao alinhá-los em filas de 5 soldados, restaram 3
soldados; ao alinhá-los em filas de 6 soldados, restaram também 3 soldados; ao alinhá-los em filas 7
soldados, restou 1 soldado; finalmente, ao alinhá-los em filas de 11 soldados, nenhum restou.
Quantos soldados sobreviveram à batalha?
R:
UNIDADE XI – TEOREMA DE FERMAT e WILSON
11.1 - Introdução:
Desde, pelo menos, 500 anos antes de Cristo, os chineses sabiam que, se p é um número
primo, então p| 2p-2. Coube a Pierre de Fermat, no século XVII, generalizar este resultado,
enunciando um pequeno, mas notável teorema que se constitui no resultado central desta unidade.
Nesta unidade estudaremos algumas propriedades referentes a congruências modulo números
primos que são as aplicações do pequeno teorema de Fermat e o teorema Wilson e sua relevância no
estudo da teoria dos números.
11.2 - Teorema de Fermat:
Teorema 11.1 - (de Fermat) - Se p é um primo e se p não divide a, então ap-1
1 (mod p).
Corolário 11.1 - Se p é primo, então ap a (mod p) qualquer que seja o inteiro a.
Exemplo 11.1 - Verificar o teorema de Fermat para a = 3 e p = 7.
Exemplo 11.2 - Mostrar que 538
4 (mod 11).
Exemplo 11.3 - Mostrar que 117 é composto.
Teorema 11.2: Se p e q são primos distintos tais que ap a (mod q) e a
q a (mod p), então:
ap.q
a (mod p.q).
Exemplo 11.4 - Mostrar que 2340
1 (mod 341).
11.2 - Teorema de Wilson:
Teorema 11.3 - (de Wilson)- Se p é primo, então (p – 1)! –1 (mod p)
Teorema 11.4 - Se (n – 1)! –1 (mod n), então n é primo.
Obs: O teorema de Wilson e o seu recíproco dão um critério para se reconhecer se um inteiro dado é
primo um inteiro n > 1 é primo se e somente se, (n – 1)! –1 (mod n). Entretanto, para inteiros
grandes este critério é impraticável e por isso apenas tem utilização teórica.
Exemplo 11.5 - Verificar o teorema de Wilson com p = 7.
Exemplo 11.6 - Reconhecer se o inteiro 11 é primo.
Questões Resolvidas
01) Verificar o teorema de Fermat com a = 2 e p = 13.
Solução: Temos que mostrar que 212
1 (mod 13).
24 3 (mod 13); 2
8 9 (mod 13); 2
12 = 2
4.2
8 3.9 1 (mod 13)
02) Verificar o teorema de Wilson para p = 5.
Solução: Temos que mostrar que (5 – 1)! –1 (mod 5)
2.3 1 (mod 5); 2.3.4 4 (mod 5); 4 –1 (mod 5); logo 4! –1 (mod 5)
03) Mostrar que 8 é composto usando o teorema de Wilson:
Solução: (8 – 1)! = 2.3.4.5.6.7 0 (mod 8); portanto, como (8 – 1)! não é congruente a –1
concluímos que 8 não é primo.
04) Mostrar que 19 é primo usando o recíproco do teorema de Wilson.
Solução: (19 – 1)! = 2.3.4...17.18. Vamos ver a que número é congruente este fatorial.
2.3.4 = 5 (mod 19); 5.6 11 ((mod 19); 7.8 –1 (mod 19); 9.10 –5 (mod 19)
11.12 –1 (mod 19); 13.14 11 (mod 19); 15.16 12 (mod 19); 7.18 2 (mod 19).
Assim 6! = 2.3.4.5.6 5.11 17 –2 (mod 19); 8! = 6!.7.8 –2.(–1) 2 (mod 19); 10! = 8!.9.10
2.(–5) 9 (mod 19); 12! = 10!.11.12 9.(–1) –9 (mod 19); 14! = 12!.13.14 –9.11 –4 (mod
19). 16! = 14!.15.16 –4.12 9 (mod 19); 18! = 16!.17.18 9.2 18 –1 (mod 19).
05) Reconhecer se 17 é primo usando o teorema de Wilson:
Solução: Temos que verificar se (17–1)! –1 (mod 17). Temos:
4! 7 (mod 17); 5.6 13 (mod (17); 6! = 4!.5.6 7.13 6 (mod 17)
7.8 5 (mod 17); 8! = 6!.7.8 6.5 –4 (mod 17); 9.10 = 5 (mod 17)
10! = 8!.9.10 –4.5 –3 (mod 17); 11.12 13 (mod 17)
12! = 10!.11.12 –3.13 –5 (mod 17); 13.14 12 (mod 17)
14! = 12!.13.14 –5.12 8 (mod 17); 15.16 2 (mod 17)
16! = 14!.15.16 8.2 16 –1 (mod 17)
06) Verificar:
a) 186 1 (mod 49) Solução: 18
230 (mod 49); 18
430.30 18 (mod 49).
186= 18
2.18
4 30.18 1 (mod 49)
b) 186
1 (mod 343) Solução: 183 = 5832 1 (mod 343); 18
61 (mod 343).
7) Achar o resto da divisão de 15! por 17.
Solução: 16! –1 (mod 17) pelo teorema de Wilson; –1 16 (mod 17) então,
16! 16 (mod 17); daí 15!.16 16 (mod 17). Podemos cancelar o fator 16, desde que mdc(16, 17) =
1 e portanto 15! 1 (mod 17). Concluímos que o resto procurado é 1.
8) Mostrar que, se o mdc(a, 35) = 1, então a12
1 (mod 35).
Solução: 35 = 5.7 e portanto mdc(a, 5) = mdc(a, 7) = 1. Aplicando o teorema de Fermat:
a4
1 (mod 5); a12
1 (mod 5) logo 5 | (a12
–1)
a6
1 (mod 7); a12
1 (mod 7) logo 7 | (a12
– 1). Como mdc(5, 7) = 1 então,
35 = 5.7 | (a12
– 1) o que demonstra a12
1 (mod 35)
9) Demonstrar que, para todo inteiro a, se tem:
a ) a13
a (mod 7).
Solução: Suponhamos que 7 | a. Então a 0 (mod 7); a13
0 (mod 7) e portanto
a13
a (mod 7). Agora, suponhamos que 7 não divide a então, pelo teorema de Fermat:
a6
1 (mod 7); a7
a (mod 7); a13
= a6.a
7a (mod 7)
b) a37
a (mod 13).
Solução: Suponhamos que 13 | a. Então a 0 (mod 13); a37
0 (mod 13) e portanto a37
a (mod
13). Agora suponhamos que 13 não divide a. Então, pelo teorema de Fermat a12
1 (mod 13);
a13
a (mod 13); a24
= (a12
)2 1 (mod 13)
a37
= a13
.a24
a (mod 13).
Questões Propostas
01) Verificar o teorema de Fermat com a = 2 e p = 17.
02) Demonstrar que, para todo inteiro a, se tem:
a) a21
a (mod 15) b) a7
a (mod 42)
03) Demonstrar que, para todo inteiro positivo n, se tem:
a) 22n
1 (mod 3) b) 23n
1 (mod 7)
04) Mostrar que 18! + 1 0 (mod 437).
05) Mostrar que 538
4 (mod 11).
06) Mostrar:
a) 561 | (2561
– 2) b) 561 | (3561
– 3).
07) Verificar o teorema de Wilson p = 5.
08) Mostrar que 8 é composto usando o teorema de Wilson.
09) Verificar que 186 1 (mod 49).
10) Achar o resto da divisão de 15! Por 17.
11) Usando o pequeno Teorema de Fermat, encontrar o resto da divisão de 2100.000
por 17.
12) Encontrar o digito das unidades de 3100
, quando expresso na base 7. R: r = 4.
13) Mostrar que se p e q são primos distintos, então q - 1 p - 1p q 1(mod p q) .
14) Mostre que 13 | 270
+ 370
, usando o teorema de Fermat.
15) Usando o teorema de Wilson encontrar o menor resíduo positivo de: 6 7 8 9(mod 5) .
16) Formar com os inteiros 2, 3, 4, ... , 21 todos os pares a e b tais que ab 1 (mod 23).
O ÚLTIMO TEOREMA DE FERMAT
Desde da antiguidade o homem sentem uma fascinação por números que surge quase
imediatamente da prática. Um dos problemas mais antigos é o de dividir um quadrado em soma de
dois quadrados e uma das soluções é {3, 4, 5}, i.e., escrever 25 = 16 + 9. Aparentemente os antigos
egípcios já usavam estes números para construir ângulos retos e reconheciam que {3, 4, 5} eram
lados de um triângulo retângulo. Por volta de 500 AC os chineses também sabiam deste triângulo.
Provavelmente também os babilônios sabiam o que está por trás disto é o teorema de Pitágoras Para
que um triângulo seja retângulo é necessário e suficiente que o quadrado de sua hipotenusa seja
igual a soma dos quadrados dos catetos. Olhando de outra maneira a equação a2 = b
2 + c
2, admita
como solução uma terna {c, b, a} de valores inteiros, as quais chama-se ternas pitagóricas. A tabela
babilônica Plimton 322 apresentam uma lista de ternas pitagóricas. Por volta de 250 AC o
matemático grego Diofanto escreveu o primeiro livro de titulo Aritmética, dedicado ao que hoje
chamamos de Teoria de Números. Ele estuda soluções inteiras de equações que hoje chamamos de
equações diofantinas.
Para construir-se ternas pitagóricas basta observarmos a identidade algébrica (a+b)2 (ab)
2
= 4ab, ajeitando a = u2 e b = v
2, obtendo-se a terna {u
2 - v
2, 2uv, u
2 + v
2}.
PIERE DE FERMAT
Pierre de Fermat (1601-1665) foi um Juiz francês que nasceu e viveu em Toulouse, França.
Ele possuía uma cultura universal na época, que cultivava a poesia, filosofia grega, direito e
principalmente matemática. Fermat seguia uma certa tradição da época propor problemas tipo
desafio, para outros matemáticos. Ele é considerado juntamente com Descartes um dos criadores da
Geometria Analítica. Suas idéias sobre métodos das tangentes contêm as raízes do Cálculo
Diferencial. Raramente encontrasse uma publicação de Fermat como também ele raramente se
encontrou pessoalmente com outros grandes matemáticos de sua época. Suas comunicações estavam
em suas correspondências que geralmente era enviada pelo padre Marin Mersenne, e seu amigo
Pierre de Carcavy, que circulavam seus manuscritos, cartas em geral. Estes últimos foram
colecionados em forma de livro por seu filho Samuel. Uma grande parte de seu trabalho e
problemas foram resolvido nos 200 anos seguintes à sua morte. Outra grande parte é dedicada as
equações diofantinas onde ele deixou uma série de problemas. Dentre os vários problemas temos a
representação de primos como soma de quadrados, geração de primos, divisibilidade por primos, e
solução de x2
- dy2 = +1. a maioria deles foi resolvida no século seguinte, por Euler, Legendre,
Dirichlet e outros.
O problema conhecido como Último Teorema de Fermat, ou FLT, i.e., o último problema de
Fermat em aberto, é uma generalização do problema das ternas pitagóricas. Ele foi proposto numa
margem de uma edição do livro de Diofanto ao lado do problema 8, livro II, que é o problema da
decomposição de um quadrado em soma de dois outros. Ele afirma que isto é impossível para cubos
e potências superiores e afirma que possui uma demonstração elegante para este fato e que não cabe
na margem. Ele também propõem este problema para outros matemáticos da época Frenicle, Wallis,
..... O problema é mostrar que a equação F[n], an + b
n = c
n, n inteiro maior que 2, não possui
soluções não triviais no sentido de que pelo menos um dos números a, b ou c é zero. É fácil de
verificar que basta mostrar que F[n] não tem solução para n = 4, e para primos diferentes de 2. O
caso n = 4 foi resolvido por Fermat onde ele exibe seu método a qual denomina método da descida
infinita. O problema se enuncia então mostrar que para todo primo impar p, F[p] não possui
soluções não triviais. O problema pode ser dividido em dois casos: O primeiro é onde se requer que
nenhum dos números a, b, e c sejam divisíveis por p, e o segundo é o caso onde precisamente um
dos números é divisível por p. Para n = 3, o cubo de 5 mais o de seis difere muito pouco do de sete.
Este problema foi proposto em 1637, e daí seguiu-se uma busca para reproduzir a
demonstração de Fermat. Como Fermat errou na solução de outros problemas, admite-se a
possibilidade dele também ter errado em sua afirmação, porem não sabemos qual era sua
demonstração.
PRIMEIRAS TENTATIVAS
As primeiras tentativas foram feitas para p = 3. Euler, no inicio do século passado,
apresentou a solução neste caso. Ele cometeu enganos porem depois de um estudo minucioso da
divisibilidade de números da forma a2+3.b
2 ele obteve uma solução correta. Gauss apresenta
também uma demonstração para este caso. Com Gauss, 1801 nasce a Teoria dos Números. O caso p
= 5, foi demonstrado por G.L.Dirichlet em 1928. O caso p = 7 é de Lamé (1839). Sophie Germain,
em 1823, foi a primeira a tentar uma solução geral ela mostra que se 2p+1 é também primo então o
primeiro caso é valido. Isto introduz um novo problema existe um numero infinito de primos para
os quais 2p + 1 é também primo? Até hoje não se sabe. Com este resultado Legendre consegue
mostrar a validade do primeiro caso para todo primo menor que 100. Lamé e Cauchy apresentam
demonstrações erradas.
KUMMER
Até o fim de 1993 o único teorema geral que se conseguiu é devido ao matemático alemão
E. Kummer. Ele introduz a noção de primo regular, estes primos estão relacionados a certas
condições de divisibilidade de uns números chamados números de Bernouilli, Kummer demonstra
por volta de 1850, que F[p] é válido para todo primo regular. Infelizmente não se sabe se existem ou
não infinitos primos regulares, sabe-se que existe um número infinito de primos não regulares. Os
primos não regulares menores que 164 são 37, 59, 67, 101, 103, 131, 149, e 157. Aí surge com
Kummer, Dirichlet e Dedekind a Teoria de Números Algébricos, teoria esta que falando
grosseiramente trata de expressões contendo radicais. A noção de número primo e de decomposição
é estendida a estes números. Isto sempre foi essencial em todos os casos demonstrados.
Em 1816, e de novo em 1850 a Academia Francesa de Ciências ofereceu uma medalha de
ouro e um prêmio de 3000 Francos a quem resolve-se o problema de Fermat. A medalha foi
concedida a Kummer pelo seu brilhante trabalho neste teorema. No inicio deste Século, um
matemático alemão Wohlfskehl a beira do suicídio descobriu o trabalho de Kummer sobre o
teorema de Fermat e decidiu dedicar-se a sua leitura. Ele deixou sua fortuna na Königliche
Gesellschaft der Wissenschaften, em Göttingen, Alemanha, oferecendo um prêmio de 100.000DM
pelo solução deste problema, devido a inflação este prêmio está reduzido a 10.000DM. Este prêmio
leva a Academia a ter que selecionar milhares de trabalhos apresentados anualmente, dentre os quais
a grande maioria ou não fazem sentido, ou são muito elementares. Deve-se observar que Fermat era
um matemático muito bom ele resolveu o caso n = 4 aplicando seu método denominado a “descente
infinita”, e que qualquer solução que se Fermat tinha em mente deveria ter conteúdo matemático.
FERMAT COMPUTACIONAL
Depois de Kummer um grande números de matemáticos como Wagstaff, Morishima, Inkeri,
Vandiver, Eichler, Brückner, tentaram desenvolver critérios para que pudéssemos verificar a
validade de F[p] via computador. Estes critérios são complicados para mencionarmos aqui. Um
deles porem é bem simples Wiefrich (1909). Se p2 não divide 2p-1-1 então o primeiro caso do
teorema de Fermat é verdadeiro.
Até hoje só conhecemos dois números dentre todos os primos menores 3x109 para os quais
isto não é verdade 1093 e 3511. Aí temos um novo problema existe um número infinito destas
exceções? Desenvolveu-se também critérios para o estudo do caso II para primos não regulares, e
com isto Wagstaff em 1976 mostra FLT para todo p < 125000. Em 1992 Buhlen verificou a
validade de FLT para todos os primos menores que 4000000. Outra direção tomada foi de estudar o
tamanho da solução, i.e.., se x é o menor valor de uma solução de F[p] qual é um estimativa de x, ou
melhor qual é a estimativa do número que deve-se tentar para exibir um contra exemplo? Usando-se
o resultado de Wagstaff a conclusão é que deveríamos tentar números com mais de 18x10 11
dígitos. Isto mostra que contra-exemplos está totalmente fora de nosso alcance.
TEORIA DE CURVAS
Na década dos 20, Mordell olha para o problema do ponto de vista de geometria algébrico
F[p] é a equação de uma curva algébrica, e dizer que existe uma solução não trivial significa dizer
que ela tem uma solução ou ponto com coordenadas racionais, ou simplesmente uma solução
racional. O primeiro passo seria mostrar que estas curvas teriam somente um número finito de
pontos racionais, desde que um dos seus invariantes, seu gênero seja maior que dois. Em 1983 o
matemático alemão G. Faltings demonstrou esta conjectura, o que lhe valeu a Field Medal prêmio
quadrienal ortografo nos Congressos Internacionais aos melhores trabalhos do período, equivalente
ao prêmio Nobel para matemática. Seguindo a idéia de Faltings em trazer toda maquinaria moderna
da geometria algébrica para a teoria de números, um grupo de matemáticos associa ao problema de
Fermat uma curva algébrica especial que possui muita estrutura aritmética a curva elítica. As curvas
de primeiro grau, equação linear em duas variáveis representa uma reta no plano as do segundo grau
representam cônicas (elipse, hipérbole, parábola ou circunferência). Uma equação do terceiro grau
representa uma cúbica, ela pode ser transformada ou em y = x(x+a)(x+b) ou em y2 = x(x-a)(x+b).
Esta última chama-se curva elítica, será indicada por E[a, b]. Elas tem este nome por estarem
associadas as integrais elíticas, integrais estas que são duplamente periódicas. Elas também possuem
uma operação natural de adição de pontos. A curva é não singular se a e b são distintos e diferentes
de zero.
Estudar a aritmética da curva significa estudar os pares de inteiros que satisfazem sua
equação. Seja E uma curva elítica. Para cada primo p vamos chamar de n(p) o número de soluções
de sua equação modulo p. Quando os números n(p) possuem uma fórmula aritmética de cálculo a
curva chama-se modular. Em 1955 um matemático japonês chamado Tanyama postulou que toda
curva elítica onde a e b são números racionais é uma curva modular.
Um matemático alemão G. Frey em 1980 teve a idéia de associar a cada solução {a, b, c} de
F[p] a curva elítica E[an,b
n] a qual tem uma estrutura algébrica muito estranha, e daí a suspeita de
que tal curva não poderia existir e isto implicaria na não existência da solução de F[p]. Em 1986 K.
Ribet mostra que a curva associada a F[p] não é modular, e daí a conjectura de Tanyiama implica
em FLT !!!. No fundo o que Ribet fez foi mostrar que uma conjectura mais fraca, a de J P Serre, um
dos grandes matemáticos deste século, se aplica a curva de Frey.
ANDREW WILES.
Andrew Wiles nasceu em 1954 na Inglaterra. Ele conta que quando tinha dez anos pegou na
biblioteca um livro onde viu este problema e desde então se propôs a resolvê-lo. Deixou depois de
varias tentativas amadora, o problema de lado foi estudar matemática em Cambridge com um
grande especialista em teoria de números, John Coates. Veio para Harvard onde passou dois anos e
resolveu dois problemas em aberto nesta área. Em seguida aceita uma posição de Professor em
Princeton. Quando soube dos resultados de Ribet, ele ganhou confiança de que poderia resolve FLT
e ao contrario do matemático comum ele decide se isolar por sete anos ate apresentar uma solução
ao problema. Levou cinco anos para ter uma idéia da solução.
A primeira vista pode-se pensar que Wiles se trancou e ignorou o que se passa na sua área;
isto não foi o caso, pois uma boa técnicas e construções não existiam em 86. Sua demonstração
apareceu volume de Maio do Annals of Mathematics de 1995. A solução apresentada em 23 de
Junho de 1993 tem um erro que depois foi consertado por um aluno dele. O trabalho original
acertado juntamente com o material necessário para corrigir o anterior ocupa todo este volume do
Annals. O que Wiles mostra é que toda curva elítica semiestavel é modular e em particular a curva
de elítica associada a uma possível solução de F[p] também é modular o que contradiz ao teorema
de Ribet. Logo a cura não existe, i.e., F[p] não admite soluções não triviais.
Observações
Obs1: Babilônios e certamente Diofanto já sabiam que existe um numero infinito (em potencial) de
ternas Pitagóricas.
Obs2: Atualmente o material lecionado no tanto no secundário como nos cursos de matemática é
uma preparação para se entender mais tarde o que realmente é a matemática. A grande aventura
lógica. Idéias que vem da natureza. Satisfação pessoal de resolver problemas e mais ainda de criar
nova matemática. Neste sentido a Matemática e é única, a cada minuto de envolvimento nos dá
grande prazer, mesmo para o profissional coisas simples como novas maneiras de apresentá-la são
gratificantes.
Obs3: O processo de verificação e publicação de resultados é longo. Por um lado a Matemático
requer lápis e papel somente (hoje em dias supercomputadores em alguns ramos como, por
exemplo, teoria de números) o que a torna acessível a milhares de pessoas, os matemáticos hoje em
dia são da ordem de 200.000. Cada anos se produz cerca de 1.000.000 de resultados novos. Cada
um ou dois anos ela dobra o que torna impossível a matemáticos (the mathematical experience)
saberem toda a matemática. H. Poincare foi o ultimo universal. nos 60 primeiros anos do século 20
A Weil era universal nas áreas de Geometria Algébrica, Álgebra, Teoria de Números, e outras áreas
relacionadas ele tinha a reputação de ter um grande “faro matemático”, uma grande intuição dos
problemas que são solúveis. Enunciar problemas é muito fácil porem a grande maioria são de
solução muito difícil ou ate impossível com técnicas atuais. Muitas vezes eles requerem um
amadurecimento de um ou vários matemáticos por décadas. Atualmente já é difícil dominar um das
centena de seus ramos e sub-ramos. O Mathematical Review é a principal revista que apresenta
resenhas dos trabalhos publicados no ultimo ano, ele atualmente é um volume maior que um dos
volumes de qualquer enciclopédia. Apesar de alguns problemas como o de Fermat serem simples de
enunciá-los a probabilidade de se resolver novos problemas com técnicas elementares é bem
pequena. Não se faz pesquisa a nível de graduação, nem mesmo a nível de mestrado, pois os
problemas em aberto requerem cada vez mais quantidades muito grande de conhecimento. Aquele
fato de que grande matemática Os é feita por jovens já esta passando, pois soluções de grandes
problemas requerem muito conhecimento de técnicas e de certo domínio de outros ramos, o que
leva tempo de aprendizado. Afinal de contas, Wiles tem quarenta anos.
Obs4: Ninguém nunca saberá qual a demonstração que Fermat tinha em mente. Muitos matemáticos
acham que ele errou em algum canto. Outros porem acham que ele pode ter descoberto uma
demonstração deste teorema. Ele tinha uma autoreputação para cuidar.
CONFERENCIAS SOBRE FLT.
Em linhas gerais seguimos a conferencia patrocinada pelo MSRI (Mathematical Sciences
Research Institute- Berkeley, California) onde que consistiu de cinco conferencias de dez minutos,
seguida de uma mesa redonda. Em ordem falaram Osserman e ,Buhlen diretores do MRSI e os
eminente matemáticos C. Rubin , Ribet e J.Conway. Osserman fala sobre a pré-história do problema
e acrescenta dois pontos não apresentados acima. O primeiro é um problema “pratico” Você entra
numa Pizzaria e você tem duas escolhas:
Comer uma pizza grande, ou uma pequena e uma media. Queremos saber qual escolha tem
mais pizza. Se cortamos as pizzas ao meio e com seus diâmetros formarmos um triângulo, se este
for obtusângulo a primeira escolha é a melhor. Se o triângulo for acutângulo a segunda escolha é a
melhor. Os existe uma posição onde as duas escolhas são iguais quando o triângulo é retângulo, e
isto é uma conseqüência imediata do teorema de Pitágoras e sua recíproca a lei dos cossenos.
O segundo ponto refere-se a Pitágoras. Na realidade ele era o líder de uma escola filosófica
de iniciação que se dedicava ao estudo da perfeição do universo. Eles descobriram que a natureza
traz um grande numero de fenômenos que podem ser descritos via matemática. A seguir ele
descreve a teoria musical de Pitágoras: a busca por notas harmônicas. O fato é o seguinte: se
tivermos uma corda vibrante de extremos AB e a subdividimos prendendo-a em um ponto C, e
tocarmos as duas sub-cordas sucessivamente observaremos que razões como 3:4 ou 2:3 soam
harmonicamente. Se considerarmos cordas sobre os lados de um triângulo retângulo teremos
triângulos harmônicos onde qualquer pares de lados são harmônicos. Os triângulos de lados inteiros
são harmônicos!. Dai o interesse por ternas Pitagóricas. Convém mencionar que no caso do
triângulo retângulo isósceles a razão é 1:2. Esta razão foi conhecida na idade media como “musica
diabólica”. O problema das construções das ternas Pitagóricas esta resolvido no livro de Diofanto.
Buhlen discute o desenvolvimento do problema, os resultados obtidos nos 349 anos seguinte. Alem
do que foi dito acima ela fala um pouco mais sobre a vida de Sophie Germain, antes deste século
uma das três matemáticas. Ela estudou matemática as escondidas, seu trabalho foi apresentado com
outro nome M. Leblach pois a Academia Francesa não admitia mulheres, e por fim teve ser trabalho
reconhecido por Gauss. O livro de Gauss sobre aritmética, publicado em 1801 quando ele tinha 21
anos dá a teoria de números um status de área da matemática.
Antes ela era tratada como recreação. Gauss também não da grande importância ao problema
de Fermat. A primeira pergunta que surge quando nos enfrentamos com um problema matemático é
saber como verificar a validade de nossas afirmações, ou tentamos também mostrar que nossa
afirmação não é valida, e para isto basta exibir um exemplo onde o teorema não é valido. Tendo isto
em mente durante pelo menos um século ou mais tentou-se encontrar contra exemplos
procedimento este que foi abandonado nos meados deste século quando se teve consciência que o
valor da menor solução é muito grande (Milnor). O caso n = 4 é um dos poucos onde Fermat
apresenta sua demonstração na margem de uma pagina do livro de Diofanto usando a descente
infinita que consiste em assumir a existência de uma solução, achar o menor valor da terna solução
e por algum processo fabricar uma outra solução que tenha menor valor que o da primeira terna.
Qualquer demonstração de FLT é feita pelo método de redução ao absurdo: parte-se de uma
suposta solução e obtém-se uma contradição. Outro método é o usado por Diofanto a analise dos
divisores primos de xn = y
n - z
n. Já que este ultimo lado direito pode ser decomposto em fatores que
em geral são números complexos. Os erros de demonstração foram na analise de divisibilidade
destes fatores. Uma analise mais critica destes fatores levou Kummer a criação da noção de
(numero) ideal, e dai a criação de uma teoria destes objetos análoga a de números. Rubin começa
tratando de uma curva elítica: o gráfico da equação y2 = x
3 - x. Ela foi tratada por Fermat que
mostrou não ter solução inteira. Esta equação aparece na determinação de todos os triângulos
retângulos de lados inteiros cuja área é um quadrado perfeito. Seu objetivo é a noção de
modularidade. Ele explicita um procedimento muito comum na teoria de números mais
especificamente quando se quer saber se uma equação tem ou não soluções inteiras o que em geral é
um problema bastante difícil. Reduz-se a equação modulo um primo dado observando-se que se ela
tem solução inteira ela terá solução modulo p para todo primo p, o que é sempre fácil de se verificar
pois ficaremos com um problema de contagem. O próximo passo é verificar se ela tem solução
modulo pn para todo n. E dai tenta-se levantar esta solução para uma solução inteira este é o
chamado principio de Hasse. No caso das curvas elíticas este procedimento apresenta enormes
dificuldades. No caso particular da equação acima Gauss em 1814 apresenta uma formula para este
calculo. Ribet baseado na formula de Gauss apresenta a seguinte tabela:
primos: 2 3 5 7 11 13 17 19 23 29 31
n(p) 2 3 7 7 11 7 15 19 23 29 31
primos 1000003 1000033 1000037 1000039
n(p) 1000003 998207 998055 1000039
O calculo de n(p) para números pequenos pode ser feito através de uma tabela contando-se o
numero de pares onde p divide y2 - x
3 + x. para p = 5 a tabela contem essencialmente 25 valores. Já
para 1000003 a tabela contem mais de 1012 valores o que é difícil de contar. Rubin botem os
valores acima da formula de Gauss. Nos casos simples n(2)=2, e se p for um primo da forma 4k-1,
n(p) = p. No outro caso a formula é mais complicada. Uma curva elítica em geral chama-se modular
se esta seqüência de inteiros n(p) admite uma formula de calculo. A curva modular desempenha um
papel fundamental na solução de Wiles. Em 1955 Yutata Tanyama apresenta a hipótese que toda
curva elítica a coeficientes inteiros é modular na época e percebeu motivos para esta hipótese.
Tanyiama morreu em 58 mais tarde Goro Shimura professor em Princeton apresenta boas
razões porque a hipótese deveria ser verdadeira. Dai em diante o numero de especialista s na área
que acreditavam na hipótese foi crescendo. Esta é a peça principal da solução de Wiles ele
demonstra a hipótese de Tanyiama para uma classe especial de curvas que são as semi-estaveis.
Ribet começa observando que um matemático alemão G. Frey no inicio da década dos 80 começou
a fazer cálculos, e associou à curva de Fermat uma curva elítica E[an, bn]. Em 1981 Frey veio a
Berkeley e trocou idéias com Ribet. Na época ele já estava percebendo a ligação de FLT e
Tanyiama, porem não estava claro. Em Janeiro de 1985, em Oberwolfach ele apresentou uma curta
comunicação onde delineava suas ideais, esta comunicação chegou a Paris onde Serre, um dos
grandes matemáticos atuais que também possui a medalha da área, observou que uma pequena
variação da conjectura de Tanyiama implicaria FLT. Em 1986 ele, Ribet tinha uma demonstração da
conjectura de Serre e apresenta a Mazur que diz que parece correta. Ribet passa todo o ano de 87 no
MSRI onde apresenta seminários semanais sobre sua demonstração. Como o processo de publicação
é lento, passa por referres onde tem-se que negociar sugestões, e somando-se o atraso nas
publicações, seu trabalho foi publicado em 1990. A seguir ele comenta como Wiles se retirou e
observa que a solução depende na realidade de muitas outras estruturas e trabalhos. Ribet observa
que a solução de Wiles não é um fato isolado. Ela depende dos trabalhos que muitos outros
desenvolveram nesta ultima década este trabalho envolve técnica desenvolvidas nas áreas:
1. Famílias de Representações de Galois (Hida, Mazur)
2.Teoria de Iwahori (Greenberg, Rubin)
3.Sistemas de Euler(Kolyvagen, Flach)
4.Formas Modulares(Ribet)
5.Geometria Algébrica(Faltings)
6.Teoria da Representação(Langlands, Tunnel)
TRABALHO E PROBLEMAS DE FERMAT NA TEORIA DE NÚMEROS
Vamos a seguir apresentar uma pequena lista com comentários sobre os problemas
enunciados por Fermat.
1. O primeiro de nossa lista é o pequeno teorema de Fermat Seja p um primo dado. Então para todo
inteiro a p divide ap-a. Este foi generalizado por Euler e sua versão geral é que para todo n inteiro
positivo e todo inteiro a n divide af(n)-a, onde f(n) é o numero de inteiros entre 0 e n-1 que são
relativamente primos a n.
2. Fermat estudou formulas para primos a primeira é quando M(n) = 2n -1 é primo. Isto leva ao
problema de saber para que valores de n, primo, M(n) é primo. Estes primos chamam-se primos de
Mersenne pois foi ele que testou todos os números primos menores que 100, com alguns erros. Não
se sabe se existe um numero infinito de primos de Mersenne. Outro caso estudado por Fermat foi a
primalidade de F(n) = 2n -1. Aqui é necessário que n seja uma potência de dois. Fermat afirmou que
todos estes números são primos. Euler mostrou que F(5) é divisível por 641. Ate hoje não se
conseguiu outro valor maior que 5 que nos forneça um numero primo, tentou-se até 11, e alguns
valores acima também.
3. Fermat estudou a representação de números como soma de outros particulares. Por exemplo um
primo cujo resto na divisão por 4 é um é uma soma de dois quadrados. Isto foi demonstrado por
Euler em 1749. Em 1977, Lagrange mostra que todo números é soma de quatro quadrados. Em 1801
Gauss demonstra o teorema de Fermat sobre Os de três números triangulares. Em 1813, Cauchy
demonstra os teoremas sobre cinco números pentagonais e outros. Em 1840 Jacobi demonstra
outros teoremas deixados por Fermat.
4. A equação de Pell x2 - dy
2 = +1, d inteiro, assim chamada erroneamente por Euler, também foi
estudada por Fermat. Fermat já sabia que esta equação possuiu um numero infinito de soluções
quando d > 0. Legendre mostra, usando frações continuas que todas soluções são potências de uma
delas mais tarde Dirichlet demonstra seu famoso teorema de unidades o qual engloba todos estes
resultados.
BIBLIOGRAFIA:
1) Edgard de Alencar Filho - Teoria Elementar dos Números - Livraria Nobel S.A. - 1981.
2) Hygino H. Domingues - Fundamentos de Aritmética - Atual - 1991.
3) L.H. Jacy Monteiro - Álgebra Moderna - Volume I - LPM - 1963.
4) I. Vinogradov - Fundamentos de la Teoria de los Números - Editorial Mir. - 1977.
5) José Plínio de Oliveira Santos – Introdução à Teoria dos Números – Coleção Matemática A. J.
6) Pettofrezzo - Teoria de los Números - Editorial Prentice / Hall Intercontinental - 1972.
7) Universitária - 1998 George E. Andrews – Number Theory – Dover Publications, Inc. - 1994.
![[Introducao a Teoria Dos Numeros - Jose Plinio Santos] (1)](https://img.document.onl/doc/110x75/55cf92ad550346f57b98a39b/introducao-a-teoria-dos-numeros-jose-plinio-santos-1.jpg)
