Остатъци и сравнения по модул — урок по теория на числата

1. Сравнения по модул

🤔 Загадка: Каква е последната цифра на $7^{2026}$ ? Числото има над 1700 цифри и никой калкулатор няма да го покаже – но отговорът се намира за минута, на ум.

О

Сравнение по модул

Казваме, че

a

е сравнимо с

b

по модул

m

, и пишем

a \equiv b \pmod{m}

, ако

m \mid a - b

, т.е. ако

a

и

b

дават еднакъв остатък при деление на

m

. Например

38 \equiv 3 \pmod 7

,

-1 \equiv 6 \pmod 7

и

100 \equiv 0 \pmod{10}

.

По модул $m$ всяко е „същото“ като остатъка си – едно от числата $0, 1, \ldots, m - 1$ . Те са като деленията на часовник с $m$ часа: при $m = 12$ това е обикновеният часовник, при $m = 7$ – дните от седмицата.

m12a5

0, 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0, …

НОД(5, 12) = 1 – стъпките по 5 обхождат всички 12 остатъка.

💡 По модул m числата „живеят“ на часовник с m деления: след m − 1 идва пак 0. При m = 12 това е обикновеният часовник, при m = 7 – дните от седмицата. Пробвай степените на 2 по модул 7 и по модул 11, или на 3 по модул 10 – оттам идват последните цифри на 3ⁿ.

2. Действия със сравнения

Т

Свойства

Ако

a \equiv b

и

c \equiv d \pmod{m}

, то

a + c \equiv b + d

,

a - c \equiv b - d

,

ac \equiv bd

и

a^n \equiv b^n \pmod{m}

. С други думи – можем да заменяме числата с остатъците им във всеки сбор, разлика, произведение и степен. Делението е опасно: може да делим на

k

само ако

\text{НОД}(k,\ m) = 1

.

Доказателство

Нека $a = b + mk$ и $c = d + ml$ . Тогава $a \pm c = (b \pm d) + m(k \pm l)$ , т.е. $a \pm c \equiv b \pm d$ .
Произведение: $ac = (b + mk)(d + ml)$ $= bd + m(bl + dk + mkl) \equiv bd$
Степен: $a^n = a \cdot a \cdots a$ – прилагаме правилото за произведение $n - 1$ пъти (по индукция).
Деление: от $ka \equiv kb$ следва $m \mid k(a - b)$ . Ако $\text{НОД}(k,\ m) = 1$ , по лемата на Евклид (чрез Безу) $m \mid a - b$ , т.е. $a \equiv b$ . Без това условие не става: $2 \cdot 3 \equiv 2 \cdot 0 \pmod 6$ , но $3 \not\equiv 0 \pmod 6$ .

∎

Пример

Последната цифра на $7^{2026}$ – отговорът на загадката.

Последната цифра е остатъкът по модул 10. $7^1 \equiv 7$ , $7^2 = 49 \equiv 9$ , $7^3 \equiv 9 \cdot 7 = 63 \equiv 3$ , $7^4 \equiv 3 \cdot 7 = 21 \equiv 1$
Щом $7^4 \equiv 1$ , степените се повтарят през 4: $2026 = 4 \cdot 506 + 2$
$7^{2026} = (7^4)^{506} \cdot 7^2 \equiv 1 \cdot 49 \equiv 9 \pmod{10}$ – последната цифра е 9.

Така се обясняват и признаците за от урока Делимост и прости числа: понеже $10 \equiv 1 \pmod 9$ , всяка степен на 10 е $\equiv 1$ и числото е сравнимо със сбора от цифрите си. А понеже $10 \equiv -1 \pmod{11}$ , степените на 10 са последователно $+1$ и $-1$ – оттам идва знакопроменливият сбор.

3. Контролни цифри

Баркодовете, номерата на банковите сметки (IBAN), ISBN на книгите и ЕГН завършват с контролна цифра, пресметната по модул. Ако касиерът сбърка една цифра при ръчно въвеждане, сравнението „не излиза“ и системата веднага го забелязва.

Баркод (12 или 13 цифри):

цифра	3	8	0	1	2	3	4	5	6	7	8	9
тегло	×1	×3	×1	×3	×1	×3	×1	×3	×1	×3	×1	×3
произв.	3	24	0	3	2	9	4	15	6	21	8	27

Сбор: 122 ≡ 2 (mod 10) ⇒ контролна цифра 8 (допълва сбора до 130)

Пълният баркод е 3801234567898.

💡 Българските баркодове започват с 380. Смени една цифра от валиден 13-цифрен баркод – проверката винаги открива грешката. Размяната на две съседни цифри също се открива, освен ако те се различават точно с 5 (тогава 1·a + 3·b и 1·b + 3·a дават еднакъв остатък по модул 10).

4. Малката теорема на Ферма

Т

Малка теорема на Ферма

Ако

p

е просто число и

p \nmid a

, то

a^{p-1} \equiv 1 \pmod{p}

. Следствие:

a^p \equiv a \pmod{p}

за всяко цяло

a

.

Доказателство

