capacitação aritmetica

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

UFRPE
CAPACITAC¸A˜O PARA PROFESSORES
DE TURMAS OLI´MPICAS
DE MATEMA´TICA
Oficina de Resoluc¸a˜o de Problemas de Aritme´tica
Professor: Thiago Dias
1 Divisibilidade
Definic¸a˜o 1.1 Dados dois inteiros a e b, dizemos que a e´ mu´ltiplo de b se existir um inteiro k tal que a = k.b. Tambe´m
diz-se que a e´ divis´ıvel por b ou que b e´ divisor de a ou ainda que b divide a. Usaremos a notac¸a˜o b|a (b divide a)
Teorema 1.2 Propriedades da Divisibilidade.
1. a|a , a|0 , 1|a , −1|a e ale´m disso, se 0|a enta˜o a = 0.
2. Se a|b e b|c enta˜o a|c.
3. Se d|a e d|b enta˜o d|ax + by quaisquer que sejam x e y inteiros, em particular a + b e a − b sa˜o mu´ltiplos de d
quando a e b tambe´m o sa˜o.
4. Se a|b e b 6= 0 enta˜o |a| ≤ |b|.
5. Se a|b e b|a enta˜o a = b ou a = −b.
Exemplo 1.3 Mostre que se a e´ um numero inteiro enta˜o
1. a− 1|an − 1 para todo numero natural n.
2. a + 1|an + 1 para todo nu´mero natural ı´mpar n.
Soluc¸a˜o:
1. De fato e´ possivel verificar que an − 1 = (a− 1)(an−1 + an−2 + ... + a + 1).
2. Se n e´ nu´mero natural ı´mpar enta˜o
(−a)n−1 = (−a−1)((−a)n−1+(−a)n−2+...+1)⇒ an+1 = (a+1)(an−1−an−2+...−a+1).
2 Numeros primos e compostos
Definic¸a˜o 2.1 Um nu´mero inteiro p e´ dito primo se possui exatamente quatro divisores inteiros: os quais sa˜o 1, −1, p
e −p.
Definic¸a˜o 2.2 Um nu´mero c e´ dito composto se possui um nu´mero finito maior que quatro de divisores distintos.
1
Das duas definic¸o˜es acima podemos perceber que os nu´meros 0, 1 e ?1 na˜o podem ser considerados primos nem
compostos.
Teorema 2.3 Lema de Euclides. Se p e´ um nu´mero inteiro primo e a e b sa˜o inteiros quaisquer enta˜o temos que se p|a.b
enta˜o p|a ou p|b.
Perceba que o Lema de Euclides na˜o vale se c e´ um nu´mero composto. De fato 6|2 · 3 mas 6 na˜o e´ divisor de 2 nem
de 3.
Teorema 2.4 Teorema Fundamental da Aritme´tica. Todo nu´mero inteiro composto n pode ser escrito de maneira u´nica
(exceto pela ordem dos fatores) como um produto de primos (na˜o necessariamente distintos):
n = pe11 · · · pekk .
Exemplo 2.5 Encontre todas as soluc¸o˜es de nu´meros naturais da equac¸a˜o x2 − y2 = 31
Soluc¸a˜o:
Temos que x2 − y2 = (x + y)(x − y) e como 31 e´ primo temos apenas dois casos a
considerar. O primeiro caso e´ x+y = 31 e x−y = 1. Esse sistema com duas equac¸o˜es
e duas inco´gnitas ademite a soluc¸a˜o x = 16 e y = 15. O segundo caso a considerar e´
x+ y = 1 e x− y = 31. Nesse caso temos x = 16 e y = −15. Como y e´ negativo essa
soluc¸a˜o e´ descartada. Logo a u´nica soluc¸a˜o para o nosso problema e´ x = 16 e y = 15.
Exemplo 2.6 Mostre que se n possui um divisor ı´mpar enta˜o 2n + 1 e´ composto.
Soluc¸a˜o:
Por hipo´tese podemos escrever n = t.k com t ı´mpar. Assim 2n + 1 = (2p)t + 1.
Fazendo 2p = a temos que
(2p)t = (a)t + 1 = (a + 1)(at−1 − at−2 + ...− 1).
Como a+1 e at−1−at−2+ ...−1 sa˜o maiores que 1 conclu´ımos que 2n+1 e´ composto.
3 Algoritmo da Divisa˜o
Teorema 3.1 Teorema de Euclides Dados inteiros a e b, com b 6= 0, existem inteiros q e r unjicamente determinados
por a e b, chamaods respectivamente de quociente e resto tais que a = bq + r com 0 ≤ r < |b|.
Exemplo 3.2 Prove que n3 + 2n e´ divis´ıvel por 3 qualquer que seja o natural n.
Soluc¸a˜o:
2
Pelo Algoritmo de Euclides todo nu´mero natural n se escreve na forma 3q, 3q + 1 ou
3q + 2.
• Se n = 3q enta˜o n3 + 2n = 27q3 + 6q = 3(9q3 + 2q) que e´ mu´ltiplo de 3.
• Se n = 3q+1 enta˜o n3+2n = 27q3+27q2+9q+1+6q+2 = 3(9q3+9q2+5q+1)
que e´ mu´ltiplo de 3.
• Se n = 3q+2 enta˜o n3+2n = 27q3+54q2+36q+8+6q+4 = 3(9q3+18q2+14q+4)
que e´ mu´ltiplo de 3.
4 Aritme´tica dos restos
• Periodicidade dos restos: O resto de um nu´mero na divisa˜o por n na˜o muda se adicionarmos ou subtrairmos
mu´ltiplos de n
• Restos de um divisor: Se d|b e conhecemos o resto r de a na divisa˜o por b, enta˜o o resto de a na divisa˜o por d
pode ser calculado a partir de r.
• Resto da soma: O resto de uma soma (ou diferenc¸a) pode ser calculado a partir da soma dos restos
• Resto do produto: O resto de um produto pode ser calculado a partir do produto dos restos
Exemplo 4.1 Calcule o resto de 1454 · 23678 + 12345 na divisa˜o por 7.
Temos que o resto de 1454 na divisa˜o por 7 e´ 5. O resto que 23678 deixa na divisa˜o
por 7 e´ 4. Ale´m disso, 12345 tambe´m deixa resto 4 na divisa˜o por 7 Logo, 1454 ·
23678 + 12345 deixa o mesmo resto que 5 · 4 + 4 = 24 na divisa˜o por 7. Assim, veˆ-se
facilmente que o resto procurado e´ 3.
Exemplo 4.2 Calcule o resto 777777 na divisa˜o por 10.
Primeiramente note que como 777 deixa resto 7 na divisa˜o por 10 pela propriedade
do resto do produto, o resto de 777777 na divisa˜o por 10 e´ igual ao resto de 7777 na
divisa˜o por 10. Ale´m disso, observe que o resto que um nu´mero n deixa na divisa˜o
por 10 e´ o seu d´ıgito das unidades. A seguir, analisaremos os restos que as poteˆncias
de 7 deixam na divisa˜o por 10. Note que 71 deixa resto 7 na divisa˜o por 10; 72 deixa
resto 9 na divisa˜o por 10; 73 reixa resto 3 na divisa˜o por 10; 74 deixa resto 1 na
divisa˜o por 10. Note ainda 75 deixa o mesmo resto que 71 na divisa˜o por 7; 76 deixa
o mesmo resto que 72 na divisa˜o por 7 e assim por diante. Desse modo, vemos que
o digito das unidades das poteˆncias de 7 se repetem de quatro em quatro a medida
que o expoente aumenta. Temos que 777 = 194.4 + 1 = 796 + 1. Pela periodicidade
dos d´ıgitos das unidades das potencias de quatro, vemos que 7776 deixa resto 1 na
divisa˜o por 7. Assim 777777 deixa resto 7 na divisa˜o por 7.
5 Crite´rios de Divibilidade e restos
• Divisibilidade por 2: Um nu´mero e´ divis´ıvel por dois se o seu d´ıgito das unidades e´ divis´ıvel por 2.
3
• Divisibilidade por 3: O resto que um nu´mero N deixa na divisa˜o por 3 e´ igual ao resto da divisa˜o do nu´mero
formado pela soma dos algarismos de N na divisa˜o por 3. Em particular um nu´mero e´ divis´ıvel por 3 quando a
soma dos seus algarismos o e´.
• Divisibilidade por 5: O resto que um nu´mero N deixa na divisa˜o por 5 e´ igual ao resto que o algarismo das
unidades de N deixa na divisa˜o por 5. Em particular um nu´mero e´ divis´ıvel por 5 se o seu algarismo das unidades
for 0 ou 5.
• Divisibilidade por 6: Um nu´mero e´ divis´ıvel por 6 se for divis´ıvel por 2 e 3 ao mesmo tempo.
• Divisibilidade por 9: O resto que um nu´mero N deixa na divisa˜o por 9 e´ igual ao resto da divisa˜o do nu´mero
formado pela soma dos algarismos de N na divisa˜o por 9. Em particular um nu´mero e´ divis´ıvel por 9 quando a
soma dos seus algarismos o e´.
• Divisibilidade por 11: Um nu´mero natural N e´ divis´ıvel por 11 quando a diferenc¸a entre a soma dos seus
algarismos de ordem ı´mpar e a soma dos algarismos de ordem par e´ um nu´mero mu´ltiplo de 11.
Exemplo 5.1 Qual o valor de a do nu´mero 6a45, para que seja divis´ıvel por 11. E para deixar resto 8 na divisa˜o por
11?.
Temos que 6a45 e´ mu´ltiplo de 11 se, e somente se −6+a−4+5 = a−5 e´ mu´ltiplo de
11. Logo, a = 5. Para que 6a45 deixe resto 8 na divisa˜o por 11, −6+a−4+5 = a−5
deve deixar resto 8 na divisa˜o por 11. Isso ocorre quando a = 2.
6 Problemas
• Grupo 1
1. Mostre que para todo n natural, m = n.(n+1).(2n+1)6 e´ um nu´mero inteiro.
2. Demonstre que o quadrado de um inteiro e´ da forma 8n, 8n + 1 ou 8n + 4.
3. Se N e´ o menor nu´mero inteiro positivo que multiplicados por 33 resulta em um nu´mero cujos algarismos sa˜o
todos iguais a 7. Determine a soma dos algarismos de N .
4. Qual o resto que o nu´mero 42017 deixa quando dividido por 3
5. O jogo do Resto Blanco e´ disputado da seguinte forma: Ha´ uma pilha com 153 moedas, cada jogador em seu
turno deve retirar uma quantidade de moedas n a sua escolha desde que 1 ≤ n ≤ 9. Perde aquele que retirar
a u´ltima moeda. Existe uma estrate´gia vencedora para o primeiro a jogar? E para o segundo?
6. Dois nu´meros
primos sa˜o chamados de geˆmeos se diferem por duas unidades. Prove que entre dois primos
geˆmeos, maiores ou iguais a 5, existe um mu´ltiplo de 6.
• Grupo 2
1. Qual e´ o resto que o nu´mero 1004× 1005× 1006 deixa quando dividido por 7?
2. Mostre que, se um nu´mero inteiro e´, ao mesmo tempo, um cubo e um quadrado, enta˜o ele e´ da forma 5n,
5n + 1, 5n + 4.
3. Mostre que o nu´mero 220 − 254 e´ composto.
4. Encontre todos os pares de inteiros positivos a, b tais que 79 = ab + 2a + 3b.
4
5. Mostre que 15 e´ divisor de todo nu´mero que e´ produto de cincos nu´meros ı´mpares consecutivos.
6. Qual e´ o resto de 5131 + 7131 + 9131 + 15131 na divisa˜o por 12
• Grupo 3
1. Ache o menor mu´ltiplo de 5 que deixa resto 2 quando dividido por 3 e por 4.
2. 2) Mostre, para todo a ∈ Z , que
(a) 2 divide a2 − a
(b) 3 divide a2 − a
3. Os nu´meros a e b satisfazem a equac¸a˜o 56a = 65b. Prove que a + b e´ um nu´mero composto.
4. Quantos dos nu´meros 2, 3, 5, 7 e 11 sa˜o divisores de 3714 − 414?
5. E´ correto afirmar que o nu´mero 52011 + 2.112011 e´ mu´ltiplo de:
(a) 13
(b) 11
(c) 7
(d) 5
(e) 3
6. Mostre que, para cada nu´mero natural existe um mu´ltiplo de diferente de zero escrito exclusivamente com os
algarismos 0 e 7.
• Grupo 4
1. Dois nu´meros positivos sa˜o tais que a divisa˜o do primeiro deles por 7 deixa resto 6, enquanto a divisa˜o do
segundo, tambe´m por 7, deixa resto 5. Somando os dois nu´meros e dividindo o resultado por 7, o resto sera´:
(a) 1
(b) 2
(c) 3
(d) 4
(e) 5
2. A expressa˜o 52678 · 24569 + 398075, ao ser dividida por 5, deixa que resto?
3. Os inteiros positivos n e m satisfazem 15m = 20n. Enta˜o e´ poss´ıvel afirmar, com certeza, que nm e´ mu´ltiplo
de:
(a) 5
(b) 10
(c) 12
(d) 15
(e) 20
4. Encontre o valor de n na seguinte expressa˜o:
6 · 12 · 18 · · · 300
(2 · 6 · 10 · · · 98)(˙4 · 8 · 12 · · · 100)
5. Mostre que entre 4 inteiros quaisquer existem 2 cuja soma ou diferenc¸a e´ um mu´ltiplo de 4.
5
6. Tom multiplicou dois nu´meros de dois algarismos no quadro negro. Depois substituiu os algarismos por letras
(algarismos diferentes foram substitu´ıdos por letras diferentes e algarismos iguais foram substitu´ıdos pela
mesma letra). Ele obteve AB · CD = EEFF . Prove que ele errou em algum lugar.
• Grupo 5
1. Encontre o resto que 2013 · 2014 · 2015 · 2016 + 20172 deixa quando e´ dividido por 7.
2. O resto da divisa˜o do inteiro N por 20 e´ 8. Qual o resto da divisa˜o de N por 5?
3. Um nu´mero natural termina com o algarismo 2.Se movermos esse u´ltimo algarismo 2 para o in´ıcio do nu´mero,
enta˜o o nu´mero tera´ seu valor dobrado. Encontre o menor nu´mero com essa propriedade.
4. Prove que se n e´ ı´mpar, enta˜o n3 − n e´ divis´ıvel por 24 .
5. Determine TODOS os valores poss´ıveis para os algarismos x, y, z, t de modo que os nu´meros abaixo, representados
na base 10, tenha a propriedade mencionada:
(a) 3x90586y e´ divis´ıvel por 60
(b) 72z41t e´ divis´ıvel por 99
6. Quantos sa˜o os pares (x, y) de inteiros positivos tais que x2 − y2 = 22010?
(a) 1000
(b) 1001
(c) 1002
(d) 1003
(e) 1004
6
	Divisibilidade
	Numeros primos e compostos
	Algoritmo da Divisão
	Aritmética dos restos
	Critérios de Divibilidade e restos
	Problemas