One of the basic techniques of number theory is Euclid’s algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers.
Greatest Common Divisor
We will use the notation gcd(a,b) to mean the greatest common divisor of a and b.The positive integer c is said to be the greatest common divisor of a and b if
1. c is divisor of a and of b;
2. any divisor of a nad b is a divisor of c.
an equivalent defenition is the following:
gcd(a,b) = max[k, such that k|a and k|b]
Because we require that the greatest common divisor be positive,
gcd(a,b)=gcd(a, -b)=gcd(-a,b)=gcd(-a,-b). In general,gcd(a,b)=gcd(|a|,|b|).
Eg: gcd(60,24)=gcd(60,-24)=12
Also because all nonzero integers divide 0, we have gcd(a,0)=|a|.
We stated that two integers a and b are relatively prime if their only common positive integer factor is 1. This is equivalant to saying that a and b are relatively prime if gcd(a,b)=1.
