youproof.orgDeep Math. Human Access.

Bizonyítás

Elegendő a 2. állítást igazolni, abból ugyanis automatikusan következik a megoldásszámra vonatkozó 1. állítás.

Azt mondtuk, hogy az ss egész szám által reprezentált [s]m[s]_m maradékosztály megoldása a kongruenciának, azaz:

as≡b(modm)as\equiv b\pmod m

Válasszunk most egy tetszőleges tt egész számot. Az általa reprezentált [t]m[t]_m maradékosztály akkor és csak akkor lesz megoldása a kongruenciának, ha teljesül

at≡b(modm)at\equiv b\pmod m

Mivel a kongruencia a 20.2. Tétel 2. és 3. pontja alapján szimmetrikus és tranzitív, ezért ez ekvivalens az alábbival:

as≡at(modm)as\equiv at\pmod m

A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük aa-val, ám eközben az mm modulust is "el kell osztanunk" az (a,m)(a,m) kitüntetett közös osztóval, azaz jelen esetben dd-vel. Az előző kongruencia tehát ekvivalens az alábbival:

s≡t(modmd)s\equiv t\pmod{\frac{m}{d}}

Vagyis a tt által reprezentált [t]m[t]_m maradékosztály akkor és csak akkor lesz megoldás, ha tt ugyanabba a modulo md\frac{m}{d} maradékosztályba esik, mint ss, azaz:

[s]md=[t]md[s]_{\frac{m}{d}}=[t]_{\frac{m}{d}}

Ez a 20.4. Tétel alapján akkor és csak akkor teljesül, ha tt felírható az alábbi alakban valamilyen alkalmasan választott kk egész számmal:

t=s+k⋅mdt=s+k\cdot \frac{m}{d}

Azt kaptuk tehát, hogy amennyiben ismerünk egy [s]m[s]_m megoldást, akkor az összes többi megoldást előállíthatjuk

[s+k⋅md]m[s+k\cdot \frac{m}{d}]_m

alakban. Így már csak azt kell igazolni, hogy kk-val végigfutva az összes egész számon épp a tétel 2. állításában szereplő dd darab modulo mm maradékosztály reprezentánselemeit kapjuk.

Nézzük meg ezért, hogy két tetszőleges k1k_1 és k2k_2 esetén az s+k1mds+k_1\frac{m}{d} és s+k2mds+k_2\frac{m}{d} kifejezések mikor fogják ugyanazt a maradékosztályt reprezentálni, azaz mikor fog teljesülni az alábbi:

[s+k1md]m=[s+k2md]m[s+k_1\frac{m}{d}]_m=[s+k_2\frac{m}{d}]_m

Ez ugye pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

s+k1md≡s+k2md(modm)s+k_1\frac{m}{d}\equiv s+k_2\frac{m}{d} \pmod m

A 20.2. Tétel 5. pontja miatt mindkét oldalból kivonhatunk ss-t:

k1md≡k2md(modm)k_1\frac{m}{d}\equiv k_2\frac{m}{d} \pmod m

A 20.3. Tétel alapján mindkét oldalt egyszerűsíthetjük md\frac{m}{d}-vel. Vigyázat! A tétel szerint ilyenkor ugyanis a modulust is egyszerűsíteni kell md\frac{m}{d} és mm kitüntetett közös osztójával. Azaz az előbbi kongruencia akkor és csak akkor akkor teljesül, amikor az alábbi kongruencia is:

k1≡k2(modm(md,m))k_1\equiv k_2 \pmod{\frac{m}{(\frac{m}{d}, m)}}

Most vizsgáljuk meg, hogy tulajdonképpen mivel egyezik meg az itt szereplő modulus. Ne feledjük, hogy itt nem törtekről van szó, hiszen jelenleg a Z\Z gyűrűben vagyunk, ahol nem értelmezhető az "osztás". Ehelyett például az md\frac{m}{d} csak egy jelölés, amely azt az egész számot jelöli, amellyel a dd egész számot megszorozva az mm egész számot kapjuk eredményül. Azaz:

md⋅d=m\frac{m}{d} \cdot d = m

Feltéve persze, ha ilyen létezik, aminek ugye a feltétele az d∣md|m oszthatóság. Ez jelen esetben nyilván fennáll, mivel azt mondtuk, hogy dd az aa és mm kitüntetett közös osztója. Ám ekkor teljesül az md∣m\frac{m}{d}|m oszthatóság is, így az (md,m)(\frac{m}{d},m) kitüntetett közös osztó a 17.6. Tétel 2. pontja miatt md\frac{m}{d} asszociáltja, és emiatt lecserélhető vele. A fenti kongruenciában szereplő modulus tehát így hozható egyszerűbb formára:

m(md,m)=m(md)\frac{m}{(\frac{m}{d}, m)}=\frac{m}{(\frac{m}{d})}

Ez tehát azt az egész számot jelöli, amelyet az md\frac{m}{d} egész számmal megszorozva az mm egész számot kapjuk eredményül. A fentebbi md⋅d=m\frac{m}{d} \cdot d = m összefüggés alapján ez épp dd-vel egyezik meg. A fenti kongruencia tehát tulajdonképpen így néz ki:

k1≡k2(modd)k_1\equiv k_2\pmod d

Azt kaptuk tehát, hogy az [s+k1md]m[s+k_1\frac{m}{d}]_m és [s+k2md]m[s+k_2\frac{m}{d}]_m modulo mm maradékosztályok akkor és csak akkor egyeznek meg, amikor a [k1]d[k_1]_d és [k2]d[k_2]_d modulo dd maradékosztályok is megegyeznek. Az ax≡b(modm)ax\equiv b\pmod m lineáris kongruenciának tehát pontosan annyi megoldása van, ahány modulo dd maradékosztály létezik.

Ezek száma viszont a 20.4. Tétel alapján dd. Így tehát ha kk végigfut a 00, 11, 22, ..., d−1d-1 egész számokon, akkor épp a tétel 2. állításában szereplő maradékosztályokat kapjuk megoldásként.

∎