Zenbakien teorian , kongruentzia terminoa bi zenbaki oso
a
{\displaystyle a}
eta
b
{\displaystyle b}
,
m
≠
0
{\displaystyle m\neq 0}
zenbaki arruntaz —modulua deiturikoa— zatitzerakoan, hondar berdina dutela adierazteko erabiltzen da. Honako notazio hau erabiliz:
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
Honela irakurtzen da:
a
{\displaystyle a}
kongruente
b
{\displaystyle b}
modulu
m
{\displaystyle m}
.
a
{\displaystyle a}
eta
b
{\displaystyle b}
m
{\displaystyle m}
moduluarekiko kongruenteak dira, baldin eta soilik baldin
m
{\displaystyle m}
moduluak
a
{\displaystyle a}
eta
b
{\displaystyle b}
-ren arteko desberdintza zehazki zatitzen badu, hau da,
m
|
a
−
b
{\displaystyle m|a-b}
. Beste modu batera esanda,
a
{\displaystyle a}
eta
b
{\displaystyle b}
-k
m
{\displaystyle m}
-rekiko zatiketan, hondar bera uzten badute. Gainera, baiezta daiteke
a
{\displaystyle a}
zenbakia
b
{\displaystyle b}
-ren batura eta
m
{\displaystyle m}
-ren multiplo bezala idatzi daitekela,
m
|
a
−
b
{\displaystyle m|a-b}
denez,
m
k
=
a
−
b
{\displaystyle mk=a-b}
izango da
k
∈
Z
{\displaystyle k\in \mathbb {Z} }
batentzat eta orduan,
a
=
b
+
m
k
{\displaystyle a=b+mk}
.
Kongruentziak hainbat modu matematikotan adieraz daitezke. Esate baterako, adierazpen hauek baliokideak dira:
a
{\displaystyle a}
kongruente
b
{\displaystyle b}
modulu
m
{\displaystyle m}
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
a
{\displaystyle a}
zati
m
{\displaystyle m}
-ren hondarra
b
{\displaystyle b}
zati
m
{\displaystyle m}
-ren hondarra da
a
mod
m
=
b
mod
m
{\displaystyle a\;{\bmod {\;}}m=b\;{\bmod {\;}}m}
m
{\displaystyle m}
-k zehatz zatitzen du
a
{\displaystyle a}
eta
b
{\displaystyle b}
-ren kendura
m
∣
a
−
b
{\displaystyle m\mid a-b}
a
{\displaystyle a}
idatz daiteke
b
{\displaystyle b}
-ren eta
m
{\displaystyle m}
-ren multiplo baten batura bezala
∃
k
∈
Z
a
=
b
+
k
m
{\displaystyle \exists k\in \mathbb {Z} \quad a=b+km}
Kongruentziak
m
{\displaystyle m}
moduluarekiko
a
{\displaystyle a}
eta
b
{\displaystyle b}
zenbakien arteko baliokidetasun-erlazio bat adierazten du, hurrengo erlazioak betetzen dituelako:
Erlazio bihurkaria (erreflexiboa) :
a
≡
a
(
mod
m
)
{\displaystyle a\equiv a{\pmod {m}}}
,
a
{\displaystyle a}
guztietarako.
Simetria erlazioa :
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
bada,
b
≡
a
(
mod
m
)
{\displaystyle b\equiv a{\pmod {m}}}
da.
Iragate-erlazioa (trantsitiboa) :
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
eta
b
≡
c
(
mod
m
)
{\displaystyle b\equiv c{\pmod {m}}}
badira,
a
≡
c
(
mod
m
)
{\displaystyle a\equiv c{\pmod {m}}}
izango da.
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
eta
k
∈
Z
{\displaystyle k\in \mathbb {Z} }
badira:
a
(
+
−
)
k
≡
b
(
+
−
)
k
(
mod
m
)
{\displaystyle a(+-)k\equiv b(+-)k{\pmod {m}}}
a
k
≡
b
k
(
mod
m
)
{\displaystyle ak\equiv bk{\pmod {m}}}
a
k
≡
b
k
(
mod
m
)
{\displaystyle a^{k}\equiv b^{k}{\pmod {m}}}
k
>
0
{\displaystyle k>0}
Gainera,
a
{\displaystyle a}
eta
b
{\displaystyle b}
elkarrekiko lehenak badira, beste zenbait propietate ere betetzen dituzte, besteak beste:
a
{\displaystyle a}
zenbakia
m
{\displaystyle m}
eta
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
-rekiko lehena bada,
b
{\displaystyle b}
ere
m
{\displaystyle m}
-rekiko lehena izango da.
k
{\displaystyle k}
m
{\displaystyle m}
-rekiko lehena bada, orduan
∃
h
−
1
{\displaystyle \exists {\displaystyle h^{-1}}}
non
k
h
−
1
≡
1
(
mod
m
)
{\displaystyle {\displaystyle kh^{-1}\equiv 1{\pmod {m}}}}
. Horregatik, zatiketari buruz aritzeak zentzua du eta beraz, zuzena da
a
k
≡
b
k
(
mod
m
)
{\displaystyle {\displaystyle {\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {m}}}}
non definizioz,
a
/
k
=
a
k
−
1
{\displaystyle {\displaystyle a/k=ak^{-1}\,}}
.
Aurrekoaren ondorio bezala, modulu bereko bi kongruentzia badaude,
a
≡
b
(
mod
m
)
{\displaystyle {\displaystyle a\equiv b{\pmod {m}}}}
eta
c
≡
d
(
mod
m
)
{\displaystyle {\displaystyle c\equiv d{\pmod {m}}}}
, batu, kendu edo biderka ditzakegu, kongruentziak egiaztatzeko:
a
+
c
≡
b
+
d
(
mod
m
)
{\displaystyle {\displaystyle a+c\equiv b+d{\pmod {m}}}}
eta
a
c
≡
b
d
(
mod
m
)
{\displaystyle {\displaystyle ac\equiv bd{\pmod {m}}}}
.
Fermaten teorema txikia : Izan bitez
p
{\displaystyle p}
lenbaki lehena eta
a
∈
N
{\displaystyle a\in \mathbb {N} }
.
a
{\displaystyle a}
,
p
{\displaystyle p}
-ren multiploa ez bada orduan:
a
(
p
−
1
)
(
q
−
1
)
≡
1
(
mod
p
q
)
{\displaystyle a^{(p-1)(q-1)}\equiv 1{\pmod {pq}}}
Izan bitez
p
{\displaystyle p}
eta
q
{\displaystyle q}
zenbaki lehenak eta
a
∈
N
{\displaystyle a\in \mathbb {N} }
.
a
{\displaystyle a}
ez bada ez
p
{\displaystyle p}
-ren ez
q
{\displaystyle q}
-ren multiploa, orduan:
Edozein kongruentzia-erlazio bezala, n kongruentzia-modulua baliokidetasun-erlazio bat da, eta a zenbaki osoaren baliokidetasun-klasea,
a
n
¯
{\displaystyle {\bar {a_{n}}}}
bidez adierazten dena, {… , a − 2n , a − n , a , a + n , a + 2n , …} multzoa da. Multzo hori, a modulo n-rekin kongruenteak diren zenbaki osoek osatzen dute. Baliokidetasun-erlazioa denez, baliokidetasun-klaseak defini daitezke. Klase bakoitzean m-rekin zatitzean hondar bera ematen duten zenbaki osoak daude. Beraz, m hondar desberdin daudenez, m baliokidetasun-klase daude. Bakoitzaren ordezkari modura 0, 1, . . . eta m − 1 zenbakiak har daitezke. Baliokidetasun klasea [
a
{\displaystyle a}
] bezala ere adieraz daiteke.
7
≡
3
(mod 4)
{\displaystyle 7\equiv 3\ {\mbox{(mod 4)}}\ }
, 7 = 3 + 1 ⋅ 4 baita.
82
≡
1
(mod 9)
{\displaystyle 82\equiv 1\ {\mbox{(mod 9)}}\ }
, 82 = 1 + 9 ⋅ 9 baita.
27
≡
0
(mod 3)
{\displaystyle 27\equiv 0\ {\mbox{(mod 3)}}\ }
, 27 = 0 + 3 ⋅ 3 baita.
−
3
≡
3
(mod 6)
{\displaystyle -3\equiv 3\ {\mbox{(mod 6)}}\ }
, -3 = 3 + -1 ⋅ 6 baita.
2
≢
5
(mod 6)
{\displaystyle 2\not \equiv 5\ {\mbox{(mod 6)}}\ }
, 2 ≠ 5 + k ⋅ 6 baita.