Podzielność przez 1991

[Elayne]

Udowodnij, że jeśli \(\displaystyle{ m}\) kończy się cyfrą pięć, wówczas \(\displaystyle{ 1991 \ | \ 12^m + 9^m + 8^m + 6^m}\).

[Premislav]

\(\displaystyle{ 1991=11\cdot 181}\),
czyli wystarczy, że sprawdzimy podzielność przez \(\displaystyle{ 11}\) i przez \(\displaystyle{ 181}\) (oczywiście są to liczby względnie pierwsze).
Z małego twierdzenia Fermata wiemy, że gdy \(\displaystyle{ 11\nmid a}\), to \(\displaystyle{ a^{10}\equiv 1\pmod{11}}\).
Zatem jeśli chodzi o podzielność przez \(\displaystyle{ 11}\), sprawa upraszcza się nam do sprawdzenia, że
\(\displaystyle{ 11|12^5+9^5+8^5+6^5}\).
Z tym nie ma wielkiego problemu:
\(\displaystyle{ 12^5=3^5\cdot 2^{10}, \ 9^5=3^{10}, \ 8^5=2^{15}}\), więc z poprzedniej uwagi mamy
\(\displaystyle{ 12^5+9^5+8^5+6^5\equiv (3^5+1+2^5+6^5)\pmod{11}}\)
a to już trywialne, wystarczy zauważyć, że \(\displaystyle{ a+b+ab+1=(a+1)(b+1)}\) dla \(\displaystyle{ a=2^5, \ b=3^5}\) (no albo na odwrót) i wychodzi.

Teraz trudniejsza sprawa, czyli podzielność przez \(\displaystyle{ 181}\).
Zachodzi równość
\(\displaystyle{ a^{5(k+1)}+b^{5(k+1)}=(a^5+b^5)(a^{5k}+b^{5k})-(ab)^5(a^{5(k-1)}+b^{5(k-1)})}\)
Dzięki tej tożsamości i odrobinie żmudnych obliczeń wykażemy, że \(\displaystyle{ 181|6^{5k}+8^{5k}}\)
oraz że \(\displaystyle{ 181|12^{5k}+9^{5k}}\) gdy \(\displaystyle{ k}\) jest liczbą nieparzystą (więcej nie potrzebujemy, jakby była parzysta, to wykładnik dzieliłby się przez \(\displaystyle{ 10}\)).
Otóż ze wzorów skróconego mnożenia
\(\displaystyle{ 6^5+8^5=(6+8)(6^4-8\cdot 6^3+8^2\cdot 6^2-8^3\cdot 6+8^4)=\\=(6+8)(100^2-48\cdot 148)=14\cdot 16\cdot (625-444)=14\cdot 16\cdot 181}\)
a to jest tak raczej podzielne przez \(\displaystyle{ 181}\).
Stąd z wykorzystaniem indukcji i wspomnianej tożsamości \(\displaystyle{ a^{5(k+1)}+b^{5(k+1)}=(a^5+b^5)(a^{5k}+b^{5k})-(ab)^5(a^{5(k-1)}+b^{5(k-1)})}\)
dowodzimy z łatwością, że dla dowolnego \(\displaystyle{ k}\) nieparzystego \(\displaystyle{ 181|6^{5k}+8^{5k}}\).
Podobnie robimy z \(\displaystyle{ 9^{5k}+12^{5k}}\) dla \(\displaystyle{ k}\) nieparzystego:
\(\displaystyle{ 9^5+12^5=(\text{ pimpirimpim} )=243\cdot 7\cdot 181}\)
i to się okazuje podzielne przez \(\displaystyle{ 181}\).
Dalej indukcja i koniec.

[a4karo]

Dla \(\displaystyle{ m}\) kończących się na \(\displaystyle{ 5}\) mamy
Fakt 1: \(\displaystyle{ 11|3^m+2^m}\), bo \(\displaystyle{ 3^{m+10}+2^{m+10}=(3^m+2^m)\cdot 3^{10}+2^m(2^{10}-3^{10})=(3^m+2^m)\cdot 3^{10}-2^m\cdot 2^2\cdot 11\cdot 211}\)

Fakt 2: \(\displaystyle{ 181|4^m+3^m}\), bo \(\displaystyle{ 4^{m+10}+3^{m+10}=(4^m+3^m)\cdot 4^{10}+3^m(3^{10}-4^{10})=(4^m+3^m)\cdot 3^m\cdot 7\cdot 11\cdot 71\cdot 181}\)

Stąd

\(\displaystyle{ 12^m+9^m+8^m+6^m=(4^m+3^m)(3^m+2^m)=11\cdot 181\cdot \mathrm{cos}=1991\cdot\mathrm{cos}}\)


Nienawidzę Premislava

[Premislav]

Zgłaszam do komisji europejskiej (celowo małymi literami) za sianie nienawiści.

No cóż, dużo prostsze rozwiązanie, ale nie każdy jest inteligentny, ja bym na to nie wpadł.