reszta z dzielenia 1111^4444

[MattiS]

Witajcie

Wszystkeigo naj z okazji swiat i wszystkiego naj w Nowym Roku.
Przepraszam ze w przerwie swiatecznej, zaprzatam wasze tegie glowy do pracy, ale mam problem.

Oblicz reszte z dzielenia \(\displaystyle{ 1111^{4444}:21}\)
znam wynik 16

ale ni huu wiem jak to udowodnic. Probowalem z malego tw. fermata, ale sie zawiesilem.

Jakby ktos znalazl wolna chwilke, i moglby krok po kroku zaprezentowac rozwiazanie, bylbym dzwieczny

Pozdrawiam

[natkoza]

\(\displaystyle{ NWD(21,111)=1}\), więc z tw. Eulera mamy:
\(\displaystyle{ \phi(21)=\phi(3\cdot 7)=\phi(3)\cdot \phi(7)=2\cdot 6=12}\)
czyli:
\(\displaystyle{ 1111^{12}\equiv 1(mod 21)\\
1111^{4444}=1111^{12\cdot 370+4}=1111^{12\cdot 370}\cdot 1111^4=(1111^{12})^{370}\cdot 1111^4=(1111^{12})^{370}\cdot (11\cdot 101)^4=(1111^{12})^{370}\cdot 11^4\cdot 101^4=(1111^{12})^{370}\cdot 11^2\cdot 11^2\cdot 101^2\cdot 101^2\equiv 1\cdot 16\cdot 16\cdot 16\cdot 16(mod 21)\equiv 1\cdot 4\cdot 4(mod 21)=16(mod 21)}\)
mam nadzieję, ze sie nigdzie nie pomyliłam

[MattiS]

natkoza, bardzo dziekuje Tylko ze jak dla mnie to czarna magia Ale dziekuje Skad sie wzial przedostatni zapis? skad sie tam biora 16tki jak w poprzednim ich nie bylo?

BTW mozna to innym sposobem udowodnic? stosujac techniki na poziomie liceum? bo Eulera i kongruencji nie ma w programie. I nauczycielka i tak by mi nie uwierzyla ze to ja do czegos takiego doszedlem, nawet gdybym to dobrze wytlumaczyl... Moze jest jakis inny sposob?

[dabros]

121 przystaje do 16 modulo 21
tak samo 101^{2}
stąd te 16

[Piotr Rutkowski]

natkoza korzysta z tw. Eulera czyli:
Jeżeli liczby naturalne a oraz n spełniają warunek \(\displaystyle{ NWD(a,n)=1}\), to \(\displaystyle{ n|a^{\phi(n)}-1}\) gdzie \(\displaystyle{ \phi(n)}\) oznacza ilość wszystkich liczb naturalnych mniejszych od n i względnie z nim pierwszych. W naszym przypadku \(\displaystyle{ a=1111 \ n=21}\)
Reszta to zwykłe kongruencje przy czym "skróty myślowe" to:
\(\displaystyle{ 101^{2} \equiv 16 \ (mod21)}\)
\(\displaystyle{ 121\equiv 16 \ (mod21)}\)
\(\displaystyle{ 16*16\equiv 4 \ (mod21)}\)

[MattiS]

Czy waszym zdaniem jest mozliwe aby rozwiazal to zwykly smiertelnik z liceum, bez pomocy osob trzecich? korzystajac tylko z podrecznikow do liceum?

[Piotr Rutkowski]

No, bez kongruencji może niekoniecznie, ale można zadanie prościej zrobić:
\(\displaystyle{ 1111\equiv -2 \ (mod21)}\)
\(\displaystyle{ 1111^{4444}\equiv (-2)^{4444}=2^{4444} \ (mod21)}\)
\(\displaystyle{ 2^{4444}=2^{4}*2^{4440}=16*(2^{6})^{720}\equiv 16*1^{720}\equiv 16 \ (mod21)}\)

[MattiS]

czyli bez doksztalcenia sie z materialow przekraczajacych zakres liceum sie nie obedzie;)

[dabros]

dlaczego?
kongruencje są w dobrych podręcznikach do liceum

[Piotr Rutkowski]

Wiesz, jeśli się uprzeć to można to wszystko napisać bez użycia kongruencji ztymże wtedy musiałbyś dorzucić mnóstwo komentarzy.

[MattiS]

eh, dostalismy takie zadanko na swieta zeby sie nie nudzilo ;p a nic z tych rzeczy o ktorych wyzej mowa nie bralismy, ani nie mielismy dostepu, oprocz oczywiscie forow zobaczymy jutro lub pojutrze w szkole, czy ktos to zrobil

[ Dodano: 1 Stycznia 2008, 21:34 ]
dabros, wyglada na to, ze u nas takowych nie ma ;(