TOPICS
Search

Greatest Common Divisor Theorem


There are two different statements, each separately known as the greatest common divisor theorem.

1. Given positive integers m and n, it is possible to choose integers x and y such that mx+ny=d, where d=gcd(m,n) is the greatest common divisor of m and n (Eynden 2001).

2. If m and n are relatively prime positive integers, then there exist positive integers x and y such that mx-ny=1 (Johnson 1965).


See also

Greatest Common Divisor

Explore with Wolfram|Alpha

References

Eynden, C. V. Elementary Number Theory, 2nd ed. New York: McGraw-Hill, 2001.Johnson, P. B. "A Construction of Regular Polygons of pq Sides Leading to a Geometric Proof of rp-sq=1." Math. Mag. 38, 164-165, 1965.

Referenced on Wolfram|Alpha

Greatest Common Divisor Theorem

Cite this as:

Weisstein, Eric W. "Greatest Common Divisor Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GreatestCommonDivisorTheorem.html

Subject classifications