Maradékosztály

Legyen az m egy 1-nél nagyobb természetes szám. Az egész számok szétválogathatók aszerint, hogy az m-mel való maradékos osztás után mennyit adnak maradékul. Ha két egész szám az m-mel maradékosan elosztva ugyanannyit ad maradékul, akkor azt mondjuk, hogy ez a két egész szám egymással kongruens. A kongruencia egy ekvivalenciareláció, és az általa létrehozott ekvivalenciaosztályok az m szerinti maradékosztályok. Minden m esetében m darab különböző maradékosztály létezik.

Szabatosan megfogalmazva: tetszőleges ${\displaystyle m\geq 2}$ egész esetén az egész számok ${\displaystyle \mathbb {Z} }$ halmaza m diszjunkt osztály uniójára bomlik fel, mégpedig úgy, hogy ${\displaystyle 0\leq i\leq m-1}$ esetén az i-dik osztályban ${\displaystyle k\cdot m+i}$ alakú számok vannak, ahol k végigfut az egészeken (más szóval, az i-dik osztályba az m-mel osztva i maradékot adó számok tartoznak). Ezeket az osztályokat m szerinti, vagy másképpen modulo m (rövid jelölése: mod m) maradékosztályoknak nevezzük. A maradékosztályok jelentősége az, hogy ha két szám azonos maradékosztályba esik (modulo m), akkor kongruensek egymással modulo m, ha pedig különböző maradékosztályból valók, akkor nem kongruensek.

Egy modulo m maradékosztályból kiválasztott tetszőleges a elemet a maradékosztály reprezentáns elemének nevezzük, s azt mondjuk, hogy a reprezentálja a maradékosztályt.

A maradékosztályok fogalmát Carl Friedrich Gauss vezette be 1801-es Számelméleti vizsgálódások című művében.

Legyen m = 5.

Ekkor 5 maradékosztály létezik

• a { ..., –20, –15, –10, –5, 0, 5, 10, 15, 20, ... } számhalmaz a 0-maradékosztály, azaz az 5·i vagy 5·i+0 alakú számok, ahol i tetszőleges egész szám;
• a { ..., –19, –14, –9, –4, 1, 6, 11, 16, 21, ... } számhalmaz az 1-maradékosztály, azaz az 5·i+1 alakú számok, ahol i tetszőleges egész szám;
• a { ..., –18, –13, –8, –3, 2, 7, 12, 17, 22, ... } számhalmaza 2-maradékosztály, azaz az 5·i+2 alakú számok, ahol i tetszőleges egész szám;
• a { ..., –17, –12, –7, –2, 3, 8 13, 18, 23, ... } számhalmaz a 3-maradékosztály, azaz az 5·i+3 alakú számok, ahol i tetszőleges egész szám;
• a { ..., –16, –11, –6, –1, 4, 9, 14, 19, 24, ... } számhalmaz a 4-maradékosztály, azaz az 5·i+4 alakú számok, ahol i tetszőleges egész szám.

Általában 0, 1, 2, ..., (m-1) mod m maradékosztályokról beszélhetünk, ahol az egyszerűség kedvéért a 0, 1, 2, ... és m-1 a megnevezésben szereplő reprezentáns elemek.

A mod m maradékosztályok gyűrűt alkotnak: összeadhatók, kivonhatók és szorozhatók, de az osztás nem végezhető el reprezentáns elemekkel. Multiplikatív inverze ugyanis pontosan a redukált maradékosztályoknak van. Ezek minden eleme relatív prím m-hez. Ha m prím, akkor az invertálás segítségével az osztás is definiálható; ekkor a maradékosztályok gyűrűje test.

Maradékosztályokkal úgy számolhatunk, hogy tetszőleges reprezentáns elemükkel számolunk, ugyanis a maradékosztályok elemei egymást helyettesíthetik az egyenletekben.

Ha adott m darab egész szám, és közülük mindegyik más mod m maradékosztályt reprezentál, akkor ezek a számok teljes maradékrendszert alkotnak.

Néhány egész szám teljes maradékrendszert alkot mod m akkor és csak akkor, ha számuk m, és nincs köztük két egymással kongruens szám.

Bizonyítás: Legyen T_m teljes maradékrendszer mod m. Minden maradékosztályból egy és csak egy elem van T_m-ben, ezért T_m elemszáma m.

Mivel minden maradékosztályból egy elemet választottuk, ezért T_m elemei között nincs két szám, amely egymással kongruens.

Tekintsünk most m darab egész számot, amik között nincsenek kongruensek. Ezek csupa különböző maradékosztályba tartoznak, és mivel m darab van belőlük, azért az összes maradékosztály képviselve van.

Legyen r₁, r₂, …, r_m teljes maradékrendszer mod m. Legyen továbbá a relatív prím m-hez, b tetszőleges egész szám. Ekkor ar₁+b, ar₂+b, …, ar_m+b is teljes maradékrendszer mod m.

Bizonyítás: Az előző kritériumokra épül. Sorra ellenőrizünk mindent:

Az új rendszer elemszáma m.

Ha ar_i+b és ar_j+b kongruensek mod m, akkor a kongruencia mindkét oldalából b-t kivonva ar_i és ar_j kongruensek lennének. a relatív prím m-hez, ezért lehet vele egyszerűsíteni. Kapjuk, hogy r_i és r_j kongruensek. Ez csak úgy lehet, hogy i = j.

Ha a kongruens b mod m, akkor lnko(a, m) = lnko(b, m).

Bizonyítás: A kongruencia azt jelenti, hogy b = a + m·c valamely c egész számra. a és m is osztható lnko(a, m)-mel, ezért lnko(a, m) b-nek és m-nek is közös osztója, így lnko(a, m) osztója lnko(b, m)-nek.

A fordított oszthatóság ugyanígy, szerepcserével adódik.

• Alice és Bob - 18. rész: Alice és Bob felcsavarja a számegyenest
• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
• Alice és Bob - 22. rész: Alice, Bob és a kínaiak

• Freud Róbert – Gyarmati Edit: Számelmélet. Budapest: Tankönyvkiadó. 2000. ISBN 963 19 0784 8