Many courses in elementary number theory and cryptography teach both Fermat’s Little Theorem and its generalization. Let’s explore.
Fermat’s Little Theorem states that if p is prime and then ap ≡ a (mod p). In the case of gcd(a,p) = 1, ap-1 ≡ 1 (mod p). The result can be easily “discovered” via computation in Magma, and this is a great example of using loops. First, let’s compute the powers of all the elements in Z5.
> Z5 := Integers(5);
> for x in Z5 do
for> x,x^2,x^3,x^4,x^5;
for> end for;
0 0 0 0 0
1 1 1 1 1
2 4 3 1 2
3 4 2 1 3
4 1 4 1 4
The last column seems to illustrate the result. But let’s use the power of Magma to check a larger example. The forall command will check that some statement is true for all elements in some set. For instance, Fermat’s Little Theorem is not true when you don’t use a prime:
> forall {x:x in Integers(24) | x^24 eq x };
false
And, we can check that the statement is true only for a few special values in Z24:
> {x:x in Integers(24) | x^24 eq x };
{ 0, 1, 16, 9 }
But we can also check that it is indeed true when we use “large” primes:
> IsPrime(9973);
true
> forall {x:x in Integers(9973) | x^9973 eq x };
true
The Euler Phi function φ is defined as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) = 1. Euler’s famous result states that if a and n are relatively prime, then aφ(n) ≡ 1 (mod n). There are many things you can do to explore values of Euler Phi. For example, if n is the product of two distinct primes, there’s a nice formula for computing the Euler Phi function. Let’s look at some examples using a loop:
for i in [1..10] do
for> for j in [1..10] do
for|for> if IsPrime(i) and IsPrime(j) and i ne j then
for|for|if> i,j, EulerPhi(i*j);
for|for|if> end if;
for|for> end for;
for> end for;
2 3 2
2 5 4
2 7 6
3 2 2
3 5 8
3 7 12
5 2 4
5 3 8
5 7 24
7 2 6
7 3 12
7 5 24
Once you have the data above, you might look for a pattern. Given two primes p and q, can you conjecture a formula for φ(pq)? (Maybe you already know this theorem. Ok, fine. Move along… nothing to see here…)
Exercise: We’re trying to figure out which of the following “theorems” is true? Use Magma to compute values and see what you can learn.
- If a|b then φ(a) | φ(b).
- If φ(a) | φ(b), then a|b.
- For any n > 1, 2|φ(2n-1).
