1. Introduction


One attractive feature about symbolic computing is that one does not read up tons of rules as required in modern compiled languages. Readers could also test-drive program lines culled from published papers without lengthy debugging and recompilations. Those who are not familiar with sequence alegebra are advised to read the first HTML paper from this URL site [2].

As far as sequence algebra is concerned practically all symbolic software packages are equally suitable or equally unsutiable. Suitable because they have functionalities in power series expansions and z-transforms. Unsuitable because the new operator Normc( ) defined in sequence algebra have yet to be implemented in these packages. In this paper, all program lines will be based on Maple V R 3's syntices.


2. Explicit Generating Function from Congruence Relation

The general congruence relation a = b (mod n) can also be written as r = (a - b) mod n where r is the remainder from modulo division by the divisor n. If r is zero, a and b are congruent. Otherwise they are incongruent [1]. For a fixed value of n, a cyclical residue set is generated which is a function of the difference (a-b) and n.

In this paper, the term congruence covers both congruencies and incongruencies. To visualise graphical patterns of congruence, all one needs to do is to plot r as a function of (a-b) and n in a 3D-sequence algebraic space. This is called visualisation for reasons already explained in papers [6,11].

The congruence equation a = b (mod n) is translated into the sequence algebraic format where a general term is contructed as (i mod j)/(d^i*n^j) where d and n represent order variables for the difference i = a-b and the divisor j respectively. Note that the indicial values for d and n are supplied by the loop counters i and j respectively. The generating function Congruence(z) is visualised in 3D sequence space with n and d assinged to the horizontal and the vertical orthogonal cartesian axes and r represents residues assinged to the third axis orthogonal to the previous two. Normally these would be plotted as a 3D Hgram graph but for publications in HTML files, sequence algebraic formulations are preferred and used throughout this paper. In other words all graphical displays are done algebraically.

In congruence relation, the absolute values of a and b are not important but only the difference d itself. One would therefore expect repetitious patterns in the remainder or residue set r. Visualisation has important pedagogical values in beginners' classes in number theory. Equations (1) shows how the remainders or residues are computated and displayed for the range of differences d from 1 to 10 and with the divisor fixed at 5. The cyclical properties of the residue sets are self-evident by studying the numerators in equation (1).

Congruence(i,j):=sum(sum(r^(i mod j)/(d^i*n^j),i=1..10),j=5..5);

...........................................2..............3...............4
.......................r.................r...............r................r..............1
...................--------+-----------+-----------+--------+---------
..........................5.............2..5............3..5............4..5..........5..5
.....................d..n............d..n............d..n............d..n..........d..n

..............................................2.................3...................4
........................r...................r...................r.................r...................1
................+-----------+-----------+-----------+ -----------+------------ ...................(1).
.........................6..5..............7..5.............8..5............9..5.............10..5
.......................d..n...............d..n.............d..n............d..n..............d...n

To gain more insight, we recompute the first five terms in equation (1) with divisors j = n ranging from 1 to 5 as shown in equation (2) and have these ploted in figure 1 in a cartesian plot.

..........................1.............1................1...............1................1
....................---------+----------+----------+----------+----------
.........................d..n..............2.................3..............4.................5
.......................................d..n.............d..n...........d..n............d..n

.............................r..............1.................r................1................r
...................----------+-----------+-----------+-----------+-----------
...............................2...........2..2.............3..2...........4..2..............5..2
...........................d.n..........d..n.............d..n............d..n..............d..n

..............................................2......................................................2
............................r................r..................1................r.................r
....................----------+-----------+-----------+-----------+-----------
...............................3.............2..3.............3..3.............4..3.............5..3
..........................d..n.............d..n............d..n..............d..n.............d..n

................................................2.................3
............................r..................r..................r...............1...............r
....................----------+-----------+-----------+-----------+-----------
...............................4............2..4.............3..4.............4..4............5..4
..........................d..n...........d..n.............d..n.............d..n.............d..n

. ..............................................2..............3................4
........................r...................r..............r..................r.................1
..................----------+-----------+-----------+-----------+-----------
............................5............2..5.............3..5.............4...5...........5..5
.......................d..n............d..n.............d..n.............d...n...........d..n ......................(2)

The sequence expansions in equation (2) can be considered graphical in its own right but to the uninitiated an ordinary cartesian graph is also plotted of the same information using the data set summarised below.

n = 1, residue set = { 0 }
n = 2, residue set = { 0, 1}
n = 3, residue set = { 0, 1, 2}
n = 4, residue set = { 0, 1, 2, 3}
n = 5, residue set = { 0, 1, 2, 3, 4}..............................................................(3).

d = i......................residue sets
5....0..........1..........2..........1..........0
4....0..........0..........1..........0..........4
3....0..........1..........0..........3..........3
2....0..........0..........2..........2..........2
1....0..........1..........1..........1..........1
--------------------------------------------------------
......1..........2..........3..........4..........5 ........ n = j

Fig.1 - Graph of remainders or residues r versus d and n

Already distinctive patterns of the remainders or residues r can be detected from figure 1 but for better insight we need to include also the negative range of the differences of d and also a wider range for the divisor j = n. For page economy, the output is not displayed. Note that i mod j in Maple V R 3 is always reported as positive whereas in number theory, i mod j can be negative.

