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$.

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