Olimpíadas ⇒ Divisibilidade Tópico resolvido

[Hanon]

Seja [tex3]k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k[/tex3]

um inteiro positivo. Ache todos os inteiros positivos [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

tais que:
[tex3]3^{k}=2^{n}-1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]3^{k}=2^{n}-1[/tex3]

.

[Superaks]

Como k ≥ 1 então 3^k ≥ 3

Aplique congruência módulo 3

3^k = 2^n - 1

2^n Ξ 1 (mod 3)

(- 1)^n Ξ 1 (mod 3)

Portanto n deve ser par

Note que para n = 0 não tem solução, então pegue n ≥ 2

3^k = 2^n - 1

3^k = (2^(n/2) - 1)(2^(n/2) + 1)

Então 2^(n/2) - 1 e 2^(n/2) + 1 tem que ser uma potência de 3

Faça:

2^(n/2) - 1 = 3^y e 2^(n/2) + 1 = 3^(k - y)

Note que mdc(2^(n/2) - 1, 2^(n/2) + 1) = mdc(2^(n/2) - 1, 2^(n/2) + 1 - (2^(n/2) - 1)) = mdc(2^(n/2) - 1, 2) = 1

Pois 2^(n/2) - 1 é ímpar

Então mdc(3^y, 3^(k - y)) = 1

Portanto uma dessas potências deve ser 1

Fazendo 3^y = 1

2^(n/2) - 1 = 1

2^(n/2) = 2

Logo,

n/2 = 1

n = 2

Achando k

3^k = 2² - 1 = 3

k = 1

Se 3^(k - y) = 1, temos

2^(n/2) + 1 = 1

2^(n/2) = 0 ← não existe solução para esse caso

Então só existe uma solução: (k, n) = (1, 2)