Podzielność sumy przez 25 a 125

[xxDorianxx]

Witam wszystkich mam problem z następującym zadankiem:

Liczby całkowite \(\displaystyle{ a,b,c,d,e,f}\) są takie, że liczba \(\displaystyle{ a^5+b^5+c^5+d^5+e^5+f^5}\) jest podzielna przez \(\displaystyle{ 25}\). Udowodnij,że liczba

\(\displaystyle{ a^{25}+b^{25}+c^{25}+d^{25}+e^{25}+f^{25}}\) jest podzielna przez \(\displaystyle{ 125}\)

[Premislav]

Jeżeli \(\displaystyle{ 5}\) nie dzieli \(\displaystyle{ x}\), to z twierdzenia Eulera mamy \(\displaystyle{ x^{20}\equiv 1\pmod{25}}\). Mamy bowiem \(\displaystyle{ \phi(25)=20}\).
Poza tym jeżeli \(\displaystyle{ 5}\) dzieli \(\displaystyle{ x^5}\), to nawet \(\displaystyle{ 5^5}\) dzieli \(\displaystyle{ x^5}\), gdyż liczba \(\displaystyle{ 5}\) jest pierwsza.
Poradzisz sobie dalej?

[xxDorianxx]

Chyba trochę mam,poprawiaj mnie we wszystkim co jest źle.

Zadanie to trzeb rozwiązać w dwóch płaszczyznach.
1) Jeśli \(\displaystyle{ 5}\) dzieli \(\displaystyle{ a^5}\) (i tak samo resztę liczb)
2)Jeśli \(\displaystyle{ 5}\) nie dzieli \(\displaystyle{ a^5}\) (i tak samo resztę liczb)

ad 1)
załóżmy więc,że \(\displaystyle{ 5}\) dzieli \(\displaystyle{ a ^{5}}\) to nawet \(\displaystyle{ 5^3}\) dzieli \(\displaystyle{ a^5}\) więc też \(\displaystyle{ 5^3}\) dzieli \(\displaystyle{ a^{25}}\).Podobnie wykazujemy to dla pozostałych liczb więc też nasza suma jest podzielna przez \(\displaystyle{ 125}\)
ad 2)
No i tutaj już mam problem mam jedynie takie coś:
\(\displaystyle{ \phi(125)=100}\) a więc \(\displaystyle{ a^{100}\equiv 1\pmod{125}}\) to też,
\(\displaystyle{ \left( a^{25}\right)^4\equiv 1\pmod{125}}\) a więc też \(\displaystyle{ a^{25}\equiv 1\pmod{125}}\)

[Premislav]

\(\displaystyle{ \left( a^{25}\right)^4\equiv 1\pmod{125}}\) a więc też\(\displaystyle{ a^{25}\equiv 1\pmod{125}}\)

Skąd taki wniosek?

Sorry, jednak z tej mojej wskazówki tylko tyle da się wynieść, że
\(\displaystyle{ a^{25}+b^{25}+c^{25}+d^{25}+e^{25}+f^{25}\pmod{125}\in \left\{ 0,25, 50, 75, 100\right\}}\)
Spróbujmy inaczej. Z MTF natychmiast dostajemy \(\displaystyle{ a+b+c+d+e+f\equiv 0\pmod{5}}\).
Rozważmy następujące przypadki:
1) wśród liczb \(\displaystyle{ a,b,c,d,e,f}\) istnieją takie \(\displaystyle{ x,y}\), że \(\displaystyle{ x+y\equiv 0\pmod{5}}\),
wówczas problem daje się zredukować (czy znasz Lifting the Exponent Lemma?) do sumy piątych/dwudziestych piątych potęg czterech pozostałych liczb, a to już się daje ze wzoru dwumianowego Newtona nawet (dla ustalenia uwagi \(\displaystyle{ (a^5+b^5)\equiv -(c^5+d^5)\pmod{25}}\) i podnosimy do piątej potęgi)
2) zaprzeczenie jedynki, to daje baardzo forsowną sprzeczność modulo \(\displaystyle{ 25}\).

