Schematic algebra - R-systems
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[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]++;
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| 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...)
Fermat's little theorem
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).
(We will return to this theorem later in paragraphs on G-systems).
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:
f(am,r) ≡ m∙f(a,r) (mod r)
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:
M(n,p) = n∙(f(n,p)+1)
resp.:
f(n,p) = (m(n,p)/n) −1
Eisenstein‘s formulaLet 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. |
Wilson‘s theorem
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
Combination of theorems
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, 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:
∑L(n,r) ≡ −2 (mod r)
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
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