(a + n * b ) % c == 0, seek n

[princemaozh]

provided: a, b, c are all integers, and c > a

I want to seek the minumum integer n which meet the below condition
(a + n * b ) % c == 0


for example
a = 1; b = 5 ; c =4,

so the minimun n is 3, so (1 + 3* 5) % 4 == 0.


the most simple and stupid way is tring every n from 1 to a big number(eg. 10000), if mod is 0, the return; otherwize try until the big number reached

Is there any formal algorithm for my requirement?
Some times we can not get an "n" which meet the condition, so there must be an abortion condition which means no resolution.

thank you.

[wildfrog]

Is there any formal algorithm for my requirement?AFAIK it's called a 'Linear Congruence Equation".

- petter

[princemaozh]

Yes, it is. Thank you!