Keresés

Legújabb cikkek

Daniell-elem - definíció
Akkumulátor - definíció
Szárazelem - definíció
Galvánelem - definíció
Kirchhoff II. törvénye (huroktörvény) - törvény

Támogató

Szabványok

35 35

Kategória:	Bizonyítás - Tétel	Évfolyam:	9.
Kulcsszó:	Maradékosztályok	Lektorálás:	Nem lektorált

A teljes maradékrendszer tétel

Bizonyítás

Bizonyítsuk be a tételt indirekt módon! Tegyük föl, hogy $\{ 0m, 1m, 2m, ..., (n-2)m, (n-1)m \} \mod n$ között van két egyenlő, legyenek ezek a maradékok $k$ és $l$ !

Ekkor $n|mk-ml$ igaz, hiszen ez egyenértékű az $mk \equiv ml \mod n$ kifejezéssel. $n|m(k-l)$ . Ezt és a kezdeti $(n; m)=1$ feltételt felhasználva nyilvánvalóan $n|k-l$ igaz.

Mivel a maradék kisebb, mint az osztó, így $k<n~~~l<n \Rightarrow (k-l)<n$ . Föntebb beláttuk, hogy $(k-l)$ -nek oszthatónak kell lennie $n$ -nel, viszont $(k-l)$ kisebb, mint $n$ . Így $k-l=0$ lehetséges csak, vagyis $k=l$ .

Tehát, ha valamely két tag egyenlő $\mod n$ , akkor az a két tag saját maga. Így minden maradékból pontosan egy van, tehát beláttunk a tételt.

Kezdés

Cikkek