Основно съдържание

Курс: Компютърни науки > Раздел 2

Урок 5: Модулна аритметика

Какво е модулна аритметика?

Въведение в модулната математика

Когато разделяме две цели числа, ще имаме уравнение като следното:

$\frac{A}{B} = Q остатък R$ ‍

A

е делимо

B

е делител

Q

е частно

R

е остатък

Понякога ни интересува само остатъкът от делението на

A

B

.
В тези случаи използваме оператор, наречен модулно делене (накратко мод).

Като използваме същите означения

A

B

Q

R

от по-горе, получаваме:

A mod B = R

Казваме, че

A

mod

B

е равно на

R

. Където

B

се означава като модул.

Например:

$\begin{array}{rcl} \frac{13}{5} & = & 2 остатък 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

Демонстриране на модула с часовник

Да разгледаме какво се случва, когато увеличаваме числа с 1 и след това ги делим на 3.

$\begin{array}{rcl} \frac{0}{3} & = & 0 остатък 0 \\ \frac{1}{3} & = & 0 остатък 1 \\ \frac{2}{3} & = & 0 остатък 2 \\ \frac{3}{3} & = & 1 остатък 0 \\ \frac{4}{3} & = & 1 остатък 1 \\ \frac{5}{3} & = & 1 остатък 2 \\ \frac{6}{3} & = & 2 остатък 0 \end{array}$ ‍

Остатъкът започва от 0 и всеки път се увеличава с 1, докато достигне числото, на което делим. След това последователността се повтаря.

След като забележим това, можем да онагледим оператора за деление по модул с използване на кръгове.

Написваме 0 в горната част на кръга и продължаваме по посока на часовниковата стрелка, като изписваме целите числа 1, 2..., докато не стигнем до числото, с 1 по-малко от модула.

Например един часовник, при който числото 12 е заменено с 0, ще бъде кръг за модулно делене на 12.

За да намерим резултата от

A mod B

, можем да следваме тези стъпки:

Взимаме часовник с размер $B$ ‍
Започваме от 0 и се движим по часовника $A$ ‍ стъпки
Там, където спрем, е нашето решение.

(Ако числото е положително, се движим по посока на часовниковата стрелка, ако е отрицателно, се движим в посока, обратна на часовниковата стрелка.)

Примери

$8 mod 4 = ?$ ‍

С модул 4 можем да направим часовник с числата 0, 1, 2, 3.
Започваме от 0 и минаваме през 8 числа по посока на часовниковата стрелка в последователността 1, 2, 3, 0, 1, 2, 3, 0.

Завършваме на 0, така че

8 mod 4 = 0

$7 mod 2 = ?$ ‍

При модул 2 взимаме часовник с числата 0 и 1.
Започваме от 0 и минаваме през 7 числа по посока на часовниковата стрелка в последователността 1, 0, 1, 0, 1, 0, 1.

Завършихме на 1, така че

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

За модул 3 правим часовник с числата 0, 1, 2.
Започваме от 0 и минаваме през 5 числа в посока обратна на часовниковата стрелка в последователността (5 е отрицателно) 2, 1, 0, 2, 1.

Завършваме на 1, така че

- 5 mod 3 = 1

Заключение

Ако имаме

A mod B

и увеличим

A

с множител на $B$ ‍, ще завършим на същото място, т.е.

$A mod B = (A + K \cdot B) mod B$ ‍ за всяко цяло число $K$ ‍.

Например:

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

Бележки към читателя

mod в езиците за програмиране и в калкулаторите

В много от езиците за програмиране има оператор за делене с остатък, който обикновено е представен със знака %. Ако изчисляваш резултата за отрицателно число, в някои езици ще получиш отрицателен резултат.
Например:

-5 % 3 = -2.

Тъждествен модул

Може да видиш израз като:

$A \equiv B (mod C)$ ‍

Това означава, че

A

е тъждествено равно на

B

modulo

C

. Прилича на изразите, които използвахме тук, но не е съвсем същото.

В следващата статия ще обясним какво означава и как е свързано с изразите по-горе.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.

Компютърни науки