Dwie ostatnie cyfry liczby

[kaszlok]

Witam, gdy trzeba policzyc dwie ostatnie cyfry liczby i liczby sa wzglednie pierwsze to wiem jak policzyc

np. z 3^1000 nie mam problemu, ale nie wiem co począć gdy jest np 2^1000 i gdy liczby w takim wypadku 2,100 nie są wzglednie peirwsze. Co trzeba wtedy zrobic ?

[kacper218]

Badasz resztę z dzielenia tej liczby przez 100.

[kaszlok]

W jaki sposób ? Miałem napisane, że 100 = 2^2 * 5^2

a potem gcd(4,25) = 1 i gcd (2,25)=1 nie wiem tylko po co i z czego to wynika

[kacper218]

Ty mówisz zapewne o algorytmie Euklidesa
Ja mówię o kongruencjach.

[kaszlok]

My liczyliśmy na podst. gcd czyli Euklides i tw. Eulera.

Moglbys pokazac na tym przykladzie jak to policzyć ?


Dla 3^1000 to było tak:

\(3^{1000} = ? (mod 100)\)

\(gcd(3,100)=1\)

\(\varphi (100) = 40\)

tw. eulera: \(3^{40} = 1 (mod 100)\)
\(3^{1000} = 1 (mod 100)\)

czyli ostatnie dwie to "\(01\)".

[patryk00714]

Twierdzenie Eulera jest najlepsze do tego

[kaszlok]

Ale jak to zastosować do 2^1000 to nie mam pojęcia..

[kaszlok]

Zrobiłem to kongruencjami i na końcu dostałem x = 100u+ 76 czyli dwie ostatnie cyfry to 7 i 6 ?

[kacper218]

Tak. To dobrze nie muszę pisać rozwiązania

[kacper218]

W jaki sposób ? Miałem napisane, że 100 = 2^2 * 5^2

a potem gcd(4,25) = 1 i gcd (2,25)=1 nie wiem tylko po co i z czego to wynika

W tym przypadku korzystamy z chińskiego twierdzenia o resztach i możemy nasze równanie zapisać jako układ równań:
\(\begin{cases}
x\equiv 2^{1000} (mod \ 4)\\
x \equiv 2^{1000} (mod \ 25)
\end{cases}\)
I rozwiązujesz ten układ równań
Pierwsze oczywiste. Drugie z twierdzenia Eulera się liczy

[kaszlok]

Dlaczego pierwsze oczywiste ?

[patryk00714]

\(2^{1000}=4^{500}\)

[kaszlok]

No tak to wiem, i reszta 0, tyle że my to zapisywaliśmy tak:

\(2^{1000} \equiv ? (mod \ 4)\).


Zastanawiam się tylko czemu było sprawdzane gcd(4,25)

zamiast gcd(2,4)

bo jest 2^1000 = ? (mod4) a nie 2^1000 = ? (mod 25)

[kacper218]

to wynika właśnie z założeń twierdzenia z którego skorzystałem. Te liczby na które rozkładamy 100 muszą być względnie pierwsze