Appendix E: Finite Fields and Number Theory
Stephen C. Newman · 2012
Let a 1 , a 2 , . . ., a n be integers, not all of which are zero.The greatest common divisor of a 1 , a 2 , . . ., a n , denoted by gcd(a 1 , a 2 , . . ., a n ), is the largest natural number that divides each of a 1 , a 2 , . . ., a n .For an arbitrary natural number c,We say that a 1 , a 2 , . . ., a n are relatively prime (to each other) if gcd(a 1 , a 2 , . . ., a n ) = 1.Theorem E.1.For all integers m and n, there are integers a and b such that gcd(m, n) = am + bn.Proof.The proof is essentially that given for the Division Algorithm, except that the absolute value of integers is used as a measure of magnitude instead of the degree of polynomials.The phi-function ϕ is defined as follows.For each natural number n, ϕ(n) is the number of natural numbers less than or equal to n that are relatively prime to n, that is,