Potęgowanie modularne

[pow3r]

Oblicz \(\displaystyle{ 2^{235} \pmod{17}}\)
Proszę o dokładne wytłumaczenie.

Trzeba skorzystać z tw. Eulera, czy z małego tw. Fermata?

[Premislav]

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).

[kerajs]

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}\)

[PoweredDragon]

Z twierdzenia Eulera dla liczb pierwszych \(\displaystyle{ \Leftrightarrow}\) Z Małego Twierdzenia Fermata

[bakala12]

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}}\)