mod student: Oblicz 27³3 mod 157

student: 27³³

Adamm: No niestety, 157 to liczba pierwsza. 27³³ = 27*729¹⁶ = 27*56¹⁶ = 27*3136⁸ = 27*4⁸ = 27*256² = = 27*58² = 2*4 = 8

Adamm: tfu 27*4 = 108

Blee: 27² mod 157 = 729 mod 157 = 101 mod 157 = (−56) mod 157 27⁴ mod 157 = (−56)² mod 157 = 3136 mod 157 = 153 mod 157 = (−4) mod 157 czyli 27⁴ mod 157 = (−4) mod 157 więc: 27³³ mod 157 = 27^{4*8 + 1} mod 157 = (−4)⁸*27 mod 157 = (−58)²*27 mod 157 = 67*27 mod157 = 82 mod 157

Blee: Adamm ... skąd masz to 2*4

Adamm: z kapelusza

Blee: to nadal nie widzę jak (−58)² mod 157 = 3364 mod 157 = 21*157 + 67 mod 157 = 4 mod 157

student: a gdyby na miejscu 157 stala liczba zlozona?

student: Robiłem trochę dłuższym sposobem, wyszło mi jak @Blee 82.

ABC: dzisiaj w dobie komputerów piszesz po prostu 27³³=171 792 506 910 670 443 678 820 376 588 540 424 234 035 840 667=1 094 219 789 239 939 131 712 231 698 016 181 046 076 661 405*157+82

Mariusz: ABC Bawiłeś się Wolframem Alpha Interpreter Pythona też to potrafi ale bez ściągania dodatkowego oprogramowania na Windowsie mamy tylko Visual Basica oraz C# ze starszą wersją kompilatora Użytkownicy Linuksa mają Pythona bez ściągania dodatkowego oprogramowania ale ilu masz użytkowników Linuksa skoro w sklepach instalują Windowsa nie zostawiając wolnej partycji na Linuksa 27³3 mod 157 33₁₀=(100001)₂ 27² mod 157 = 729 mod 157 27² mod 157 = 4*157 +101 mod 157 27² mod 157 = 101 mod 157 27⁴ mod 157 = 101² mod 157 27⁴ mod 157=10201 mod 157 27⁴ mod 157 = 64*157+153 mod 157 27⁴ mod 157 = 153 mod 157 27⁸ mod 157 = 153² mod 157 27⁸ mod 157 = 10000+10600+2809 mod 157 27⁸ mod 157 = 23409 mod 157 27⁸ mod 157 = 16 mod 157 27¹⁶ mod 157 = 16² mod 157 27¹⁶ mod 157 = 256 mod 157 27¹⁶ mod 157 = 99 mod 157 27³² mod 157 = 9801 mod 157 27³² mod 157 = 67 mod 157 27³³ mod 157 = 67*27 mod 157 27³³ mod 157 = (47+20)(47−20) mod 157 27³³ mod 157 = 2209 − 400 mod 157 27³³ mod 157 = 1809 mod 157 27³³ mod 157 = 11*157 + 82 mod 157 27³³ mod 157 = 82 mod 157

Mariusz: a gdyby na miejscu 157 stala liczba zlozona? 7 lis 2019 18:01 To mógłbyś próbować korzystać z twierdzenia Eulera (takiego uogólnienia małego twierdzenia Fermata) Musiałbyś policzyć liczbę liczb względnie pierwszych z tą liczbą złożoną Wtedy 27 oraz ta liczba powinny być względnie pierwsze

Mariusz: Jak znasz rozkład liczby n na czynniki pierwsze to funkcję φ(n) całkiem szybko można policzyć