{"id":26,"date":"2016-09-22T19:15:50","date_gmt":"2016-09-22T19:15:50","guid":{"rendered":"http:\/\/keithmellinger.com\/magma\/?page_id=26"},"modified":"2016-11-17T01:58:40","modified_gmt":"2016-11-17T01:58:40","slug":"number-theory","status":"publish","type":"page","link":"https:\/\/keithmellinger.com\/magma\/number-theory\/","title":{"rendered":"Number Theory"},"content":{"rendered":"

Many courses in elementary number theory and cryptography teach both Fermat\u2019s Little Theorem and its generalization. Let\u2019s explore.<\/p>\n

Fermat\u2019s Little Theorem states that if p<\/em> is prime and \u00a0then a<\/em>p<\/em><\/sup>\u00a0\u2261 a<\/em> (mod p<\/em>). In the case of gcd(a<\/em>,p<\/em>) = 1,\u00a0ap<\/em>-1<\/sup> \u2261\u00a01 (mod p<\/em>). The result can be easily \u201cdiscovered\u201d via computation in Magma<\/em>, and this is a great example of using loops. First, let\u2019s compute the powers of all the elements in Z5<\/sub>.<\/p>\n

> Z5 := Integers(5); <\/code>
\n > for x in Z5 do <\/code>
\n for> x,x^2,x^3,x^4,x^5;<\/code>
\n for> end for;<\/code>
\n 0 0 0 0 0<\/code>
\n 1 1 1 1 1<\/code>
\n 2 4 3 1 2<\/code>
\n 3 4 2 1 3<\/code>
\n 4 1 4 1 4<\/code><\/p>\n

The last column seems to illustrate the result. But let\u2019s use the power of Magma<\/em> to check a larger example. The forall<\/code> command will check that some statement is true for all elements in some set. For instance, Fermat\u2019s Little Theorem is not true when you don\u2019t use a prime:<\/p>\n

> forall {x:x in Integers(24) | x^24 eq x }; <\/code>
\n false <\/code><\/p>\n

And, we can check that the statement is true only for a few special values in Z24<\/sub>:<\/p>\n

> {x:x in Integers(24) | x^24 eq x }; <\/code>
\n { 0, 1, 16, 9 } <\/code><\/p>\n

But we can also check that it is indeed true when we use \u201clarge\u201d primes:<\/p>\n

> IsPrime(9973);<\/code>
\n true<\/code>
\n > forall {x:x in Integers(9973) | x^9973 eq x };<\/code>
\n true<\/code><\/p>\n

The Euler Phi function \u03c6\u00a0is defined as the number of integers k<\/em> in the range 1 \u2264 k<\/em> \u2264 n<\/em> for which the greatest common divisor gcd(n<\/em>, k<\/em>) = 1. Euler\u2019s famous result states that if a<\/em> and n<\/em> are relatively prime, then a<\/em>\u03c6(n)<\/sup> \u2261 1 (mod n<\/em>). \u00a0There are many things you can do to explore values of Euler Phi. For example, if n<\/em> is the product of two distinct primes, there\u2019s a nice formula for computing the Euler Phi function. Let\u2019s look at some examples using a loop:<\/p>\n

for i in [1..10] do<\/code>
\nfor> for j in [1..10] do<\/code>
\nfor|for> if IsPrime(i) and IsPrime(j) and i ne j then<\/code>
\nfor|for|if> i,j, EulerPhi(i*j);<\/code>
\nfor|for|if> end if;<\/code>
\nfor|for> end for;<\/code>
\nfor> end for;<\/code>
\n2 3 2<\/code>
\n2 5 4<\/code>
\n2 7 6<\/code>
\n3 2 2<\/code>
\n3 5 8<\/code>
\n3 7 12<\/code>
\n5 2 4<\/code>
\n5 3 8<\/code>
\n5 7 24<\/code>
\n7 2 6<\/code>
\n7 3 12<\/code>
\n7 5 24<\/code><\/p>\n

Once you have the data above, you might look for a pattern. Given two primes p<\/em> and q<\/em>, can you conjecture a formula for\u00a0\u03c6(pq<\/em>)? (Maybe\u00a0you already know this theorem. Ok, fine. Move along… nothing to see here…)<\/p>\n

Exercise:<\/em><\/strong> We\u2019re trying to figure out which of the following \u201ctheorems\u201d is true?\u00a0 Use Magma<\/em> to compute values and see what you can learn.<\/p>\n