Exercícios resolvidos

Prévia do material em texto

Exerćıcios Resolvidos de Teoria dos Números
Vinicius Cabral da Silva
1) Prove que n3 + 5n é diviśıvel 6 para todo n ∈ N.
Solução:
Provaremos por indução sobre n.
Temos que 6|13 + 5 · (1) = 6.
Suponha que 6|(k3 + 5k) para algum k ∈ N.
Logo, (k + 1)3 + 5(k + 1) = k3 + 3k2 + 3k + 1 + 5k + 5 = k3 + 5k + 3k2 + 3k + 6 =
k3 + 5k + 3(k2 + k + 2).
Por hipótese de indução 6|(k3 + 5k). Temos 3(k2 + k+ 2) = 3(k2 + k) + 6 = 3k(k+ 1) + 6,
logo k ou k + 1 é par, donde 3k(k + 1) é múltiplo de 6.
Portanto, 6|(k3 + 5k) + 3k(k + 1) + 6 = (k3 + 5k) + 3(k2 + k + 2) = (k + 1)3 + 5(k + 1).
2) Conjecture uma fórmula para a soma dos primeiros n números naturais ı́mpares 1 +
3 + 5 + · · ·+ (2n− 1), e prove sua fórmula usando indução matemática.
Solução:
1 + 3 + 5 + · · ·+ (2n− 1)
1 + 3 = 4 = 22, 1 + 3 + 5 = 9 = 32, 1 + 3 + 5 + 7 = 16 = 42, · · ·
Conjectura-se que 1 + 3 + 5 + · · ·+ (2n− 1) = n2.
Provaremos por indução sobre n.
Para n = 1, temos 1 = 12.
Suponha a conjectura verdadeira para n = k.
Logo, 1 + 3 + 5 + · · ·+ (2k − 1) + (2k + 1) = k2 + (2k + 1) = (k + 1)2.
Donde obtemos o resultado válido para todo n ∈ N.
3) Prove que se p é um número primo e p divide o produto de dois números inteiros a e
b, então p|a ou p|b.
Solução:
Se p|a não há o que demonstrar. Se p - a, então mdc(p, a) = 1, logo existem x, y ∈ Z
tal que px + ay = 1. Multiplicando os dois lados da equação por b, obtemos pbx + aby = b.
Portanto, p|ab⇒ p|aby ⇒ p|pbx+ aby = b.
4) Mostre que existem infinitos números primos.
Solução:
Se houvessem um número finito de números primos p1, p2, · · · , pn, nenhum dos pi, 1 ≤ i ≤
n iria dividir o número p1p2 · · · pn + 1, o que contradiz o teorema fundamental da aritmética.
1
5) Calcule o resto da divisão de 42012 por 3.
Solução:
Temos que: 42012−1 = (4−1)(42011+42010+ · · ·+4+1) = 3(42011+42010+ · · ·+4+1) = 3q
onde q = (42011 + 42010 + · · · + 4 + 1). Logo, 42012 = 3q + 1 e, portanto, deixa resto 1 na
divisão por 3.
6) Teorema dos restos: Prove que se b1 e b2 deixam restos r1 e r2 na divisão por a,
respectivamente, então b1 + b2 deixa o mesmo resto que r1 + r2 na divisão por a e b1b2 deixa
o mesmo resto que r1r2 na divisão por a.
Solução:
Temos que b1 = q1a+r1, 0 ≤ r1 < a e b2 = q2a+r2, 0 ≤ r2 < a. Seja r1+r2 = qa+r, 0 ≤
r < a, logo b1 + b2 = q1a+ q2a+ (r1 + r2) = (q1 + q2)a+ (qa+ r) = (q1 + q2 + q)a+ r.
Considere agora r1r2 = q
′a + r′, 0 ≤ r′ < a. Então b1b2 = (q1a + r1)(q2a + r2) =
q1q2a
2 + q1r2a+ q2r1a+ r1r2 = (q1q2a+ q1r2 + q2r1)a+ r1r2 = (q1q2a+ q1r2 + q2r1 + q
′)a+ r′.
7) Qual é o resto que o número 1002 · 1003 · 1004 deixa quando dividido por 7?
Solução:
Temos que: 1002 = 7 · (143) + 1, 1003 = 7 · (143) + 2, 1004 = 7 · (143) + 3.
Portanto, o número 1002 · 1003 · 1004 deixa resto 1 · 2 · 3 = 6 na divisão por 7.
8) Qual é o resto que o número 45000 deixa quando dividido por 3?
Solução:
45000 = 4 · 4 · 4 · · · 4︸ ︷︷ ︸
5000 vezes
e como 4 deixa resto 1 na divisão por 3, 45000 deixa resto 1·1·· · · 1 = 1
na divisão por 3.
9) Qual é o resto que o número 22k+1, k ∈ N deixa quando dividido por 3?
Solução:
Podemos escrever 22k+1 = 22k ·2 = (22)k ·2 = 4k ·2 que deixa o mesmo resto que 1k ·2 = 2
na divisão por 3. Portanto, qualquer potência de 2 com expoênte ı́mpar, quando dividido
por 3 deixa resto 2.
10) Qual o resto da divisão de n3 + 2n por 3?
Solução:
Temos que n deixa resto 0, 1 ou 2 na divisão por 3.
Se n deixa resto 0, então n3 + 2n deixa resto 03 + 2(0) = 0 na divisão por 3; se n deixa
resto 1, então n3 + 2n deixa resto 13 + 2(1) = 3, ou seja 0 na divisão por 3; se n deixa resto
2, então n3 + 2n deixa resto 23 + 2(2) = 12 que é multiplo de 3. Portanto, em qualquer caso,
2
n3 + 2n deixa resto 0 na divisão por 3.
Outro modo de resolver:
n3 + 2n = n3 − n+ 3n = n(n2 − 1) + 3n = n(n− 1)(n+ 1) + 3n.
Como n − 1, n e n + 1 são 3 números consecutivos, um deles é múltiplo de 3, logo
n(n− 1)(n+ 1) + 3n é múltiplo de 3, isto é, 3|n(n− 1)(n+ 1) + 3n = n3 + 2n.
Portanto, n3 + 2n deixa resto zero na divisão por 3.
11) Cada um dos números a, b, c, d é diviśıvel por ab− cd que é um inteiro positivo. Prove
que ab− cd = 1.
Solução: Podemos escrever a = (ab−cd)x, b = (ab−cd)y, c = (ab−cd)z e d = (ab−cd)w
com x, y, z, w ∈ Z. Temos (ab − cd) = (ab − cd)x(ab − cd)y − (ab − cd)z(ab − cd)w =
(ab− cd)2xy− (ab− cd)2zw = (ab− cd)2(xy− zw)⇒ 1 = (ab− cd)(xy− zw). Como ab− cd
é um inteiro positivo, então só pode ocorrer ab− cd = 1.
12) Encontre todos os naturais a e b tais que a|b+ 1 e b|a+ 1.
Solução:
a e b são inteiros positivos. Se a = b, então a|b+ 1 = a+ 1⇒ a|(a+ 1)− a = 1⇒ a = 1
e b = 1 é solução. Caso contrário, se a 6= b, vamos supor sem perda de generalidade que
a < b. De b|a + 1, como a + 1 > 0, b = |b| ≤ |a + 1| = a + 1 < b + 1, logo a + 1 = b, mas
a|b+ 1 = a+ 2, donde a|(a+ 2)− a = 2⇒ a = 1 ou a = 2. Isso nos dá as soluções:
(a, b) = (1, 1), (1, 2), (2, 3), (2, 1), (3, 2).
13) Critério de divisibilidade por 7 : 10a + b é múltiplo de 7 se, e somente se, a − 2b é
múltiplo de 7.
Solução:
10a+ b = 7(a+ b) + 3(a− 2b)⇔ 7|10a+ b− 7(a+ b) = 3(a− 2b)⇔ 7|a− 2b.
14) Mostre que para todo n ∈ N,
a) 9|10n − 1;
b) 8|32n − 1;
c) 53|74n − 24n.
Solução: Provaremos os três itens por indução sobre n.
a) Temos que 9|101 − 1 = 9, portanto vale para n = 1. Suponha que vale para n, então:
10n+1 − 1 = 10 · 10n − 1 + 10n − 10n = 9 · 10n + 10n − 1, como 9|9 · 10n e por hipótese de
indução, 9|10n−1, então 9|(9·10n)+(10n−1) = 10n+1−1. Portanto, vale para todo n natural.
b) Para n = 1, temos que 32·1−1 = 8 e 8|8. Suponha que vale para n e analisaremos para
n+ 1.
3
32(n+1)−1 = 32n+2−1 = 32n ·32−1 = 9 ·32n−1+32n−32n = 8 ·32n+32n−1, como 8|8 ·32n
e por hipótese de indução, 8|32n− 1, então 8|(8 · 32n) + (32n− 1) = 32(n+1)− 1. Portanto, vale
para todo n natural.
c) Para n = 1, 74−24 = (72)2− (22)2 = 492−42. Pela proposição 3.1.9 (livro do Abramo)
que diz que: se a ≥ b > 0 com a, b ∈ N, então a+b|a2n−b2n, temos que 53 = 49+4|492−42 =
74−24. Portanto vale para n = 1. Agora suponha que vale para n e verificaremos para n+1.
74(n+1)−24(n+1) = 74n+4−24n+4 = 74n ·74−24n ·24 = 74n ·74−24n ·24 + 74n ·24−74n ·24 =
74n(74 − 24) + 24(74n − 24n). Como 53|74 − 24 e por hipótese de indução, 53|74n − 24n, então
53|(74 − 24) + (74n − 24n) o que implica que 53 divide qualquer combinação linear de 74 − 24
e 74n − 24n. Assim, 53|74n(74 − 24) + 24(74n − 24n) = 74(n+1) − 24(n+1). Portanto, vale para
todo n ∈ N.
15) Mostre que 17|267 + 334.
Solução:
267 + 334 = 266 · 2 + (32)17 = (23)22 · 2 + (32)17 = 822 · 2 + 917 = 817 · 85 · 2 + 917.
Pela proposição 3.1.8 (livro do Abramo) que diz que: se a + b 6= 0 com a, b ∈ N, então
a+ b|a2n+1 + b2n+1, temos que 17 = 8 + 9|82·8+1 + 92·8+1 = 817 + 917. Como 85 · 2 = (23)5 · 2 =
216, ϕ(17) = 16 e mdc(2, 17) = 1, então pelo teorema de Euler-Fermat, 2ϕ(17) = 216 ≡
1(mod 17), logo 17|817 · 216 + 917 = 817 · 85 · 2 + 917 = 267 + 334.
16) Para quais valores de a ∈ N, a− 2|a3 + 4 ?
Solução:
a3+4 = (a3−8)+12 = (a−2)(a2+2a+4)+12⇒ a−2|a3+4−(a−2)(a2+2a+4) = 12⇒
a− 2 ≤ 12⇒ a ≤ 14. Analisando os casos de 1 até 14, temos as soluções {1, 3, 4, 5, 6, 8, 14}.
17) Mostre que um número natural a é par se, e somente se, an é par, qualquer que seja
n ∈ N.
Solução:
Se a é par, então a = 2k para algum k ∈ N, logo an = (2k)n = 2nkn = 2(2n−1kn) = 2r
onde r = 2n−1kn. Agora, se an é par, então an = 2k para algum k ∈ N. Se a for ı́mpar, então
a = 2m+ 1 com m ∈ N. Logo,
an = (2m + 1)n = (2m)n +
(
n
1
)
(2m)n−1 +
(
n
2
)
(2m)n−2 + · · · +
(
n
n− 1
)
(2m) +
1 = 2(2n−1mn) + 2
[(
n
1
)
2n−2mn−1
]
+ 2
[(
n
2
)
2n−3mn−2
]
+ · · · + 2
[(
n
n− 1
)
m
]
+ 1 =
2
[
2n−1mn +
(
n
1
)
2n−2mn−1 +
(
n
2
)
2n−3mn−2 + · · ·+
(
n
n− 1
)
m
]
+ 1
que é da forma 2q+1 com q ∈ N. Mas por hipótese, an é par, logo temos uma contradição,
4
portanto a é par.
18) Mostre que, se a e b são ı́mpares, então a2 +b2 é diviśıvel por 2 mas não diviśıvel por
4.
Solução:
Como a e b são ı́mpares, então a = 2m + 1 e b = 2n + 1 com m,n ∈ N, logo a2 + b2 =
(2m + 1)2 + (2n + 1)2 = 4m2 + 4m + 1 + 4n2 + 4n + 1 = 4m2 + 4m + 4n2 + 4n + 2 =
2(2m2 + 2m+ 2n2 + 2n+ 1) que é diviśıvel por 2.
Mas 4 - 2(2m2 + 2m+ 2n2 + 2n+ 1) = 4m2 + 4m+ 4n2 + 4n+ 2 = 4(m2 +m+n2 +n) + 2,
pois a2 + b2 é da forma 4r + 2 com r natural.
19) Seja n um número natural. Mostre que um, e apenas um, número de cada terna
abaixo é diviśıvel por 3.
a) n, n+ 1, n+ 2;
b) n, n+ 10, n+ 23.
Solução:
a) Se n é diviśıvel por 3, então n = 3k com k ∈ N. Logo n + 1 = 3k + 1 não é diviśıvel
por 3 e n+ 2 = 3k + 2 também não é diviśıvel por 3.
Agora se n + 1 é diviśıvel por 3, então n + 1 = 3q, q ∈ N, logo n = 3q − 1 que não é
diviśıvel por 3 e n+ 2 = 3q + 1 que também não é diviśıvel por 3.
Se n + 2 é diviśıvel por 3, então n + 2 = 3r, r ∈ N. Assim, n = 3r − 2 e n + 1 = 3r − 1
são ambos não diviśıveis por 3.
b) Se n é diviśıvel por 3, então n = 3k com k ∈ N. Logo n+10 = 3k+10 = (3k+9)+1 =
3(k + 3) + 1 que não é diviśıvel por 3 e n + 23 = 3k + 23 = (3k + 21) + 2 = 3(k + 7) + 2
também não é diviśıvel por 3.
Se n+10 é diviśıvel por 3, então n+10 = 3q, q ∈ N. Assim, n = 3q−10 = (3q−9)−1 =
3(q− 3)− 1 e n+ 23 = 3q+ 13 = (3q+ 12) + 1 = 3(q+ 4) + 1 são ambos não diviśıveis por 3.
Se n+ 23 é diviśıvel por 3, então n+ 23 = 3r, r ∈ N. Logo, n = 3r−23 = (3r−21)−2 =
3(r−7)−2 e n+10 = 3r−13 = (3r−12)−1 = 3(r−4)−1 que são ambos não diviśıveis por 3.
20) Mostre que:
a) Se n é ı́mpar, então n2 − 1 é diviśıvel por 8;
b) Se n não é diviśıvel por 2, nem por 3, então n2 − 1 é diviśıvel por 24.
Solução:
a) Como n é ı́mpar, então n é da forma 2k + 1, k ∈ N. Logo, n2 = (2k + 1)2 =
4k2 + 4k + 1 ⇒ n2 − 1 = 4k2 + 4k = 4k(k + 1). Como k e k + 1 são naturais consecutivos,
então um deles é par que é múltiplo de 2, donde 4k(k + 1) é múltiplo de 8, ou seja, 8|n2 − 1
5
para n ı́mpar.
b) Como n não é diviśıvel por 2, então n é ı́mpar, logo é da forma 2r + 1 com r ∈ N e,
como n não é diviśıvel por 3, então n deixa resto 1 ou 2 na divisão por 3, isto é, n = 3s+1 ou
n = 3s+ 2 com s ∈ N. Assim, n2 = (2r+ 1)2 = 4r2 + 4r+ 1⇒ n2− 1 = 4r2 + 4r = 4r(r+ 1).
Pelo item (a), n2 − 1 é diviśıvel por 8. Por outro lado, n2 = (3s + R)2 = 9s2 + 6Rs + R2 =
3(3s2 + 2Rs) + R2 com R = 1, 2. Para R = 1, temos n2 − 1 = 3(3s2 + 2s) que é diviśıvel
por 3; se R = 2, n2 − 1 = 3(3s2 + 4s) + 3 = 3(3s2 + 4s + 1) que também é múltiplo de 3.
Portanto, 8|n2 − 1 e 3|n2 − 1⇔ 8 · 3
(8, 3)
|n2 − 1⇔ 24|n2 − 1.
21) Determinar os posśıveis valores de m,n ∈ N de modo que o número N = 9m10n tenha
243 divisores.
Solução:
Sabemos que qualquer número natural maior do que 1 pode ser fatorado como potências
de primos, ou seja, dado n ∈ N, existem primos p1, p2, · · · , pr e naturais α1, α2, · · · , αr de
modo que n = pα11 p
α2
2 · · · pαrr .
Denotando por d(n) o número de divisores do número natural n, então d(n) = (α1 +
1)(α2 + 1) · · · (αr + 1).
De acordo com isto, temos que N = 9m10n = (32)m(5 · 2)n = 32m · 5n · 2n.
Logo, d(N) = (2m+ 1)(n+ 1)(n+ 1) = (2m+ 1)(n+ 1)2 = 243.
n não pode ser ı́mpar, pois caso contrário n+ 1 seria par, donde o produto (2m+ 1)(n+
1)2 = d(N) é sempre par, contradição já que 243 é ı́mpar.
Vamos então analisar os casos em que n é um número par.
Se n = 0⇒ 2m+ 1 = 243⇒ m = 121;
se n = 2⇒ 9(2m+ 1) = 243⇒ m = 13;
se n = 4⇒ 25(2m+ 1) = 243⇒ m /∈ N;
se n = 6⇒ 49(2m+ 1) = 243⇒ m /∈ N;
se n = 8⇒ 81(2m+ 1) = 243⇒ m = 1.
n não pode ser maior do que 8, pois caso contrário, (2m + 1)(n + 1)2 > 243 para todo
m ≥ 1.
Portanto, temos as soluções (m,n) = (121, 0), (13, 2), (1, 8).
6