Kongruence a aritmetické funkce
Řešené příklady
Příklad. Určete, zda jsou čísla a, b kongruentní podle modulu m:
1. a = 5, b = 15, m = 4
2. a = 3, b = 1, m = 2
3. a = 7, b = 25, m = 3
4. a = 7, b = 25, m = 4
Řešení. 1.
5 - 15 = -10
4  -10
5  15 (mod 4)
2.
3 = 1  2 +1
1 = 0  2 +1
3  1 (mod 2)
3.
7 - 25 = -12
3 | -12
7  25 (mod 3)
4.
7 = 1  4 +3
25 = 6  4 +1
7  25 (mod 6)
Příklad. Udejte příklad aritmetické funkce.
Řešení. Například funkce (a), (a).
1
Příklad. Určete (72).
Řešení. 72 = 23
 32
(72) = 0
Příklad. Určete, zda je Möbiova funkce multiplikativní. Zdůvodněte.
Řešení. Funkce je multiplikativní, pokud je aritmetická a pro všechna nesoudělná čísla a, b
splňuje rovnost f(a  b) = f(a)  f(b).
Möbiova funkce je definovaná na množině přirozených čísel, je tedy aritmetická. Zbývá
dokázat, že je funkcí multiplikativní.
Nechť a = pk1
1  pk2
2      pkn
n , b = pl1
1  pl2
2      pln
n , kde pi je prvočíslo, ki, li  N0, ki + li  1,
i  {1, 2, . . ., n}, n je největší přirozené číslo takové, že kn > 0  ln > 0.
a  b = pk1+l1
1  pk2+l2
2      pkn+ln
n
1. i  {1, 2, . . ., n} : ki > 1  li > 1  (a) = 0  (b) = 0  (a)  (b) = 0 = (a  b)
2. i  {1, 2, . . ., n} : ki  1  li  1. Protože čísla a, b jsou ze zadání multiplikativní
funkce nesoudělná, platí také (ki = 0  li = 1)  (ki = 1  li = 0). Označme k počet
prvočísel, pro která platí ki = 1, l počet prvočísel, pro která platí li = 1. Platí tedy:
(a  b) = (-1)k+l
= (-1)k
 (-1)l
= (a)  (b).
Möbiova funkce tedy je funkcí multiplikativní.
Příklad. Určete (10) podle definice.
Řešení.
(10) = |{a  N|0 < a  10, (a, 10) = 1}| = |{1, 3, 7, 9}| = 4
Příklad. Určete (1377).
Řešení. 1377 = 34
 17
(1377) = (34
)  (17) = (3 - 1)  33
 (17 - 1) = 864
Příklad. Dokažte, že pro všechna přirozená čísla m, k platí:
(mk
) = mk-1
 (m).
Řešení. Označme m = pk1
1  pk2
2      pkn
n .
(mk
) = ((pk1
1 pk2
2   pkn
n )k
) = (pkk1
1 pkk2
2   pkkn
n ) = (pkk1
1 )(pkk2
2 )  (pkkn
n ) =
= pkk1-1
1  (p1)  pkk2-1
2  (p2)      pkkn-1
n  (pn) =
= (pk1
1 )k-1
 pk1-1
1  (p1)  (pk2
2 )k-1
 pk2-1
2  (p2)      (pkn
n )k-1
 pkn-1
n  (pn) =
= (pk1
1  pk2
2      pkn
n )k-1
 (pk1
1 )  (pk2
2 )      (pkn
n ) = mk-1
 (m)
Příklad. Určete řád čísla 7 modulo 15.
2
Řešení. Řád čísla a modulo m je nejmenší takové číslo, pro nějž platí ar
 1 (mod m).
Také víme, že řád r dělí (m). Protože (15) = 2  4 = 8, stačí ověřit čísla 1, 2, 4 a 8.
71
 7 (mod 15)
72
 49  4 (mod 15)
74
 (72
)2
 42
 16  1 (mod 15).
Řád čísla 7 modulo 15 je roven 4.
Příklad. Určete poslední číslici dekadického zápisu čísla 3123456
.
Řešení. Určení poslední číslice dekadického zápisu je ekvivalentí otázce, jaký zbytek dává
zadané číslo po dělení deseti, a tedy i kongruenci modulo deset. Řešíme tedy kongruenci
3123456
? (mod 10).
(10) = (2)(5) = 1  4 = 4
Z Eulerovy věty víme, že platí 34
 1 (mod 10).
Protože 123456 : 4 = 30864, můžeme zadanou kongruenci snadno vyřešit:
3123456
 (34
)30864
 130864
 1 (mod 10).
Příklad. Určete poslední číslici dekadického zápisu čísla 17151311
.
Řešení. Řešíme kongruenci 17151311
? (mod 10). Využijeme vlastnosti řádu r čísla a, pro
který platí:
am
 an
(mod m)  m  n (mod r)
V našem případě je a = 17  7 (mod 10), hledáme tedy řád čísla 7 modulo 10.
(10) = 4  r  {1, 2, 4}
71
 7 (mod 10)
72
 9  -1 (mod 10)
74
 (72
)2
 (-1)2
 1 (mod 10)  r = 4.
17151311
 7151311
 7x
(mod 10)  151311
 x (mod 4).
151311
 (-1)1311
(mod 4) řád čísla -1 modulo 4 je roven číslu 2 
 (-1)1311
 x  (-1)y
(mod 4)  1311
 y (mod 2)  y  1 (mod 2) 
 x  -1  3 (mod 4)  7x
 73
 3 (mod 10)  17151311
 3 (mod 10)
Poslední číslicí čísla 17151311
je číslice 3.
Příklad. Kolik m  N : 106
< m < 107
je dělitelných 786?
Řešení. m  {k  786, (k + 1)  786, . . . , (k + l)  786 : k  m > 106
 (k + l)  786 < 107
}
počet: [(x < 107
) - (x < 106
)]
107-1
786
- 106
786
Příklad. Určete počet n  N : n < 100  (n, 36) = 1.
Řešení. 36 = 22
 32
počet čísel dělitelných 2. . . 99
2
= 49
počet čísel dělitelných 3. . . 99
3
= 33
počet čísel dělitelných 6. . . 99
6
= 16
99 - (49 + 33) + 16 = 33
3