Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

Suppose that m,n,q,r are integers satisfying the identity n=mq+r. Then gcd(m,n)=gcd(m,r).

Let gcd(m,n)=k where k is some integer, then k|m and k|n. n=mq+r can be expressed as r=n-mq=k|n+k|m. Therefore k|r.

Let gcd(m,r)=p where p is some integer, then p|m and p|r. n=mq+r=p|m+p|r. Therefore p|n.

Therefore, p|m,n,r and k|m,n,r.

Next step is where my notes do not make sense for me.

If k|m and p|m then kx=m and py=m for some integers x and y. Therefore kx=py and k=p. Q.E.D.

Re: Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

Quote:

Originally Posted by

**mokaro** n=mq+r can be expressed as r=n-mq=k|n+k|m.

One cannot write k | n + k | m. Indeed, k | n is not a number; it is either true or false depending on whether k divides n. Addition is not defined on Boolean values (true and false). Instead, you could write, "Since k | n and k | m, we have k | (mq) and therefore k | (n - mq)".

Quote:

Originally Posted by

**mokaro** Next step is where my notes do not make sense for me.

If k|m and p|m then kx=m and py=m for some integers x and y. Therefore kx=py and k=p. Q.E.D.

The conclusion k = p does not make sense to me either. Your proof showed that every common divisor (not just GCD) of n and m is a also a common divisor of m and r and vice versa, i.e., the sets of common divisors of (n, m) and (m, r) are the same. Therefore, the maximums of these sets are also the same, i.e., the gcd(n, m) = gcd(m, r).

More generally, call r a linear combination of n and m if r = an + bm for some integers a and b. So, if r is a linear combination of n and m, then every common divisor of n and m is also a divisor of r. Similarly, if r and p are two linear combinations of n and m, then every common divisor of n and m is also a common divisor of r and p. Therefore, if r, p are linear combinations of n, m and, vice versa, n, m are linear combinations of r, p, then gcd(n, m) = gcd(r, p). Now, if n = mq + r, then m = 0 * n + 1 * m and r = 1 * n + (-q) * m are linear combinations of n and m. Conversely, n and m are linear combinations of m and r. By the claim above, their GCDs are the same.

Re: Suppose that m,n,q,r are integers satisfying n=mq+r. Then gcd(m,n)=gcd(m,r).

Love it. Thanks buddy. Very thorough and clear.