Kongruencia
Kongruencia (lat.) alatt rendesen két idom egybevágását értik. Kongruensnek v. egybevágónak oly idomokat mondunk, melyek ugy alakra, mint nagyságra nézve megegyeznek, tehát egymástól csak helyzetre nézve különböznek. - K.-nak nevezik továbbá a vonalaknak, különösen az egyenes vonalaknak valamely kétszeresen végtelen sokaságát. Ilyent képeznek p. a tér mindazon egyenesei, melyek két adott egyenes mindegyikét metszik.
A számelméletben két szám, a és b az n osztóra (modulusra) nézve kongruensnek akkor mondatik, ha n-nel való osztásuk után ugyanazt a maradékot hagyják. Jelekben ezt igy fejezzük ki:
a ≡ b (mod. n).
P.
18 ≡ 23 (mod. 5),
mert 18 és 23 az 5 osztóra nézve egyaránt 3-at hagy maradékul. A K. tehát a maradékok azonosságának rövidített kifejezésmódja. Ha n valamely egész szám és
f(x) ≡ a0 xm + a1 xm-1 + ... + am-1 x + am
| (mod. n), |
akkor x amaz értékeinek meghatározása, amelyekre nézve f(x) osztható n-nel, az
f(x) ≡ 0 (mod. n) (1)
m-ed foku K. megoldásának neveztetik. Ha a modulus összetett szám, akkor (1)-nek megoldása az n törzstényezőire vonatkoztatott K.-k megoldására vezethető vissza, ugy hogy külön csakis törzsszám-modulusokra vonatkozó K.-kkal kell foglalkoznunk. Legyen tehát
Φ(x) ≡ b0xm + b1xm-1 + ... + bm ≡ 0
| (mod. p) (2) |
K.-nak modulusa p törzsszám és tegyük fel, hogy a b együtthatók nem mindannyian oszthatók p-vel (ellenkező esetben a K.-t minden szám elégíti ki), akkor a K. fokszáma (p-2)-re redukálható, még pedig az x-nek minden p-vel nem osztható értékére fennálló
xp-1 ≡ 1 (mod. p)
Fermat-féle K. segítségével. Ily módon a K. megoldása mindig
Ψ(x) ≡ c0xp-2 + ... + cp-2 (mod. p) (3)
alaku K.-ra vezet. Arra az alapkérdésre, mikor van ily K.-nak megoldása, a következő Königtől származó tétel adja a felvilágosítást: arra, hogy a
Ψ(x) ≡ 0 (mod. p)
K.-nak a k különböző megoldása legyen, szükséges és elegendő, hogy a
ciklikus determináns, valamint annak összes aldeterminánsai egészen a k-adikig, p-vel oszthatók legyenek. - K. a nyelvtanban, l. Szóegyeztetés.
