# prove

Printable View

• Sep 18th 2008, 04:59 AM
mandy123
prove
Prove that if d s a positive integer, d/a and d/b, then gcd(a,b)=d iff
gcd(a/d,b/d)=1
• Sep 18th 2008, 05:09 AM
kalagota
Quote:

Originally Posted by mandy123
Prove that if d s a positive integer, d/a and d/b, then gcd(a,b)=d iff
gcd(a/d,b/d)=1

this is straightforward..

\$\displaystyle ax + by = d \Longleftrightarrow (a/d)x + (b/d)y = 1\$ and a/d and b/d are both integers since d|a and d|b
• Sep 18th 2008, 05:22 AM
Laurent
Quote:

Originally Posted by kalagota
\$\displaystyle ax + by = d \Longleftrightarrow (a/d)x + (b/d)y = 1\$ and a/d and b/d are both integers since d|a and d|b

The following addendum to kalagota's answer is probably obvious, but just in case: \$\displaystyle ax + by = d\$ implies that \$\displaystyle \gcd(a,b)|d\$, so that \$\displaystyle \gcd(a,b)=d\$ since conversely \$\displaystyle d|a\$ and \$\displaystyle d|b\$ imply \$\displaystyle d|\gcd(a,b)\$.
{"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}