Number Theory

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 ≤ kn 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).