Schematická algebra - R-systémy

g_rsystem_5_4

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ěta

Systé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.

Čínská věta

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.

4
Fermatův koeficient

Podí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 Vztah

Nechť 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 
  쐐ōҰ  CESKY   쐐ō쉸m巈څ— 8  ĵ   쐐ōҰ  
k쐐ō쉸m㼨څh ! 쐐ō쉸m阈څ{  ɚ 쐐ō쉸m㼨څe " r 쐐ō쉸m阈څv . Ƕ 쐐ō쉸m阈څz  ə 쐐ō쉸m阈څy  Ǹ 쐐ō쉸m阈څx  ǵ 쐐ō쉸m阈څw  ǵ 쐐ō쉸m阈څu - ɜ 쐐ō梄B  ﷩  쐐ōҰ  9 쐐ō쉸m蝘څ„ X ɛ 쐐ōҰ 
 
  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
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).
Leibnitzova věta

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.
Wilsonova věta

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

Opačná Wilsonova věta

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
Wilsonův koeficient

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]

Abelův problém

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    
Návazné úvahy

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
Latinské pravoúhelníky

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
Malá Fermatova věta pro r=pq

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
Fermat-Eulerova věta pro r=mn

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