Ensino Superior ⇒ Soma dos restos de uma divisão

[Superaks]

Seja x e y inteiros positivos e considere r(x, y) sendo o resto da divisão de x por y, encontre o menor x tal que r(m, 1) + r(m, 2) + ... + r(m, 10) = 5

[leozitz]

alguém tem alguma ideia???
aparentemente a resposta é

Resposta

---

540

eu encontrei usando um programa

[leozitz]

note que a gente precisa zerar alguns desses restos se não a gente vai uma soma muito grande
digamos que a gente zere o resto mod a, mas se 2a <= 10 vamos ter o seguinte
[tex3]m = k\cdot a = 2a + r\implies r\equiv 0 \pmod a[/tex3] e com isso a gente vai ter a "muito grande" ou a gente vai ter que incluir todo multiplo daquele número q está no intervalo
primeiro caso: m par)
m = 2k
[tex3]2k = 4q_4 + r_4\implies r_4 = 0[/tex3] ou r_4 é par e como o outro único par possível é 2
subcaso 1: r_4 = 2
se [tex3]r_4 = 2[/tex3] temos [tex3]4q_4 + 2 = 8q_8 + r_8[/tex3] r_8 é par e não pode ser 0 e nem 4 (olha a igualdede mod 4) e tbm n pode ser nada maior pq se não a soma iria passar então r_8 é 2
[tex3]r(m, 3) + r(m, 5) + r(m, 6) + r(m, 9) + r(m, 7) + r(m, 10) = 1[/tex3]
se k não é divisível por 3 e nem por 5 vamos ter um problema, então k é divisível por esses 2
(se k não é divisível por 3 então r(m, 3) > 0 e r(m, 6) > 0, algo semelhante vale para o 5)
[tex3]m = 2\cdot 3\cdot 5x = 8q_4 + 2[/tex3]
agora com a mesma ideia r(m, 9) = 0 ou pelo menos 3, como 3 > 1 então [tex3]m = 2\cdot9\cdot5\cdot x = 8q_8 + 2 \equiv 1 \pmod 7[/tex3]
precisamos encontrar o menor número da forma [tex3]2\cdot9\cdot5\cdot x \equiv 2\pmod 8\implies 9\cdot5x \equiv 1\pmod 4[/tex3] e [tex3]2\cdot9\cdot5\cdot x\equiv 1 \pmod 7\\6x\equiv 1 \pmod 7[/tex3]

pela primeira x = 4t + 1, vamos substituir na segunda
[tex3]24t + 6\equiv 1 \pmod 7\implies 3t \equiv 2\pmod 7\implies -t\equiv 4 \pmod 7\implies t \equiv 3\pmod 7[/tex3]
x = [tex3]4(3 + 7a) + 1[/tex3] selecionando o menor a possivel encontramos [tex3]x = 13[/tex3] kkkkkkkkk, muito trabalho para um número pequeno
então melhor que temos até agora é [tex3]m=2\cdot9\cdot5\cdot 13 = 1170[/tex3]

subcaso 2: r_4 = 0
subcaso do subcaso
se r_8 for 4 vamos ter [tex3]r(m, 3) + r(m, 5) + r(m, 6) + r(m, 9) + r(m, 7) + r(m, 10) = 1[/tex3] de novo e vamos poder usar basicamente a mesma ideia para argumentar que m é divisível por 9 e 5 e é 1 mod 7
agora precisamos encontrar o menor número [tex3]4\cdot 9\cdot5\cdot x\equiv 4\pmod 8[/tex3] e [tex3]4\cdot 9\cdot5\cdot x\equiv 1 \pmod 7[/tex3]
a ideia para encontrar o x é o mesmo da solução anterior, multiplica pelo inverso até encontrar x congruente a alguma coisa mod 4 e substitui na outra, vou usar o wolfram para encontrar
ai no caso a gente encontra [tex3]m = 540[/tex3]

se m for divisível por 8 vamos ter [tex3]r(m, 3) + r(m, 6) + r(m, 5) + r(m, 7) + r(m, 10) + r(m, 9) = 5[/tex3]

se m é ímpar vamos ter o seguinte r(m, 2), r(m, 4), r(m, 6), r(m, 8 ), r(m, 10) são todos pelos menos 1 dai necessariamente eu preciso ter m divisível por 9, por 7 e por 5 se n deixa resto e a gente vai ter uma soma muito grande porem m = 3a já que é divisivel por 9 e m = 6b + 1 mas isso é claramente um absurdo já que 1 não é divisivel por 3

se eu n errei nada ainda falta fazer o caso em que m é divisível por 8 e o melhor até agora foi m = 540 mas essa solução está muito chata, depois termino

[JigsawMOD]

@cajuADMIN poderia confirmar se a resolução apresentada contempla a referida questão.