Łączność dodawania modulo

[VirtualUser]

Witam, mam problem z udowodnieniem tego twierdzenia:
Niech \(\displaystyle{ q}\) oznacza dodawanie modulo. Wykaż, że
\(\displaystyle{ (X q Y) q Z = X q (Y q Z)}\)

Spróbowałem zamienić to na postać

\(\displaystyle{ ((( x \mod n + y \mod n ) \mod n )\mod n + z \mod n )\mod n}\)

ale nic z tego nie potrafię wypocić...

[janusz47]

Najpierw dowodzimy własność:

\(\displaystyle{ (x+y)\mod(z) = (x \mod(z) +y \mod(z))\mod(z)\ \ (0)}\)

Dowód:

\(\displaystyle{ x = z\cdot q_{1}+r_{1}, \ \ 0\leq r_{1}< z, \ \ x \mod(z) = r_{1}}\)

\(\displaystyle{ y = z\cdot q_{2}+r_{2}, \ \ 0\leq r_{2}< z, \ \ y \mod(z) = r_{2}}\)

Z własności dodawania "modulo":

\(\displaystyle{ (x+y)\mod(z) = (z\cdot q_{1}+r_{1}+ z\cdot q_{2}+r_{2})\mod(z)}\)

\(\displaystyle{ (x+y)\mod(z) = (z\cdot ( q_{1}+ q_{2}) + r_{1}+r_{2})\mod(z)}\)

\(\displaystyle{ (x+y)\mod(z) = (r_{1}+r_{2})\mod(z) \ \ (1)}\)

\(\displaystyle{ [x\mod(z)+y\mod(z)] \mod(z) = (r_{1}+r_{2})\mod(z) \ \ (2)}\)

Na podstawie (1) (2) otrzymujemy (0).

Proszę udowodnić teraz własność dystrybutywności (łączności) dodawania modulo.