Conţinutul principal

Adunarea și scăderea claselor de resturi modulo n

Să explorăm proprietățile adunării în contextul aritmeticii modulare (a claselor de resturi modulo n)

(A + B) mod C = (A mod C + B mod C) mod C

Exemplu:

Fie A=14, B=17, C=5

Acum să verificăm: (A + B) mod C = (A mod C + B mod C) mod C
PSE = Partea stângă a egalității
PDE = Partea dreaptă a egalității

PSE = (A + B) mod C
PSE = (14 + 17) mod 5
PSE = 31 mod 5
PSE = 1

PDE = (A mod C + B mod C) mod C
PDE = (14 mod 5 + 17 mod 5) mod 5
PDE = (4 + 2) mod 5
PDE = 1

PSE = PDE = 1

Explicație intuitivă a adunării claselor de resturi modulo n

Să observăm figura de mai jos. Dacă vrem să calculăm 12+9 mod 7, putem să parcurgem cercul resturilor modulo n pentru o secvență de 12+9 pași în sens orar (după cum este prezentat în cercul din stânga jos).

Putem să o folosim o scurtătură observând că la fiecare 7 pași ajungem în aceeași poziție pe cercul resturilor. Aceste bucle de parcurgere în jurul cercului resturilor nu contribuie la găsirea poziției noastre finale. Putem ignora aceste bucle complete în jurul cercului calculând fiecare număr mod 7 (după cum este arătat în cele două cercuri de resturi modulare din partea de sus a desenului). Acest lucru ne va da numărul de pași în sens orar, pornind din 0, care au contribuit la fiecare dintre pozițiile lor finale în jurul cercului de resturi modulo n.

Acum tot ce mai trebuie să facem este să parcurgem cercul în sens orar atâția pași câți au contribuit la poziția finală pentru fiecare dintre numere (după cum se vede la cercul de resturi din dreapta jos). Această metodă se aplică, în general, la oricare două numere întregi și orice cerc de resturi modulo n.

Demonstrație pentru adunarea în clasele de resturi modulo n

Vom demonstra că (A + B) mod C = (A mod C + B mod C) mod C
Trebuie să arătăm că PSE=PDE

Conform teoremei împărțirii cu rest putem scrie A și B după cum urmează:

A = C * Q1 + R1, unde 0 ≤ R1 < C și Q1 este un număr întreg. A mod C = R1
B = C * Q2 + R2, unde 0 ≤ R2 < C și Q2 este un număr întreg. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2

PSE = (A + B) mod C
PSE = (C * (Q1 + Q2) + R1+ R2) mod C
Putem elimina multiplii lui C atunci când calculăm restul modulo C
PSE = (R1 + R2) mod C

PDE = (A mod C + B mod C) mod C
PDE = (R1 + R2) mod C

PSE=PDE= (R1 + R2) mod C

Scăderea claselor de resturi modulo n

Demonstrația pentru scăderea claselor de resturi modulo n se face similar cu cea pentru adunare.

(A - B) mod C = (A mod C - B mod C) mod C

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.

Teoria informației și criptografie

Curs: Teoria informației și criptografie > Unitatea 2