Zeige: Kongruenz modulo p

Question

Sei n∈ℕ und p∈ℙ. Zeigen Sie: für jedes x∈ℤ gilt:

x ^1+n(p-1) ≡ x (mod p)

Answer 1

Verwende den kleinen Satz von Fermat:

Für jede Primzahl \(p\) und jede ganze Zahl \(x\in\mathbb{Z}\) ist \(x^{p} \equiv x \bmod{p}\).

Nutze diesen Satz für eine vollständige Induktion bzgl. \(n\in \mathbb{N}\).

[spoiler]

IA: Für \(n = 1\) ...

Für jede Primzahl \(p\) und jede ganze Zahl \(x\in\mathbb{Z}\) ist \[x^{1+1\cdot(p-1)}\equiv x^{p}\stackrel{\text{Fermat}}{\equiv}x\bmod{p}\text{.}\]

IV:

Für eine natürliche Zahl \(n\in\mathbb{N}\) sei bereits gezeigt, dass \[x^{1+n\cdot(p-1)}\equiv x \bmod{p}\] für jede Primzahl \(p\) und jede ganze Zahl \(x\in\mathbb{Z}\) ist.

IS: Für das \(n\) aus IV ...

Für jede Primzahl \(p\) und jede ganze Zahl \(x\in\mathbb{Z}\) ist dann \[x^{1+(n+1)\cdot(p-1)} \equiv x^{1+n\cdot(p-1) + p - 1} \equiv x^{p + n\cdot(p-1)} \equiv x^{p} \cdot x^{n\cdot(p-1)} \stackrel{\text{Fermat}}{\equiv} x \cdot x^{n\cdot(p-1)} \equiv x^{1+n\cdot(p-1)} \stackrel{\text{IV}}{\equiv} x \bmod{p}\text{.}\]

[/spoiler]

Answer 2

  Denke immer vom Prinzip her. Wir bewegen uns in dem ===>  Primrestklassenkörper

    F_p  :=  |Z  /  p  |Z       (  1  )

       Die Elemente von F_p  sind die p Wurzeln des Polynoms aus F_p [ x ]

             x  ^  p  =  x        (  2a  )

     ( wird z.B. im ===> v.d. Waerden bewiesen und stellt eine direkte Folge des binomischen Lehrsatzes dar. )

     Dann sind aber die ( p - 1 ) Elemente der multiplikativen Gruppe G_p  ( also alle außer der Null )  die sämtlichen ( p - 1 )_ten  ===>  EINHEITSWURZELN Lösungen des Polynoms

       x  ^ (  p  -  1  )  =  1        (  2b  )

   Oder noch einfacher gesagt. Die Ordnung von G ist

      °  G  =  p  -  1     (  3  )

     woraus bereits ( 2b ) folgt.

    Sonderfall  x  =  0  ;  ansonsten

       x  ^ [  1  +  n  (  p  -  1  )  ]   =     (  4a  )

     =  x  ^  1  *  [  x  ^   (  p  -  1  )  ]  ^  n  =   (  4b  )

      =  x  *   (  1  ^   n  )   =      (  4c  )        (  wegen  ( 2b  )

      =  x       (  4d  )