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?
Weryjikacja zadania z resztą z dzielenia
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Weryjikacja zadania z resztą z dzielenia
Używając tego "tricku" można pokazać, że:szatek pisze: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}\)
\(\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.
Weryjikacja zadania z resztą z dzielenia
Ok w takim razie jak to zadanie zrobić?Qń pisze: Kongruencji nie wolno pierwiastkować stronami! (a to właśnie niejawnie zrobiłeś)
Q.