Małe tw. Fermata

[gollum]

mógłby ktoś rozwiązać krok po kroku przykład: \(16^{104}MOD \ 103\)

[patryk00714]

chyba chodzi o Fermata.

[gollum]

tak, tak, literówka.

[patryk00714]

to co mówi małe tw. Fermata?

[gollum]

Jeżeli p jest liczbą pierwszą, to dla każdej liczby całkowitej a liczba ap−a jest podzielna przez p.

[gollum]

pomoże mi ktoś?

[patryk00714]

czyli co mam pokazać? Że liczba \(16^{104} \equiv \text{do czego?} \text{(mod 103)}\)

[Panko]

\((16,103)=1\) czyli są względnie pierwsze oraz \(103\) --liczba pierwsza
\(a^{p-1} \equiv\) \(1\) \((\) \(mod\) \(\\) \(p\) \()\)
\(16^{103-1} \equiv\) \(1\) \((\) \(mod\) \(\\) \(103\) \()\)
czyli \(16^{102} \equiv\) \(1\) \((\) \(mod\) \(\\) \(103\) \()\)
teraz mnożę kongruencję obustronnie przez \(16^2\)
\(16^{104} \equiv\) \(16^2\) \((\) \(mod\) \(\\) \(103\) \()\)
oraz \(16^{2} \equiv\) \(50\) \((\) \(mod\) \(\\) \(103\) \()\)
stąd z przechodniości jest
\(16^{104} \equiv\) \(50\) \((\) \(mod\) \(\\) \(103\) \()\)

[gollum]

i to jest już końcowy wynik? co dalej z tym zrobić?

[gollum]

\(16^{104} \equiv\) \(16^2\) \((\) \(mod\) \(\\) \(103\) \()\)
oraz \(16^{2} \equiv\) \(50\) \((\) \(mod\) \(\\) \(103\) \()\)

nie bardzo rozumiem to przejście skąd się wzięło to 50 ?

[denatlu]

\(50\) to reszta przy dzieleniu \(263\) przez \(103\), zajrzyj jeszcze raz do twierdzenia
http://pl.wikipedia.org/wiki/Ma%C5%82e_ ... ie_Fermata

[gollum]

wielkie dzięki