Wyznacz resztę z dzielenia tw. Eulera/małe tw. Fermata
: 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.
\(\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.