Relatively Prime Linear Combinations

If there exist x and y for which ax+by=GCD(a,b) then GCD(x,y)=1.


Let g=GCD(a,b) and x and y solutions to ax+by=g.

Since g|a and g|b, there exist integers n and m such that a=gn and b=gm.

ax+by=gnx+gmy=g

So, nx+my=1

The GCD(n,m)=1 since g is the GCD(a,b).

Let d be a divisor of x. If d also divides my, then d must divide 1, which isn’t possible. So, GCD(x,y)=1.

One Response to Relatively Prime Linear Combinations
  1. gparker says:

    Interesting, but I don’t think it applies to the fraction problem.

Leave a Reply