Modula aritmetiko

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search

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

Ekzemplo por modula aritmetiko estas kutima horloĝo: la aritmetiko de horoj sur la horloĝo. Se la tempo estas 7 horoj do post 8 horoj estas 15 horoj (kiel en kutima aldono). Se la tempo estas 7 horoj do post 19 horoj estas (7+19)=26 horoj (laŭ en kutima aldono), sed horloĝo uzas modulon 24, do estas 26 mod 24=2 horoj (de la sekva diurno).

La rilato[redakti | redakti fonton]

Du entjeroj a kaj b estas kongruaj module (aŭ modulite) je n, se a kaj b havas la saman reston kiam 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

ab (mod n).

Ekzemple,

38 ≡ 14 (mod 12)

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

Kongrueco estas ekvivalentrilato. Ekvivalentklaso de la entjero a estas signifita per [a]n = { ..., a − 2n, an, a, a + n, a + 2n, a + 3n, ...}. Ĉi tiu aro de ĉiuj entjeroj kongruaj al a module je n estas nomita kiel la kongrueca klason-modula restoklaso de a module je n, kaj estas ankaŭ signifis per .

Se

a1b1 (mod n)

kaj

a2b2 (mod n)

tiam

a1 + a2 ≡ (b1 + b2) (mod n)

kaj

a1a2b1b2 (mod n).