Berechnungen mit dem Satz von Fermat und Wilson

Question

ich war die Woche über im Krankenhaus und verstehe nicht ganz wie ich dies berechnen soll.

Würde mich freuen.

Answer 1

Wilson:    Für Primzahlen p gilt   (p-1)! ≡ -1  (mod p)

Für p=101 also     100!  ≡ -1  (mod 101)

           

also läßt  100! bei Division durch 101 den Rest 100, d.h.

    97! * 98 * 99 * 100     ≡   100       (mod 101)

<=>    97! * 970200      ≡   100       (mod 101)

da    970200      ≡  95       (mod 101)

gilt für den gesuchten Rest x von 97!

x*95  ≡   100       (mod 101)

da 5 und 101 teilerfremd sind

  x*19 ≡   20       (mod 101)

also x=17.

Probe:  17*95 = 1615  ≡   100       (mod 101)  Passt !

Comments

b)   Fermat:  Wenn p prim und kein Teiler von a,

dann   a ^p-1 ≡ 1  (p)

Da 83 kein Teiler von 50 ist, gilt also

 50 ⁸² ≡ 1  (83)

also  auch    50 ^3*82 ≡ 1  (83) 

 50 ²⁴⁶ ≡ 1  (83)

also    50 ²⁴⁷ ≡ 50  (83)