Weryjikacja zadania z resztą z dzielenia

[szatek]

Polecenie brzmi: wyznacz resztę z dzielenia: \(\displaystyle{ 3^{1000000} \ mod \ 91}\)

a więc wiemy, że liczby 3 i 91 są względnie pierwsze, możemy przy tym zastosować Twierdzenie Eulera i dostajemy, że:
\(\displaystyle{ 3^{\varphi{91}}\equiv1 \ mod \ 91}\)

By obliczyć \(\displaystyle{ \varphi(91)}\) rozkładamy tą liczbę na czynniki pierwsze: 7 i 13.
Wiemy, że obie te liczby są pierwsze i wiemy, że dla każdego \(\displaystyle{ n,m \in \mathbb{N} \ \varphi(nm)=\varphi(n)\varphi(m)}\)

Ponadto wiemy, że 13 i 7 to liczby pierwsze, a więc \(\displaystyle{ \varphi(13)=12 \ \varphi(7)=6}\)

Z tego wynika, że \(\displaystyle{ \varphi(91)=72}\)

Otrzymujemy zatem, że:
\(\displaystyle{ 3^{72}\equiv 1 \ mod \ 91}\)

I teraz moje pytanie, czy możemy zrobić taki trik:
\(\displaystyle{ {(3^{72})}^{\frac{1000000}{72}}\equiv1^{\frac{1000000}{72}} \ mod \ 91 \Rightarrow 3^{1000000}\equiv1 \ mod \ 91 \Rightarrow 3^{1000000} \ mod \ 91=90}\)

Czy to zadanie jest dobrze zrobione?

[Qń]

I czy możemy zrobić taki trik:
\(\displaystyle{ {(3^{72})}^{\frac{1000000}{72}}\equiv1^{\frac{1000000}{72}} \ mod \ 91 \Rightarrow 3^{1000000}\equiv1 \ mod \ 91 \Rightarrow 3^{1000000} \ mod \ 91=90}\)

Używając tego "tricku" można pokazać, że:
\(\displaystyle{ 3 =(3^{72})^\frac{1}{72} \equiv 1^\frac{1}{72} = 1 \mod 91}\)
co do rzeczywistości ma się nijak.

Kongruencji nie wolno pierwiastkować stronami! (a to właśnie niejawnie zrobiłeś)

Q.

[szatek]

Kongruencji nie wolno pierwiastkować stronami! (a to właśnie niejawnie zrobiłeś)
Q.

Ok w takim razie jak to zadanie zrobić?