OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Euclid’s lemma|elementary number theory

Euclid’s lemma|elementary number theory

Euclid’s lemma: If a/bc, with gcd(a, b) = 1, then a/c.

Proof: Since gcd(a, b) = 1 then we can write 1 = ax + by, where x and y are integers. Multiplication of this equation by c, provides

c = 1. c = (ax + by) c = acx + bcy

Since a\ac and a\bc, it follows that a\ (acx + bcy), which can be recast ac a\c.

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *