But you shouldn't think that this mod 5 "times-table" is typical of residue classes for all moduli.
In contrast, consider the residue classes of natural number (or integers) modulo 6 under multiplication:
x|| C1 | C2 | C3 | C4 | C5
----------------------------
C1|| C1 | C2 | C3 | C4 | C5
C2|| C2 | C4 | C0 | C2 | C4
C3|| C3 | C0 | C3 | C0 | C3
C4|| C4 | C2 | C0 | C4 | C2
C5|| C5 | C4 | C3 | C2 | C1ASSIGNMENT: Work out the "meanings" these 6 residue classes.
Compare the times-tables modulo 5 and modulo 6.
In the (mod 5) times-table, each non-null residue classes -- C1, C2, C3, C4 -- is present in each row and column of the table.
However, in the (mod 6) time-table, this is not so. C1 and C3 are missing from row 2 and column 2, and from row 4 and column 4. C1, C2, C4, and C5 are missing from row 3 and column 3.
Furthermore, there is no C0 in the (mod 5) times-table, as there is in the (mod 6) times-table.
Actually, there would be if we put in a multiplier C0, which would turn every other C-term into C0 just as multiplication any non-zero number turns it into zero. That seems natural for residue products. But mod 5 does not allow a non-C0-term to turn another non-C0-term into C0. However, that sort of thing happens in the mod 6 times-table. C2 and C3 "kill" or NULLIFY each other, in product. And so do C3 and C4.
(Analogous to case wherein two kinds of light cancel each other out -- because they are out of phase. And two kinds of sound can combine into silence! So this kind of math has further uses we cannot, herein, take up.)
But please notice! The really critical difference is that every element in the "5" times-table has a multiplicative inverse. In the "6"-table, C1 is self-inversive (as nuber 1 is), but C5 is self-inversive. Onn the other hand, neither of C2, C3, C4 has a multiplicative inverse!
Why? The difference between the two times-tables arises because 5 is prime, while 6 is composite.
The "secret of success" of the Galois fields for efficiently encoding signals between satellites and ground stations. For, every encoding must have a decoding -- an inverse! So Galois fields (in which each non-null element has a multiplicative inverse) are all based on prime moduli.
And prime moduli yield the "primitive roots" that tell us how to construct that "diffraction"-ceiling to "waste not phonons" for great listening.
As promised, we'll see how to construct such a ceiling (mod 11). Here's the procedure:
I'll describe how this is done, and then I'll comment on the three needed arithmetic procedures and how to make them easily available.
A primitive root of a prime is:
There's a well-known formula for doing this, involving "Euler's phi function" or "Euler's totient function". But we can bypass that function by noting that it asks an easily answered question, "How many numbers are coprime to this number?".
Two numbers are coprime if their greatest common factor is 1. Thus, 6 (= 2 x 3) and 35 (= 5 x 7) are coprime because 35 lacks factors 2, 3, while 6 lacks factors 5, 7, but both contain factor 1.
I call all numbers less than a given number its "subnumbers". Given a prime number p, I call all p - 1 numbers less than p its "subprimes".
All p - 1 subprimes of p are coprime to p. Thus, 11 has 10 (coprime) subprimes, namely, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
To answer the question, "How many primtive roots does a prime, such as 11, have?", you twice ask the question, "How numbers of a certain kind are coprime to this number?"
We've already asked that question once in asking, "How many subprimes for 11?", receiving the answer, "10". Now we formulate that question about 10 = 11 - 1.
"How many subnumbers of 10 are coprime to 10?" The subnumbers of 10 are 1, 2, 3, 4, 5, 6, 7, 8, 9. Of these, 2, 4, 6, 8 share with 10 the factor 2, and 5 is a factor of 10, hence, 2, 4, 5, 6, 8 are noncoprimes of 10. Only 3, 7, 9 are coprime to 10, i.e., there are 3 such numbers. So 11 has 3 primitive roots. That deals with the first property of primitive roots of a prime.
For the second property, leaving out 1, we raise the subprimes 2, 3, 4, 5, 6, 7, 8, 9, 10 to powers of the number to find which ones "run the complete cycle of all remainders or residues before repeating". These cyclic subprimesare the actual primitive roots of 11.
Its primitive roots happen to be 2, 6, 7, 8. But, for purposes of our construction, we don't need to know all of this, along with all the work entailed in discovering this. We need only discover the least primitive root and use it. This greatly simplifies our problem!
In all cases, whether with the prime 3 or 5 or 7 or 11 or 13 or 17, etc., we can always start with the same testee: 2. It's no use starting with 1 since 1 x 1 = 1, and 1 x 1 x 1 = 1, and 1 x 1 x 1 x 1 = 1, etc. Raising 1 to powers never gets us beyond 1, hence, cannot generate the residue system modulo 11. Therefore, we always start with "the next candidate", 2.
It's powers are easy to obtain, and can also be found in available tables, since 2 is the base of the binary numeration used in computers. The first to eleventh powers of 2 are easily obtained by doubling: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048. (Incidentally, doubling is the basis of a gambling method known as "The Martingale". Clever casino owners make "Martingale betting" too expensive by instituting minimal and maximal bets.)
We find: 2 º 2 (mod 11); 4 º 4 (mod 11); 8 º 8 (mod 11); 16 º 5 (mod 11); 32 º 10 (mod 11); 64 º 9 (mod 11); 128 º 7 (mod 11); 256 º 3 (mod 11); 512 º 6 (mod 11); 1024 º 1; 2048 º 2 (mod 11).
This last result repeats the first result obtained, residue 2. Hence, higher powers (or doublings) would only run us through this ten-cycle again. We have all the desired ten residues. Let's examine them.
We found, in order, the residues: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1. All of the possible nun-null residues are present. That is, powers of 2 generate the residue system modulo 11. Hence, 2 is a primitive root of 11.
And look at the generated order of the residues. That's the order to be used in constructing the "diffraction"-ceiling of a concert hall for "good listening". (Below I'll suggest how to construct its cross-section.)
Before turning to this construction, I'll make a brief remark about simplying the calculations for this ordering. (Later, I'll refer to results in decimal expansions of fractions which bears a resemblance to the above result.)
Elsewhere, at this website, I cite a simple algorithm which is helpful here: "casting out elevens", which is the complement of the better known algorithm, "casting out nines". A sidetrip explains this.
Returning to our general procedure for finding a primitive root of a prime, along with its cycle of residues, if 2 fails to span this cycle, try the next number, 3. Etc., going up in ots cycle of residues.
For example, prime 17 (with 16 non-null residues) has 8 primitive roots. The testee 2, in its powers, spans only 8 of the 16 non-null residues, so cannot be a primitive root of 17. But 3, in its powers, spans the sixteen-cycle system of residues, so 3 is the least primitive root of 17, and could be used for the kind of purpose we're going to demonstrate below.
If 3 were to fail, we'd try 4. Etc.
You can sketch the cross-section of the kind of ceiling "bump" which will provide optimal reflection of sound throughout a concert hall ("other things equal"). Take some graph paper and use the squares as unit blocks to construct one of these "ceiling or wall bumps": 2 blocks deep; 4 blocks deep; 8 blocks deep; 5 blocks deep; 10 blocks deep; 9 blocks deep; 7 blocks deep; 3 blocks deep; 6 blocks deep. Then this "bar graph" is repeated.
How do we get the second dimension for these blocks? (The third dimension is the thickness from the ceiling, which is a question for non-mathematical experts.) We noted above that, for p = 11, our p - 1 = 10 has two proper factors, 2 and 5, and these form a coprime pair. That is one of the conditions for developed a two-dimensional non-specular modulus -- another reason for using 11.
Before closing, I wish to show the resemblance of the above material on "cycles of residue" to decimal expansions of fractions predominantly of the form, 1/p, where p is a prime: 1/2, 1/3, 1/5, 1/7, 1/11, etc. To do so, I revive two terms.
People usually think "characteristic" and "mantissa" apply only to parts of logarithms, but they apply more generally to parts of decimal fractions. The characteristic is the part to the left of the decimal; the mantissa, to the right. A decimal fraction is rational if, and only if, the mantissa can be fitted to a form with a repeated cycle of digits (equivalently, to the form of a geometric progression). This cycle is often denoted by a bar drawn above it. For convenience of typing, I'll make that an underline.
Thus, 1/2 = 0.50; 1/3 = 0.3; 1/7 = 0.142857; 1/11 = 0.09; etc. A decimal fraction that defies this form, such as p = 3.1416... or Ö2 = 1.41462..., is irrational. Thus, the decimal fraction for 1/3 has a characteristic of 0 and a repeated or one-cycle mantissa of 3, whereas the decimal fraction for 1/7 has 0 characteristic and a mantissa made up of strings of the six-cycle shown above.
Here's the type of remedial problem I used to give to college freshpersons. "m = 412.593894; write m as an ordinary fraction." Solution: For convenience of calculations, transform m into a decimal fraction with the cycle beginning the mantissa by multiplying with 100. 100m = 41259.3894. Now derive another number from this with the same cycle mantissa so that their difference removes the mantissa. Multiplying 100m by 10000 will move a complete cycle into the characterisitic, leaving the mantissa unchanged: 1000000m = 41259000.3894. If we now subtract 100m from 1000000m, the mantissa becomes zero, since their mantissas match term for term. 1000000m - 100m = 999900m = 4129. Then m = 4129/9999000, which can be further reduced.
Numbers of the form 1/n are known, for historical reasons, as "Egyptian fractions"; those of the form 1/p can then be called "Egyptian primal fractions" or, for short, "Egyptian primals".
The decimal fraction form of an Egyptian primal has a cycle of length p - 1 or a factor thereof -- just as do the subprimes of primes. Thus, 1/3 has a cycle of no more than 3 - 1 = 2 digits, but, in fact, has a cycle of 1 digit (1/2 = 0.50; 1/11 has a cycle of no more than 11 - 1 = 10, but, in fact, has a cycle of 2 digits (1/11 = 0.09), a factor of 10; 1/7 has a cycle of no more than 6 digits, and, in fact, requires that number of digits to repeat (1/7 = 0.142857).
I propose calling an Egyptian primal, such as 1/7, which need its allowed cycle-length, an "Egyptian primitive". Then, if this present material should later be taught to students hearing such language, they would be prepared for the parallel.
Repeating, this is what was implied, above, in describing the primitive roots and imprimitive roots of prime p. If, in fact, you thoroughly investigate the prime 17, you find that it has 8 primitive roots and 8 imprimitive roots. I noted that 3 is a primitive root of 17 because its powers requre the full 17 - 1 = 16 cycle. This is also the case for the other three primitive roots. The eight imprimitive roots have cycles of length 1, 2, 4, or 8, factors of 16.
Please, observe the parallel. An Egyptian prime has a cycle in its mantissa of no more than p - 1 digits or any factor thereof.
Restated, the cycle has the form (k x 1/10(p - 1))/f = (k x 10 - (p - 1))/f, where f is a factor of p - 1. The digits in the mantissa of an Egyptian prime repeat after so many negative ten powers, while the primitive and imprimitive roots of a prime repeats after so many positive ten powers.
Thus, enough practice with decimal fractions can prepare students for learning how to build a good ceiling for a concert hall or a surface for a stealth bomber or stealth fighter or for a submarine.