Olimpíadas ⇒ Função Parte Inteira Tópico resolvido

[goncalves3718]

Sejam [tex3]a, m, b [/tex3] inteiros dados, com [tex3]mdc(a, m) = 1[/tex3].
Calcule [tex3]\sum_{x=0}^{m-1} \left\lfloor \dfrac{ax+b}{m}\right\rfloor[/tex3]

[Ittalo25MOD]

[tex3]\sum_{x=0}^{m-1} \left\lfloor \dfrac{ax+b}{m}\right\rfloor = \sum_{x=0}^{m-1} \frac{ax+b}{m} - \sum_{x=0}^{m-1} \big\{\frac{ax+b}{m}\big\}= \frac{a \cdot (m-1)}{2}+b - \sum_{x=0}^{m-1}\frac{(ax+b \space \space \mod(m))}{m}[/tex3]

agora a ideia vem dessa outra questão: viewtopic.php?f=20&t=90663

no conjunto dos resíduos módulo m: [tex3]\{0,1,2,3,4,...,m-1\} [/tex3].

Considere [tex3]x_1 [/tex3] e [tex3]x_2 [/tex3]:

Se [tex3]ax_1+b \equiv ax_2+b \mod(m)[/tex3]
Como mdc(a,m) = 1, então vale "cortar":
[tex3]ax_1 \equiv ax_2 \mod(m)[/tex3]
[tex3]x_1 \equiv x_2 \mod(m)[/tex3]
Portanto variando [tex3]x_1 [/tex3] e [tex3]x_2 [/tex3] em [tex3]\{0,1,2,3,4,...,m-1\} [/tex3] e [tex3]x_1 \neq x_2[/tex3] não tem como [tex3]ax_1+b \equiv ax_2+b \mod(m)[/tex3].

Ou seja, na soma: [tex3]\sum_{x=0}^{m-1}(ax+b \space \space \mod(m))[/tex3] temos m termos e eles são todos diferentes, ou seja, essa é a soma de todos os restos possíveis na divisão por m.

[tex3]\frac{a \cdot (m-1)}{2}+b - \sum_{x=0}^{m-1}\frac{(ax+b \space \space \mod(m))}{m} = \frac{a \cdot (m-1)}{2}+b -\frac{0+1+2+3+4+....+m-1}{m} =[/tex3]

[tex3]\frac{a \cdot (m-1)}{2}+b -\frac{m\cdot (m-1)}{2m} = \boxed{\frac{a\cdot (m-1)}{2}- \frac{m-1}{2}+b}[/tex3]

[goncalves3718]

O que são resíduos nunca entendo!?

[Ittalo25MOD]

O que são resíduos nunca entendo!?

resíduos módulo m são os restos possíveis que podem acontecer quando um número é dividido por m: [tex3]\{0,1,2,3,4,....,m-1\} [/tex3]
Exemplo: resíduos do 4: [tex3]\{0,1,2,3\} [/tex3]. Qualquer número que você divida por 4, vai ter um desses restos.

Também é comum representar os resíduos como classes de congruência, exemplo:
Classe de congruência [tex3]\overline{2} \mod(4)[/tex3].
[tex3]\overline{2} \mod(4)[/tex3] significa todos os números que deixam resto 2 quando divididos por 4: [tex3]\{2,6,10,14,....\} [/tex3]