2 ostatnie cyfry liczby. pytanie!

[amave]

witam
mam pytanie: czy jeżeli mam wyznaczyć dwie ostatnie cyfry liczby \(\displaystyle{ 12^{13 ^{14} }}\) to czy konieczne jest rozdzielenie tego na \(\displaystyle{ (3 \cdot 4)^{13^{14}}}\) czy można od razu wyliczyć z \(\displaystyle{ 12^{13 ^{14} }}\)?
na kolokwium policzyłam zadanie drugim sposobem i niestety zadanie za 10 punktów zostało wyzerowane, pomimo tego, że wynik wyszedł identyczny jak przy liczeniu sposobem pierwszym.
czy rozdzielenie tej liczby na \(\displaystyle{ (3 \cdot 4)^{13^{14}}\) jest po prostu uproszczeniem czy może czynnością konieczną w takim przypadku?

[abc666]

Możesz powiedzieć jak to "policzyłaś" ?

[Mistrz]

Być może jest uproszczeniem, ale na pewno nie koniecznością. Jaka to uczelnia?

[amave]

z modulo. najpierw \(\displaystyle{ \phi(100)=40}\) później wyliczyłam , że \(\displaystyle{ 13^{14}\equiv9\pmod{40}}\), następnie obliczyłam, że \(\displaystyle{ 12^{9}\equiv 52\pmod{100}}\). czyli, że dwie ostatnie cyfry to \(\displaystyle{ 52}\)
połowa grupy rozwiązała zadanie w ten sposób i niestety wszyscy mają 0 punktów. przy maksymalnej ilości 40 punktów 10 robi ogromną różnicę.

@Mistrz Politechnika Rzeszowska

[tkrass]

No bo to rozwiązanie korzysta z błędnego rozumowania, opierającego się na tym, że \(\displaystyle{ a \equiv b \pmod{c} \Rightarrow d^a \equiv d^b \pmod{c}}\).

[amave]

przepraszam, ale pomyliłam się w zapisie tam oczywiście powinno być \(\displaystyle{ 12^{9}\equiv 52\pmod{100}}\), a nie tak jak wcześniej napisałam \(\displaystyle{ 12^{9}\equiv 52\pmod{40}}\). błąd już poprawiony

[Vax]

No bo to rozwiązanie korzysta z błędnego rozumowania, opierającego się na tym, że \(\displaystyle{ a \equiv b \pmod{c} \Rightarrow d^a \equiv d^b \pmod{c}}\).

Jesteś pewien? To rozwiązanie opiera się na tym, że \(\displaystyle{ a \equiv b \pmod{\varphi(n)} \Rightarrow c^a \equiv c^b \pmod{n}}\)

Co jest poprawne.

[tkrass]

Teraz jak amave już to zmieniła, to naturalnie jest okej (jeżeli te obliczenia są okej).

[amave]

już sama doszłam w czym problem. chodzi o wniosek z twierdzenia Eulera
tw. Eulera \(\displaystyle{ NWD(a,m)=1 \Rightarrow a^{\varphi(m)}\equiv1\pmod{m}}\)
wniosek z tw Eulera \(\displaystyle{ NWD(a,m)=1}\) i \(\displaystyle{ n'}\) jest resztą z dzielenia \(\displaystyle{ n}\) przez \(\displaystyle{ \varphi(m) \Rightarrow a^n\equiv a^{n'} \end{cases} \pmod{m}}\)

[Vax]

No tak, ale jaki problem? W swoim rozwiązaniu z tego korzystasz, a jest to poprawne, więc Twoje rozwiązanie jest poprawne.

[amave]

problem w tym, że z tego twierdzenia i z mojego toku liczenia wynika, że \(\displaystyle{ NWD(12,100)=1}\) co nie jest przecież prawdą. dlatego też wychodzi na to, że konieczne jest rozłożenie tej liczby nie tylko na \(\displaystyle{ (3 \cdot 4)^{13^{14}}}\), ale na \(\displaystyle{ (3 \cdot 2 \cdot 2)^{13^{14}}}\)

[Zordon]

To przecież i tak nie pomoże, bo \(\displaystyle{ nwd(2,100)\neq 1}\).
To najlepiej robić z chińskiego tw. o resztach, czyli liczysz to najpierw modulo 25 i modulo 4.
Modulo 4 to jest oczywiste 0. Natomiast modulo 25 to juz mozesz skorzystac z tw. Fermata. Załóżmy, że wyjdzie \(\displaystyle{ d}\). Dostaniemy:

\(\displaystyle{ \begin{cases}x=0\pmod{4} \\ x=d\pmod{25} \end{cases}}\)
Pozostaje kwestia wyliczenia z tego jaki bedzie \(\displaystyle{ x\pmod{100}}\)