sum(sum(r^(i mod j)/(d^i*n^j),i=-10..10),j=1..10);..................................(4).

Figure 2 shows the pattern of remainders or residues for differences (a-b) ranging from -10 to +10 and the divisor n from 1 to 10. Various patterns can be detected depended on how one looks at it but the most obvious way is to read along vertical columns. One immediately detects that the largest residue is one less than the value of the divisor n.

i.....................................................Residue sets
5....0..........0..........1..........2..........0..........4..........3..........2..........1..........0
4....0..........1..........0..........1..........4..........3..........2..........1..........0..........9
3....0..........0..........2..........0..........3..........2..........1..........0..........8..........8
3....0..........1..........1..........3..........2..........1..........0..........7..........7..........7
2....0..........0..........0..........2..........1..........0..........6..........6..........6..........6
5....0..........1..........2..........1..........0..........5..........5..........5..........5..........5
4....0..........0..........1..........0..........4..........4..........4..........4..........4..........4
3....0..........1..........0..........3..........3..........3..........3..........3..........3..........3
3....0..........0..........2..........2..........2..........2..........2..........2..........2..........2
2....0..........1..........1..........1.........1..........1..........1..........1..........1..........1
0....0..........0..........0..........0.........0..........0..........0..........0..........0..........0
-1...0........ -1........ -1....... -1....... -1....... -1........ -1........ -1....... -1....... -1
-2...0......... 0......... -2....... -2....... -2....... -2........ -2........ -2....... -2....... -2
-3...0......... -1........ 0........ -3....... -3....... -3........ -3........ -3....... -3....... -3
-4...0......... 0......... -1....... 0........ -4....... -4........ -4........ -4....... -4....... -4
-5...0........ -1........ -2....... -1........ 0........ -5........ -5........ -5........ -5....... -5
-6...0......... 0......... 0........ -2........ -1........ 0......... -6........ -6........ -6....... -6
-7...0........ -1........ -1....... -3........ -2........ -1........ 0........ -7........ -7....... -7
-8...0......... 0......... -2....... 0........ -3........ -2........ -1........ 0......... -8....... -8
-9...0........ -1........ 0........ -1........ -4........ -3........ -2........ -1........ 0........ -9
-10.0..........0..........-1........-2..........0.........-4........ -3........ -2........ -1....... 0
--------------------------------------------------------------------------------------------------------------------------
......1..........2..........3..........4...........5..........6..........7..........8..........9........10..n = j

Fig. 2 - Pattern of remainders in congruence relation.
Other than difference in arithmetic signs, there are horizontal
reflectionary symmetries of the residue sets about the d = 0 line.

Although modular arithmetic is powerful, its presence gives rise to the same algebraic difficulty as Normc( ). An alternative explicit formulation which does not depend on modular arithmetic operator is attempted in this seciton. The reason for this development is an attempt to answer the enquiry:

"Is it possible to substitute modular arithmetic by ordinary arithmetic operations?"

Past research in sequence algebra showed that many number theoretic functions cannot be expressed in pure arithemtic forms but require the use of mixed mode arithmetics, i.e., the use of both arithmetical and logical operators [9 to 11]. Here is how the sequence algebraic formulation is derived.

Due to reflectionary symmetries, we can confine derivation to the positive half of figure 2, and assuming the divisors to start from 1, one can write down the residue set for each value of divisor n. Here are the first three residue sets.

n=2: Residue set R2(z) = {0101010101..........} = z^2/(z^2-1)*(1/z) ............................(5a).

n=3: Residue set = {0120120120..........}
This can be resolved into the sum of two sequences shown as follows:

0100100100100.. = z^3/(z^3-1)*(1/z)
0020020020020.. = z^3/(z^3-1)*(2/z^2)

Therefore Residue set R3(z) = (012012012....} = z^3/(z^3-1)*(1/z+2/z^2) .....................(5b).

n=4: Residue set = {012301230123......}

This can be resolved into the sum of three sequences shown as follows:

0100010001000 = z^4/(z^4-1)*(1/z)
00200020002000 = z^4/(z^4-1)*(2/z^2)
000300030003000 = z^4/(z^4-1)*(3/z^3)

Therefore residue set R4(z) = {012301230123....) = z^4/(z^4-1)*(1/z+2/z^+3/z^3) .........(5c).

Thus in general, we can write down the residue set for divisor n as follows:

R(z) = z^n/(z^n - 1)*(1/z + 2/z^2 + 3/z^3 + ....... + (n-1)/z^(n-1)) .......................................(6).

Tests:

series(z^2/(z^2-1)*(1/z),z=infinity,15);

......................................1......1........1........1.......1.......1..........1
...........................1/z+-----+-----+-----+-----+----+----+O(----) ................................(7a).
........................................3.......5.........7.......9......11....13.......15
.......................................z......z.........z........z.......z.......z.........z

