Остатък при делене

[b1ck0]

Да се пресметне остатъка, когато
[tex]\sum_{k=1}^{30303} k^k[/tex]
се раздели на 101

[martin123456]

29?

[b1ck0]

Продължаваш да ме радваш. Как я реши .. ?

[nikko]

101 - просто, [tex]\varphi(101)=100[/tex] и тогава ако [tex]\overline{k}[/tex] е остатъка от деленето на k на 101, то
[tex]k^k\equiv k^{\overline{k}}(\text{mod}\;101)[/tex]
Първите 30000 събираеми се групират в 300 групи от вида:
[tex]1^1,2^2,\dots,100^{100},0[/tex]
[tex]1^2,2^3,\dots,100^1,0[/tex]
[tex]\dots,\dots,\dots[/tex]
[tex]1^{100},2^1,\dots,100^{99},0[/tex]
Сумираме по стълбове и имаме суми от вида [tex]\sum\limits_{i=1}^{100}{j^i}[/tex] за j=1,2,...,100.
Освен това всяка сума [tex]\sum\limits_{i=1}^{100}{j^i}[/tex] дава остатък 0 при делене със 101 (като пълна система остатъци без нулата това са всички остатъци {1,2,...,100} със сума 5050, което се дели на 101).
Остават 300 единици от 300-та групи, както и още три събираеми [tex]1^1+2^2+3^3=32[/tex] и
окончателно [tex]300+32\equiv 29(\text{mod}\;101)[/tex]

[martin123456]

ами това ми е рождената дата
Нека подредим числата в таблица, всеки ред на който съдържа 101 елемента. Тогава [tex]a_{ij}=(101(i-1)+j)^{101(i-1)+j}[/tex], където индексите са базирани на числото 1. T.e. ако [tex](j,101)=1[/tex], то [tex]a_{ij}=(101i-101+j)^{101i-101+j} \equiv j^{100i+i-100-1+j} \equiv j^{i+j-1}[/tex] - това е така понеже [tex](n,101) =1 \Rightarrow n^{100} \equiv 1 \pmod {101}[/tex]. Тъй като [tex]300.101 = 30300[/tex], то имаме [tex]300[/tex] реда и остава сумата на [tex]30301^{30301}+30302^{30302}+30303^{30303}[/tex]. Като използваме горното за последната сума получаваме че тя е [tex]=a_{301,1}+a_{301,2}+a_{301,3} \equiv 1^{301+1-1}+2^{301+2-1}+3^{301+3-1} \equiv 1+2^{1+2-1}+3^{1+3-1} \equiv 1+2^2+3^3[/tex]. Първата колона на таблицата се състои само от единици и значи сумата им е [tex]300 \equiv -3 \pmod{101}[/tex]. Сега нека разгледаме една от 101 суми с вид [tex]\sum_{i=1}^{300}j^{i+j-1}[/tex] и нека [tex]j \ne 1[/tex]. Тази сума е [tex]j^j\sum_{i=1}^{300}j^{i-1}=j^j\sum_{i=0}^{299}j^i=j^j[(\sum_{i=0}^{99}j^i)+(\sum_{i=100}^{199}j^i)+(\sum_{i=200}^{299}j^i)]\equiv j^j[(\sum_{i=0}^{99}j^i)+(\sum_{i=0}^{99}j^i)+(\sum_{i=0}^{99}j^i)][/tex][tex]\equiv 3j^j(\sum_{i=0}^{99}j^i)[/tex]. В последната сума участват [tex]100[/tex] числа. Никой 2 от тях не са конгруентни [tex]\pmod{101}[/tex], значи сумата е [tex]\sum_{i=1}^{100}i=\frac{100.101}{2} \equiv 0 \pmod{101}[/tex]. Значи отговорът е [tex]1+2^2+3^3-3=29[/tex].

[b1ck0]

Не ми остана друго освен да ви покажа и "официалното решение":