Teorija, formulas, atrisināts piemērs un pārbaudes jautājumi latviešu valodā. Bezmaksas CE matemātikas sagatavošanās.
Skaitlis $a$ dalās ar $b$, ja $a = b \cdot k$ kādam veselam $k$ (atlikums $0$).
Kongruence: $a \equiv r \pmod{m}$ nozīmē, ka $a$ un $r$ dod vienādu atlikumu, dalot ar $m$.
Piemērs: $17 \equiv 2 \pmod 5$, jo $17 = 3 \cdot 5 + 2$ (atlikums $2$).
Pirmskaitļi dalās tikai ar $1$ un sevi; salikti — ir citi dalītāji.
| Dalās ar | Pazīme |
|---|---|
| $2$ | pēdējais cipars pāra |
| $3$ | ciparu summa dalās ar 3 |
| $5$ | beidzas ar 0 vai 5 |
| $9$ | ciparu summa dalās ar 9 |
Kongruences saskaita un reizina kā vienādojumus: ja $a \equiv b$ un $c \equiv d \pmod m$, tad $a+c \equiv b+d$ un $ac \equiv bd$.
Uzdevums: Kāds ir $2^{100}$ atlikums, dalot ar $3$?
1. solis. $2 \equiv -1 \pmod 3$ (jo $2 = 3 - 1$).
2. solis. Tad $2^{100} \equiv (-1)^{100} = 1 \pmod 3$.
Atbilde: atlikums $1$.
Dalāmības piemērs: vai $471$ dalās ar $3$? Ciparu summa $4+7+1 = 12$ dalās ar $3$ → jā.
Kongruences ļauj strādāt ar mazo atlikumu, ne lielo skaitli. $2 \equiv -1 \pmod 3$ padara lielas pakāpes triviālas.
Dalāmības pazīmes ietaupa laiku: ciparu summas triks 3 un 9, pēdējie cipari 2, 5, 10.
Atlikumu uzdevumos meklē ciklu: $2^1=2, 2^2=1, 2^3=2, \ldots \pmod 3$ — atkārtojas ik pēc 2.
⚠️ Kongruence attiecas uz ATLIKUMU, ne vienādību. $17 \equiv 2 \pmod 5$ nenozīmē $17 = 2$.
⚠️ Dalāmība ar $3$ un $9$ — ciparu summa, ne pats skaitlis. $471$: skaties $4+7+1$.
⚠️ Dalot negatīvus, atlikums parasti ņem nenegatīvu ($0 \le r < m$).