Nivel_2_TN_Aula_congruencias Critérios de divisibilidade

Prévia do material em texto

Teoria de Números
Notas de Aula
Nível 2 - UFPR
Eduardo C. Araujo e
Rondivânia M.
Ferreira
AULA 05 - CONGRUÊNCIAS I
Algoritmo da divisão. Para quaisquer inteiros a e b, com a 6= 0, existe um único par de
inteiros (q, r) tais que b = aq + r, 0 ≤ r < |a|.
Teorema dos restos. Se b1 e b2 deixam restos r1 e r2 na divisão por a, respetivamente, en-
tão:
b1 + b2 deixa o mesmo resto que r1 + r2 na divisão por a
b1b2 deixa o mesmo resto que r1r2 na divisão por a.
Definição 1. Dizemos que os inteiros a e b são congruentes módulo m se eles deixam o mesmo
resto quando divididos por m. Denotaremos isso por a ≡ b (mod m).
Por exemplo, 7 ≡ 2 (mod 5), 9 ≡ 3 (mod 6), 37 ≡ 7 (mod 10) mas 5 6= 3 (mod 4). Veja
que a ≡ b (mod m) ⇔ (se e somente se) m|a− b.
Quando temos um ⇔ , temos uma relação de equivalência, sendo os seus dois sentidos são vá-
lidos.
Portanto, temos que a (ida) do teorema é:
a ≡ b (mod m) ⇒ (implica que) m|a− b.
Uma ideia da demonstração pode ser dada da seguinte maneira:
Pelo algoritmo da divisão podemos escrever: a = mq1 + r1
b = mq2 + r2
Como a ≡ b (mod m), temos que r1 = r2.
Logo,
a− b = mq1 + r1 − (mq2 + r2)
= mq1 + r1 −mq2 − r2
= mq1 −mq2
= m(q1 − q2)
Sendo assim, pelo algoritmo da divisão podemos escrever:
m|a− b = m(q1 − q2) + 0
Nesse caso, como r = 0, temos que a − b é divisível por m. Portanto, m|a − b. Logo, a ida do
teorema está demonstrada.
Nesse sentido, agora devemos demonstrar a volta, que é: m|a− b⇒ a ≡ b (mod m).
Pelo algoritmo da divisão podemos escrever:
a = mq1 + r1
b = mq2 + r2
Nesse caso, a− b = mq1 + r1 −mq2 − r2
= m(q1 − q2) + r1 − r2
1
Se esse valor é divisível por m, temos que m|m(q1 − q2), o que é verdadeiro e que m|r1 − r2. Pelo
algoritmo da divisão temos que 0 ≤ r1 − r2 < |m|. Como, r1 − r2 é divisível por m, a única opção
que respeita o algoritmo da divisão é: r1 − r2 = 0. Logo, r1 = r2. Portanto, como os restos de a e
b são iguais, podemos dizer que a ≡ b (mod m). Logo, está demonstrada a volta do teorema.
Teorema 2..Se a ≡ b (mod m) e c ≡ d (mod m), então:
Podemos escrever a, b, c e d pelo algoritmo da divisão, como:
a = mq1 + r1
b = mq2 + r1
c = mq3 + r2
d = mq4 + r2
Agora que escrevemos os valores pelo algoritmo da divisão podemos dar uma ideia da demonstra-
ção das seguintes propriedades:
i) a+ c ≡ b+ d (mod m)
Aplicando a escrita do algoritmo da divisão podemos escrever:
mq1 + r1 +mq3 + r2 ≡ mq2 + r1 +mq4 + r2 (mod m)
= m(q1 + q3) + (r1 + r2) ≡ m(q2 + q4) + (r1 + r2) (mod m)
Como, os restos de a+ c e b+ d são iguais (r1 + r2) eles são congruentes mod m.
ii) a− c ≡ b− d (mod m)
Aplicando a escrita do algoritmo da divisão podemos escrever:
mq1 + r1 −mq3 − r2 ≡ mq2 + r1 −mq4 − r2 (mod m)
= m(q1 − q3) + (r1 − r2) ≡ m(q2 − q4) + (r1 − r2) (mod m)
Como, os restos de a+ c e b+ d são iguais (r1 − r2) eles são congruentes mod m.
iii) ka ≡ kb (mod m) para todo k pertencente aos inteiros.
k(mq1 + r1) ≡ k(mq2 + r1)
kmq1 + kr1 ≡ kmq2 + kr1
Como os restos de ka e kb são iguais (kr1) temos que ka ≡ kb (mod m).
iv) ac ≡ bd (mod m)
Aplicando a escrita do algoritmo da divisão podemos escrever:
(mq1 + r1)(mq3 + r2) ≡ (mq2 + r1)(mq4 + r2)
m2q1q3 +mq1r2 +mq3r1 + r1r2 ≡ m2q2q4 +mq4r1 + r1r2
Nesse caso, como ac e bd deixam o mesmo resto (r1r2), temos que ac ≡ bd (mod m).
v) ak ≡ bk (mod m) para todo k pertencente aos naturais.
Com base na propriedade iv)ac ≡ bd (mod m), temos que se a ≡ b (mod m) então a · a ≡
b · b (mod m), da mesma maneira que usando novamente a propriedade iv), temos que a · a · a ≡
b · b · b (mod m). Por essa razão temos que a multiplicação de a e b n vezes mantêm a congruência.
Logo, podemos dizer que ak ≡ bk (mod m).
Algumas aplicações:
Podemos usar o estudos das congruências para estabelecer critérios de divisibilidades entre os nú-
meros.
2
Um critério de divisibilidade por 6
Veja que:
10 ≡ 4 (mod 6)
102 ≡ 42 ≡ 4 (mod 6)
103 ≡ 102 · 10 ≡ 4 · 4 (mod 6)
Logo, 102 ≡ 4 (mod 6)
Portanto, seja n um número natural escrito no sistema decimal como nr...n1n0, ele pode ser escrito
como:
n = n0 + 10n1 + 10
2n2 + ...+ 10
rnr ≡ n0 + 4n1 + 4n2 + ...4nr (mod 6)
Logo, o resto da divisão de n por 6 equivale ao resto da divisão de n0 + 4n1 + 4n2 + ...4nr por 6.
Portanto, provamos que:
Um número n = nr...n1n0 é divisível por 6 se e somente se n0 + 4n1 + 4n2 + ...4nr é divisível
por 6.
Exemplo:Calcule o resto de 3215529 na divisão por 6:
Solucão: Utilizando o critério estabelecido acima, temos que o número acima tem o mesmo resto
na divisão por 6 que o número
9 + 4 · (2 + 5 + 5 + 1 + 2 + 3) = 9 + 4 · 18 ≡ 3 (mod 6)
Logo, 3215529 deixa resto 3 na divisão por 6.
Um critério de divisibilidade por 7,11 e 13
Observe que 7 · 11 · 13 = 1001. Portanto,
1000 ≡ −1(mod7) e 1000 ≡ −1(mod11) e 1000 ≡ −1 (mod 13).
Logo, módulo 7,11, e 13, temos que:
103 ≡ 1,
106 ≡ (−1)2 ≡ 1,
109 ≡ (−1)3 ≡ −1,
1012 ≡ (−1)4 ≡ 1,
etc.
Escrevendo um número n na representação decimal como nr...n2n1n0, temos, módulo 7, 11 ou
13, que
n = n2n1n0 + n5n4n3 · 103 + n8n7n6 · 106 + .... ≡ n2n1n0 − n5n4n3 + n8n7n6 − ..
Logo, o resto da divisão de n por 7,11 ou 13 é igual ao resto da divisão de n2n1n0 − n5n4n3 +
n8n7n6 − ... por 7, 11 ou 13, respectivamente.
Sendo assim, obtemos o seguinte critério de divisibilidade por 7, 11 ou 13 se, e somente se, o
número n2n1n0 − n5n4n3 + n8n7n6 − ... é divisível por 7,11 ou 13, respectivamente.
3
Exemplo. Encontre o resto da divisão por 7, 11 e 13 do número 3215529.
Aplicando o critério de multiplicidade enunciado acima, temos:
529 − 215 + 3 = 317| Como, 317 deixa resto 2 na divisão por 7, 9 na divisão por 11 e 5 na
divisão por 13, temos que o resto de 3215529 na divisão por 7 é 2, na divisão por 11 é 9 e na
divisão por 13 é 5.
Exercícios
Questão 1. Calcule o resto de 4100 por 3.
Questão 2.Calcule o resto de 4100 por 7.
Questão 3.Prove que p2 − 1 é divisível por 24 se p é um primo maior que 3.
Questão 4.Prove que n2 + 1 não é divisível por 3 qualquer que seja o inteiro n.
Questão 5. Verifique se são verdadeiras ou falsas as seguintes afirmações:
i)35 ≡ 24 (mod 4).
ii)72 ≡ 32 (mod 5).
iii)78 ≡ 33 (mod 9).
Questão 6.Determine o resto de 220 − 1 na divisão por 41.
Questão 7.Qual o resto na divisão de 270 + 370 por 13.
Questão 8. Se n é ímpar prove que 7|22n+1 + 3n+2.
Questão 9.Escreva uma única congruência que é equivalente ao par de congruências x ≡ 1 (mod 4)
e x ≡ 2 (mod 3).
Questão 10.Sejam a um número inteiro qualquer e m um inteiro maior que 1. Suponha que
r seja um número tal que 0 ≤ r < m e a ≡ r(modm).Mostre que r é o resto da divisão a por m.
Dica: Utilize a unicidade da escrita no Algoritmo da Divisão.
Questão 11.Os 2.019 armários dos 2.019 alunos de uma escola são numerados com os quadrados
dos 2.019 primeiros naturais positivos, ou seja, o primeiro armário tem o número 12 = 1, o segundo
armário tem o número 22 = 4,terceiro armário tem o número 32 = 9, e assim até o último armário
que tem o número 20192 = 4076361
a) Quantos algarismos foram utilizados para pintar os cem primeiros armários?
b) Somando todos os números dos armários, qual o algarismo das unidades deste resultado?
Questão 12.
a) Qual é o número associado à palavra CABIDE?
4
b) Escreva uma palavra com quatro letras cujo número associado seja 455.
c) Explique por que não existe uma palavra cujo número associado seja 2013.
5
Soluções
Solução 1. Como 4 ≡ 1 (mod 3), temos 4100 ≡ 1100 = 1 (mod 3). Logo, 4100 deixa resto 1
na divisão por 3.
Solução 2. Você deve ter percebido que encontrar relações do tipo a ≡ ±1 (mod m) podem
simplificar bastante o cálculo de ak (mod m).
Procuremos alguma relação como essa para 4 e 7. Veja que: 40 ≡ 1 (mod 7) ,41 ≡ 4 (mod 7),
42 ≡ 2 (mod 7), 43 ≡ 1 (mod 7). Assim, 499 = (43)33 ≡ 133 = 1 (mod 7)
Como 43 ≡ 1 (mod 7), os restos das potências de 4 na divisão por 7 se repetem periodicamente
de 3 em 3 pois 43k+r ≡ 43k×4r(mod7).Sendo assim, como 100 deixa resto 1 na divisão por 4, temos
que: 4100 ≡ 499 · 4 (mod 7). Como, 499 ≡ 1 (mod 7),concluímos que 4100 ≡ 1 · 4 (mod 7). Logo, o
resto da divisão de 4100 por 7 é 4.
Solução 3.Se p é um primo maior que 3, p ≡ ±1(mod3) e p ≡ 1(mod2). Daí , p2 ≡ 1(mod3).
Além disso, se p = 2k + 1, segue que p2 = 4k(k + 1) + 1 ≡ 1(mod8) pois k(k + 1) é par. Como
mdc(8, 3) = 1 e ambos dividem p2 − 1 , segue que 24|p2 − 1.
Solução 4. Analise os restos de n na divisão por 3. Se r = 0 então n ≡ 0(mod3), logo
n2 ≡ 0(modm). Sendo assim, n2+1 deixa resto 1 na divisão por 3. Logo não é divisível. O mesmo
vale para r = 1 e r = 2. (Analise o resto de n2+1 quando os restos de n na divisão por 3 são 0 e 1).
Solução 5. i)35 - 24 = 11, como 11 não é divisível por 4 não há congruência, logo, i) é falsa.
ii)72 - 32 = 40, como 40 é divisível por 5, temos uma congruência. Logo, ii) Verdadeira
iii)78 - 33 = 45, como 45 é divisível por 9, temos uma congruência. Logo iii) é verdadeira.
Solução 6. Veja que
25 ≡ 32 ≡ −9(mod41)
210 ≡ 81 ≡ −1(mod41) 220 ≡ 1(mod41).
Assim, os resto procurado é zero.
Solução 7.Inicialmente é interessante buscarmos alguma relação entre os números envolvidos
no problema. Como 13 = 4 + 9, podemos escrever:
9 ≡ −4(mod13)
935 ≡ (−4)35(mod13)
370 + 270 ≡ 0(mod13)
Portanto, o resto é zero
Solução 8. Veja que:
32 ≡ 2(mod7)
Além disso,
3 ≡ −4(mod7), elevando ambos os lados a n:
3n ≡ −4n(mod7)
3n ≡ (−22)n(mod7)
3n ≡ −22n(mod7)
Como podemos multiplicar congruências e como n é ímpar, o valor será sempre negativo, logo:
3n · 32 ≡ −22n · 21(mod7)
6
3n+2 ≡ −22n+1(mod7)
Como temos uma congruência pela sua definição temos: 3n+2− (−22n+1) = 3n+2+22n+1 é divisível
por 7
Solução 9.x ≡ 5(mod12)
Solução 11. a) Vamos dividir em grupos pela quantidade de algarismos:
I) 1 algarismo: 3 armários ( 12, 22, 32);
II) 2 algarismos: 9 - 3 = 6 armários (42 a 92);
III) 3 algarismos: 31 - 9 = 22 armários (102 a 312);
IV) 4 algarismos: 99-31 = 68 armários (322 a 992);
V) algarismos : apenas o armário 1002.
Portanto, foram pintados 3+2 ·6+3 ·22+4 ·68+5 ·1 = 358 algarismos nos cem primeiros armários.
b)Solução: O algarismo das unidades dos 10 primeiros quadrados desses armários são 1, 4, 9,
6, 5, 6, 9, 4, 1, 0. Essa sequência de algarismos repete-se de 10 em 10. Como a soma de uma dessas
sequências termina em 5 e são, até 20202 (vamos considerar o 20202 para termos uma quantidade
inteira de sequências e como seu algarismo das unidades é zero, não altera o resultado) 202 somas
que terminam em 5, que somadas, o resultado termina em 0.
Solução 12. a)Temos da tabela C → 3, A → 1, B → 2, I → 9, D → 4 e E → 1. O nú-
mero da palavra CABIDE é então 3× 1× 2× 9× 4× 5 = 1080.
b)A decomposição de 455 em fatores primos é 455 = 5 × 7 × 13 ; as letras correspondentes a
5, 7 e 13 são, respectivamente, E, G e M. Como A corresponde a 1, qualquer palavra formada
pelas letras A, E, G e M é uma solução do problema; por exemplo, GEMA.
c)A fatoração de 2013 em fatores primos é 2013 = 3 × 11 times61. Isso mostra que em qual-
quer produto cujo resultado seja 2013 aparece um fator que é múltiplo de 61. Como o maior
número associado a uma letra é 26, concluímos que não é possível escrever uma palavra cujo nú-
mero associado seja 2013.
7
AULA 06 - CONGRUÊNCIAS II
Propriedade vi) Se ka ≡ kb (mod m) e mdc(m, k) = 1, então a ≡ b (mod m)
Teorema de Fermat.Seja p um primo. Se p não divide a então
ap−1 ≡ 1 (mod p)
Além disso, para todo inteiro a, ap ≡ a (mod p).
Exemplo 1. Encontre os restos da divisão de 224 na divisão por: a)5 b)7 c)15
Solução. a)Pelo Teorema de Fermat,
24 ≡ 1 (mod 5)
Pela propriedade v) elevando ambos os lados a 6, temos:
224 ≡ 1 (mod 5)
Logo, o resto é 1.
b) a)Pelo Teorema de Fermat,
26 ≡ 1 (mod 7)
Pela propriedade v) elevando ambos os lados a 4, temos:
224 ≡ 1 (mod 7)
Logo, o resto é 1.
c) Como 15 = 5 · 3 aplicando o Teorema de Fermat para 5 e 3 chegamos a:
24 ≡ 1 (mod 5)
Pela propriedade v) elevando ambos os lados a 6, temos:
224 ≡ 1 (mod 5)
e
22 ≡ 1 (mod 3)
Pela propriedade v) elevando ambos os lados a 12, temos:
224 ≡ 1 (mod 3)
Logo, como 224 deixa resto 1 na divisão por 3 e por 5, sabendo que mdc(5,3) = 1, podemos concluir
que 224 deixa resto 1 na divisão por 15.
Exemplo 2. Mostre que se p é primo e a2 ≡ b2 (mod p), então a ≡ ±b (mod p)
Solução. Se a2 ≡ b2 (mod p), então, p|a2 − b2 como a2 − b2 = (a+ b)(a− b) temos que p|a− b ou
8
p|a+ b, logo a ≡ ±b (mod p)
Exemplo 3. Mostre que não existe m tal que m2 + 1 ≡ 0 (mod 7)
Solução. Substituindo no lugar de m os restos possíveis na divisão por 7, temos as seguintes
possibilidades:
02 + 1 ≡ 1 (mod 7)
12 + 1 ≡ 2 (mod 7)
22 + 1 ≡ 5 (mod 7)
32 + 1 ≡ 10 ≡ 3 (mod 7)
42 + 1 ≡ 17 ≡ 3 (mod 7)
52 + 1 ≡ 26 ≡ 5 (mod 7)
62 + 1 ≡ 37 ≡ 2 (mod 7)
Sendo assim, para todos os casos possíveis m2 + 1 não é divisível por 7.
Exemplo 4. Mostre que n7 ≡ n (mod 42), ∀n ∈ N
Solução. Fatorando o 42 em fatores primos, temos 42 = 2 · 3 · 7. Aplicando o Teorema de Fermat
para cada um deles,
n7 ≡ n (mod 7)
Pelo teorema, n3 ≡ n (mod 7), logo,
n7 ≡ n · n3 · n3 ≡ n3 ≡ n (mod 3)
Pelo teorema, ainda temos que n2 ≡ n (mod 2, logo,
n7 ≡ n · n2 · n2 · n2 ≡ n2 · n2 ≡ n2 ≡ n (mod 7)
Como 2, 3 e 7 são primos entre si, n7 ≡ n (mod 2 · 3 · 7 = 42)
Questão 1. Encontre os restos das divisões de:
a)3003000 − 1 por 1001
b)7120 − 1 por 143
Questão 2. Prove que se n é ímpar, então n5 ≡ n (mod 240).
Questão 3. Prove que 2015 − 1 é divisível por 11 · 31
Questão 4. Sejam p e q primos distintos. Mostre que
i) (a+ b)p ≡ ap + bp (mod p)
ii)pq + qp ≡ p+ q (mod pq)
Questão 5. Se n não é múltiplo de 7, mostre que n3 ≡ ±1 (mod 7).
Questão 6. Prove que p2 − q2 é divisível por 24 se p e q são primos maiores que 3.
9
Questão 7.Seja n > 6 um inteiro positivo tal que n−1 e n+1 são primos. Mostre que n2(n2+16)
é divisível por 720.
Primos gêmeos: são os números primos cuja diferença equivale a 2, eles são expressos da forma
(6k -1, 6k+1)
Questão 8.(Balcânia 2003)Existe um conjunto B de 4004 inteiros tal que, para cada subcon-
junto A de B com 2003 elementos, a soma dos elementos em A não é divisível por 2003?
Questão 9. Prove que se p é primo então ap ≡ bp (mod)⇒ ap ≡ bp (mod p2)
Questão 10. Seja p um primo ímpar maior que 5. Encontre o resto de 111..11 (p-1 uns) na
divisão por p.
10
Soluções
1a). Perceba que 1001 = 7·11·13 e que 7 1, 11 1 e 13 1 dividem 3000. Como 7,11 e 13 são números
primos, todos realtivamente primos com 300, segue em virtude do Teorema de Fermat, que esses
primos dividem 3003000− 1. Como esses primos são distintos vale que 1001 = 7 · 11 · 13|3003000− 1.
1b). Perceba que 143 = 11 · 13 e que 11 - 1 e 13 - 1 dividem 120. Como 11 e 13 são núme-
ros primos, ambos realtivamente primos com 7, segue em virtude do Teorema de Fermat, que esses
primos dividem 7120 − 1. Como esses primos são distintos vale que 143 = 11 · 13|7120 − 1.
2. Perceba que 240 = 24 · 3 · 5. Daí pelo Toerema de Fermat, segue que:
n5 equiv (mod 5) e
n5 ≡ n32 (mod 3)
≡ n · n2 (mod 3)n
≡ n (mod 3)
Como mdc(3, 5) = 1, segue que 15 = 5 · 3|n5 − n. Como n é ímpar podemos escrever n = 2k + 1.
Daí,
n5 − n = n(n4 − 1) = n(n2 − 1)(n2 + 1) = 4k(k + 1)(n2 + 1)
Como 2|k(k + 1), segue que 8|4k(k + 1). Além disso, como n2 + 1 é par, podemos afirmar que
16 = 2 · 8|4k(k + 1)(n2 + 1)
Portanto, como mdc(16, 15) = 1, segue que
240 = 15 · 16|n5 − n
3. Resolução análoga a da questão 1.
4 i). Pelo Teorema de Fermat,
(a+ b)p ≡ a+ b ≡ ap + bp (mod p)
4 ii). Pelo Teorema de Fermat,
pq + qp ≡ 0 + q ≡ p+ q (mod p)
pq + qp ≡ p+ 0 ≡ p+ q(mod q)
Como p e q são primos distintos, segue que mdc(p, q) = 1 e daí
pq + qp ≡ 0(mod pq)
5. Analise os restos na divisão por 7.
6. Dica: Tente usar o resultado da questão 3 da aula 05.
11
7. (Extraído da Olímpiada Britânica) Veja que n é da forma 6k, pois n - 1 e n + 1 são pri-
mos maiores que 3, portanto da forma 6k-1 e 6k +1 , respectivamente. Logo,
n2(n2 + 16) = 144(9k4 + 4k2)
Resta provar que 9k4 + 4k2 é um múltiplo de 5. Vamos analisar a igualdade acima módulo 5.
i) Se k ≡ 0, 2 ou 3 (mod 5), temos 9k4 + 4k2 ≡ 0 (mod 5)
ii) Se k ≡ 1 (mod 5) ⇒ n ≡ 1 (mod 5), temos n − 1 ≡ 0 (mod 5), um absurdo, pois n-1 é
primo e n>6.
iii) Se k ≡ 4 (mod 5)⇒ n ≡ 4 (mod5), temos n+ 1 ≡ 0 (mod 5), novamente um absurdo.
Isso conclui a demonstração.
8. Sim. Um exemplo de tal conjunto é a união de um conjunto de 2002 inteiros positivos que
deixem resto 0 com outro conjunto composto por 2002 inteiros que deixem resto 1 por 2003.
9. Pelo Teorema de Fermat, a ≡ ap ≡ bp ≡ b (mod p)
Como a ≡ b (mod p), temos que a− b ≡ 0 (mod p)
ap − bp = (a− b)(ap−1 + ap−2b+ ..+ abp−2 + bp−1)
ap−1 + ap−2b+ ..+ abp−2 + bp−1 ≡ ap−1 + ap−1 + ...+ ap−1 ≡ pap−1 ≡ 0 (mod p)
10. Veja que:
111...11 =
999...99
9
=
10p−1 − 1
9
Pelo Teorema de Fermat, o numerador 10p−1− 1 é divisível por p, pois mdc(5, p) = 1. Além disso,
usando que p 6= 3, segue que 10p−1−1
9
também é múltiplo de p.
12