# 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).