Разглеждаме числата $a,\ 2a,\ 3a,\ \ldots,\ (p - 1)a$ . Никое не се дели на $p$ (простото $p$ не дели нито $i < p$ , нито $a$ ).
Остатъците им са различни: ако $ia \equiv ja$ , то $p \mid (i - j)a$ , значи $p \mid i - j$ , а при $1 \le i,\ j \le p - 1$ това е възможно само при $i = j$ .
Следователно остатъците са точно $1, 2, \ldots, p - 1$ , разбъркани. Например при $p = 7$ , $a = 3$ : $3, 6, 2, 5, 1, 4$ .
Умножаваме всички: $a \cdot 2a \cdots (p - 1)a \equiv 1 \cdot 2 \cdots (p - 1)$ , т.е. $(p - 1)! \cdot a^{p-1} \equiv (p - 1)! \pmod p$ .
Числото $(p - 1)!$ е взаимно просто с $p$ , затова можем да го съкратим: $a^{p-1} \equiv 1 \pmod p$ . Следствието $a^p \equiv a$ получаваме, като умножим по $a$ ; при $p \mid a$ двете страни са $\equiv 0$ .

∎

a \ k	1	2	3	4	5	6
1	1	1	1	1	1	1
2	2	4	1	2	4	1
3	3	2	6	4	5	1
4	4	2	1	4	2	1
5	5	4	6	2	3	1
6	6	1	6	1	6	1

m7

7 е просто: в колоната k = 6 всички числа са 1 – това е малката теорема на Ферма.

💡 Клетката в ред a и колона k е остатъкът на aᵏ при деление на m; зелените са единиците. Сравни m = 7, 11, 13 с m = 8, 9, 12. Забележи и че всеки ред се повтаря периодично – периодът дели m − 1, когато m е просто.

Пример

Да намерим остатъка на $2^{100}$ при деление на 7.

По Ферма $2^6 \equiv 1 \pmod 7$ (всъщност дори $2^3 = 8 \equiv 1$ ).
$100 = 6 \cdot 16 + 4 \Rightarrow 2^{100} \equiv 2^4 = 16 \equiv 2 \pmod 7$

Пиер дьо Ферма формулира теоремата в писмо през 1640 г., без доказателство („бих ви изпратил доказателството, ако не се опасявах, че е твърде дълго“). Първото публикувано доказателство е на Ойлер, близо век по-късно.

5. Уравнения по модул

Т

Линейно сравнение

Ако

\text{НОД}(a,\ m) = 1

, сравнението

ax \equiv b \pmod{m}

има единствено решение по модул

m

. Намираме обратното число

a^{-1}

(с

a \cdot a^{-1} \equiv 1

) и умножаваме:

x \equiv a^{-1} b

.

Доказателство

Обратно число съществува: по Безу $\text{НОД}(a,\ m) = 1$ означава, че $au + mv = 1$ за някои цели $u,\ v$ , т.е. $au \equiv 1 \pmod m$ . Полагаме $a^{-1} = u$ .
$x = a^{-1}b$ е решение: $a \cdot a^{-1}b \equiv 1 \cdot b = b$ .
Единственост: ако $ax_1 \equiv ax_2$ , делим на $a$ (може, защото $\text{НОД}(a,\ m) = 1$ ) и получаваме $x_1 \equiv x_2 \pmod m$ .

∎

Пример

Да решим $3x \equiv 4 \pmod 7$ .

Обратното на 3 по модул 7 е 5: $3 \cdot 5 = 15 \equiv 1$ .
$x \equiv 5 \cdot 4 = 20 \equiv 6 \pmod 7$
Проверка: $3 \cdot 6 = 18 = 2 \cdot 7 + 4$ ✓

Т

Китайска теорема за остатъците

Ако модулите

m_1, m_2, \ldots, m_k

са два по два взаимно прости, системата

x \equiv r_i \pmod{m_i}

има единствено решение по модул

m_1 m_2 \cdots m_k

.

Доказателство (за два модула)

Нека $\text{НОД}(m_1,\ m_2) = 1$ . Намираме обратните числа: $u$ с $m_1 u \equiv 1 \pmod{m_2}$ и $v$ с $m_2 v \equiv 1 \pmod{m_1}$ . Полагаме $x = r_1 m_2 v + r_2 m_1 u$
По модул $m_1$ второто събираемо е 0, а $m_2 v \equiv 1$ , следователно $x \equiv r_1$ . По модул $m_2$ – симетрично, $x \equiv r_2$ .
Единственост: ако $x$ и $x_1$ са решения, $x - x_1$ се дели на $m_1$ и на $m_2$ . Щом те са взаимно прости, $x - x_1$ се дели на $m_1 m_2$ .
Пример: $x \equiv 2 \pmod 3$ , $x \equiv 3 \pmod 5$ . Имаме $3 \cdot 2 \equiv 1 \pmod 5$ ( $u = 2$ ) и $5 \cdot 2 \equiv 1 \pmod 3$ ( $v = 2$ ), откъдето $x = 2 \cdot 5 \cdot 2 + 3 \cdot 3 \cdot 2 = 38 \equiv 8 \pmod{15}$ .
При повече модули прилагаме същото последователно: първо обединяваме първите две сравнения в едно по модул $m_1 m_2$ , който е взаимно прост с $m_3$ , и т.н.

