BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Let a and b be integers not both zero. Then a and b are relatively prime if and only if there exist integers x and y such that 1 = ax + by.

# Let a and b be integers not both zero. Then a and b are relatively prime if and only if there exist integers x and y such that 1 = ax + by.

Proof: If a and b are relatively prime so that gcd(a, b) = 1. Then the theorem

( “ Given integers a and b, not both of which are zero, there exist integers x and y say that gcd(a, b) = ax + by”)

guarantees the existence of integers x and y satisfying 1 = ax + by. As for the converse, suppose that 1 = ax + by for some choice of x and y, and that d = gcd(a, b). Since d\a and d\b, then d\(ax + by), or d\1. In as much as d is a positive integer, this last divisibility condition forces d to equal 1and the desired conclusion follows.

Relatively Prime: Let a and b integers not both zero are said to be relatively prime whenever gcd(a, b) = 1.

## Application of Euclidian’s algorithm in Diophantine equation

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