Nézzük először a teljes maradékrendszerre vonatkozó állítást! Mivel az új maradékrendszer elemszáma is m, ezért a 20.16. Tétel alapján elegendő a páronkénti inkongruenciát ellenőrizni. Legyen tehát ar_i+b és ar_j+b az új maradékrendszer két tetszőleges eleme, és tegyük fel, hogy ezek között fennáll a kongruencia, azaz:

ar_i+b\equiv ar_j+b\pmod m

A 20.2. Tétel 6. 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:

r_i\equiv r_j\pmod m

Ez viszont csak akkor lehetséges, ha r_i=r_j, hiszen az eredeti teljes maradékrendszer elemei páronként inkongruensek modulo m. Így tehát az ar_i+b=ar_j+b egyenlőség is szükségképpen fennáll. Megfordítva a gondolatmenetet: ha az új maradékrendszernek vesszük két egymástól különböző tetszőleges elemét, akkor ők szükségképpen inkongruensek modulo m.

Most nézzük a redukált maradékrendszerre vonatkozó állítást! Mivel az új maradékrendszer elemszáma is \varphi(m), ezért a 20.16. Tétel alapján elegendő a páronkénti inkongruenciát, valamint az m-hez relatív prímséget ellenőrizni. Legyen tehát as_i és as_j az új maradékrendszer két tetszőleges eleme, és tegyük fel, hogy ezek között fennáll a kongruencia, azaz:

as_i\equiv as_j\pmod m

Innentől a gondolatmenet teljesen megegyezik az előzővel.

Azt kell még megmutatni, hogy az új maradékrendszer minden eleme relatív prím m-hez. Legyen tehát as_i az új maradékrendszer tetszőleges eleme. 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.

Ez azt jelenti, hogy sem a-nak, sem pedig s_i-nek nincs m-mel közös osztója az egységeken kívül. Mivel a 17.22. Tétel szerint az egész számok \Z gyűrűjében teljesül a számelmélet alaptétele, ezért ez azt is jelenti, hogy a és s_i prímtényezői mind különböznek m prímtényezőitől, és így a szorzatuknak sincs m-mel közös prímtényezője, tehát osztója sem az egységeken kívül. Azaz as_i valóban relatív prím m-hez.