﻿ Schematic algebra - R-systems

# Schematic algebra - R-systems

You're reading an English translation of the original Czech page. ## Definition of R-systems

### Break-up of geometrical sequence

Sequence of numbers g,gn,gn²,gn³,... (g,n ε Z) is called geometrical sequence. Let us assume numbers nj (n,j ε Z) of such a sequence and their  remainders  after division by number  r (i.e. by module): u=nj mod r.

For n=2, r=7, j=0..6 we have:
2j   1  2  4  8 16 32 64
2j mod 7   1  2  4  1  2  4  1

Now, if a number occurs again, we break the row and start on the next row with the first unused number. For lucidity we add also numbers 0 (at the beginning) and  r  (to the end).

For r=7, nε{1..r−1} we get:

```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
```

We call schema of numbers nj mod r  R-system with  base n,  of order k according to module r and mark it R(n,k,r).

Value k depends on values n and r, but it is important property of  R-systems – so we place it to the mark R(n,k,r) as well.

Rows (excluding marginal) breaks for r=7, n=4 after third number, so k=3 and we mark the system as R(4,3,7). Applies 43≡1 (mod 7).

```       (0) (1) (2)
(g0)   0
(g1)   1   4   2     m=4
(g2)   3   5   6
(g3)   7
k=3
```

Numbers in the first column {0,1,3,7} are so called  representatives of classes and we mark them gi ,iε(0,m−1). Number m denote number of all classes. We mark ui (j) all numbers 0,1,..,r and call them instances. Number jε(0,k−1) is number of  transpositions. Maximum possible number of  transposition in system R(n,k,r) is equal to order k.

Order k of number n according to module r is such minimum number k (for given n and r) , that nk ≡1 (mod r).

### Structural rule

In geometrical sequence 1,n,n²,n³,...there exists always (apart from the first member)  at least one next (k-) member congruent with number one according to module r.

We will use it for construction of R-systems. Geometrical sequence 1,n,n²,n³,... is always in the first row and the first  row breaks up when number one appears in the sequence of numbers nj mod r (for j=1,2,3...).  Therefore for numbers n,k,r of the system R(n,k,r) it holds:

#### nk ≡ 1 mod r

If we start with any other number on any row, we get – after multiplying by nk  - again the same number (mod r).

It holds:  a ∙ nk mod r = a, i.e.:

#### a∙(nk−1) ≡ 0 mod r

resp. r | a∙(nk−1).

If (a,r)=1, i.e. when number a and r are relative primes (for rεP suffice a<r) then: r | (nk−1), i.e. nk ≡ 1 mod r.

### Algorithm for creation

Hint of the R-system algorithm (n = this.Degree, r = this.Size):

```  BitArray marked = new BitArray(this.Size + 1, false);
int g = 1;
this.TotalClasses++;      this.TotalInstances++;
this.SelfClasses++;    this.SelfInstances++;
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++;      this.SelfInstances++;
```

### The bases of orders

When systems with bases n1,n2,...have order k, we say that bases n1,n2,...  are owned by order k.

For r= 7 own orders k the following bases n:

```   k │ n
──┼──────
1 │ 1
2 │ 6
3 │ 2,4
6 │ 3,5
```

If  nk ≡1 (mod r)  for the given n,k and  exists no d<k,  nd ≡1, then number n  owned by number k.

If system R(n,k,r) exists, then any d<k with R(n,d,r) is impossible, because in opposite case R(n,k,r) cannot exists  (row breaks on position d …).

## Simple R-systems

If module r is prime, we say systems R(n,k,r) are simple.

### Roots of congruence

When nk ≡1 (mod r), all number n,n²,n³,...nk are distinct (mod r). Because (n)k, (n²)k, (n³)k,... ≡1,  n,n²,n³,...nk are roots of congruence xk ≡1.

E.g..:

 Fermat, Pierre de [ferma], 1661-1665, French mathematician, 'King of amateurs', a lawyer by profession. Knowledge of languages enabled him to study the works of ancient mathematicians. He had a special intuition to formulate new problems and to guess non-standard solutions. Discovered a method of finding the maximum and minimum values of functions. He formulated the principle of the shortest time in optics. In theory of curves anticipated analytical geometry. He did not pay much attention to publishing, his collected works were published in print after y.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)
```

(Fermat's theorem for cyclical groups...)

Systems R(n,k,r) arise according to rule:

nk ≡ 1 mod r.

If r is prime and k=r−1 (i.e. n is primitive root), we get so called Fermat’s little theorem:

#### nr−1 ≡ 1 mod r

So, number nr − n is divisible 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
```

Generally for rεP it holds: (a+b+c+...)r ≡ ar + br + cr +... (mod r). From substitution a=b=c=...=1 we have nr ≡ n (mod r).

``` 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
```

Fermat's little theorem holds generally for all numbers n,

which are not multiple of r.
In case n=15 validity fade for primes r = 3 and 5.

Inverse to Fermat's little theorem is called Chinese theorem. This theorem generally does not hold   (it holds for exponents r<300).

