We started with some comments about the problem from Class 12 (being handed back). Everyone had managed to do it as stated, but the actual behavior of phi was not clarified by just the assigned examples. It seemed natural to investigate further. After some discussion, this problem was turned into a "challenge problem," to be done optionally, graded at a higher standard, possibly substituting for a missed regular problem. (NOTE: this challenge problem has a deadline -- to get the optional credit for it, you must turn it in before we return to it in class, possibly as soon as Tuesday, November 9).
Today's problem illustrates the proof of the statement in the heading (above). Since it is both pretty and important, we went over part of the problem, and even did an additional example. Today's problem asked for the subgroup S generated by 4 in Z17*. That is, S={4, 4^2=16, 4^3=13, 4^4=1}. One sees that the order of 4 in Z17* is 4, because its 4th power is 1 (mod 17). Now 4 certainly divides phi(17)=16, but the problem illustrates WHY: if we take some element not in S, like 2, and multiply S through by 2, we find {2*4=8, 2*16=15, 2*13=9, 2*1=2} (mod 17). The thing to notice is that the elements found in this way, 8, 15, 9, 2, are all different from each other, and all different from the elements of S, namely 4, 16, 13, 1. Thus we now have 8 of the elements of Z17*. Since there are still elements not produced in this way, we can take one of them, say 3, and multiply S through by 3, finding {3*4=12, 3*16=14, 3*13=5, 3*1=3} (mod 17). Once again, these are all different from each other, and all different from the previous ones, so we now have 12 of the elements of Z17*. But some elements, such as 6, have still not appeared, so we multiply S through by 6, finding {6*4=7, 6*16=11, 6*13=10, 6*1=6}, which are all new elements, distinct from each other and from the previous ones, and there are no elements left to find. Thus the elements of Z17* can be thought of in a rectangular array
| 4 | 16 | 13 | 1 |
| 8 | 15 | 9 | 2 |
| 12 | 14 | 5 | 3 |
| 7 | 11 | 10 | 6 |
showing graphically that phi(17) (the number of cells) is a composite number, with the order of 4 in Z17*, namely 4, as a factor (the first row is S, the subgroup generated by 4). Thus the order of 4 in Z17* divides phi(17).
Here is another example, quicker: consider the element 8 in Z19*, which happens to have order 6. The subgroup generated by 8 in Z19* is {8, 7, 18, 11, 12, 1}. Multiplying through by 2, which is an element not in S, gives the elements {16, 14, 17, 3, 5, 2}, and multiplying through by 4, which has not appeared yet, gives {13, 9, 15, 6, 10, 4}. Once again, we always get distinct, new elements. Since none are left, the process is done, and the elements of Z19* can be thought of in the rectangular array
| 8 | 7 | 18 | 11 | 12 | 1 |
| 16 | 14 | 17 | 3 | 5 | 2 |
| 13 | 9 | 15 | 6 | 10 | 4 |
where the first row is the subgroup generated by 8, and the succeeding rows are found from the first by multiplication by a new element. Thus the order of 8, namely 6, is a factor of phi(19).
The above two examples just illustrate what always happens. (The proof was sketched in Class 13).
Notice that 4^16=(4^4)^4=1^4=1 mod 17.
Also 8^18=(8^6)^3=1^3=1 mod 19.
In general, for any a in Zn*,
Proof: let m be the order of a in Zn*. Then phi(n)/m is an integer (m divides phi(n)), so
(1 to any integer power is 1).
In particular, if n is a prime number, then phi(n)=n-1. In this form it is called Fermat's Little Theorem (and the name n is changed to p to suggest prime):
for all a in Zp*.
Fermat's Little Theorem is very busily used these days in finding large primes. Large primes are needed for encryption of data, something we will say more about. But even to get started one must HAVE some large primes, and establishing that a large number is prime is not easy, even with fast computers. In particular, if you have to factor the large number to prove it is not prime, it is practically impossible. Factoring is a VERY slow operation (compared with the ordinary operations of arithmetic, for example). What is actually done is to use Fermat's Little Theorem. Suppose you generate a large number N as a random string of digits, chosen in such a way that it could be prime, i.e., it isn't even, it doesn't end in a 5, it isn't divisible by 3, etc. (That is, to save time, just avoid the obvious numbers which are not prime.) Now you test N with Fermat's Little Theorem: choose a<N, and form a^(N-1) mod N. If N is prime, that must be 1! If it comes out different from 1, you know that your N is not prime, and you can stop wasting time on it. Generate a new candidate in that case. On the other hand, if it does come out 1, it doesn't necessarily mean that N is prime. It just means that it didn't fail the first test. Test it again, with a different a, and keep testing it. If it ever fails, it is not prime. If it passes every test, you begin to get the feeling that it must be prime. This is what is actually done. The primes in use are not known with certainty to be prime, but only with very high probability.
We tested the number 1151, which looks as if it could be prime. In fact, taking a=2, we found 2^1150=1 (mod 1151), which suggests that 1151 really is prime. Taking a=3, we found 3^1150=1 (mod 1151), which makes it seem even more likely, etc. On the other hand, testing 1157, which also looks as if it could be prime, shows immediately that it is not: 2^1156=536 (mod 1157), not 1. There is no need to try another a in this case. It is clear that 1157 is not prime. Notice that we have learned this without factoring 1157, or having any idea what its factors are.
Use Fermat's Little Theorem to test 4-digit numbers which look as if they could be prime, and keep a running account of what you are doing and what you are thinking. Find an example in which a number seems to be prime, and another in which a number is obviously not prime after the test (although it wasn't obvious before). Explain your evidence in each case, in words.
Use the ModP Calculator, on the machines in 402 (and also, I think 420) Clapp to do this. Some of you did this already in class time.