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 *a*^{p} ≡ *a* (mod *p*). In the case of gcd(*a*,*p*) = 1, a^{p-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 Z_{5}.

` > 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 Z_{24}:

` > {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|φ(2-1).^{n}