Composite number r can divide the expression (nr−n). E.g.. 341 | 2341−2, and 341=11∙31.  Such number r is called pseudoprime.

So called pseudoprimes contains all composite numbers M(2,p), where pεP. Any integer divisor of these numbers has form 2sp+1, where sεN0.
E.g.. M(2,11) is divisible by numbers {1,23,89,2047} i.e. 2sp+1, where s ε{0,1,4,93}.
For genuine odd prime p (pεP, p≡3 mod 4, p>7) number M(2,κ(p)) is not prime. This number we will call Euler pseudoprime.

It holds:

#### p|(2κ(p)−1) => pεP

E.g.. 23|M(2,11), 47|M(2,23), 167|M(2,83), 263|M(2,131), ...

Absolute pseudoprime r are such r, where r | nr−n for all n, e.g.. 561 | n561−n, 561 = 3∙11∙17.

Quotient f(n,r) = ((nr−1)−1)/r is so called Fermat’s coefficient. E.g.. for 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
....
```

For numbers a,b relative prime to r,  Fermat’s coefficients respect  relation analogous to logarithms:

#### f(a∙b,r) ≡ f(a,r) + f(b,r) (mod r)

E.g.: for 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)

Specially when a=b:

### Fermat’s coefficient & number of classes in G-system

Fermat’s coefficient f(n,p) = ((np−1)−1)/p. Systems G(n,p), pεP have total number of classes equal to m(n,p) = (np + (p−1)∙n)/p.

So:

resp.:

#### f(n,p) = (m(n,p)/n) −1

Let rεP, r>2. It holds for sum of numbers 1/m, mε(1,p−1):

#### 1/1−1/2+1/3....−1/(p−1) ≡ 2∙f(2,r) mod r

where f(2,r) is Fermat’s coefficient.

## Similarity of R-systems

### Dual systems

In systems for more distinct primes r some similar schemas exists in pairs.

We say two systems R(n1,k1,r) a R(n2,k2,r) to be dual, if it holds:

#### n1∙n2≡1 mod r

Simultaneously also k1=k2.

E.g.. for 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
```

Systems R(2,7),R(4,7), resp. R(3,7),R(5,7) makes dual pairs, 2∙4≡1 mod 7, resp. 3∙5≡1 mod 7.

Generally systems R(n,k,r) have always (for rεP):

·   (r div 2)−1 dual systems; product of their bases is ∏n≡1 (mod r)

·   one system with n=1; i.e. n ≡ 1 mod r

·   one system having n=r−1; i.e. n ≡ −1 mod r

If n, n' are two dual base, then p\(n∙n'−1).

### Coefficient of dual bases

Let us mark 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

Let us multiply all the bases except the last, i.e. all numbers 1..(r-2).  According to module r we get always the result 1.

E.g.. for p=11:

1∙(2∙6)∙(3∙4)∙(5∙9)∙(7∙8) ≡ 1 (mod 11)

Generally for n=1..r−2 :

∏ n ≡ 1 (mod r).

For all r ε P then holds so called Leibnitz’s theorem:

#### (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[wilzn], 1741-1793, English mathematician and physician. A short time he worked as a professor of mathematics at Cambridge.

The last (until now omitted) member (r−1), is  -1 according to module r.

After multiplying of the previous product by this member we get for 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
```

Therefore for prime r  so called Wilson’s theorem holds:

#### (r−1)! ≡ −1 mod r

Wilson’s  theorem was first published by E.Waring (1770) and proved by J.L.Lagrange (1771).

Inverse to Wilson’s theorem holds: composite number r cannot divide the expression (r−1)! + 1.

For composite r is (except for case r=4) always:

#### (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
```

Quotient w(r) = ((r−1)!+1)/r for rεP

is so called Wilson’s coefficient. E.g.:

```        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
```

It is possible to join Fermat’s and Wilson’s theorem together. E.g. it holds:

·   p | [ap + (p−1)!a]

·   p | [a + (p−1)!ap]

N.H.Abel published question, if number np−1−1 (pεP) can be divisible by p². Congruence np−1−1 ≡ 0 (mod p²) leads to (np−1−1)/p ≡ 0 (mod p), i.e. f(n,p) ≡ 0 (mod p).

Solution of this Abel’s problem was found by C.G.J.Jacobi, and it responds to question, when is the Fermat’s coefficient divisible by number p.

### Wieferich‘s prime numbers

Wieferich’s primes are generally such numbers p for which:

#### ∑f(n,p) ≡ 0 (mod p²)

Specially for n=2 Wieferich proved, that only these primes can satisfy  (in exponents)   I.case  (p does not divide xyz) of the Last Fermat’s theorem xp+yp=zp.

Wieferich’s primes are rare (e.g.. numbers 1093 and 3511).

 Lerch, Matyáš

### Lerch’s formula

Sum of Fermat coefficients for n=1,..,r−1 and Wilson’s coefficient are congruent according to module rεP:

#### ∑f(n,r) ≡ w(r) (mod r)

For r=7:

```   F-coefficients  W-coefficient
───────────────────────────────────
(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
```

