Modula aritmetiko

Modula aritmetiko
matematika studfako matematika teorio
aritmetiko • matematiko
v • d • r

Modula aritmetiko estas sistemo de aritmetiko por entjeroj, kie nombroj "turniĝas reen", al nulo, post kiam ili atingas certan valoron — la modulon. Modulan aritmetikon prezentis Carl Friedrich Gauss en sia libro Disquisitiones Arithmeticae (publikigita en 1801).

Ekzemplo de modula aritmetiko estas kutima horloĝo: la aritmetiko de horoj sur la horloĝo. Se la tempo estas 7 horoj, tiam post 8 horoj estos 15 horoj (t.e. validas kutima adicio). Se la tempo estas 7 horoj, tiam post 19 horoj estos 7+19=26 horoj (laŭ la kutima adicio). Sed horloĝo uzas modulon 24, do estas 26 mod 24=2 horoj (de la sekva tagnokto).

Du entjeroj a kaj b estas kongruaj module (aŭ modulite) je n, se a kaj b havas la saman reston, kiam ili estas dividitaj per n (por pozitivaj entjeroj), aŭ ekvivalente, ke ilia diferenco (a−b) estas produto de n kaj entjero (por ĉiaj entjeroj). En ĉi tiu okazo, la afero estas esprimita kiel

a ≡ b (mod n).

Ekzemple,

38 ≡ 14 (mod 12)

ĉar 38 − 14 = 24, kiu estas entjera oblo de 12.

Kongrueco laŭ modulo estas ekvivalentrilato tia, ke la ekvivalentklaso de entjero a estas la aro [a]_n = { ... a − 3n, a − 2n, a − n, a, a + n, a + 2n, a + 3n, ...}. Ĉi tiu aro de ĉiuj entjeroj kongruaj al a je modulo n estas nomata kongrueca klaso aŭ n-modula restoklaso de a je modulo n kaj estas skribata ankaŭ kiel ${\displaystyle {\hat {a}}}$.

Se

a₁ ≡ b₁ (mod n)

kaj

a₂ ≡ b₂ (mod n)

tiam

a₁ + a₂ ≡ (b₁ + b₂) (mod n)

kaj

a₁a₂ ≡ b₁b₂ (mod n).

• RSA (kriptado)