terça-feira, 3 de novembro de 2020

Matemática - Divisibilidade


Questão da Olimpíada de Matemática da Albânia: prove que o número acima é divisível por 39.

(Question from the Albania Math Olympiad: prove that the number above is divisible by 39.)

PCFilho

2 comentários:

  1. Given: p = 19^37 + 13^37 + 7^37

    Prove: 39 | p

    First, let’s rearrange the terms a little:

    p = 19^37 + 7^37 + 13^37

    Then, we show that the sum of the first two terms is divisible by (19 + 7), or 26:

    p = (19 + 7)(19^36 – 7*19^35 + (7^2)(19^34) – … – 19*7^35 + 7^36) + 13^37
    p = 26(19^36 – 7*19^35 + (7^2)(19^34 – … – 19*7^35 + 7^36) + 13^37

    Then we factor 13 out of the whole thing:

    p = 13[2(19^36 – 7*19^35 + (7^2)(19^34) – … – 19*7^35 + 7^36) + 13^36]

    Regrouping the terms a little and then simplifying, we get:

    p = 13[2(19^36 + (7^2)(19^34) + … + (7^34)(19^2) + 7^36 – (7*19^35 + (7^3)(19^33) + … + 19*7^35)) + 13^36]
    p = 13[2(361(19^34 + (7^2)(19^32) + … + 7^34) – 133(19^34 + (7^2)(19^32) + … + 7^34)) + 13^36 + 2*7^36]
    p = 13[2(228(19^34 + (7^2)(19^32) + … + 7^34)) + 13^36 + 2*7^36]
    p = 13[456*Σ((49^k)(361^(17 – k)),k,0,17)) + 13^36 + 2*7^36]

    Now, in the bracketed expression, we add 3 to the first term, subtract 1 from the second term, and subtract 2 from the third:

    p = 13[456*Σ((49^k)(361^(17 – k)),k,0,17)) + 3 + 13^36 – 1 + 2*7^36 – 2]
    p = 13[(456*Σ((49^k)(19^(17 – k)),k,0,17)) + 3) + (13^36 – 1) + 2(7^36 – 1)]
    p = 13(x + y + 2z)

    where

    x = 456*Σ((49^k)(19^(17 – k)),k,0,17)) + 3
    y = 13^36 – 1
    z = 7^36 – 1

    We will now show that each of the expressions above is divisible by 3. The first one’s easy—since both 456 and 3 are divisible by 3, we conclude that 3 | x. The others are a little trickier, but with a little math, they’re not so tough:

    y = (13 – 1)(13^35 + 13^34 + … + 1) = 12*Σ(13^k,k,0,35) → 3 | y (since 3 | 12)
    z = (7 – 1)(7^35 + 7^34 + … + 1) = 6*Σ(7^k,k,0,35) → 3 | z (since 3 | 6)

    Since x, y, and z are all divisible by 3, this means that 3 | (x + y + 2z). And, since p is 13 times a number that is divisible by 3, it follows that 39 | p.

    Proven.

    ResponderExcluir

Regras para postar comentários:

I. Os comentários devem se ater ao assunto do post, preferencialmente. Pense duas vezes antes de publicar um comentário fora do contexto.

II. Os comentários devem ser relevantes, isto é, devem acrescentar informação útil ao post ou ao debate em questão.

III. Os comentários devem ser sempre respeitosos. É terminantemente proibido debochar, ofender, insultar e/ou caluniar quaisquer pessoas e instituições.

IV. Os nomes dos clubes devem ser escritos sempre da maneira correta. Não serão tolerados apelidos pejorativos para as instituições, sejam quais forem.

V. Não é permitido pedir ou publicar números de telefone/Whatsapp, e-mails, redes sociais, etc.

VI. Respeitem a nossa bela Língua Portuguesa, e evitem escrever em CAIXA ALTA.

Os comentários que não respeitem as regras acima poderão ser excluídos ou não, a critério dos moderadores do blog.