LeGauss: Problemas LeGauss: Problema 2 - IMO 1984

quinta-feira, 4 de fevereiro de 2010

Problemas LeGauss: Problema 2 - IMO 1984

O seguinte problema de Teoria dos Números foi proposto na IMO de 1984:

Ache um par de inteiros positivos

e

que satisfazem, simultaneamente,

não é divisível por

;

é divisível por

.

Por incrível que pareça, este problema não é muito difícil e requer apenas alguma familiaridade com congruências e fatoração de polinômios. Segue a solução obtida por mim e pelo Gabriel:

Uma boa estratégia é impor que

é

módulo

e fatorar esta expressão para fazer aparecer

e aplicar a restrição do item

. Portanto, note que

$\center{(a+b)^7 - (a^7 +b^7) = (a+b)(a+b)^6 - (a+b)(a^6 - a^5b + a^4b^2 - a^3b^3 + a^2b^4 - ab^5 + b^6)}$

Como

(a+b)^6 = a^6 + 6a^5b + 15a^4b^2 + 20a^3b^3 + 15a^2b^4 + 6ab^5 + b^6

podemos colocar (a+b)

(a+b)

em evidência na expressão anterior e, efetuando as devidas adições e subtrações, ficaremos com

(a+b)^7 - (a^7 +b^7) = (a+b)(7a^5b + 14a^4b^2 + 21a^3b^3 + 14 a^2b^4 + 7ab^5)

Magicamente, também podemos fatorar

e

, obtendo

(a+b)^7 - (a^7 +b^7) = 7ab(a+b)(a^4 + 2a^3b + 3a^2b^2 + 2 ab^3 + b^4)

Muito melhor, agora vamos impor que isto é

módulo

7^7

, isto é,

$7ab(a+b)(a^4 + 2a^3b + 3a^2b^2 + 2 ab^3 + b^4) \equiv 0 \pmod{7^7}$

Podemos "cancelar" o

no início da expressão e teremos

$ab(a+b)(a^4 + 2a^3b + 3a^2b^2 + 2 ab^3 + b^4) \equiv 0 \pmod{7^6}$

Mas, por

(i)

, sabemos que $ab(a+b) \not\equiv 0 \pmod 7$ . Logo,

$a^4 + 2a^3b + 3a^2b^2 + 2 ab^3 + b^4 \equiv 0 \pmod{7^6}$

Agora, observe que, por (i)

(i)

, nem

nem

podem ser múltiplos de

. Portanto, eles são invertíveis módulo 7^6

7^6

. Fazendo $\theta \equiv ab^{-1} \pmod{7^6}$ , ficamos com

$\theta^4 + 2\theta^3 + 3\theta^2 + 2\theta + 1 \equiv 0 \pmod{7^6}$

Mas, observe que $\theta^4 + 2\theta^3 + 3\theta^2 + 2\theta + 1 = (\theta^2 + \theta + 1)^2$ . Logo,

$\theta^2 + \theta + 1 \equiv 0 \pmod{7^3}$

Isto quer dizer que existe um inteiro

tal que

$\theta^2 + \theta + 1 = 7^3k$

Basta achar o

certo. Obviamente,

não pode ser

e muito menos negativo. Você não vai precisar fazer muitas tentativas, pois tomando k=1

k=1

temos que uma solução é $\theta = 18$ . Substituindo $\theta$ , temos

$a \equiv 18b \pmod{ 7^6}$

Claramente, podemos tomar b=1

b=1

e

a=18

. Note que estes inteiros são positivos e satisfazem (i)

(i)

. Além disso, satisfazem (ii)

(ii)

em razão dos cálculos acima. E isto termina o problema.

Até.

2 comentários:

Gabriel Martins disse...: Engraçado que esse problema morre só pretando atenção na fatoração.. =P; 4 de fevereiro de 2010 às 18:52
Anônimo disse...: Malandragem de rua rapá.
Fatorar é uma arte.; 6 de fevereiro de 2010 às 18:26

Postar um comentário

Assinar: Postar comentários (Atom)