Wyznacz resztę z dzielenia tw. Eulera/małe tw. Fermata

adu · Post autor: **adu** » 23 lis 2013, o 18:35

Dzień dobry. Mam do obliczenia resztę z:

\(\displaystyle{ 99 ^{2000000}mod43}\)

Znalazłem rozwiązanie małym tw. Fermata, ale jak się domyślam można resztę znaleść z tw. Eulera.

Ok, przedstawię rozwiązanie z małego tw. Fermata, nie jestem pewien czy dobrze.

\(\displaystyle{ 99 ^{42}mod43 = 1}\)

\(\displaystyle{ 2000000 mod 42 = 2}\)

\(\displaystyle{ 2000000 = 42k + 2}\)

\(\displaystyle{ 99 ^{2000000}mod43 = (99 ^{42} ^{k} mod43)(99 ^{2} mod43)mod43 = (9981mod43)mod43 = 40mod43 = 40}\)

Czy to jest dobrze? W międzyczasie spróbuje rozwiązać z tw. Eulera.

Premislav · Post autor: **Premislav** » 23 lis 2013, o 18:59

Najpewniej pod sam koniec masz literówkę, bo wynik jest prawidłowy i nie zgadza się z tym, co otrzymałbyś licząc resztę z \(\displaystyle{ 9981}\)(dodam tylko, że zamiast podnosić \(\displaystyle{ 99}\) do kwadratu, można np. tak: \(\displaystyle{ 99\equiv 13\pmod{43}}\), zatem \(\displaystyle{ 99 ^{2}\equiv}\)...).

adu · Post autor: **adu** » 23 lis 2013, o 19:17

\(\displaystyle{ 99 ^{2} mod43 = (99mod43) ^{2} mod 43 = 169mod43 = 40}\)

Teraz dobrze?