Questões de Divisibilidade, múltiplos e primos da OBMEP

O quadrado de um número inteiro a é o número a². Dada a expressão 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10, podemos decompor os fatores compostos em seus fatores primos, de modo que

1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 × 2) × (3 × 3) × (2 × 5)

Vemos que há oito fatores 2, quatro fatores 3, dois fatores 5 e um único fator 7.

Assim, podemos reescrever o produto acima como

2² × 2² × 2² × 2² × 3² × 3² × 5² × 7

O número que impede que o resultado seja o quadrado de um inteiro é o 7, pois ele não aparece elevado ao quadrado. Eliminando esse fator, temos

2² × 2² × 2² × 2² × 3² × 3² × 5² = (2 × 2 × 2 × 2 × 3 × 3 × 5)² = 720²

Logo, um único fator deve ser eliminado, o fator 7.

Basta contar o número de fatias e observar se o resultado é um múltiplo de 9.

Se todas as cinco pizzas tivessem sido cortadas em 6 fatias, teríamos um total de 6 x 5 = 30 fatias, o que não permitiria a divisão exata entre os 9 amigos.

Se quatro pizzas tivessem sido cortadas em 6 e uma em 8, teríamos 6 x 4 + 8 x 1 = 32 pedaços, divisão novamente incorreta.

Se três pizzas tivessem sido cortadas em 6 e duas em 8, teríamos 6 x 3 + 2 x 8 = 34 pedaços, divisão novamente incorreta.

Se duas pizzas tivessem sido cortadas em 6 e três em 8, teríamos 6 x 2 + 3 x 8 = 36 pedaços. Nesse caso, cada amigo teria comido 4 pedaços, pois 9 x 4 = 36.

Se uma pizza tivesse sido cortada em 6 e quatro em 8, teríamos 6 x 1 + 4 x 8 = 38 pedaços, divisão novamente incorreta.

Finalmente, a possibilidade de termos as cinco pizzas com 8 fatias resultariam em 40 pedaços, impossível de dividir exatamente por 9.

Logo, os 9 amigos comeram 4 fatias cada. Note que eles não comeram a mesma quantidade de pizza, mas sim a mesma quantidade de fatias.

Outra solução:

Sejam x o número de pizzas cortadas em 6 fatias e y o número de pizzas cortadas em 8 fatias. O enunciado diz que x + y = 5, o que nos dá as possbilidades (x,y) = (5,0),(4,1),(3,2),(2,3),(1,4),(0,5). Além disso, o número total de fatias em que as pizzas foram cortadas é 6_x_ + 8_y_; como essas foram igualmente divididas entre os 9 amigos, segue que 6_x_ + 8_y_ deve ser um múltiplo de 9. Substituindo os possíveis valores de (x,y) nessa expressão, vemos que o único múltiplo de 9 que aparece é 2 × 6 + 3 × 8 = 36, ou seja, duas pizzas cortadas em 6 fatias e três pizzas em 8 fatias. Segue que cada um dos amigos comeu (36/9) = 4 fatias.

Uma maneira de tornar essa solução mais rápida é escrever o número de fatias como 9_z_ e reescrever 6_x_ + 8_y_ = 9_z_ como

8_y_ = 9_z_ - 6_x_ = 3(3_x_ - 2_z_).

Isso mostra que 8_y_ deve ser um múltiplo de 3, que só acontece para y = 3 e chegamos à solução (2,3), como acima.

Vamos encontrar todos os pares de números inteiros positivos a e b para os quais sejam cumpridas as condições do enunciado. Como a + 2 é múltiplo de b, temos b ≤ a + 2; como b + 2 é múltiplo de a, temos a ≤ b + 2. Portanto, a diferença b − a só pode variar entre −2 e 2. Pela simetria entre a e b, basta examinar os casos em que a diferença b − a é igual a 0, 1 ou 2 (os casos em que a diferença é igual a −1 ou −2 dão origem às mesmas soluções que os casos em que é igual a 1 ou 2, com os valores de a e b trocados).

Caso b − a = 0:

