MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
0

For some given positive integers A, B, and C, how can I find the lowest value of x such that:

Ax+B=Cy

where x,y also positive integers.

For example 10x+6=7y the lowest value of x is x=5 where y=8.

I thought I could use Euclidean algorithm, but I haven't figured out how I could apply it here. Is there a different general algorithm for solving this?

Thanks,

Dan

(Not homework, just related something I'm working on)

flag
7 
 You can, in fact, use the Euclidean algorithm. The Wikipedia article on the extended Euclidean algorithm describes how to do this. – Qiaochu Yuan Mar 15 2010 at 17:56
1 
 Thanks for clarifying that it's not homework. Nevertheless, I reckon you'll get better answers from the sites listed on the FAQ under "Math Overflow is not for homework help". Good luck. – Tom Leinster Mar 15 2010 at 19:34
Thanks. Took me a bit of tooling around but I now got it. Taking Extended Euclidean gives me 10*2+1=7*3. Which gives 10*12+6=7*18. This is just one possible answer, to get the one I want I must take y MOD A (18 mod 10) and x MOD C which gives me 10*5+6=7*8. – Dan Mar 15 2010 at 19:43

closed as too localized by Steve Huntsman, Reid Barton, Tom Leinster, Yemon Choi, Gjergji Zaimi Mar 15 2010 at 19:54

Browse other questions tagged or ask your own question.