Teorēma par pakāpes periodiskumu pēc moduļa — teorija. Matemātika, Gatavošanās matemātikas olimpiādēm.

Uzdevumos par veselu skaitļu pakāpēm ar mainīgu vai lielu kāpinātāju, bieži vien izmanto sekojošu teorēmu:

Virkne

x_{n} = a^{n}

pēc moduļa $m$ ir periodiska.

Perioda garumu un tajā ietilpstošos skaitļus var atrast, rakstot pēc kārtas skaitļus

a^{n}

pēc moduļa $m$. Tiklīdz virknē

a^{n} (\mod m)

parādās kāds jau bijis skaitlis, ir atrasts periods. Perioda garums nepārsniedz $m$.

Tā kā kongruence pēc moduļa $m$ sadala visus veselos skaitļus $m$ klasēs, kur katrā klasē ietilpst skaitļi, kas dod vienādus atlikumus pēc moduļa $m$, tad īpašību, kas jāpierāda visiem veseliem skaitļiem, pietiek pierādīt katras klases skaitļiem atsevišķi.

Piemērs:

Kādu atlikumu dod skaitlis

3^{49}

dalot ar $7$?

Atrisinājums. Pēc teorēmas, virkne

3^{n}

, ja $n =0,1,2,...,$ ir periodiska pēc moduļa $7$. Apskata šīs virknes pirmos locekļus:

ja $n=0$, tad

3^{0} \equiv 1 (\mod 7)

;

ja $n=1$, tad

3^{1} \equiv 3 (\mod 7)

;

ja $n=2$, tad

3^{2} \equiv 9 \equiv 2 (\mod 7)

;

Ievēro, ka tālāk izdevīgi izmantot iepriekšējo kongruenci!

ja $n=3$, tad

3^{3} \equiv 3^{2} \cdot 3 \equiv 2 \cdot 3 \equiv 6 (\mod 7)

;

ja $n=4$, tad

3^{4} \equiv 3^{3} \cdot 3 \equiv 6 \cdot 3 \equiv 18 \equiv 4 (\mod 7)

;

ja $n=5$, tad

3^{5} \equiv 3^{4} \cdot 3 \equiv 4 \cdot 3 \equiv 12 \equiv 5 (\mod 7)

;

ja $n=6$, tad

3^{6} \equiv 3^{5} \cdot 3 \equiv 5 \cdot 3 \equiv 15 \equiv 1 (\mod 7)

ja n=7, tad

3^{7} \equiv 3^{6} \cdot 3 \equiv 1 \cdot 3 \equiv 3 (\mod 7)

...

Redzam, ka atlikums $1$ un $3$ atkārtojas, tāpēc ir atrasts periods.

Šo informāciju ērti apkopot tabulā:

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	...
$3^{n} (\mod 7)$	$1$	$3$	$2$	$6$	$4$	$5$	$1$	…

Redzam, ka virkne

3^{n} (\mod 7)

ir periodiska ar perioda garumu $6$.

3^{0} \equiv 3^{6} \equiv 1 (\mod 7)

Tātad

3^{49} \equiv 3^{6 \cdot 8 + 1} \equiv 3^{1} \equiv 3 (\mod 7)

Atbilde. Skaitlis

3^{49}

, dalot ar $7$, dod atlikumu $3$.

Atsauce:

http://nms.lu.lv/wp-content/uploads/2015/12/teorija_Skaitludalamiba_Kongruences.pdf

Materiālu sagatavoja Mg. math. Laima Baltiņa, JTV skolotāja

Iepriekšējā teorija

Atgriezties tēmā

Nākamais uzdevums

Nosūtīt atsauksmi

Atradi kļūdu?

Sūti mums ziņu!

\(n\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	...
$3^{n} (\mod 7)$	\(1\)	\(3\)	\(2\)	\(6\)	\(4\)	\(5\)	\(1\)	…

9. Teorēma par pakāpes periodiskumu pēc moduļa

Teorija