If gcd(a,b)=1 and ax+by=c has a positive integer solution, then so does ax+by=d when d>c. I need help proving this. Thanks.

Printable View

- Sep 17th 2013, 06:04 PMclintonh0610Proof Help Needed
If gcd(a,b)=1 and ax+by=c has a positive integer solution, then so does ax+by=d when d>c. I need help proving this. Thanks.

- Sep 17th 2013, 09:16 PMchiroRe: Proof Help Needed
Hey clintonh0610.

Its been a while since I've seen this, but my guess is to look at the conditions and procedures for solving a linear Diophantine equation and find the relationship between the gcd and the number of solutions.

From my prior coursework in cryptography I do know there is a specific protocol for solving linear Diophantine equations but I can't remember exactly what is involved. - Sep 18th 2013, 07:03 PMjohngRe: Proof Help Needed
I'm not certain how to interpret your problem? Given a and b

__positive__integers with gcd(a,b)=1. By a positive integer solution of ax + by = c, do you mean__positive__integers x and y with ax + by = c? If so, your assertion is false. Take a=3, b=5, c=8 and d=9. Clearly, ax+by=8 has solution x=y=1 but also clearly ax+by=9 has no positive integer solutions.

So amend your assertion to__non-negative__solutions. Your assertion is still false. Again a=3, b=5, c=3 and d=4 is a counter example.

A "standard" number theory exercise is:

Let a and b be positive integers with gcd(a,b)=1. If d is any integer with d >= ab, then there are non_negative integers x and y with ax + by = d.

Perhaps this is what you meant?