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

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

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

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

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

Класна стая на Google

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

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

start fraction, A, divided by, B, end fraction, equals, Q, start text, space, о, с, т, а, т, ъ, к, space, end text, R

A е делимо
B е делител
Q е частно
R е остатък

Понякога ни интересува само остатъкът от делението на A и B.
В тези случаи използваме оператор, наречен модулно делене (накратко мод).

Като използваме същите означения A, B, Q и R от по-горе, получаваме: A, start text, space, m, o, d, space, end text, B, equals, R

Казваме, че A mod B е равно на R. Където B се означава като модул.

Например:

$\begin{eqnarray} \dfrac{13}{5} &=& 2 \text{ остатък } \bf{3} \\ 13 \text{ mod } 5 &=& \bf{3} \\ \end{eqnarray}$

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

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

$\begin{eqnarray} \frac{0}{3} &=& 0 \text { остатък } \bf{0} \\ \frac{1}{3} &=& 0 \text { остатък } \bf{1} \\ \frac{2}{3} &=& 0 \text { остатък } \bf{2} \\ \frac{3}{3} &=& 1 \text { остатък } \bf{0} \\ \frac{4}{3} &=& 1 \text { остатък } \bf{1} \\ \frac{5}{3} &=& 1 \text { остатък } \bf{2} \\ \frac{6}{3} &=& 2 \text { остатък } \bf{0} \end{eqnarray}$

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

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

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

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

За да намерим резултата от A, start text, space, m, o, d, space, end text, B, можем да следваме тези стъпки:

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

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

Примери

8, start text, space, m, o, d, space, end text, 4, equals, question mark

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

Завършваме на 0, така че 8, start text, space, m, o, d, space, end text, 4, equals, 0.

7, start text, space, m, o, d, space, end text, 2, equals, question mark

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

Завършихме на 1, така че 7, start text, space, m, o, d, space, end text, 2, equals, 1.

minus, 5, start text, space, m, o, d, space, end text, 3, equals, question mark

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

Завършваме на 1, така че minus, 5, start text, space, m, o, d, space, end text, 3, equals, 1.

Заключение

Ако имаме A, start text, space, m, o, d, space, end text, B и увеличим A с множител на B, ще завършим на същото място, т.е.

A, start text, space, m, o, d, space, end text, B, equals, left parenthesis, A, plus, K, dot, B, right parenthesis, start text, space, m, o, d, space, end text, B за всяко цяло число K.

Например:

$\begin{eqnarray} 3 \text{ mod } 10 = 3 \\ 13 \text{ mod } 10 = 3 \\ 23 \text{ mod } 10 = 3 \\ 33 \text{ mod } 10 = 3 \\ \end{eqnarray}$

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

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

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

-5 % 3 = -2.

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

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

A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Това означава, че A е тъждествено равно на B modulo C. Прилича на изразите, които използвахме тук, но не е съвсем същото.

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

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

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

Сортирай по:

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

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