Fölérendelt lap:20.19. TételTeljes és redukált maradékrendszer képzése

Bizonyítás

Az 1. állítás: Mivel az új számhalmaz elemszáma is $m$ , ezért a 20.17. Tétel 1. pontja alapján elegendő a páronkénti inkongruenciát ellenőrizni. Legyen tehát $ar_i+b$ és $ar_j+b$ az új számhalmaz két tetszőleges, egymástól különböző eleme, és tegyük fel indirekt, hogy ezek között mégis fennáll az alábbi kongruencia:

ar_i+b\equiv ar_j+b\pmod m

A 20.2. Tétel 5. pontja alapján mindkét oldalból kivonhatunk $b$ -t. Így az alábbit kapjuk:

ar_i\equiv ar_j\pmod m

Mivel $a$ -ról azt mondtuk, hogy relatív prím $m$ -hez, így a 20.3. Tétel utáni megjegyzés alapján $a$ -val egyszerűsíthetjük mindkét oldalt a modulus változatlanul hagyása mellett:

r_i\equiv r_j\pmod m

Mivel az eredeti teljes maradékrendszer elemei páronként inkongruensek modulo $m$ , így ez csak akkor lehetséges, ha $r_i=r_j$ . Ebből viszont az következik, hogy az $ar_i+b=ar_j+b$ egyenlőség is szükségképpen fennáll, vagyis indirekt feltételezésünkkel ellentétben az új számhalmaz két kiválasztott eleme mégis megegyezik.

A 2. állítás: Mivel az új számhalmaz elemszáma is $\varphi(m)$ , ezért a 20.17. Tétel 2. pontja alapján elegendő a páronkénti inkongruenciát, valamint az $m$ -hez való relatív prímséget ellenőrizni. Kezdjük az előbbivel. Legyen tehát $as_i$ és $as_j$ az új számhalmaz két tetszőleges, egymástól különböző eleme, és tegyük fel indirekt, hogy ezek között mégis fennáll az alábbi kongruencia:

as_i\equiv as_j\pmod m

Innentől a páronkénti inkongruencia az előzővel szinte teljesen megegyező gondolatmenet alapján adódik.

Azt kell még megmutatni, hogy az új számhalmaz minden $as_i$ eleme relatív prím $m$ -hez. Azt ugye a tétel szövegéből tudjuk, hogy $a$ relatív prím $m$ -hez. Továbbá $s_i$ is relatív prím $m$ -hez, mivel ő az eredeti redukált maradékrendszer egyik eleme. Azt kell igazolni, hogy ekkor az $as_i$ szorzat is relatív prím $m$ -hez.

Tegyük fel indirekt, hogy nem ez a helyzet, ami a 17.10. Definíció alapján azt jelenti, hogy $as_i$ -nek és $m$ -nek létezik olyan $d$ közös osztója, ami nem egység. Továbbá a $0$ sem lehet, hiszen ez azt jelentené, hogy teljesül a $0|m$ oszthatóság, vagyis a 16.2. Tétel 4. pontja miatt $m=0$ lenne, ami ellentmond a tétel szövegének, miszerint $m\gt 0$ .

Mármost ha a $d$ közös osztó, ami nem $0$ és nem is egység, akkor – mivel a 17.23. Tétel alapján $\Z$ -ben teljesül a számelmélet alaptétele – ő a 16.16. Definíció alapján felbontható prímtényezők szorzatára. Létezik tehát olyan $p$ prím, amely osztója $d$ -nek, és így az oszthatóság tranzitivitása miatt $as_i$ -nek és $m$ -nek is. Azaz létezik olyan $p$ prím, hogy:

\begin{aligned} p&|as_i \\ p&|m \end{aligned}

Mivel $p$ prím, ezért a 16.13. Definíció alapján két eset lehetséges. Első esetben teljesül a $p|a$ oszthatóság is, ami lehetetlen, hiszen $p|m$ miatt ekkor $p$ közös osztója $a$ -nak és $m$ -nek, ami ellentmond a tétel szövegének, miszerint $a$ relatív prím $m$ -hez. Második esetben pedig teljesül a $p|s_i$ oszthatóság, ami ugyancsak lehetetlen, hiszen $p|m$ miatt ekkor $p$ közös osztója $s_i$ -nek és $m$ -nek. Ez viszont ellentmond annak a fentebb már bizonyított ténynek, hogy $s_i$ relatív prím $m$ -hez.

∎

Iratkozz fel a hírlevelünkre