OBM 2008

⇒ Vamos chamar de garboso o número que possui um múltiplo cujas quatro primeiras casas de sua representação decimal são 2008. Por exemplo, 7 é garboso pois 200858 é múltiplo de 7 e começa com 2008. Observe que 200858 = 28694 x 7.
      →Mostre que todos os inteiros positivos são garbosos.

notação: [latex](a, b)=\operatorname{mdc}(a, b)[/latex]
Basta mostrar para os inteiros [latex]k[/latex] tais que [latex](k, 10)=1[/latex]. De fato, supondo já resolvido pro caso anterior, se [latex]n=2^a\cdot5^bg[/latex], onde [latex](g, 10)=1[/latex], existe algum múltiplo [latex]m[/latex] de [latex]g[/latex] satisfazendo as condições do enunciado, de forma que [latex]10^{\max\{a, b\}}m[/latex] é múltiplo de [latex]n[/latex] e então [latex]n[/latex] é garboso.

Supondo, então, [latex](k, 10)=1[/latex] e sendo [latex]r[/latex] o resto de [latex]2008[/latex] na divisão por [latex]k[/latex], pelo teorema de Euler, [latex]10^{\phi(k)}\equiv 1 \pmod{k}[/latex], e então
Veja que [latex]m[/latex] segue as condições do enunciado, de modo que [latex]k[/latex] é garboso.


Essa construção é meio ruinzinha pois gera numeros muito grande (por exemplo, para 7 ela gera o número 2008000000000000000000000000000000000001000000), mas funciona.

Tava pensando aqui e saiu uma segunda solução mais simples, acho.
Para cada inteiro positivo [latex]k[/latex], seja [latex]a[/latex] tal que [latex]10^a\leq k< 10^{a+1}[/latex] e seja [latex]r[/latex] o resto da divisão de [latex]2008\cdot10^{a+1}[/latex] por k.
Nesse caso, [latex]0 < k-r < 10^{a+1}[/latex] e [latex]2008\cdot 10^{a+1}+k-r\equiv 0 \pmod{k}[/latex] e tal número satisfaz os múltiplos descritos no enunciado, de modo que [latex]k[/latex] é garboso.