Math IOQM

Proof: p = a.x q = b.x gcd(p,q) = k Using Bezout's identity: k = s.p + r.q = s.a.x + r.b.x = x(s.a + r.b) => x divides k H.P.

6.2 Euclid’s GCD Algorithm Euclid’s algorithm is an efficient method for computing the greatest common divisor of two integers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. The Division Lemma. For any two integers \( a \) and \( b \) (where \( b \neq 0 \)), there exist unique integers \( q \) and \( r \) such that: \[ a = bq + r, \quad 0 \le r

 1. GCD is the largest positive integer(with one exception) that divides each of the integers in a given set. 2. Even if one or more input numbers are negative, output is always positive. 3. Both inputs/output are integers. 4. gcd(a,0) = |a| 5. gcd(0,0) = 0, this is defined like this. Though gcd(0,0) can be any integer. This is the only case where gcd is not positive. It is 0.