potęgowanie modularne

pow3r · Post autor: **pow3r** » 21 maja 2018, o 13:54

Oblicz:

a) \(\displaystyle{ 2 ^{65} \pmod{99}}\)

b) \(\displaystyle{ 11 ^{100} \pmod{55}}\)

leg14 · Post autor: **leg14** » 21 maja 2018, o 13:59

Zacznijmy od a).
Czy 2 jest względnie pierwsze z 99?
Ile wynosi \(\displaystyle{ \phi(99)}\) (funkcja Eulera, czyli ilość liczb mniejszych od 99 i z nią względnie pierwszych)?
Co nam daje twierdzenie Eulera w tym wypadku?

pow3r · Post autor: **pow3r** » 21 maja 2018, o 14:11

2 jest względnie pierwsze z 99
funkcja Eulera \(\displaystyle{ \phi(99)=60}\)

leg14 · Post autor: **leg14** » 21 maja 2018, o 14:18

To zastosuj tw eulera

pow3r · Post autor: **pow3r** » 21 maja 2018, o 14:32

nie do końca potrafie

leg14 · Post autor: **leg14** » 21 maja 2018, o 14:37

Za \(\displaystyle{ a}\) podstaw \(\displaystyle{ 2}\), za \(\displaystyle{ m}\) podstaw \(\displaystyle{ 99}\).

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29

pow3r · Post autor: **pow3r** » 21 maja 2018, o 14:56

\(\displaystyle{ \phi \left( 99 \right) =99 \left( 1- \frac{1}{3} \right) \left( 1- \frac{1}{11} \right) = 60}\) ?

czy to jest poprawny zapis? gdyz \(\displaystyle{ 99=3 ^{2} \cdot 11}\) i liczby sa pierwsze

leg14 · Post autor: **leg14** » 21 maja 2018, o 15:06

Nie, przecież nawet inna wartość Ci wyszła, niż 60.

Post autor: **Jan Kraszewski** » 21 maja 2018, o 15:09

leg14 pisze:Nie, przecież nawet inna wartość Ci wyszła, niż 60.

JK

pow3r · Post autor: **pow3r** » 21 maja 2018, o 15:11

jak inna, dokladnie wychodzi 60, tyle ile powinno, ale nie wiem co z tym dalejzrobic jak to rozpisac

leg14 · Post autor: **leg14** » 21 maja 2018, o 15:12

Jan Kraszewski, pow3r zedytowała wiadomość, oryginalnie było źle

Napisałem Ci żebyś podstawiła to do tw. Eulera

Post autor: **Jan Kraszewski** » 21 maja 2018, o 15:13

pow3r pisze:ale nie wiem co z tym dalej zrobic jak to rozpisac

leg14 pisze:Za \(\displaystyle{ a}\) podstaw \(\displaystyle{ 2}\), za \(\displaystyle{ m}\) podstaw \(\displaystyle{ 99}\).
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29

Masz wzór, masz dane do podstawienia, to podstaw.

JK

PS

leg14 pisze:Jan Kraszewski, pow3r zedytowała wiadomość, oryginalnie było źle

Masz rację, poprzednio napisała źle.

pow3r · Post autor: **pow3r** » 21 maja 2018, o 15:32

czy jest ktoś w stanie pomoc mi z tymi przykładami?

leg14 · Post autor: **leg14** » 21 maja 2018, o 15:35

Napisz tu, jak wygląda twierdzenie Eulera w tym konkretnym przypadku. Krok po kroku dojdziemy do rozwiązania

pow3r · Post autor: **pow3r** » 21 maja 2018, o 15:43

Kod: Zaznacz cały

http://smurf.mimuw.edu.pl/node/838

korzystajac z tego wychodzi mi dokladnie to co wyslalam wyzej

Matematyka.pl