Van-e olyan x és y természetes szám, amelyre teljesül, hogy a 17 osztója a 20x-11y-nak, de nem osztója a 46x + 7y-nak?

Ez a jel ("≡") a kongruencia. Hajaz az egyenlőségjelre, mert azt fejezi ki, hogy két szám vagy kifejezés ugyanabba a maradékosztályba tartozik az adott számmal (modulo) való oszthatóság szempontjából. Így aztán bizonyos tekintetben valóban egyenlőségről is van szó. Az algebra ismer olyan struktúrákat (algebrai testeknek hívják ezeket), ahol definiálható két művelet (az összeadás és a szorzás), és teljesülnek bizonyos feltételek. Ilyen algebrai test a valós számok halmaza, a komplex számok, a racionális számok, de a maradékosztályok is, ha a modulus prímszám.

A feladat, amit hoztál, F_17-ben számol (F mint "field", az algebrai test angol neve, és 17 mint modulus). Ennek a testnek az elemei a 17 maradékosztályai, és az egyes maradékosztályok minden tagja egyenértékű (pl. a 34 a nullával teljesen egyenértékű, mert nullát ad maradékul 17-tel osztva). Ezért lehetett csak úgy elvenni és hozzáadni a kifejezéshez.

Természetesen maradékosztályokat más modulus mellett is fel lehet állítani, nem kizárólag prímszámokkal, csak ezek nem alkotnak algebrai testet, és bizonyos műveleteknél ezt figyelembe kell venni.

@24: Igen, de igazából pont ettől nem kell megijedni.

Ha van két halmazod, akkor azok elemeiből tudsz párokat alkotni, ahol az első elem az egyik, a második elem a másik halmazból származik. Ezen párok halmazt alkotnak. Ennek a halmaznak a részhalmazait nevezzük relációknak. Ha az (a,b) pár benne van az R relációban, azt aRb formában írjuk hagyományosan.

Ha a két halmaz ugyanaz, akkor a relációt a "halmaz felett" értelmezzük. Na, ezekről lehet a következőket állítani:

- Reflexív a reláció, ha minden elem önmagával relációban van: xRx.

- Szimmetrikus egy reláció, ha aRb esetén bRa is teljesül. Antiszimmetrikus, ha az aRb vagy bRa teljesül.

- Tranzitív a reláció, ha aRb és bRc esetén aRc is teljesül.

Na, a reflexív, szimmetrikus és tranzitív relációkat nevezzük ekvivalenciának. Ilyen az egyenlőség a számok között, és ilyen a kongruencia is, amiről fentebb volt szó.

Konkrétan a≡b mod(p) azt jelenti, hogy p|(a-b).

Az ekvivalenciarelációk a halmaz elemeit csoportokba sorolja, amiket faktorhalmazoknak nevezünk. Ezek a faktorhalmazok szigorúan diszjunktak (próbáld bizonyítani, tök könnyű), úgyhogy sok esetben a halmaz egy belső tulajdonságát jellemzik. De például így lehet a természetes számokból az egész és azokból a racionális számokat megalkotni.