∎

Обратното число по модул се намира и с разширения (виж НОД и НОК): от $ax + my = 1$ следва $ax \equiv 1 \pmod{m}$ .

6. Тренажор

Остатъци на степени, последни цифри, дни от седмицата и сравнения.

✅ Решени: 0🔥 Серия: 0🏆 Рекорд: 0

3x \equiv 1 \pmod{5}

Намери $x$ от $0$ до $4$ .

7. Модулната аритметика около нас

Календарът, часовникът, музикалните тонове и контролните цифри са модулна аритметика. Тя движи и компютрите: процесорът смята по модул $2^{32}$ или $2^{64}$ , а шифрирането в интернет степенува огромни числа по модул.

0 / 6

📅 След 100 дни

12 октомври 2026 г. е понеделник. Кой ден от седмицата ще е 100 дни по-късно? Въведете номера му (1 – понеделник, …, 7 – неделя).

🕘 Часовникът

Сега е 9 ч. Колко ще е часът след 100 часа (в 24-часов формат)?

🛒 Баркод

Баркодът на български продукт започва с 380123456789. Каква е контролната (13-а) цифра? Цифрите се умножават последователно по 1 и 3, а контролната цифра допълва сбора до кратно на 10.

🏯 Задачата на Сун Дзъ

В древнокитайски трактат (между III и V век) се пита: има неизвестен брой предмети. Ако ги броим по 3, остават 2; по 5 – остават 3; по 7 – остават 2. Колко е най-малкият възможен брой?

🔁 Последната цифра

Каква е последната цифра на $3^{2026}$ ?

🎹 Квинтовият кръг

Октавата има 12 полутона, а квинтата е 7 полутона. Ако тръгнем от „до“ и се изкачваме с квинти, след колко квинти ще стигнем отново до „до“ (в някоя по-висока октава)?

Зелено – решена сам(а), жълто – с решението. Десетичните числа може да пишеш със запетая.

8. ⚠️ Чести грешки

Деление на сравнение

✗ $\displaystyle 6 \equiv 16 \pmod{10} \Rightarrow 3 \equiv 8 \pmod{10}$

✓ делим на 2, но $\displaystyle \text{НОД}(2,\ 10) \ne 1$ : вярно е само $\displaystyle 3 \equiv 8 \pmod 5$

Отрицателен остатък

✗ $\displaystyle -7$ дава остатък $\displaystyle -1$ при деление на 3

✓ остатъкът е 2: $\displaystyle -7 = 3 \cdot (-3) + 2$

Степенният показател по модул

✗ $\displaystyle 7^{2026} \equiv 7^{6} \pmod{10}$ , защото $\displaystyle 2026 \equiv 6$

✓ показателят се намалява по периода на степените (4), не по модула

Ферма без просто число

✗ $\displaystyle 2^8 \equiv 1 \pmod 9$

✓ $\displaystyle 2^8 = 256 \equiv 4 \pmod 9$ – теоремата е за прости модули

Сравнение в показателя

✗ $\displaystyle 1 \equiv 4 \pmod 3 \Rightarrow 2^1 \equiv 2^4 \pmod 3$

✓ $\displaystyle 2 \not\equiv 16 \equiv 1 \pmod 3$

Последна цифра на сбор

✗ последната цифра на $\displaystyle 17 + 28$ е $\displaystyle 7 + 8 = 15$

✓ вземаме и нея по модул 10: цифрата е 5

9. 🎯 Бърз тест

1 / 9

✓ 0

Какъв е остатъкът при деление на 17 на 5?

Избери отговор (или натисни 1–4)

10. 📝 Задачи за упражнение

0 / 0

Ниво А· Областен кръг

Ниво В· Национален кръг

Ниво С· Международна олимпиада

11. Обобщение

✓ $a \equiv b \pmod{m} \iff m \mid a - b$ – еднакви остатъци
✓ Ферма се доказва, като видим, че $a, 2a, \ldots, (p - 1)a$ са разбъркани остатъците $1, 2, \ldots, p - 1$
✓ Сравненията се събират, изваждат, умножават и степенуват; делим само на числа, с модула
✓ Степените по модул се повтарят периодично – така намираме последни цифри и остатъци на огромни степени
✓ Ферма: $a^{p-1} \equiv 1 \pmod p$ за просто $p \nmid a$
✓ $ax \equiv b \pmod m$ при $\text{НОД}(a,\ m) = 1$ : умножаваме по обратното число
✓ Китайска теорема: системи с взаимно прости модули имат единствено решение по модул произведението

💡 Интересен факт

Шифърът RSA (1977 г., Ривест, Шамир и Ейдълман) се основава на обобщението на теоремата на Ферма от Ойлер: съобщението се повдига на огромна степен по модул произведение на две големи . Да шифроваш е лесно, а да дешифрираш без ключа изисква разлагане на модула – задача, за която не е известен бърз начин. По-късно се разбира, че британският криптограф Клифърд Кокс открива същата идея още през 1973 г., но работата му остава секретна до 1997 г.