BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / If gcd(a, b) = d, then gcd(a/d, b/d) = 1

# If gcd(a, b) = d, then gcd(a/d, b/d) = 1

Proof: Before starting with the proof proper, we should observe that although a/d and b/d have the appearance of the functions, in fact, they are integers because d is a divisor both of a and of b. Now, knowing that gcd(a, b) = d, it is possible to find integers x and y such that d = ax + by. Upon dividing each side of this equation by d, we obtain the expression

1 = (a/d)x + (b/d)y

Because a/d and b/d are integers, an appeal to the theorem is legitimate. The conclusion is that a/d and b/d are relatively prime. (Proved)

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}