Schematická algebra - R-systémy
Definice R-systémů
Rozpad geometrické posloupnosti
Posloupnost čísel g,gn,gn²,gn³,... (g,n ε Z) se nazývá geometrická posloupnost. Uvažujme čísla nj (n,j ε Z) takové posloupnosti a jejich zbytky u po vydělení
číslem r (modulem): u=nj mod r.
Pro n=2, r=7, j=0..6 dostáváme:
2j 1 2 4 8 16 32 64
2j mod 7 1 2 4 1 2 4 1
Nyní, při každém výskytu čísla, které jsme již použili, zalomíme řádek a na dalším řádku začneme číslovat prvním dosud nepoužitým číslem. Pro přehlednost doplníme k zobrazeným číslům na začátek a na konec čísla 0 a r.
Pro r=7, nε{1..r−1} tak dostaneme:
n=1: 0 n=4: 0
1 1 4 2
2 3 5 6
3 7
4
5 n=5: 0
6 1 5 4 6 2 3
7 7
n=2: 0
1 2 4 n=6: 0
3 6 5 1 6
7 2 5
3 4
7
n=3: 0
1 3 2 6 4 5
7
Schéma čísel nj mod r nazýváme R-systém se základem n, řádu k podle modulu r a značíme R(n,k,r).
Hodnota k závisí na hodnotách n a r, protože je ale důležitou charakteristikou R-systému zařazujeme ji také do označení R(n,k,r).
Pro r=7, n=4 zjistíme, že řádky (kromě okrajových) se zalamují za třetím číslem, tedy k=3 a systém označíme R(4,3,7). Platí 43≡1 (mod 7).
(0) (1) (2)
(g0) 0
(g1) 1 4 2 m=4
(g2) 3 5 6
(g3) 7
k=3
Čísla v prvním sloupci {0,1,3,7} budeme považovat za reprezentanty druhů a označíme je gi, iε(0,m−1). Číslo m udává počet všech druhů. Všechna čísla 0,1,..,r nazveme instance a označíme je ui (j). Čísla jε(0,k−1) jsou čísla transpozic. Nejvyšší možný počet transpozic v systému R(n,k,r) je roven řádu k. Řád k čísla n podle modulu r je nejmenší číslo k (pro dané n a r) takové, že nk ≡1 (mod r).
Konstrukční pravidlo
V geometrické posloupnosti 1,n,n²,n³,...vždy existuje kromě prvního členu ještě nejméně jeden (k-tý) člen kongruentní s jedničkou podle modulu r. Toho využijeme při konstrukci R-systémů. Geometrická posloupnost 1,n,n²,n³,... je vždy v prvním řádku a první řádek se zalamuje, když se v posloupnosti čísel nj mod r (pro j=1,2,3...) objeví znovu jednička. Pro čísla n,k,r systému R(n,k,r) proto platí:
nk ≡ 1 mod r
Ať začneme jakýmkoliv číslem na kterémkoliv řádku, dostaneme po vynásobení nk opět totéž číslo (mod r).
Platí: a ∙ nk mod r = a, tj:
a∙(nk−1) ≡ 0 mod r
resp. r | a∙(nk−1).
Pokud (a,r)=1, tj. když čísla a a r jsou nesoudělná (pro rεP stačí aby bylo a<r) tak: r | (nk−1), tj. nk ≡ 1 mod r.
Algoritmus pro vytvoření
Náznak algoritmu pro R-systém (n=this.Degree, r=this.Size):
BitArray marked = new BitArray(this.Size + 1, false);
int g = 1;
this.TotalClasses++; this.TotalInstances++;
this.SelfClasses[1]++; this.SelfInstances[1]++;
while (g < this.Size) {
if (!marked.Get(g)) {
int u = g;
this.TotalClasses++;
int k = 0;
while (u != 0 && u < this.Size && !marked.Get(u)) {
this.TotalInstances++;
this.WriteInstance(u)
k++;
marked.Set(u, true);
u = (u * this.Degree) % this.Size;
}
this.SelfClasses[k]++;
this.SelfInstances[k] += k;
}
g = g + 1;
}
this.TotalClasses++; this.TotalInstances++;
this.SelfClasses[1]++; this.SelfInstances[1]++;
Základy patřící řádům
Když systémy se základy n1,n2,...mají řád k, říkáme že základy n1,n2,... patří řádu k.
Pro r= 7 přísluší řádům k základy n následovně:
k │ n ──┼────── 1 │ 1 2 │ 6 3 │ 2,4 6 │ 3,5
Když pro daná n, k platí: nk ≡1 (mod r) a neexistuje žádné d<k, pro které by bylo nd ≡1, říkáme, že číslo n patří číslu k. K existujícímu systému R(n,k,r) takové d<k se systémem R(n,d,r) nemůže existovat, jinak by R(n,k,r) nemohl vzniknout (řádky by se zalamovaly již na pozici d,…).
Prosté R-systémy
Když modul r je prvočíselný, říkáme, že systémy R(n,k,r) jsou prosté.
Kořeny kongruence
Když nk ≡1 (mod r), všechna čísla n,n²,n³,...nk jsou různá (mod r). Protože (n)k, (n²)k, (n³)k,... ≡1 ... jsou n,n²,n³,...nk kořeny kongruence xk ≡1.
Např.:
Fermat, Pierre de| Fermat, Pierre de [ferma], 1661-1665, francouzský matematik, 'král amatérů', povoláním právník. Znalosti jazyků mu umožnily studovat díla antických matematiků. Měl zvláštní intuici k formulování nových problémů i k tušení nestandardních řešení. Objevil metodu hledání maximálních a minimálních hodnot funkcí. Formuloval princip nejkratšího času v optice. V teorii křivek předjímal analytickou geometrii. Publikování nevěnoval velkou pozornost, jeho sebrané práce vyšly tiskem až r.1679. |
26 ≡ 64 ≡ 1 (mod 7)
36 ≡ 729 ≡ 1 (mod 7)
46 ≡ 4096 ≡ 1 (mod 7)
56 ≡ 15625 ≡ 1 (mod 7)
66 ≡ 46656 ≡ 1 (mod 7)
( Fermatova věta pro cyklické grupy...)
Malá Fermatova větaSystémy R(n,k,r) konstruujeme podle pravidla:
nk ≡ 1 mod r
Je-li r prvočíslo a k=r−1 (tj. n je primitivní kořen), dostáváme přímo tzv. malou Fermatovu větu:
nr−1 ≡ 1 mod r
Tedy číslo nr − n je dělitelné r.
r 2r-1 mod r 2r-1 ───────────────────────────────── 3 1 4 5 1 16 7 1 64 11 1 1024 13 1 4096 17 1 65536 19 1 262144 23 1 4194304 29 1 268435456 31 1 1073741824 37 1 68719476736 41 1 1099511627776
Obecně pro rεP platí: (a+b+c+...)r ≡ ar + br + cr +... (mod r). Po dosazení a=b=c=...=1 vyplyne přímo nr ≡ n (mod r).
(K větě se ještě vrátíme v odstavcích o G-systémech).
r 15r-1 mod r 15r-1 ─────────────────────────────────────── 2 1 15 7 1 11390625 11 1 576650390625 13 1 129746337890625 14 1 1946195068359375 17 1 6568408355712890625
Malá Fermatova věta platí obecně pro všechna čísla n, která nejsou násobkem r.
V případě n=15 ztrácí platnost pro prvočísla r = 3 a 5.
Opačná věta k malé Fermatově větě se nazývá čínská věta. Tato věta ale obecně neplatí (platí pro exponenty r<300). Složené číslo r může dělit výraz (nr−n). Např. 341 | 2341−2, přičemž 341=11∙31. Taková čísla r se nazývají pseudoprvočísla.
Mezi tzv. pseudoprvočísla patří všechna složená čísla M(2,p), kde pεP. Každý přirozený dělitel těchto čísel má tvar 2sp+1, kde sεN0.
Např. M(2,11) je dělitelné čísly {1,23,89,2047} tj. čísly 2sp+1, kde s ε{0,1,4,93}.
Pro ryzí lichá prvočísla p (pεP, p≡3 mod 4, p>7) číslo M(2,κ(p)) není prvočíslo.
Tato čísla budem nazývat Eulerova pseudoprvočísla. Platí:
p|(2κ(p)−1) => pεP
Např. 23|M(2,11), 47|M(2,23), 167|M(2,83), 263|M(2,131), ...
Absolutní pseudoprvočísla jsou taková r, kdy r | nr−n pro všechna n, např. 561 | n561−n, 561 = 3∙11∙17.
4Podíl f(n,r) = ((nr−1)−1)/r je tzv. Fermatův koeficient. Např. pro n=2 a 3:
r f(2,r) 2r−1 f(3,r) 3r−1
─────────────────────────────────────────────────────
3 1 4 − 9
5 3 16 16 81
7 9 64 104 729
11 93 1024 5368 59049
13 315 4096 40880 531441
17 3855 65536 2532160 43046721
19 13797 262144 20390552 387420489
23 182361 4194304 1364393896 31381059609
....
Pro čísla a,b nesoudělná s r splňují Fermatovy koeficienty vztah analogický logaritmování:
f(a∙b,r) ≡ f(a,r) + f(b,r) (mod r)
Např: pro a=2, b=3: f(2∙3,r) = f(2,r) + f(3,r) (mod r) :
r= 5: f(6, 5)=(64−1)/ 5 = 259 = f(2, 5)+f(3, 5) = 3+ 16 = 4(mod 5) r= 7: f(6, 7)=(66 −1)/ 7 = 6665 = f(2, 7)+f(3, 7) = 9+ 104 = 1(mod 7) r=11: f(6,11)=(610 −1)/11 = 5496925 = f(2,11)+f(3,11) = 93+ 5368 = 5(mod 11)
Specielně po dosazení a=b:
f(am,r) ≡ m∙f(a,r) (mod r)
Vztah k počtu druhů G-systému
Fermatův koeficient f(n,p) = ((np−1)−1)/p. V systémech G(n,p), pεP je celkový počet druhů roven m(n,p) = (np + (p−1)∙n)/p.
Tedy:
M(n,p) = n∙(f(n,p)+1)
resp.:
f(n,p) = (m(n,p)/n) −1
Eisensteinův VztahNechť rεP, r>2. Pro součet řady čísel 1/m, mε(1,p−1) platí:
1/1−1/2+1/3....−1/(p−1) ≡ 2∙f(2,r) mod r
kde f(2,r) je Fermatův koeficient.
Podobnost R-systémů
Duální systémy
Vygenerujeme-li systémy pro více různých prvočísel r, zjistíme, že některá podobná schemata se vyskytují vždy 2x. Dva systémy R(n1,k1,r) a R(n2,k2,r) nazveme duální, když platí:
n1∙n2≡1 mod r
Přitom je také k1=k2. Např. pro r=7, nε{1..r−1}:
R(1,1,7): 0 R(6,2,7): 0 1 1 6 2 2 5 3 3 4 4 7 5 6 7 R(2,3,7): 0 R(4,3,7): 0 1 2 4 1 4 2 3 6 5 3 5 6 7 7 R(3,6,7): 0 R(5,6,7): 0 1 3 2 6 4 5 1 5 4 6 2 3 7 7
Systémy R(2,7),R(4,7), resp. R(3,7),R(5,7) tvoří duální páry, 2∙4≡1 mod 7, resp. 3∙5≡1 mod 7.
Obecně mezi systémy R(n,k,r) existuje vždy (při rεP):
· (r div 2)−1 duálních systémů; součin jejich základů je ∏n≡1 (mod r)
· jeden systém s n=1; tj. n ≡ 1 mod r
· jeden systém s n=r−1; tj. n ≡ −1 mod r
Jsou-li n a n' dva duální základy, platí p\(n∙n'−1)
Koeficient duálních základů
Označme q(n,k) = (n∙n'−1)/p.
p │ k │ n (n←-→n') │ q(n,k)
────┼────┼────────────┼──────
3 │ 2 │ 2 │ 1
────┼────┼────────────┼──────
5 │ 2 │ 4 │ 3
│ 4 │ 2 ←-→ 3 │ 1
────┼────┼────────────┼──────
7 │ 2 │ 6 │ 5
│ 3 │ 2 ←-→ 4 │ 1
│ 6 │ 3 ←-→ 5 │ 2
────┼────┼────────────┼──────
11 │ 2 │10 │ 9
│ 5 │ 3 ←-→ 4 │ 1
│ │ 5 ←-→ 9 │ 4
│ 10 │ 2 ←-→ 6 │ 1
│ │ 7 ←-→ 8 │ 5
|
p │ k │ n (n←-→n') │ q(n,k)
────┼────┼────────────┼──────
13 │ 2 │12 │ 11
│ 3 │ 3 ←-→ 9 │ 2
│ 4 │ 5 ←-→ 8 │ 3
│ 6 │ 4 ←-→10 │ 3
│ 12 │ 2 ←-→ 7 │ 1
│ │ 6 ←-→11 │ 5
────┼────┼────────────┼──────
17 │ 2 │16 │ 15
│ 4 │ 4 ←-→13 │ 3
│ 8 │ 2 ←-→ 9 │ 1
│ │ 8 ←-→15 │ 7
│ 16 │ 5 ←-→ 7 │ 2
│ │ 3 ←-→ 6 │ 1
│ │10 ←-→12 │ 7
|
|
Leibnitz, Gottfried Wilhelm [lajbnyc], 1646-1716, německý matematik a filozof,
považovaný pro své znalosti širokého spektra oborů za polyhistora. Inspirován Pascalem vynalezl kalkulátor pro násobení a dělení, zabýval se dvojkovou soustavou, logickým kalkulem,... Pracoval s nekonečnými řadami. Objevil diferenciální a integrální počet, jeho symbolika se používá dodnes. Definoval tzv. živou sílu (kinetickou energii). Za základ světa považuje nekonečně malé (oduševnělé) substance (monády). |
Vynásobíme-li všechny základy kromě posledního, tj.všechna čísla 1..(r-2) dostaneme podle modulu r vždy výsledek 1.
Např. pro p=11:
1∙(2∙6)∙(3∙4)∙(5∙9)∙(7∙8) ≡ 1 (mod 11)
Obecně pro n=1..r−2 je:
∏ n ≡ 1 (mod r).
Pro každé r ε P tak platí tzv.Leibnitzova věta:
(r−2)!≡1 mod r
r (r−2)! mod r (r−2)! ─────────────────────────────────────── 2 1 1 3 1 1 5 1 6 7 1 120 11 1 362880 13 1 39916800 17 1 1307674368000 19 1 355687428096000 23 1 51090942171709440000
Wilson, John
| Wilson, John [wilzn], 1741-1793, anglický matematik a lékař. Krátce působil jako profesor matematiky v Cambridge. |
Poslední člen (r−1), který jsme doposud opomíjeli dává vždy podle modulu r výsledek −1.
Když vynásobíme předchozí součin ještě tímto členem dostaneme pro n=1..r−1:
∏ n ≡ −1 mod r
r (r-1)! mod r (r-1)! ────────────────────────────────── 2 -1 1 3 -1 2 5 -1 24 7 -1 720 11 -1 3628800 13 -1 479001600 17 -1 20922789888000 19 -1 6402373705728000 23 -1 1124000727777607680000
Pro prvočíselná r proto platí tzv.Wilsonova věta:
(r−1)! ≡ −1 mod r
Wilsonovu větu první publikoval E.Waring (1770) a dokázal J.L.Lagrange (1771).
K Wilsonově větě platí věta opačná: složené číslo r nemůže dělit výraz (r−1)! + 1. Pro neprvočíselná r je kromě případu r=4 vždy:
(r−1)! ≡ 0 mod r
r (r−1)! mod r (r−1)! ────────────────────────── 1 0 1 4 2 6 6 0 120 8 0 5040 9 0 40320 10 0 362880
Podíl w(r) = ((r−1)!+1)/r je pro rεP
tzv. Wilsonův koeficient. Např.
r w(r) (r-1)!+1 ─────────────────────────────── 1 2 2 2 1 2 3 1 3 5 5 25 7 103 721 11 329891 3628801 13 36846277 479001601
Kombinace vět
Fermatovu a Wilsonovu větu je možné spojit dohromady. Např. platí:
· p | [ap + (p−1)!a]
· p | [a + (p−1)!ap]
N.H.Abel uveřejnil úlohu, zda číslo np−1−1 (pεP) může být dělitelné p². Kongruenci np−1−1 ≡ 0 (mod p²) odpovídá (np−1−1)/p ≡ 0 (mod p), tj. f(n,p) ≡ 0 (mod p). Řešení Abelovy úlohy, které našel C.G.J.Jacobi, proto odpovídá na otázku, kdy je Fermatův koeficient dělitelný číslem p.
Wieferichova prvočísla
Wieferichova prvočísla jsou obecně taková čísla p pro která:
∑f(n,p) ≡ 0 (mod p²)
Specielně pro n=2 Wieferich dokázal, že jedině takováto prvočísla mohou vyhovět jako exponenty v I.případu (p nedělí xyz) Velké Fermatovy věty xp+yp=zp. Wieferichova prvočísla se vyskytují velmi řídce (jsou jimi např. čísla 1093 a 3511).
Lerch, Matyáš| Lerch, Matyáš , 1860-1922, český matematik. Zabýval se teorií čísel a matematickou analýzou. Objevil nové souvislosti týkající se funkce gama. Věnoval se také kvadratickým formám, eliptickým funkcím, funkcím, které nemají derivaci. Do českého jazyka zavedl pojem 'množina'. |
Lerchův vztah
Součet Fermatových koeficientů pro n=1,..,r−1 a Wilsonův koeficient jsou kongruentní podle modulu rεP:
∑f(n,r) ≡ w(r) (mod r)
Pro r=7:
F-koeficienty W-koeficient
───────────────────────────────────
(16−1)/7 = 0
(26−1)/7 = 9
(36−1)/7 = 104 (6!+1) / 7 = 103
(46−1)/7 = 585
(56−1)/7 = 2232
(66−1)/7 = 6665
───────────────────────────────────
9595 ≡ 103 mod 7
r ∑f(n,r)≡w(r) mod r ∑f(n,r) w(r) ───────────────────────────────────────────────────────────── 3 1 1 1 5 0 70 5 7 5 9595 103 11 1 1355849265 329891 13 0 1032458258546 36846277 17 5 1653031004194447736 1230752346353 19 2 3167496749732497119309 336967037143579 23 8 22841077183004879532481321651 48869596859895986087
Každé číslo nk−1 je (pro n>0) dělitelné číslem (n−1). Nabízí se proto každý uvedený Fermatův koeficient dělit ještě číslem (n−1) a zkoumat součet takto vznikajících hodnot.
Označme: L(n,r) = (nr−1/r/(n−1). Pro r=7:
L(n,r)
─────────────────────────
(16−1)/7/0 = (0)
(26−1)/7/1 = 9
(36−1)/7/2 = 52
(46−1)/7/3 = 195
(56−1)/7/4 = 558
(66−1)/7/5 = 1333
─────────────────────────
2147 ≡ −2 mod 7
Pro další r vycházejí následující výsledky:
r ∑L(n,r) mod r ∑L(n,r)
────────────────────────────────────────
3 −2 1
5 −2 28
7 −2 2147
11 −2 160213161
13 −2 98726033092
17 −2 114396055574628848
19 −2 192586455871197007965
23 −2 1117328029955356409095870411
...
Odtud tvrzení:
∑L(n,r) ≡ −2 (mod r)
Složené R-systémy
Složenými nazýváme systémy R(n,k,r), když r je číslo složené.
Úprava schemat
Konstantní počet čísel v řádcích (tj. počet transpozic) vzniká ve schematech jen pro prvočíselné moduly rεP. Ostatní moduly tuto vlastnost obecně nemají, např. pro r=10:
n=2: 0 n=3: 0
1 2 4 8 6 1 3 9 7
3 2 6 8 4
5 5
7 10
9
10
Schemata nejsou přehledná - algoritmus, který fungoval pro prvočíselná r, nedává smysl. Program R-system proto upravíme. Připustíme opakování čísel ve schematu - odřádkujeme jen při opakovaném výskytu čísla v řádku.
Pro r=7 dostaneme:
R(1,1,7) R(2,3,7) R(4,3,7) R(6,2,7) 0 0 0 0 1 1 2 4 1 4 2 1 6 2 2 4 1 2 1 4 2 5 3 3 6 5 3 5 6 3 4 4 4 1 2 4 2 1 4 3 5 5 3 6 5 6 3 5 2 6 6 5 3 6 3 5 6 1 7 7 7 7 R(3,6,7) R(5,6,7) 0 0 1 3 2 6 4 5 1 5 4 6 2 3 2 6 4 5 1 3 2 3 1 5 4 6 3 2 6 4 5 1 3 1 5 4 6 2 4 5 1 3 2 6 4 6 2 3 1 5 5 1 3 2 6 4 5 4 6 2 3 1 6 4 5 1 3 2 6 2 3 1 5 4 7 7
Pro prvočíselný modul r dostávají některá schemata podobu tzv.latinských čtverců řádu k nebo obecně latinských pravoúhelníků. V latinském pravoúhelníku se v každém řádku i sloupci každé číslo vyskytuje právě jednou.
Např. mezi uvedenými schematy pro r=7 jsou dva latinské čtverce: R(3,6,7),R(5,6,7) a tři obdélníky R(2,3,7),R(4,3,7),R(6,2,7).
Podobně pro r=3 najdeme jeden čtverec R(2,2,3) a pro r=5 dva čtverce R(2,4,5),R(3,4,5):
R(2,2,3) R(2,4,5) R(3,4,5)
0 0 0
1 2 1 2 4 3 1 3 4 2
2 1 2 4 3 1 2 1 3 4
3 3 1 2 4 3 4 2 1
4 3 1 2 4 2 1 3
5 5
Uvažujme složený modul r=pq, kde p,q εP. Podle malé Fermatovy věty pro prvočíselná p,q je:
pq−1−1 ≡ 0 (mod q) a qp−1−1 ≡ 0 (mod p)
Odtud:
(pq−1−1)(qp−1−1) ≡ 0 (mod pq)
pq−1qp−1−pq−1−qp−1+1 ≡ 0 (mod pq)
Tedy:
pq−1+qp−1 ≡ 1 mod pq
Např. 34+5²=106 ≡ 1 mod 15.
Fermat-Eulerova věta
Schemata pro r=10, n=2 a n=3:
n=2: 0 n=3: 0
1 2 4 8 6 1 3 9 7
2 4 8 6 2 6 8 4
3 6 2 4 8 3 9 7 1
4 8 6 2 4 2 6 8
5 5
6 2 4 8 6 8 4 2
7 4 8 6 2 7 1 3 9
8 6 2 4 8 4 2 6
9 8 6 2 4 9 7 1 3
10 10
V případě, kdy čísla n a r jsou nesoudělná, tj.(n,r)=1, nemají schemata více než φ(r) sloupců.
Např. pro r=10, n=3, (10,3)=1 a φ(10)=4 má schema právě 4 sloupce.
Tuto zákonitost shrnuje věta Fermat-Eulerova, tj. zobecněná (malá) Fermatova věta. Pro nesoudělná čísla n,r platí:
nφ(r) ≡ 1 mod r
Tedy číslo nφ(r)+1−n je dělitelné r.
Podíl q(n,r) = (nφ(r)−1)/r nazveme Fermat-Eulerův koeficient. Pro prvočíselná r je roven Fermatovu koeficientu.
Pro každé rεN platí φ(r)|r!. Proto je nr!≡ 1 mod r a každé číslo nr!−1 je dělitelné r.
K popisu tabulek označme e(n,r) = nφ(r) mod r. Pro r=10, resp. pro n=3:
n e(n,10) nφ(10) r e(3,r) 3φ(r)
──────────────────── ────────────────────
1 1 1 2 1 3
3 1 81 4 1 9
7 1 2401 5 1 81
9 1 6561 7 1 729
11 1 14641 8 1 81
Uvažujme r=mn, kde m,n εN. Protože
mφ(n)−1≡ 0 (mod n) a nφ(m)−1≡ 0 (mod m)
tak:
(mφ(n)−1)(nφ(m)−1)≡ 0 (mod mn) a mφ(n)nφ(m)−mφ(n)−nφ(m)+1≡ 0 (mod mn)
Tedy:
mφ(n)+nφ(m) ≡ 1 mod mn
Např. 8φ(3)+3φ(8)=8²+34=145 ≡ 1 mod 24.
Fermat-Gaussova věta
Jiné zobecnění malé Fermatovy věty ukázal K.F.Gauss [GaussII,$..]. Nechť r=pt, pεP a číslo p je nesoudělné s n, (p,n)=1. Platí:
nr−r/p ≡ 1 mod r
Tedy:
n(pt−pt−1) ≡ 1 (mod pt)
Např.:
3(23−22) ≡ 1 (mod 2³) 3(55−51) ≡ 1 (mod 5²)
36 ≡ 1 mod 8 320 ≡ 1 mod 25
Pro t=1 přechází vztah do malé Fermatovy věty:
np−1 ≡ 1 mod p
Kvadratické zbytky
Kvadratické zbytky podle modulu pt vždy obsahují i kvadratické zbytky podle modulu p. Např. pro p=7 jsou kvadratickými zbytky 1,2 a 4, podle modulu p²=49 je: 1²≡1, 10²≡2 a 2²≡4.
Univerzální exponent
V některých případech mají schemata R(n,k,r) ještě méně sloupců, než je φ(r). Označme nejmenší společný násobek řádů k, která vznikají pro dané r, symbolem λ(r).
λ(r) = nsn(k1,k2,...)
Carmichaelova funkce λ(r) (zavedená r.1912) má následující vlastnosti:
λ(2k) = φ(2k), pro k<3
λ(2k) = φ(2k)/2, pro k≥3
λ(pk) = φ(pk), pro lichá pεP
λ(a∙b∙c...) = nsn(λ(a),λ(b),λ(c),...)
Číslu λ(r) se říká také univerzální exponent. Platí:
λ(r) | φ(r)
a pro nesoudělná čísla n,r zobecnění malé Fermatovy věty:
nλ(r) ≡ 1 mod r
Např. pro r=8 existují vedle triviálního systému R(1,1,8) ještě tři systémy s (n,r)=1 a všechny mají řád k=2, tj. λ(8)=2, což je číslo menší než φ(8)=4, přičemž λ(8)|φ(8).
R(3,2,8) R(5,2,8) R(7,2,8)
0 0 0
1 3 1 5 1 7
2 6 2 2 6
3 1 3 7 3 5
4 4 4
5 7 5 1 5 3
6 2 6 6 2
7 5 7 3 7 1
8 8 8
Druhá mocnina lichého čísla dává proto při dělení osmi vždy zbytek 1, tj. z(8) = nλ(8) mod 8 = 1.
n z(8) nλ(8) n z(8) λ(8)
──────────────── ─────────────────
1 1 1 11 1 121
3 1 9 13 1 169
5 1 25 15 1 225
7 1 49 17 1 289
9 1 81 19 1 361