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:
A 20.2. Tétel 5. pontja alapján mindkét oldalból kivonhatunk b-t. Így az alábbit kapjuk:
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:
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:
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:
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.
∎