0 Daumen
233 Aufrufe

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

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

von

2 Antworten

+1 Daumen
 
Beste Antwort

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]

von 1,2 k
0 Daumen

  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  )

von 5,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community