Mocniny v modulární aritmetice

x^y mod a = x^{y mod b} mod a

V minulé metodě jsme zjistili, že x^y mod 10 = x^{y mod 4} mod 10. Zajímalo mě, proč je to zrovna čtyři a ne kterékoliv jiné číslo. Samozřejmě to souvisí s tím, že bereme mod 10. Kdybychom např. brali mod 6, bylo by to:

x^y mod 6 = x^{y mod 2} mod 6

Proto mě zajímalo, jaký je vztah mezi a a b. Podívejte se na tuto tabulku:

a	b	c
2	1
3	2
4	2	1
5	4
6	2
7	6
8	2	2
9	6	1
10	4
11	10

Tabulka je samozřejmě velmi zjednodušená, musel jsem počítat s desítkami (přičemž ani Excel nedokázal zobrazit taková čísla, takže jsem musel něco občas počítat na Windows kalkulačce, která dokáže zobrazit více cifer než naprostá většina kalkulaček).

c udává počet prvních mocnin x, které musíme vynechat, aby tam to vyšlo. Př.

	x	x2	x3	x4	x5	x6	x7
1	1	1	1	1	1	1	1
2	2	4	0	0	0	0	0
3	3	1	3	1	3	1	3
4	4	0	0	0	0	0	0
5	5	1	5	1	5	1	5
6	6	4	0	0	0	0	0
7	7	1	7	1	7	1	7
8	0	0	0	0	0	0	0
9	1	1	1	1	1	1	1

Samozřejmě jsou všechny výsledky v mod 8. Jak je vidět, když vynecháme x¹ a x², tak se nám opakují dvě posloupnosti. Proto když a = 8 –> b = 2 a c = 2.

Pojďme se tedy podívat na způsob, jak zjistit b a c.

Nejprve si udělejte rozklad čísla a na prvočísla. Nejvyšší prvočíslo v rozkladu nazývejme p (jeho mocninu n) a nejvyšší mocninu všech prvočísel nazývejme m.

b = p^{n - 1}(p - 1)

Pokud p = 2 (2 je největší prvočíslo, takže a je mocnina dvojky, tedy např. čísla 8, 16, 32…) a n ≥ 3, udělejte operace n – 2 místo n – 1. Přiznám se, že nedokážu odůvodnit, proč to tak je, ale musíte to udělat, aby vám to vyšlo.

c = m – 1

 

Př.

a = 24 = 2³ * 3

p = 3

n = 1

m = 3

b = 3⁰(2) = 2

c = 3 – 1 = 2

 

Př.

a = 25 = 5²

p = 5

n = 2

m = 2

b = 5¹(4) = 20

c = 2 – 1 = 1

 

A konečně s desítkou:

a = 10 = 5 * 2

p = 5

b = 4

c = 0

Tak jsem si konečně odpověděl na otázku, proč zrovna 4.