ostatnie trzy cyfry

[leszczu450]

Cześć

Mam takie zadanie:
Znajdź ostatnie trzy cyfry liczby \(\displaystyle{ 7^{14404}}\)


Chodzi zapewne o reszte z dzielenia tej liczby przez \(\displaystyle{ 1000}\).
Jednak nie za bardzo wiem od czego wyjść. Przeczytałem gdzieś, że w tego typu zadanich przydaje się funkcja Eulera. Jednak nie rozumiem jej działania.

Proszę Was o pomoc z tym zadaniem i wytłumaczenie o co chodzi z tą funkcją

Z góry dzięki!

[yorgin]

Nie wiem, jak funkcja Eulera może pomóc, ale można posłużyć się operacją modulo:

\(\displaystyle{ 7^4\equiv 401 \mod 1000}\)

I dalej łatwo wyznacza się:

\(\displaystyle{ 7^8\equiv 801 \mod 1000}\)

\(\displaystyle{ 7^{16} \equiv 601 \mod 1000}\)

\(\displaystyle{ 7^{24} \equiv 401\mod 1000}\)

I mamy zapętlanie się reszt.

[leszczu450]

yorgin, skąd wiesz jaka jest reszta z dzielenia dla \(\displaystyle{ 7^{16}}\) i tak dalej? Może czegoś nie umiem. Przyznam, że miałem z tego tylko jedne ćwiczenia. Wyjaśniłbyś mi trochę więcej ? : )

[yorgin]

Wiesz jak działa operacja modulo? Na niej wszystko bazuje.

Wiem, że \(\displaystyle{ 7^4\equiv 401\mod 1000}\)

więc

\(\displaystyle{ (7^4)^2\equiv (401)^2\mod 1000}\)

a to ostatnie jest równe \(\displaystyle{ 160801}\) więc mam

\(\displaystyle{ 7^8\equiv 801\mod 1000}\)

itd

[leszczu450]

yorgin, czyli bierzesz kalkulator w ręke i to liczysz tak?. Czyli musisz policzyć najpierw ile to jest \(\displaystyle{ 7^4}\) potem \(\displaystyle{ 7^8 , 7^{16} , 7^{24}}\) i na dobra sprawe jeszcze \(\displaystyle{ 7^{32}}\) żeby zobaczyć, że te reszty powtarzają się cyklicznie. A co byś zrobił gdybyś nie miał kalkulatora? Bo ja mam tak to właśnie zrobić : )

-- 9 mar 2013, o 14:38 --

I błąd mały Ci się chyba wkradł : )

-- 9 mar 2013, o 14:48 --

yorgin, tutaj:
\(\displaystyle{ (7^2)^2\equiv (401)^2\mod 1000}\)

Powinno być:
\(\displaystyle{ (7^4)^2\equiv (401)^2\mod 1000}\)

Ale to takie tam estetyczne poprawki : )

[yorgin]

Chwilka, zjem obiad i napiszę więcej

[leszczu450]

yorgin, smacznego : ) u mnie teź lasagne już w piekarniku : P

[yorgin]

Okej, babole poprawione. Tak to jest, jak się człowiek spieszył na obiad

W tym zadaniu oczywiście bez kalkulatora wszystko da się bardzo łatwo policzyć.

\(\displaystyle{ 7^4=2401}\)

i to liczy się w kilka sekund.

Mamy więc

\(\displaystyle{ 7^4\equiv 401\mod 1000}\)

Teraz podnosimy obie strony do kwadratu

\(\displaystyle{ 7^8\equiv 401^2\mod 1000}\)

Zauważ, że ja wcale nie liczę \(\displaystyle{ 7^8}\), tylko resztę z dzelenia przez \(\displaystyle{ 1000}\).

Łatwo też bez kalkulatora policzyć, że \(\displaystyle{ 401^2=160801}\).

A więc

\(\displaystyle{ 7^8\equiv 801\mod 1000}\)

Znów podnosimy do kwadratu i skracamy modulo \(\displaystyle{ 1000}\), wychodzi

\(\displaystyle{ 7^{16}\equiv 601\mod 1000}\)

Na końcu mnożę ostatnie dwie równości stronami:

\(\displaystyle{ 7^8\cdot 7^{16}\equiv 801\cdot 601\mod 1000}\)

I wychodzi

\(\displaystyle{ 7^{24}\equiv 401\mod 1000}\)

Wszystkie te rachunki dają się zrobić "pod kreską".

[Qń]

Można też tak:

Z dostajemy, że:
\(\displaystyle{ 7^{\phi (1000)}\equiv 1 \pmod{1000}}\)
Ponieważ:
\(\displaystyle{ \phi (1000) = 1000 \cdot \left( 1-\frac 12\right) \cdot \left( 1- \frac 15\right) =400}\)
więc mamy:
\(\displaystyle{ 7^{400}\equiv 1 \pmod{1000}}\)
a po podniesieniu do \(\displaystyle{ 36}\)-tej potęgi:
\(\displaystyle{ 7^{14400}\equiv 1 \pmod{1000}}\)
czyli po pomnożeniu stronami przez \(\displaystyle{ 7^4}\):
\(\displaystyle{ 7^{14404}\equiv 7^4=2401 \equiv 401 \pmod{1000}}\)

Q.

[yorgin]

Qń, ja patrzyłem tylko na funkcję Eulera, zapomniawszy o twierdzeniu Eulera, być może dlatego, że moja wiedza z reguły ogranicza się do własności kongruencji, a twierdzeń z reguły nie pamiętam.

[leszczu450]

yorgin, super wielkie dziękie dla Ciebie! Kłaniam się! : )
Qń, wyjaśniłbyś mi o co dokładnie chodzi z tą funkcją ? Czemu tak to liczysz?

[Qń]

Q.

[leszczu450]

Qń, własnie czytam i już rozumiem. Jednak mam problem z ustaleniem czynników pierwszych. Chodzi o to, że każda liczbę mogę zapisać jako iloczyn liczb pierwszych? I te własnię liczby pierwsze, czasami z potęgami to są te czynniki właśnie?

[yorgin]

Z twierdzenia o rozkładzie każda liczba całkowita jest odpowiedniej postaci - iloczyn pewnej liczby liczb pierwszych wraz z ich potęgami.

\(\displaystyle{ 1000}\) rozkłada się bardzo łatwo:

\(\displaystyle{ 1000=10^3=(2\cdot 5)^3=2^3\cdot 5^3}\)

i już masz rozkład + podstawkę pod twierdzenie.

[leszczu450]

yorgin, super Wam dziękuję : ) I sama funkcja Eulera mówi ile jest liczb mniejszych od danej, które są z nią względnie pierwsze, tak?