Each number nk−1 is (for n>0) divisible by number (n−1).

Let use therefore divide each Fermat’s coefficient by number (n−1) and observe sum of these values.

Let us mark:  L(n,r) = (nr−1/r/(n−1).  For 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
```

For the following prime  r it results:

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

Thereof assertion:

## Composite R-systems

If number r is composite, we say the systems R(n,k,r) to be composite.

### Modification of schemas

Only schemas with prime modules rεP have constant number of members in rows (i.e. number of transpositions).

Other modules this property generally do not have, e.g.. for 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
```

These schemas are not transparent - algorithm, which works for prime r, do not have sense.

Let us therefore change program for R-systems - we allow repetition in schema and we will break row only when number in given row repeats.

For r=7 we get:
```       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
```

For prime module r some schemas have form of  so called Latin squares of order k or generally Latin rectangles.

In Latin rectangles occurs numbers on each row and each column just ones.

E.g. in above schemas for r=7 we see two Latin squares: R(3,6,7),R(5,6,7) and three rectangles R(2,3,7),R(4,3,7),R(6,2,7). Similarly for r=3 we find one square R(2,2,3) and for r=5 two squares 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
```

Le us consider composite module r=pq, where p,q εP. According to Fermat's little theorem for primes p,q it holds:
pq−1−1 ≡ 0 (mod q)  a    qp−1−1 ≡ 0 (mod p)

Thereof:
(pq−1−1)(qp−1−1)   ≡ 0 (mod pq)
pq−1qp−1−pq−1−qp−1+1 ≡ 0 (mod pq)

So:

#### pq−1+qp−1 ≡ 1 mod pq

E.g.. 34+5²=106 ≡ 1 mod 15.

### Fermat-Euler‘s theorem

Schemas for 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
```

In case, when numbers n and r are relative prime,  i.e. (n,r)=1, schemas do not have more then φ(r) columns.

E.g.. for r=10, n=3, (10,3)=1 and φ(10)=4: schema has just 4 columns.

This rule is known as Fermat-Euler’s theorem, generalized  Fermat's (little) theorem.

For relative prime n,r it holds:

#### nφ(r) ≡ 1 mod r

So number nφ(r)+1−n  is divisible by r.

Quotient q(n,r) = (nφ(r)−1)/r is called Fermat-Euler’s coefficient. For prime r is equal to Fermat’s coefficient.

For each rεN is φ(r)|r!. Therefore is nr!≡ 1 mod r and every number nr!−1 is divisible by r.

For heading of tables let us mark e(n,r) = nφ(r) mod r.

For r=10, resp. for n=3 we have:
```    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
```

Let r=mn, where m,n εN. Because
mφ(n)−1≡ 0 (mod n)  a    nφ(m)−1≡ 0 (mod m)

then:
(mφ(n)−1)(nφ(m)−1)≡ 0 (mod mn)  a   mφ(n)nφ(m)−mφ(n)−nφ(m)+1 ≡ 0 (mod mn)

So:

#### mφ(n)+nφ(m) ≡ 1 mod mn

E.g.. 8φ(3)+3φ(8)=8²+34=145 ≡ 1 mod 24.

### Fermat-Gauss‘s theorem

K.F.Gauss demonstrated [Gauss II,\$..] other generalization of Fermat's little theorem. Let r=pt, pεP and p, n relative prime, (p,n)=1.

It holds:

#### nr−r/p ≡ 1 mod r

So:
n(pt−pt−1) ≡ 1 (mod pt)

E.g..:
3(23−22) ≡ 1 (mod 2³)     3(55−51) ≡ 1 (mod 5²)
36 ≡ 1 mod 8    320 ≡ 1 mod 25

For t=1 formula pass into Fermat's little theorem:
np−1 ≡ 1 mod p

Quadratic remainders of module pt always contains also quadratic remainders of module p.

E.g.. for p=7 are quadratic zbytky 1,2 a 4, according to module p²=49 is: 1²≡1, 10²≡2 a 2²≡4.

### Universal exponent

In some cases have schemas R(n,k,r) still less columns, than  φ(r). Let us mark the least common multiple (lcm) of orders k,  which arise for given r, by symbol λ(r).
λ(r) = lcm(k1,k2,...)

Carmichael’s  function λ(r) (established in 1912) has the following properties:
λ(2k) = φ(2k),   for k<3
λ(2k) = φ(2k)/2, for k≥3
λ(pk) = φ(pk),   for odd pεP
λ(a∙b∙c...) = lcm(λ(a),λ(b),λ(c),...)

Number λ(r) is called universal exponent. It holds:

#### λ(r) | φ(r)

and for relative prime n,r it generalized Fermat's little theorem holds:

#### nλ(r) ≡ 1 mod r

E.g.. for r=8 there exists besides trivial system R(1,1,8)  three more systems with  (n,r)=1 and all have order k=2, i.e. λ(8)=2, what is  number less than φ(8)=4, and λ(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
```

Therefore second power of odd number gives always remainder 1 in case of  module 8, i.e. 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
```