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.
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.
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?