Oblicz \(\displaystyle{ 2^{235} \pmod{17}}\)
Proszę o dokładne wytłumaczenie.
Trzeba skorzystać z tw. Eulera, czy z małego tw. Fermata?
Potęgowanie modularne
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Potęgowanie modularne
Zauważmy, że \(\displaystyle{ 2^8=256=255+1=17^2-2\cdot 17+1\equiv 1\pmod{17}}\)
oraz \(\displaystyle{ 235=8\cdot 29+3}\), więc
\(\displaystyle{ 2^{235}=2^{8\cdot 29+3}=(2^8)^{29}\cdot 2^3\equiv 2^3\pmod{17}}\),
czyli ostatecznie \(\displaystyle{ 2^{235}\equiv 8\pmod{17}}\).-- 23 kwi 2018, o 18:36 --Zdecydowałem się na podanie takiego rozwiązania, choć może się ono wydawać z kapelusza wzięte, ponieważ po skorzystaniu z małego twierdzenia Fermata i tak stajemy przed zadaniem obliczenia \(\displaystyle{ 2^{11}\pmod{17}}\), co nie jest zbyt wygodne (choć można pod kreską), chyba że i tak się zauważy \(\displaystyle{ 2^8\equiv 1\pmod{17}}\) (ale wówczas tak naprawdę okazuje się, że zastosowanie małego twierdzenia Fermata jest już zbędne).
oraz \(\displaystyle{ 235=8\cdot 29+3}\), więc
\(\displaystyle{ 2^{235}=2^{8\cdot 29+3}=(2^8)^{29}\cdot 2^3\equiv 2^3\pmod{17}}\),
czyli ostatecznie \(\displaystyle{ 2^{235}\equiv 8\pmod{17}}\).-- 23 kwi 2018, o 18:36 --Zdecydowałem się na podanie takiego rozwiązania, choć może się ono wydawać z kapelusza wzięte, ponieważ po skorzystaniu z małego twierdzenia Fermata i tak stajemy przed zadaniem obliczenia \(\displaystyle{ 2^{11}\pmod{17}}\), co nie jest zbyt wygodne (choć można pod kreską), chyba że i tak się zauważy \(\displaystyle{ 2^8\equiv 1\pmod{17}}\) (ale wówczas tak naprawdę okazuje się, że zastosowanie małego twierdzenia Fermata jest już zbędne).
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Potęgowanie modularne
Podobnie:
\(\displaystyle{ 2^{235}\pmod{17}=2^{232+3}\pmod{17}=16^{58} \cdot 2^3\pmod{17}\equiv \\ \equiv(-1)^{58} \cdot 8\pmod{17}\equiv 1 \cdot 8\pmod{17}\equiv 8}\)
\(\displaystyle{ 2^{235}\pmod{17}=2^{232+3}\pmod{17}=16^{58} \cdot 2^3\pmod{17}\equiv \\ \equiv(-1)^{58} \cdot 8\pmod{17}\equiv 1 \cdot 8\pmod{17}\equiv 8}\)
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Re: Potęgowanie modularne
Z twierdzenia Eulera dla liczb pierwszych \(\displaystyle{ \Leftrightarrow}\) Z Małego Twierdzenia Fermata
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Re: Potęgowanie modularne
Jeszcze inaczej:
\(\displaystyle{ 235 = 5 \cdot 47}\)
\(\displaystyle{ 2^235 = 32^47 \equiv \left(-2\right)^47 = -2^47 = -2^{-1} \cdot \left(2^16\right)^3 \equiv -9 \equiv 8 \pmod{17}}\)
Z MTF \(\displaystyle{ 2^16 \equiv 1 \pmod{17}}\) i łatwo widać, że \(\displaystyle{ 2^{-1} = 9 \pmod{17}}\)
\(\displaystyle{ 235 = 5 \cdot 47}\)
\(\displaystyle{ 2^235 = 32^47 \equiv \left(-2\right)^47 = -2^47 = -2^{-1} \cdot \left(2^16\right)^3 \equiv -9 \equiv 8 \pmod{17}}\)
Z MTF \(\displaystyle{ 2^16 \equiv 1 \pmod{17}}\) i łatwo widać, że \(\displaystyle{ 2^{-1} = 9 \pmod{17}}\)