series(z^3/(z^3-1)*(1/z+2/z^2),z=infinity,15);
.............................2......1........2........1........2.......1........2........1.......2.........1
................1/z + ---- + ---- + ---- + ---- + ---- + --- + --- + --- + --- + O(---) ..................(7b).
...............................2......4.........5........7........8......10......11.....13....14........16
.............................z.......z.........z........z........z........z........z.....z......z.........z


series(z^4/(z^4-1)*(1/z+2/z^2+3/z^3),z=infinity,15);

.......................2........3.........1.......2.......3.......1........2.......3.......1........2........1
..........1/z + ---- + ---- + ---- + ---- + ---- + ---- + --- + --- + --- + --- + O(---) ..............(7c).
........................2.......3..........5.......6.......7........9.......10......11......13......14......15
.......................z.......z..........z.......z.......z..........z........z.........z.......z.........z.......z

series(z^5/(z^5-1)*(1/z+2/z^2+3/z^3+4/z^4),z=infinity,15);

..................2.......3........4........1........2.......3.......4.......1........2.......3........4..........1
....1/z + ---- + ---- + ---- + ---- + ---- + ---- + ---- + --- + --- + --- + --- + O(---) .........(7d).
...................2........3........4........6.......7........8.......9.......11......12.....13......14......16
..................z.......z........z........z........z..........z........z.......z........z.......z........z........z

From the above, one deduces that the general explicit sequence algebraic formulation for the congruence relation is given by equation (8):

series(sum(z^n/(z^n-1)*sum(i/z^i,i=1..n-1),n=n1..n2),z=infinity,ub); .............(8).

where n = the value of the divisor from n1 to n2 and ub is the upperbound of the number of terms in the expansion. Tests with n = 2, 3, 4, and 5 respectively confirm that the previous results from equation (7a) to (7d) are correct.


3. Modular Arithmetic and Sequence Algebra

The above derivation shows that it is possible to develop an alternative formulation for the congruence relation which appears to dispense with modular arithmetic. To explan how this could arise, one needs to explain what is meant by the periodicity of a sequence. All closed form sequence algebraic formulations developed so far contain, without exception, one or more periodic sequences.

For example, the equation of divisibles given by equation (9):

Comp(z):= {1/(z^i*(z^i-1)) | i = 2.. infinity} .......................................(9),

contains an infinity number of periodic sequences with intervals from 2 to infinity. These are generated by the general closed form of 1/(z^i-1). The premultiplying term 1/z^i has the effect of shifting the original sequence by i intervals to the right but it does not affect the interval itself. Thus in Comp(z), we have an infinite summation of periodic sequences. Of course you can also prove that Nat(z), Even(z), and Odd(z) are all periodic sequences. Note that all closed form generating functions involve integer divisions just as in modular arithmetic. Therefore there must be connections between them. The only difference is that in sequence algebra, only exact divisions are described by the periodic sequences whereas the modular arithmetic operator includes residues. Since residue sets are cyclical, these can be expressed as functions of periodic sequences. In actual fact, a special type of cyclical generating functions can be formulated by using modular arithmetic in the sequence expressions in either open or closed form as shown in equation (10).

Cyclic(z) := 1/z^(i mod j) or z/(z^(i mod j + 1) - 1) ....................................(10).

If Cyclic(z) is expanded, you will find that the infinitely repeating cyclic patterns are dependent on the value of the divisor j chosen. Cyclic generating functions will be the next topic in this series. It will not be elaborated further here.


4. Conclusions

This paper shows that the congruence relation r = (a-b) mod n can be replaced by an explicit sequence algebraic formulation which does not contain mod operators. Since both modular arithmetics and sequence algebra are periodic, it is easy to translate from one form to the other. Although there is a relation between them, this relation is not directly mapped. The fact that a sequence algebraic formulation can be found is because of the common periodic properties.


5. References

1. Burton M. Burton: Elementary Number Theory, Third Edition, WCB publishers, 1994, 17 to 48 to 50.

2. Huen Y.K.: A Simple Introduction To Sequence Algebra, URL site: http://web.singnet.com.sg/~huens/

3. Huen Y.K.: The Canonical Generating Function or CGF(z) - a Swiss-knife function. URL site: http://web.singnet.com.sg/~huens/ .

4. Huen Y.K.: Information Contents Of Number Theoretic Functions. URL site: http://web.singnet.com.sg/~huens/ .

5. Huen Y.K.: In Search Of Exotic Arithmetic Operators, URL site: http://web.singnet.com.sg /~huens/ .

6. Huen Y.K.: Visual Solutions Of Number Theoretic Functions in Multidimensional Sequence Space, URL site: http://web.singnet.com.sg /~huens/ .

7. Huen Y.K.: Final Value Theorems Applied To Number Sequences -- its strengths and weaknesses, URL site: http://web.singnet.com.sg /~huens/ .

8. Huen Y.K.: Unsolved Problems In Sequence Algebra, URL site: http://web.singnet.com.sg /~huens/ .

9. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci. Technol., 1994, VOL. 25, NO.6, pp 913-920.

10. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ. Sci. Technol., 1996, VOL.27, NO. 5, 685-691.

11. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,1996, VOL.??, NO.?, ???-??? (In the press as proof paper mes 100421).

=====================END OF PAPER ======================