# Proof Help Needed

• Sep 17th 2013, 06:04 PM
clintonh0610
Proof 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 PM
chiro
Re: 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 PM
johng
Re: 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?