Myślę jednak, że powinno istnieć ładniejsze rozwiązanie, tylko że ja nie potrafię go niestety wymyślić.-- 20 lip 2018, o 15:40 --Szczerze mówiąc trochę mnie to boli, że nie mogę tego zaprzeczenia 1) zapisać zgrabniej niż tak:
a) jedna liczba podzielna przez \(\displaystyle{ 5}\) i pięć o tej samej, niezerowej reszcie z dzielenia przez \(\displaystyle{ 5}\). Z LTE (choć można to też ze wzoru dwumianowego bez problemu rozpisać)
jeśli \(\displaystyle{ a\equiv r\pmod{5}, \ r\neq 0}\), to \(\displaystyle{ a^5\equiv r^5\pmod{25}}\), a oczywiście liczba \(\displaystyle{ 5r^5}\) nie dzieli się przez \(\displaystyle{ 25}\), gdy \(\displaystyle{ 5\nmid r}\).
b) [piszę resztami z dzielenia \(\displaystyle{ a,b,c,d,e,f}\) przez \(\displaystyle{ 5}\)]: dwie trójki i cztery jedynki;
c) cztery czwórki i dwie dwójki

Innych przypadków nie ma, ale niestety nie widzę innego sposobu, by to pokazać, niż żmudne obliczenia.

[Premislav]

Ponieważ ten szkic powyżej to straszna brzydota, a może ktoś jeszcze będzie tego potrzebował, postanowiłem umieścić tutaj rozwiązanie, które jest owocem mojej wymiany wiadomości z xxDorianxx.
Jak się okazuje, można było trafić na następujące wskazówki:
1. uzasadnić, że jeśli \(\displaystyle{ 25}\) dzieli \(\displaystyle{ a+b}\), to \(\displaystyle{ 125}\) dzieli \(\displaystyle{ a^5+b^5}\)
2. wykazać, że jedyne możliwe reszty z dzielenia piątej potęgi liczby całkowitej przez \(\displaystyle{ 25}\) to \(\displaystyle{ 0, \ \pm 1, \ \pm 7}\).

Dowód faktu z \(\displaystyle{ 1.}\) (postulowałem w poprzedniej wiadomości użycie Lifting the Exponent Lemma, ale da się jednak dużo bardziej elementarnie, z czego później zdałem sobie sprawę):
ze wzoru na sumę n-tych potęg dla nieparzystego \(\displaystyle{ n}\) i ze wzoru na \(\displaystyle{ (a+b)^4}\) mamy
\(\displaystyle{ a^5+b^5=\\=(a+b)(a^4-a^3b+a^2b^2-ab^3+b^4)=\\=(a+b)(a^4+4a^3b+6a^2b^2+4ab^3+b^4-5(a^3b+a^2b^2+ab^3))=\\=(a+b)^5-5(a+b)(a^3b+a^2b^2+ab^3)}\),
stąd już nietrudno wywnioskować, że jeśli \(\displaystyle{ a,b\in \ZZ}\) są takie, że \(\displaystyle{ 25}\) dzieli \(\displaystyle{ a+b}\), to \(\displaystyle{ 125}\) dzieli \(\displaystyle{ a^5+b^5}\).

