Liekanos

Nagrinėjant skaitinių ar algebrinių reiškinių dalumą kartais labai patogu nagrinėti veiksmus tik su liekanomis. Atskirai panagrinėsime veiksmus su liekanomis skaitiniams reiškiniams ir algebriniams reiškiniams.

Liekanų panaudojimas skaitiniuose reiškiniuose

Apibrėžimas 1. Duoti sveikieji skaičiai a, b ir natūralusis skaičius $n\ge 2$. Sakome, kad skaičiai a ir b lygsta moduliu n ir rašome $a\equiv b(\mathrm{mod}n)$, jei a–b dalijasi iš n.
Teorema 1. $a\equiv b(\mathrm{mod}n)$ tada ir tik tada, kai skaičius a ir b dalydami iš n, gauname vienodas liekanas.

Savybės:
1) Jei a, dalijant iš n , gauname liekaną r, tai $a\equiv r(\mathrm{mod}n)$.
2) Jei $a\equiv b(\mathrm{mod}n)$ ir $c\equiv d(\mathrm{mod}n)$, tai
a) $a+c\equiv b+d(\mathrm{mod}n)$,
b) $a-c\equiv b–d(\mathrm{mod}n)$,
c) $a\cdot c\equiv b\cdot d(\mathrm{mod}n)$,
d) $a^m\equiv b^m(\mathrm{mod}n)$.
3) Refleksyvumas: visiems skaičiams a: $a\equiv a(\mathrm{mod}n)$ .
4) Simetriškumas: jei $a\equiv b(\mathrm{mod}n)$, tai $b\equiv a(\mathrm{mod}n)$.
5) Tranzityvumas: jei $a\equiv b(\mathrm{mod}n)$, $b\equiv c(\mathrm{mod}n)$, tai $a\equiv c(\mathrm{mod}n)$.

Be įrodymo pateiksim dar porą teoremų, kuriomis galima naudotis sprendžiant uždavinius.

Teorema 2. Seka $x_n=a^n$ bet kuriuo moduliu yra periodinė. Periodo didumą ir jį sudarančius narius galima rasti, rašant paeiliui skaičius $a^n$ moduliu m. Kuomet sekos kiekvienas narys kartojasi, mes esame radę periodą. Aukštesnių laipsnių reiškiniams naudosime tokią teoremą:
Teorema 3. (Mažoji Ferma teorema (MFT)) Jei p yra pirminis skaičius ir a nesidalija iš p, tuomet $a^{p-1}-1$ dalijasi iš p.

Naudodami lyginius pagal modulį  MFT galim parašyti taip: $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Pavyzdys 1. Kokia liekana gaunama skaičių $A={10}^3\cdot {20}^2\cdot 30$ dalijant iš $n=7$?

Sprendimas. $10\equiv 3(\mathrm{mod}7)$,
$20\equiv -1(\mathrm{mod}7)$,
$30\equiv 2(\mathrm{mod}7)$.
Tuomet ${10}^3\cdot {20}^2\cdot 30=3^3\cdot (-1{)}^2\cdot 2=5(\mathrm{mod}7)$.

Pavyzdys 2. Apskaičiuokime  $1234+5678+9876(\mathrm{mod}10)$.

Sprendimas. $1234\equiv 4(\mathrm{mod}10)$,
$5678\equiv 8(\mathrm{mod}10)$,
$9876\equiv 6(\mathrm{mod}10)$.
Tada $1234+5678+9876\equiv 4+8+6\equiv 8(\mathrm{mod}10)$.

Pavyzdys 3. Apskaičiuokime $5^5(\mathrm{mod}7)$.

Sprendimas. $5^1\equiv 5(\mathrm{mod}7)$,
$5^2=25\equiv 4(\mathrm{mod}7)$,
$5^3=5^2\cdot 5^1\equiv 4\cdot 5=20\equiv 6(\mathrm{mod}7)$,
$5^4=5^3\cdot 5^1\equiv 6\cdot 5=30\equiv 2(\mathrm{mod}7)$,
$5^5=5^4\cdot 5^1\equiv 2\cdot 5=10\equiv 3(\mathrm{mod}7)$,
Tuomet $5^5\equiv 3(\mathrm{mod}7)$.

Pavyzdys 4. Apskaičiuokime $2^{23}(\mathrm{mod}10)$.

Sprendimas.

n	1	2	3	4	5	6	…
$2^n(\mathrm{mod}10)$	2	4	8	6	2	4	…

Tuomet, $2^{4k+1}\equiv 2(\mathrm{mod}10)$,
$2^{4k+2}\equiv 4(\mathrm{mod}10)$,
$2^{4k+3}\equiv 8(\mathrm{mod}10)$,
$2^{4k}\equiv 6(\mathrm{mod}10)$,
$2^{23}=2^{4\cdot 5+3}\equiv 8(\mathrm{mod}10)$.

Liekanų panaudojimas algebriniuose reiškiniuose

Pavyzdys 1. Įrodykime, kad skaičius $5^n+2\cdot 3^{n-1}+1$ dalijasi iš 8 su visais natūraliaisiais skaičiais n.

Sprendimas. Jei $n=2k+1$, tai
$5^n+2\cdot 3^{n-1}+1=5\cdot {25}^k+2\cdot 9^k+1=5\cdot 1^k+2\cdot 1^k+1\equiv 0(\mathrm{mod}8)$.
Jei $n=2k$, tai
$5^n+2\cdot 3^{n-1}+1={25}^k+2\cdot 3\cdot 9^{k-1}+1=1^k+6\cdot 1^k+1\equiv 0(\mathrm{mod}8)$.

Pavyzdys 2. Koks yra skaičiaus ${9999}^{{999}^{{99}^9}}$ paskutinis skaitmuo?

Sprendimas. Duotojo skaičiaus paskutinis skaitmuo yra 9, nes
${9999}^{{999}^{{99}^9}}\equiv {(-1)}^{2k+1}\equiv -1\equiv 9(\mathrm{mod}10)$.