# Thread: prove that c is negative if c = xa + yb < gcd(a, b)

1. ## prove that c is negative if c = xa + yb < gcd(a, b)

for a, b, c, x, y Є Z and a, b != 0

How do I approach this question?

2. It is very similar to the proof that shows for all d>0 where d is a common divisor of $\displaystyle a,b\epsilon Z$ that $\displaystyle d=gcd(a,b)$ if and only if $\displaystyle d=x*b*ya$ for some $\displaystyle x,y \epsilon Z$

Prove that c is negative if $\displaystyle c=xa+yb<gcd(a,b)$.

Proof:

Suppose $\displaystyle c=xb+ya$ for some $\displaystyle x,y \epsilon Z$

Any common divisor d of a,b divides $\displaystyle xb+ya \implies d|c$
Since d|c we know that |d| is less than or equal to |c|. This means that gcd(a,b)=|c|<gcd(a,b). This means that c must be -gcd(a,b), and since gcd(a,b) is always positive, then c must be negative.

Where gcd = greatest common divisor
|c|= magnitude of c

I am not guaranteeing its correctness but this is the basic idea... you may have to be more descriptive in areas.

3. Originally Posted by SaxyTimmy
This means that gcd(a,b)=|c|<gcd(a,b).
I think you've made a small mistake here. What I think you meant to say was:

|c| = gcd(a,b)
c < gcd(a,b) (What the question is asking to prove.)

4. No, I am pretty sure that I answered the question as it was asked. I proved that c must be negative if it was less than gcd(a,b)