Dowód faktu z \(\displaystyle{ 2.}\):
oczywiście jeżeli \(\displaystyle{ x\equiv 0\pmod{5}}\), to mamy \(\displaystyle{ x^5\equiv 0\pmod{5^5}}\), w szczególności \(\displaystyle{ x^5\equiv 0\pmod{25}}\). Niech teraz \(\displaystyle{ \ZZ\ni x}\) będzie takie, że \(\displaystyle{ 5\nmid x}\). Wówczas, jak już pisałem w pierwszej wskazówce, z twierdzenia Eulera mamy, że \(\displaystyle{ x^{20}\equiv 1\pmod{25}}\). Zatem jeżeli \(\displaystyle{ 5\nmid x}\) i oznaczymy \(\displaystyle{ t=x^5}\), to
\(\displaystyle{ t^4\equiv 1\pmod{25}}\), równoważnie:
\(\displaystyle{ (t^2-1)(t^2+1)\equiv 0\pmod{25}}\)
Oczywiście liczby \(\displaystyle{ (t-1)(t+1)=t^2-1}\) oraz \(\displaystyle{ t^2+1}\) różnią się o liczbę niebędącą wielokrotnością \(\displaystyle{ 5}\), więc co najwyżej jedna z nich dzieli się przez \(\displaystyle{ 5}\). W dalszej perspektywie \(\displaystyle{ t^2-1=(t-1)(t+1)}\) i znów najwyżej jeden z tych czynników może być podzielny przez \(\displaystyle{ 5}\). Czyli dokładnie jeden z czynników \(\displaystyle{ t-1, \ t+1, \ t^2+1}\) dzieli się przez \(\displaystyle{ 25}\). To daje nam takie oto przypadki do rozważenia:
a) \(\displaystyle{ t-1\equiv 0\pmod{25}}\), wówczas oczywiście \(\displaystyle{ t\equiv 1\pmod{25}}\);
b) \(\displaystyle{ t+1\equiv 0\pmod{25}}\), wtedy po prostu \(\displaystyle{ t\equiv 24\pmod{25}}\) (czy jak kto woli, \(\displaystyle{ t\equiv -1\pmod{25}}\));
c) \(\displaystyle{ t^2+1\equiv 0\pmod{25}}\), widzimy, że jest to spełnione, gdy \(\displaystyle{ t\equiv 7\pmod{25}}\). Ponadto uzasadnimy, że jest jeszcze tylko jedna możliwość.
Przypuśćmy, że \(\displaystyle{ p>q, \ p, q\in \left\{ 1,2\ldots 24\right\}}\) (zera nie bierzemy pod uwagę, gdyż w oczywisty sposób nie spełnia warunku \(\displaystyle{ t^2+1\equiv 0\pmod{25}}\)) są takie, że
\(\displaystyle{ p^2+1\equiv 0\pmod{25}}\) oraz \(\displaystyle{ q^2+1\equiv 0\pmod{25}}\).
Wówczas \(\displaystyle{ 25}\) dzieli też różnicę, czyli
\(\displaystyle{ p^2-q^2\equiv 0\pmod{25}\\(p-q)(p+q)\equiv 0\pmod{25}}\)
Skoro \(\displaystyle{ p>q}\), to \(\displaystyle{ 25\nmid (p-q)}\), bo \(\displaystyle{ p-q\in \left\{ 1,2, \ldots 23\right\}}\).
Ponadto liczby \(\displaystyle{ p+q, \ p-q}\) różnią się o niepodzielną przez \(\displaystyle{ 5}\) liczbę \(\displaystyle{ 2q}\) (niepodzielną, gdyż \(\displaystyle{ 5\nmid q}\), a tak jest, bo gdyby \(\displaystyle{ 5|q}\), to \(\displaystyle{ q^2+1\equiv 1\pod{25}}\)), a stąd już wynika, że
\(\displaystyle{ 25|(p+q)}\).
Jednakże \(\displaystyle{ 2\le p+q\le 48}\), stąd musi być \(\displaystyle{ p+q=25}\), czyli \(\displaystyle{ q=25-p}\).
Zatem skoro już powiedzieliśmy, że działa \(\displaystyle{ t\equiv 7\pmod{25}}\), to drugą i ostatnią możliwością jest \(\displaystyle{ t\equiv 18\pmod{25}}\) (czy jak kto woli, co będzie wygodniejsze w zapisie, \(\displaystyle{ t\equiv -7\pmod{25}}\)).
Podsumowując, wykazaliśmy, że \(\displaystyle{ x^5\pmod{25}\in\left\{ -7, -1, 0, 1, 7\right\}}\).

Teraz już łatwo dowodzimy (wystarczy zauważyć, że piątych potęg dających resztę \(\displaystyle{ 7}\) musi być tyle samo, co dających resztę \(\displaystyle{ -7}\) z dzielenia przez \(\displaystyle{ 25}\) i dalej samo idzie), że skoro
\(\displaystyle{ a^5+b^5+c^5+d^5+e^5+f^5\equiv 0\pmod{25}}\),
to \(\displaystyle{ a,b,c,d,e,f}\) da się dobrać w pary, w których zachodzi
\(\displaystyle{ x^5+y^5\equiv 0\pmod{25}}\), a zatem na mocy \(\displaystyle{ 1.}\) wtedy \(\displaystyle{ x^{25}+y^{25}\equiv 0\pmod{125}}\) w każdej takiej parze.