Wie sind Restklassen zu beweisen?

Question

Sei n ∈ N eine natürliche Zahl. Für x ∈ Z bezeichnet \( \overline { x } \) = x + nZ = {x + nz | z ∈ Z} die Restklasse von x ∈ Z modulo n.

Definiere Z/nZ := {\( \overline { x } \) | x ∈ Z} als die Menge aller Restklassen.

Beweisen Sie: Es gilt $$ \overline { x } = \overline { x } ^ { \prime } \Leftrightarrow x - x` ∈ nZ $$

Könnte jemand helfen wie ich vorgehen soll?

Answer 1

Das heißt doch in Worten:

x und x' sind in der gleichen Restklasse mod n

<=>  x - x' ist ein Vielfaches von n.

Seien also x und x ' aus ℤ und

es gibt a, b und r  aus ℤ  mit

x=n*a+r   und  x ' = n*b + r

(Das heißt doch: Beide sind in der gleichen

Restklasse, haben also beid er Division durch n den

gleichen Rest r.)

Dann gilt also x-n*a=r   und  x ' - n*b = r

==>      x-n*a  =   x ' - n*b

<=>      x - x ' =  n*a - n*b = n *- (a-b)

Also ist x - x ' gleich einem Produkt aus n

und einer ganzen Zahl, also aus n*ℤ.

Umgekehrt entsprechend, wenn x-x' = n*k    #

und wenn man x und x' durch n dividiert

entstehen die Reste r1 und r2 also

x = a*n+ r1  und x ' = b*n + r2 das gibt bei #

(a*n+ r1)  - ( b*n + r2) = n*k

<=> (a*n  -  b*n ) +( r1 -  r2) = n*k

<=> r1 -  r2 = n*k   -   n*(a  -  b )  = n * ( k - a + b )

Also ist die Differenz der Reste durch n teilbar.

Da aber beide  Reste aus 0,...,n-1} sind,

sind sie gleich also x und x ' in der

gleichen Restklasse mod n.