Neste caso, a + 2 é múltiplo de a, o que equivale a dizer que 2 é múltiplo de a. Logo, a pode ser 1 ou 2, o que fornece as soluções a = b = 1 e a = b = 2.

Caso b − a = 1:

Neste caso, b = a + 1. Em consequência, a + 2 deve ser múltiplo de a + 1. Como a + 2 = (a + 1) + 1, isto implica que 1 seja múltiplo de a + 1. Como a é positivo, essa hipótese é impossível e, portanto, não há soluções neste caso.

Caso b − a = 2.

Neste caso, b = a + 2 e as condições a serem satisfeitas são de que a + 2 = b seja múltiplo de b (o que é sempre verdade) e de que b + 2 = a + 4 seja múltiplo de a. Para que isso aconteça, 4 deve ser múltiplo de a ou, equivalentemente, a deve ser um divisor de 4. Logo, temos as possibilidades a = 1, b = 3; a = 2, b = 4; e a = 4, b = 6.

Como no caso b − a = 1, não há soluções para o caso b − a = −1. As soluções para o caso b − a = −2 são as mesmas do caso b − a = 2, com a e b trocados: a = 3, b = 1; a = 4, b = 2; e a = 6, b = 4.

O maior valor de a + b ocorre nas soluções a = 4, b = 6 e a = 6, b = 4, para as quais a + b = 10.

Inicialmente, observamos que as decomposições em fatores primos dos números que aparecem no enunciado são:

462 = 2.3.7.11

150 = 2.3.5.5

495 = 3.3.5.11

84 = 2.2.3.7

Na interseção de 150 com 462, deve aparecer o 2, pois o 3 já está na interseção de 150 com 294.

A interseção de 495 com 84 deve ser preenchida com o 3, pois é o único fator primo comum entre esses dois números. Desta forma, sobra o 7 para a interseção de 462 com 84.

Então, como a fatoração do 84 é 3 . 2 . 7 . 2, concluímos que * = 2.

O MDC de dois números que estão fatorados como produto de primos é o produto dos primos comuns, cada um elevado ao menor expoente que comparece nas fatorações.

Denotamos por α e β os dois números cujo produto é 6000 = 2⁴ × 3 × 5³. Assim, os fatores primos de α e β são 2, 3 ou 5.

O MDC de α e β será o maior possível, quando os fatores primos estiverem distribuídos de forma mais equânime possível. Em particular, o fator primo 2, que ocorre com expoente par na fatoração de 6000, deve ocorrer com o mesmo expoente nas fatorações de α e β, a saber, a metade do expoente (4 ÷ 2 = 2) que aparece na fatoração de 6000. Para o primo 5, cujo expoente é um número ímpar maior do que 2, devemos maximizar sua ocorrência nas fatorações de α e β. Para isso, subtraímos 1 de seu expoente na fatoração de 6000, ou seja, fazemos 3 − 1 = 2, e depois tomamos a metade (2 ÷ 2 = 1). Assim, para o caso estabelecido no enunciado, a fim de maximizar o MDC entre α e β, devemos ter em suas fatorações o produto 2 × 2 × 5 = 20. Uma possibilidade é α = 2 × 2 × 5 × 3 = 60 e β = 2 × 2 × 5 × 5 = 100. Assim, o maior valor possível para o MDC entre α e β é 20.

Lembramos primeiro que, se a e b são números naturais, dizer que a é múltiplo de b (ou b divide a) é dizer que existe outro número natural c tal que a = bc. O algoritmo da divisão nos diz que, se b ≠ 0, existem únicos inteiros q e r tais que a = qb + r e 0 ≤ r < |b|; os números q e r são ditos, respectivamente, o quociente e o resto da divisão de a por b (se r = 0, temos o caso em que a é múltiplo de b).

Seja agora n o número natural do enunciado. Como n + 1 é múltiplo de 11, existe um número natural t tal que n + 1 = 11_t_; do mesmo modo, existe um número natural s tal que n − 1 = 8_s_. Multiplicando membro a membro essas expressões, temos (n + 1)(n − 1) = n² − 1 = 88_ts_, ou seja, n² = 88_ts_ + 1. Essa última expressão mostra que o resto da divisão de n² por 88 é 1.