Buscar

diofantina-usamo2005

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 7 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

E´ so´ fatorar. . . Sera´mesmo?
Neste pequeno artigo resolveremos o problema 2 da USAMO (USA Mathematical Olympiad) 2005:
Problema. Prove que o sistema ∣∣∣∣∣ x
6 + x3 + x3y + y = 147157
x3 + x3y + y2 + y + z9 = 157147
na˜o tem soluc¸a˜o em inteiros x, y, z.
Soluc¸a˜o. No comec¸o, podemos pensar que este e´ mais um problema simples na qual “e´ so´ fatorar”:∣∣∣∣∣ x
6 + x3 + x3y + y = 147157
x3 + x3y + y2 + y + z9 = 157147
⇐⇒
∣∣∣∣∣ (x
3 + 1)(x3 + y) = 147157
(x3 + y)(1 + y) = 157147 − z9
Aı´ e´ so´ fatorar 147157 = 3157 · 7314 e testar todos os 2 · (157 + 1) · (314 + 1) casos, certo?
Infelizmente, acho que na hora da prova na˜o ir´ıamos ter tempo para fazer isso. Enta˜o temos que dar
um jeito de estudar menos casos.
Observe que x3 + 1 e´ um divisor de 3157 · 7314. Logo
x3 + 1 = ±3α · 7β
Voceˆ poderia pensar no x3 + y, mas isso na˜o seria uma boa, considerando que x3 + y e´ linear em
y e poderia assumir qualquer valor inteiro por causa disso. Ale´m disso, x3 + 1 tem so´ uma varia´vel e o
principal. . . fatora!
Assim, o principal no problema e´ resolver a equac¸a˜o diofantina
x3 + 1 = ±3α · 7β (∗)
em que x e´ inteiro (positivo, negativo ou ate´ quem sabe nulo!) e α e β sa˜o inteiros na˜o negativos.
Podemos fatorar o primeiro membro de (∗):
x3 + 1 = ±3α · 7β ⇐⇒ (x+ 1)(x2 − x+ 1) = ±3α · 7β
Quando fatoramos em equac¸o˜es diofantinas, devemos calcular o mdc dos fatores, sena˜o a equac¸a˜o fica
ofendida! Vamos usar tanto esse fato que o chamaremos de
Lema. Seja x inteiro. Enta˜o mdc(x + 1;x2 − x + 1) = 1 ou mdc(x + 1;x2 − x + 1) = 3. Ale´m disso, se 3
divide um dos nu´meros x + 1 ou x2 − x + 1 enta˜o divide ambos, ou seja, 3 divide x+ 1 se, e somente se, 3
divide x2 − x+ 1.
Demonstrac¸a˜o. Seja d = mdc(x+1;x2−x+1). Vendo x+1 mo´d d, obtemos x+1 ≡ 0 (mo´d. d) ⇐⇒ x ≡
−1 (mo´d. d). Vendo agora x2−x+1 mo´d d, obtemos x2−x+1 ≡ 0 (mo´d. d) ⇐⇒ (−1)2− (−1)+1 ≡ 0
(mo´d. d) ⇐⇒ 3 ≡ 0 (mo´d. d) ⇐⇒ d|3 ⇐⇒ d = 1 ou d = 3.
Vimos acima que se x+1 e´ divis´ıvel por 3 enta˜o x2 − x+1 tambe´m e´. Vejamos agora a rec´ıproca. Mas
isso e´ ta˜o fa´cil quanto resolver equac¸a˜o do segundo grau!
x2 − x+ 1 ≡ 0 (mo´d. 3) ⇐⇒ 4x2 − 4x+ 4 ≡ 0 (mo´d. 3) ⇐⇒ 4x2 − 4x+ 1 ≡ 0 (mo´d. 3)
⇐⇒ (2x− 1)2 ≡ 0 (mo´d. 3) ⇐⇒ 2x− 1 ≡ 0 (mo´d. 3)
⇐⇒ −x− 1 ≡ 0 (mo´d. 3) ⇐⇒ x+ 1 ≡ 0 (mo´d. 3)
Agora, voltemos a` equac¸a˜o (∗), ou seja,
(x+ 1)(x2 − x+ 1) = ±3α · 7β
Logo x+ 1 = ±3α1 · 7β1 e x2 − x+ 1 = 3α2 · 7β2 (note que x2 − x+ 1 = 1
4
(
(2x− 1)2 + 3)
)
> 0), sendo
α1, β1, α2 e β2 inteiros na˜o negativos.
Veja que, do Lema, conclu´ımos que α1 = 0 ⇐⇒ α2 = 0 e, ale´m disso, β1 = 0 ou β2 = 0, pois se ambos
os expoentes β1 e β2 forem positivos enta˜o 7 seria um dos fatores de mdc(x+ 1;x
2 − x+ 1), absurdo. Ale´m
disso, se α1 > 0 (ou α2 > 0) enta˜o α1 = 1 ou α2 = 1 pois, caso contra´rio, 9 dividiria mdc(x+ 1;x
2 − x+ 1),
absurdo.
Suponha primeiro que α1 e β1 sa˜o ambos na˜o nulos. Logo α2 > 0 e β2 = 0.
Se α1 ≥ 2, α2 = 1 e, portanto, x
2− x+1 = 3 ⇐⇒ x = −1 ou x = 2. x = −1 e´ o mesmo que x+1 = 0,
o que na˜o e´ poss´ıvel. x = 2 e´ equivalente a x+ 1 = 3, absurdo ja´ que supomos que β1 > 0.
Logo α1 = 1 e, portanto, x + 1 = ±3 · 7
β1 e x2 − x+ 1 = 3α2 . Mas a´ı, sendo a = 7β1 , x = 3a− 1 ⇐⇒
x3 = 27a3 − 27a2 + 9a − 1 ⇐⇒ x3 + 1 = 9(3a3 − 3a2 + 1). Como 3a3 − 3a2 + 1 na˜o e´ divis´ıvel por 3, a
maior poteˆncia de 3 que divide x2− x+1 e´ 32, ou seja, α2 = 2. Portanto, x
2− x+1 = 9, o que e´ imposs´ıvel
para x inteiro.
Desta forma, na˜o e´ poss´ıvel que α1 e β1 sejam ambos na˜o nulos. Resta-nos, enta˜o, dois casos: α1 = 0 e
β1 = 0.
• Primeiro caso: α1 = 0 e β1 = 0. Neste caso, x + 1 = ±1 e, portanto, x = 0 ou x = −2. Veja que, para
esses valores de x, x3 + 1 e´ da forma 3α · 7β.
• Segundo caso: α1 = 0 e β1 > 0. Aqui temos x+1 = ±7
β1, α2 = 0 e β2 = 0, ou seja, x
2−x+1 = 1 ⇐⇒
x = 1 ou x = 0. Nenhum desses valores de x satisfaz x+ 1 ser uma poteˆncia de 7 maior que 1.
• Terceiro caso: α1 > 0 e β1 = 0. Temos x+ 1 = ±3
α1 , α2 > 0 e β2 ≥ 0. Ale´m disso, α1 = 1 ou α2 = 1.
Se α1 = 1, x+1 = ±3, ou seja, x = 2 ou x = −4. Novamente, para esses valores de x, x
3 +1 e´ da forma
3α · 7β.
Se α2 = 1, x+1 = ±3
α1 e x2−x+1 = 3·7β2 . Logo x = ±3α1−1 e x2−x+1 = (±3α1−1)2−(±3α1−1)+1 =
32α1 ∓ 3α1+1 + 3. Logo x2 − x+ 1 = 3 · 7β2 ⇐⇒ 32α1 ∓ 3α1+1 + 3 = 3 · 7β2 ⇐⇒ 3α1(3α1−1 ∓ 1) = 7β2 − 1.
Agora temos que resolver esta outra equac¸a˜o diofantina:
3α1(3α1−1 ∓ 1) = 7β2 − 1 (∗∗)
Neste caso utilizamos o
Lema de Hensel. Seja p um primo ı´mpar, a um inteiro e n um inteiro positivo. Sejam α e β inteiros na˜o
negativos, com α > 0.
(i) Se a maior poteˆncia de p que divide n e´ pβ e a maior poteˆncia de p que divide a − 1 e´ pα (atenc¸a˜o, p
deve dividir a− 1! Mas note que p na˜o precisa dividir n), enta˜o a maior poteˆncia de p que divide an− 1
e´ pα+β.
(ii) Se n e´ ı´mpar, a maior poteˆncia de p que divide n e´ pβ e a maior poteˆncia de p que divide a+1 e´ pα (as
mesmas condic¸o˜es sobre os expoentes α e β do item (i) devem valer), enta˜o a maior poteˆncia de p que
divide an + 1 e´ pα+β .
Vejamos como aplica´-lo no problema.
Seja 3γ a maior poteˆncia de 3 que divide β2. Como a maior poteˆncia de 3 que divide 7−1 e´ 3, aplicando
o Lema de Hensel para a = 7, p = 3, n = β2, α = 1 e β = γ, obtemos que a maior poteˆncia de 3 que divide
7β2−1 e´ γ+1. Mas, de (∗∗), a maior poteˆncia de 3 que divide 7β2−1 e´ 3α1 , logo γ+1 = α1 ⇐⇒ γ = α1−1.
Logo 3α1−1 divide β2 e, portanto, β2 ≥ 3
α1−1. Sendo w = 3α1−1, temos
3α1(3α1−1 ∓ 1) = 7β2 − 1 ≥ 73
α1−1
− 1 =⇒ 3w(w ∓ 1) ≥ 7w − 1
Mas note que a exponencial 7w − 1 cresce bem mais que o polinoˆmio 3w(w − 1). De fato, uma simples
induc¸a˜o mostra que 7w − 1 > 3w(w + 1) ≥ 3w(w ∓ 1) para w ≥ 2: 7w+1 − 1 − 3(w + 1)
(
(w + 1) + 1
)
=
(7w − 1)− 3w(w + 1) + 6(7w − 1 − w). Por hipo´tese, 7w − 1 − 3w(w + 1) > 0 e, ale´m disso, 7w − 1 − w >
(7w − 1)− 3w(w+ 1) > 0. Logo se a desigualdade 7w − 1 > 3w(w+ 1) e´ va´lida enta˜o a mesma desigualdade
vale para valores maiores de w. Como, em particular, vale para w = 2, acabou.
Logo w = 1 ⇐⇒ 3α1−1 = 1 ⇐⇒ α1 = 1, que ja´ estudamos.
As aplicac¸o˜es do Lema de Hensel geralmente seguem esse script: primeiro, aplicamos o teorema e depois
chegamos a alguma desigualdade que limita algum dos expoentes, chegando a um nu´mero normalmente bem
finito de casos.
Voceˆ deve estar se perguntando como e´ a demonstrac¸a˜o do Lema de Hensel. Vamos demonstra´-lo nesse
caso particular (a = 7, p = 3). A prova do Lema em si na˜o e´ muito diferente do que se segue.
Primeiro, seja β2 = 3
γ · t, sendo que 3 na˜o divide t. Utilizaremos a fatorac¸a˜o xt − 1 = (x − 1)(xt−1 +
xt−2 + · · ·+ x+ 1) para x = 73
γ
:
7β2 − 1 = (73
γ
)t − 1 = (73
γ
− 1)
(
(73
γ
)t−1 + (73
γ
)t−2 + · · ·+ 73
γ
+ 1
)
Como ja´ dissemos antes, se na˜o calcularmos o mdc das parcelas, a equac¸a˜o fica ofendida! Assim, seja
D = mdc(x− 1;xt−1 + xt−2 + · · ·+ x+1), com x = 73
γ
. Vendo x− 1 mo´d D temos x ≡ 1 (mo´d. D). Logo
xt−1 + xt−2 + · · · + x + 1 ≡ 0 (mo´d. D) ⇐⇒ 1 + 1 + · · ·+ 1︸ ︷︷ ︸
t uns
≡ 0 (mo´d. D) ⇐⇒ t ≡ 0 (mo´d. D), ou
seja, D divide t. Note que esse resultado na˜o depende do valor de x (desde que seja inteiro, e´ claro!), enta˜o,
voceˆ pode guardar:
Fato. Seja x inteiro e D = mdc(x− 1;xt−1 + xt−2 + · · ·+ x+ 1). Enta˜o D divide t.
Na nossa demonstrac¸a˜o, o que interessa e´ que 3 na˜o divide t e, portanto, na˜o divide D. Em outras
palavras, todos os fatores 3 esta˜o em 73
γ
− 1.
Agora vamos provar que 73
γ
− 1 tem γ + 1 fatores 3 por induc¸a˜o em γ: a base γ = 0, 1 e´ o´bvia. Agora,
note que 73
γ+1
− 1 = (73
γ
)3 − 1 = (73
γ
− 1)((73
γ
)2 + 73
γ
+ 1). Mas mdc(x − 1;x2 + x + 1) = 3 para todo
x inteiro, em particular para x = 73
γ
. Logo a maior poteˆncia de 3 que divide (73
γ
)2 + 73
γ
+ 1 e´ 3 e, pela
hipo´tese deinduc¸a˜o, a maior poteˆncia de 3 que divide 73
γ
− 1 e´ γ +1. Assim, o passo indutivo esta´ provado
e a induc¸a˜o tambe´m.
Enfim, chegamos a` soluc¸a˜o de (∗): x = −2; x = 0; x = 2; x = −4. Assim, x3 + 1 so´ tem fatores primos
3 e 7 para esses valores de x.
Agora e´ so´ testar no sistema original. Da primeira equac¸a˜o encontramos y; subsitu´ımos na segunda e
provamos que na˜o existe z.
• x = −2 ⇐⇒ x3 + 1 = −7.∣∣∣∣∣ (x
3 + 1)(x3 + y) = 147157 = 3157 · 7314
(x3 + y)(1 + y) = 157147 − z9
⇐⇒
∣∣∣∣∣ y = 8− 3
157 · 7313
−3157 · 7313(9 − 3157 · 7313) = 157147 − z9
Vendo mo´d 157 (e observando que 157 e´ primo e, portanto, a156 ≡ 1 (mo´d. 157) para a na˜o divis´ıvel
por 157), obtemos
− 3156 · 3 · 72·156 · 7(9− 3156 · 3 · 72·156 · 7 ≡ −z9 (mo´d. 157)
⇐⇒ 3 · 7(9− 3 · 7) ≡ z9 (mo´d. 157)
⇐⇒ − 252 ≡ z9 (mo´d. 157)
⇐⇒ z9 ≡ 62 (mo´d. 157)
Notando que 156 = 3 · 52, elevando a 52 obtemos no lado esquerdo z3·156 ≡ 1 (mo´d. 157). Logo
6252 ≡ 1 (mo´d. 157)
Vejamos se isso e´ verdade. Se na˜o for, na˜o ha´ soluc¸o˜es nesse caso.
622 = 62 · 3 · 20 + 62 · 2 ≡ 29 · 20− 33 ≡ −48− 33 ≡ −81 (mo´d. 157)
=⇒ 6252 ≡ (−34)26 (mo´d. 157)
=⇒ 6252 ≡ 3104 (mo´d. 157)
Logo 6252 ≡ 1 (mo´d. 157) ⇐⇒ 3104 ≡ 1 (mo´d. 157) ⇐⇒ 3156−104 = 352 ≡ 1 (mo´d. 157). Vamos
la´!
36 = 729 ≡ −56 (mo´d. 157) =⇒ 312 ≡ 562 (mo´d. 157)
⇐⇒ 312 ≡ 56 · 3 · 18 + 56 · 2 ≡ 11 · 18− 45 ≡ −4 (mo´d. 157)
=⇒ 348 ≡ 256 (mo´d. 157) ⇐⇒ 352 ≡ −58 · 81 (mo´d. 157)
⇐⇒ 352 ≡ −58 · 3 · 27 ≡ −17 · 27 ≡ −17 · 9 · 3 ≡ −(−4) · 3 ≡ 12 (mo´d. 157)
Logo 352 ≡ 12 (mo´d. 157) e, portanto, na˜o ha´ soluc¸o˜es nesse caso.
• x = 2 ⇐⇒ x3 + 1 = 9.∣∣∣∣∣ (x
3 + 1)(x3 + y) = 147157 = 3157 · 7314
(x3 + y)(1 + y) = 157147 − z9
⇐⇒
∣∣∣∣∣ y = 3
155 · 7314 − 8
3155 · 7314(3155 · 7314 − 7) = 157147 − z9
Vendo mo´d 157:
3156−1 · 72·156+2(3156−1 · 72·156+2 − 7) ≡ −z9 (mo´d. 157)
⇐⇒ 3−1 · 72(3−1 · 72 − 7) ≡ −z9 (mo´d. 157)
⇐⇒ − 52 · 7 · 7(−52 · 7 · 7− 7) ≡ −z9 (mo´d. 157)
⇐⇒ 364 · 7(−364 · 7− 7) ≡ z9 (mo´d. 157)
⇐⇒ 50 · 7(−50 · 7− 7) ≡ −z9 (mo´d. 157)
⇐⇒ 350 · 357 ≡ −z9 (mo´d. 157)
⇐⇒ 36 · 43 ≡ −z9 (mo´d. 157)
⇐⇒ 22 ≡ z9 (mo´d. 157)
Elevando a 52,
2252 ≡ 1 (mo´d. 157)
Vamos la´!
222 = 484 ≡ 13 (mo´d. 157) =⇒ 224 ≡ 169 ≡ 12 (mo´d. 157)
=⇒ 228 ≡ 144 ≡ −13 (mo´d. 157) ⇐⇒ 228 ≡ −222 (mo´d. 157)
⇐⇒ 226 ≡ −1 (mo´d. 157) =⇒ 2248 ≡ 1 (mo´d. 157)
⇐⇒ 2252 ≡ 224 ≡ 12 (mo´d. 157)
De novo, na˜o temos soluc¸o˜es nesse caso.
• x = −4 ⇐⇒ x3 + 1 = −63.∣∣∣∣∣ (x
3 + 1)(x3 + y) = 147157 = 3157 · 7314
(x3 + y)(1 + y) = 157147 − z9
⇐⇒
∣∣∣∣∣ y = 8− 3
155 · 7313
−3155 · 7313(9 − 3155 · 7313) = 157147 − z9
Vendo mo´d 157:
− 3156−1 · 72·156+1(9− 3156−1 · 72·156+1) ≡ −z9 (mo´d. 157)
⇐⇒ − 3−1 · 7(9− 3−1 · 7) ≡ −z9 (mo´d. 157)
⇐⇒ 52 · 7(9 + 52 · 7) ≡ −z9 (mo´d. 157)
⇐⇒ 364(9 + 364) ≡ −z9 (mo´d. 157)
⇐⇒ 50 · 59 ≡ −z9 (mo´d. 157)
⇐⇒ 33 ≡ z9 (mo´d. 157)
Elevando a 52,
3352 ≡ 1 (mo´d. 157)
Vamos ver se isso e´ verdade mesmo: primeiro note que 3352 = 352 · 1152 e que ja´ sabemos que 352 ≡ 12
(mo´d. 157). Assim, basta calcular 1152 mo´d 157.
112 ≡ −36 (mo´d. 157) =⇒ 114 ≡ 362 = 36 · 4 · 9 ≡ (−13) · 9 ≡ 40 (mo´d. 157)
=⇒ 118 ≡ 1600 ≡ 30 (mo´d. 157) =⇒ 1116 ≡ 900 ≡ −42 (mo´d. 157)
=⇒ 1132 ≡ 422 = 42 · 40 + 42 · 2 ≡ 1680 + 84 ≡ 110− 73 ≡ 37 (mo´d. 157)
=⇒ 1148 = 1132 · 1116 ≡ 37 · (−42) ≡ −37 · 40− 37 · 2 ≡ 90− 74 ≡ 16 (mo´d. 157)
=⇒ 1152 = 1148 · 114 ≡ 16 · 40 = 640 ≡ 12 (mo´d. 157)
Novamente, na˜o ha´ soluc¸o˜es.
• x = 0 ⇐⇒ x3 + 1 = 1. Nesse caso, obtemos y = 147157 − 1 e y(y + 1) = 157147 − z9 ⇐⇒ (147157 −
1)147157 = 157147 − z9 =⇒ (147− 1)147 ≡ −z9 (mo´d. 157) ⇐⇒ z9 ≡ 47 (mo´d. 157) =⇒ 4752 ≡ 1
(mo´d. 157).
Vamos fazer mais uma vez as contas! Algo que pode ajudar e´ que 4752 ≡ (−110)52 ≡ 1152 · 1052
(mo´d. 157) e que sabemos que 1152 ≡ 12 (mo´d. 157). Falta, enta˜o, calcular 1052 mo´d 157.
103 ≡ −58 (mo´d. 157) ⇐⇒ 104 ≡ −580 ≡ 48 (mo´d. 157) ⇐⇒ 105 ≡ 480 ≡ 9 ≡ 32 (mo´d. 157)
Ja´ calculamos algumas poteˆncias de 3 mo´d 157! Entre elas, 312 ≡ −4 (mo´d. 157):
1030 ≡ 312 ≡ −4 (mo´d. 157) =⇒ 1045 = 1030 · (105)3 ≡ −4 · 36 ≡ −4 · (−56) ≡ 67 (mo´d. 157)
=⇒ 1050 = 1045 · 105 ≡ 67 · 9 = 603 ≡ −25 (mo´d. 157)
=⇒ 1052 ≡ −250 · 10 ≡ 64 · 10 ≡ 12 (mo´d. 157)
De novo, nenhuma soluc¸a˜o.
Assim, o sistema dado na˜o tem soluc¸o˜es inteiras.
O problema tambe´m admite uma soluc¸a˜o mais curta. Vamos apresenta´-las e depois fazemos alguns
comenta´rios sobre as duas soluc¸o˜es.
Soluc¸a˜o alternativa. No sistema ∣∣∣∣∣ x
6 + x3 + x3y + y = 147157
x3 + x3y + y2 + y + z9 = 157147
o que aparece mais sa˜o nu´meros ao cubo. Enta˜o pode ser interessante ver algum mo´dulo primo com poucos
res´ıduos cu´bicos.
O fato e´ que os primos com “poucos” res´ıduos cu´bicos sa˜o os da forma 3k + 1. Depois vamos ver por
queˆ.
Ver mo´d 7 na˜o da´ certo (tente e veja por si mesmo!). Mas ver mo´d 13 funciona bem. A tabela a seguir
mostra os res´ıduos cu´bicos mo´d 13:
x mo´d 13 0 ±1 ±2 ±3 ±4 ±5 ±6
x3 mo´d 13 0 ±1 ±8 ±1 ∓1 ±8 ±8
Como no problema o x so´ aparece ao cubo, podemos encontrar y mo´d 13 na primeira equac¸a˜o e substituir
na segunda. Temos 147 ≡ 4 (mo´d. 13) =⇒ 1476 ≡ 212 ≡ 1 (mo´d. 13) =⇒ 147156 ≡ 1 (mo´d. 13) ⇐⇒
147157 ≡ 4 (mo´d. 13) e 157 ≡ 1 (mo´d. 13) =⇒ 157147 ≡ 1 (mo´d. 13). Assim, vendo mo´d 13 o sistema
fica ∣∣∣∣∣ (x
3 + 1)(x3 + y) ≡ 4 (mo´d. 13)
(x3 + y)(1 + y) ≡ 1− z9 (mo´d. 13)
⇐⇒
∣∣∣∣∣ (x
3 + 1)(x3 + y) ≡ 4 (mo´d. 13)
z9 ≡ 1− (x3 + y)(1 + y) (mo´d. 13)
Ja´ vemos, por exemplo, que x3 6≡ −1 (mo´d. 13). Vamos testar os outros quatro casos (x3 ≡ 0, 1, 5, 8
(mo´d. 13)):
x3 mo´d 13 (x3 + y) ≡ 4(x3 + 1)−1 (mo´d. 13) z9 ≡ 1− (x3 + y)(1 + y) (mo´d. 13)
0 0 + y ≡ 4 · 1−1 ≡ 4 z9 ≡ 1− 4 · (1 + 4) ≡ 11
1 1 + y ≡ 4 · 2−1 ≡ 2 z9 ≡ 1− 2 · (1 + 1) ≡ 10
5 5 + y ≡ 4 · 6−1 ≡ 5 z9 ≡ 1− 5 · (1 + 0) ≡ 9
8 8 + y ≡ 4 · 9−1 ≡ −1 z9 ≡ 1− (−1) · (1 + 4) ≡ 6
Nenhum dos nu´meros 6, 9, 10, 11 e´ res´ıduo cu´bico de 13 e portanto z9 = (z3)3 ≡ 6, 9, 10, 11 (mo´d. 13)
na˜o tem soluc¸a˜o. Logo o sistema na˜o tem soluc¸a˜o.
Agora, vamos explicar por que os primos com “poucos” res´ıduos sa˜o os da forma 3k + 1.
Lema. Seja p um primo maior que 3. Enta˜o
• Se p ≡ −1 (mo´d. 3) enta˜o todo res´ıduo e´ res´ıduo cu´bico, ou seja, p admite p res´ıduos cu´bicos.
• Se p ≡ 1 (mo´d. 3) enta˜o p admite p−1
3
+ 1 res´ıduos cu´bicos.
A demonstrac¸a˜o desse lema e´ baseado no seguinte fato:
Fato. Seja p primo ı´mpar e a inteiro na˜o divis´ıvel por p. A congrueˆncia x3 ≡ a3 (mo´d. p) tem
• 1 soluc¸a˜o se p ≡ −1 (mo´d. 3);
• 3 soluc¸o˜es se p ≡ 1 (mo´d. 3).
Vamos provar esse fato: primeiro, temos
x3 ≡ a3 (mo´d. p) ⇐⇒ x3 − a3 ≡ 0 (mo´d. p)
⇐⇒ (x− a)(x2 + ax+ a2) ≡ 0 (mo´d. p)
⇐⇒ x ≡ a (mo´d. p) ou x2 + ax+ a2 ≡ 0 (mo´d. p)
Ja´ temos uma soluc¸a˜o, x ≡ a (mo´d. p). Estudemos a congrueˆncia quadra´tica.
x2 + ax+ a2 ≡ 0 (mo´d. p) ⇐⇒ 4x2 + 4ax+ 4a2 ≡ 0 (mo´d. p) ⇐⇒ (2x+ a)2 ≡ −3a2 (mo´d. p)
Essa congrueˆncia tem soluc¸a˜o se, e somente se, −3a2 e´ res´ıduo quadra´tico de p, o que ocorre se, e
somente se, −3 e´ res´ıduo quadra´tico de p. Para verificar quando isso acontece, utilizamos (sem demonstrar)
a lei da reciprocidade quadra´tica:
Lei da reciprocidade quadra´tica. Defina o s´ımbolo de Legendre por(
a
p
)
=
{
0 se p divide a
1 se p na˜o divide a e a e´ res´ıduo quadra´tico de p
−1 caso contra´rio
Enta˜o, sendo p e q primos, (
p
q
)
·
(
q
p
)
= (−1)
p−1
2
·
q−1
2
Queremos saber
(
−3
p
)
. Fazendo q = 3, obtemos(
p
−3
)
·
(
−3
p
)
= (−1)
p−1
2
·
−3−1
2 = 1 ⇐⇒
(
−3
p
)
=
(
p
3
)
Mas os res´ıduos quadra´ticos de 3 sa˜o 0 e 1. Logo se p e´ maior que 3(
−3
p
)
=
{
1 se p ≡ 1 (mo´d. 3)
−1 se p ≡ −1 (mo´d. 3)
Deste modo, o fato esta´ demonstrado. Poder´ıamos ter demonstrado uma (mas so´ essa!) mais facilmente:
sep ≡ −1 (mo´d. 3), p−2
3
e´ inteiro e
x3 ≡ a3 (mo´d. p) =⇒ (x3)
p−2
3 ≡ (a3)
p−2
3 (mo´d. p)
⇐⇒ xp−2 ≡ ap−2 (mo´d. p)
⇐⇒ x−1 ≡ a−1 (mo´d. p)
⇐⇒ x ≡ a (mo´d. p)
O resto da demonstrac¸a˜o do lema e´ combinato´ria: para cada k = 0, 1, 2, . . . , p− 1 seja Ak o nu´mero de
soluc¸o˜es de x3 ≡ k (mo´d. p). Sabemos que se p ≡ 1 (mo´d. 3) enta˜o
|Ak| =
{
1 se k = 0
3 se k e´ res´ıduo cu´bico de p
0 caso contra´rio
e se p ≡ −1 (mo´d. 3) enta˜o
|Ak| =
{
1 se k = 0 ou k e´ res´ıduo cu´bico de p
0 caso contra´rio
Observe que os conjuntos Ak’s sa˜o disjuntos e que todo x e´ raiz de alguma congrueˆncia do tipo x
3 ≡ k
(mo´d. p) (e´ so´ tomar k = x3!), logo S = |A0|+ |A1| + · · ·+ |Ap−1| = p. Temos A0 = {0}, enta˜o 0 e´ res´ıduo
cu´bico.
Seja n a quantidade de res´ıduos cu´bicos de p. Se p ≡ 1 (mo´d. 3), temos S = 1 + 3n ⇐⇒ n = p−1
3
e
se p ≡ −1 (mo´d. 3), temos S = 1 + n ⇐⇒ n = p− 1 e a demonstrac¸a˜o do fato esta´ completa.
Comenta´rios sobre as duas soluc¸o˜es. Ha´ algumas considerac¸o˜es sobre o problema:
(i) O expoente 9 em z9 na˜o e´ necessa´rio. Poderia ser z3 no lugar de z9.
(ii) Podemos trocar 157147 por qualquer mu´ltiplo de 157.
Comparando as soluc¸o˜es, sem du´vida a segunda soluc¸a˜o e´ mais curta e envolve menos contas. Mas
a primeira soluc¸a˜o tem mais a dizer: ale´m de provar (ii), o que a segunda soluc¸a˜o na˜o faz, nela tambe´m
conseguimos um fato bastante interessante sobre nu´meros da forma x3 + 1: eles consistem so´ em fatores
primos 3 e 7 para poucos valores de x (quatro, para ser exato). Na verdade isso e´ razoavelmente esperado,
dado que o mdc dos fatores x + 1 e x2 − x + 1 e´ pequeno: e´ de se esperar que os fatores primos de x + 1 e
x2 − x+ 1 sejam bem diferentes.
Isso pode levar a outras perguntas interessantes: seja Xk a quantidade de nu´meros inteiros x tais que
x3 +1 tem exatamente k fatores primos distintos. Xk e´ finito ou infinito? E se trocarmos x
3 +1 por xn− 1,
n inteiro positivo maior que 3?

Outros materiais