Conţinutul principal

Să învățăm despre operatorul modulo!

Introducere în împărțirea cu rest

Când împărțim două numere întregi, avem o egalitate care arată în felul următor:

$\frac{A}{B} = Q rest R$ ‍

A

este deîmpărțitul

B

este împărțitorul

Q

este câtul

R

este restul

Uneori, ne interesează doar valoarea restului atunci când împărţim

A

B

.
Pentru aceste situații, există un operator numit operator modulo (abreviat mod).

Folosind aceleași denumiri

A

B

Q

și

R

ca mai sus, am avea:

A mod B = R

Putem spune că

A

modulo

B

este egal cu

R

, unde

B

este numit modulus (Atenție! Nu este modul, ci reprezintă altceva.)

De exemplu:

$\begin{array}{rcl} \frac{13}{5} & = & 2 rest 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

Vizualizăm resturile cu ajutorul ceasurilor

Observă ce se întâmplă când incrementăm (creștem) numerele cu unu și apoi le împărțim la 3.

$\begin{array}{rcl} \frac{0}{3} & = & 0 rest 0 \\ \frac{1}{3} & = & 0 rest 1 \\ \frac{2}{3} & = & 0 rest 2 \\ \frac{3}{3} & = & 1 rest 0 \\ \frac{4}{3} & = & 1 rest 1 \\ \frac{5}{3} & = & 1 rest 2 \\ \frac{6}{3} & = & 2 rest 0 \end{array}$ ‍

Resturile încep de la 0 și cresc cu 1 de fiecare dată, până când numărul ajunge cu unu mai puțin decât împărțitorul. După aceea, secvența se repetă.

Observând acest lucru, putem vizualiza operatorul modulo folosind cercuri.

Scriem 0 în partea de sus a unui cerc și continuăm să scriem, în sensul acelor de ceasornic, numere întregi 1, 2, ... până la o valoare cu unu mai mică decât modulus.

De exemplu, un ceas cu ora 12 înlocuită cu 0 ar fi cercul pentru modulus egal cu 12.

Pentru a găsi rezultatul

A mod B

putem parcurge pașii următori:

Construim acest ceas pentru dimensiunea $B$ ‍
Începem de la 0 și ne deplasăm pe ceas $A$ ‍ pași
Punctul în care ne oprim reprezintă soluția noastră.

(Dacă numărul este pozitiv atunci vom parcurge cercul în sensul acelor de ceasornic, dacă este negativ atunci îl vom parcurge în sens invers acelor de ceasornic

Exemple

$8 mod 4 = ?$ ‍

Pentru modulus având valoarea 4 facem un ceas cu numerele 0, 1, 2, 3.
Începem de la 0 și parcurgem succesiv 8 numere în sensul acelor de ceasornic: 1, 2, 3, 0, 1, 2, 3, 0.

Am ajuns la 0, ceea ce înseamnă că

8 mod 4 = 0

$7 mod 2 = ?$ ‍

Pentru modulus având valoarea 2 facem un ceas cu numerele 0, 1.
Începem de la 0 și parcurgem succesiv 7 numere în sensul acelor de ceasornic: 1, 0, 1, 0, 1, 0, 1.

Am ajuns la 1, ceea ce înseamnă că

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

Pentru modulus având valoarea 3 facem un ceas cu numerele 0, 1, 2.
Începem de la 0 și parcurgem succesiv 5 numere în în sens invers acelor de ceasornic (-5 este negativ): 2, 1, 0, 2, 1.

Am ajuns la 1, ceea ce înseamnă că

- 5 mod 3 = 1

Concluzie

Dacă avem

A mod B

și adunăm la

A

un multiplu de $B$ ‍, vom ajunge în același loc, adică:

$A mod B = (A + K \cdot B) mod B$ ‍ pentru orice întreg $K$ ‍.

De exemplu:

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

Observații pentru cititor

Modulo în limbajele de programare și calculatoare

Multe limbaje de programare și calculatoare au un operator pentru mod, reprezentat de obicei cu simbolul %. Calculând rezultatul pentru un modululus negativ, unele limbaje vor da un rezultat negativ.
De exemplu:

-5 % 3 = -2.

Congruență Modulo

Putem vedea o expresie precum:

$A \equiv B (mod C)$ ‍

Se spune că

A

este congruent cu

B

modulo

C

. Este similar cu expresiile pe care le-am folosit aici, dar nu chiar identic.

În articolul următor explicăm ce înseamnă și care este legătura cu expresiile de mai sus.

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