Simple integers problem

Question

If a, b,& c are positive integers, what is a formula for all the integer values of n such that (an+b)/c is an integer?

For sets {a,b,c} that allow a solution, all the solution n's should be expressible in the form $n_k \equiv f(a,b,c,k)$ where k is an arbitrary indexing integer.

I re-edited this because a couple of answers below state the obvious about necessary/sufficient conditions but don't answer the question.

Answer 1

The necessary and sufficient condition is that ax+b should be a multiple of c. Then Suppose $(ax+b)/c =p$ where p is any integer. Then $n=(pc-b)/a$.

Answer 2

You need $kc-b\equiv 0 \pmod a$ for the division to come out. If $a$ and $c$ are coprime, you can find the modular inverse of $c$ and solve it as $k \equiv bc^{-1} \pmod a$. If $a$ and $c$ are not coprime, you need their $\gcd$ to divide $b$ and you can divide the whole equation by the $\gcd$, getting $\frac {kc-b}{\gcd(a,c)} \equiv 0 \pmod {\frac a{\gcd(a,c)}}$ and solve it the same way.

Answer 3

I hope you don't mind if I get a few thoughts out there. The first question we need to ask is:

1. Are there always solutions to the integer solutions to $(an+b)/c=d$ for a given $(a,b,c)$?

   No: $(3,1,9)$ is a counterexample.

2. Are there any conditions where there are solutions?

   Yes: If $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $n$ must solve $an\equiv c-b \mod c$ since $a,b$ are relatively prime with $c$ we are guaranteed that $n$ exists up to modulo $c$.

3. Say we find a solution, how can we get the next one?

   $n_{k+1} = n_{k}+\frac{c}{\gcd(a,c)}$if you multiply that expression by $a$ you are guaranteed to get $a\cdot n_k+b+\frac{ac}{\gcd(a,c)}$. The left part is divisible by $c$ since they were last time, the right part of this expression is guaranteed to be divisible by $c$ since $a$ is divisible by $\gcd(a,c)$ by definition of divisor.

I can therefore give you some idea of what your final answer will look like: $f(a,b,c,k) = f(a,b,c,k-1)+\frac{ac}{\gcd(a,c)}\rightarrow f(a,b,c,k) = f(a,b,c,1)+(k-1) \frac{ac}{\gcd(a,c)}$

Hunting for $f(a,b,c,1) = f(a',b',c')$ where $x' = \frac{x}{\gcd(a,b,c)}$:

We search for $(c'-b')(a')^{-1} \mod c'$. If $a'$ is relatively prime to $c'$ then the answer is $(c'-b')(a')^{\phi(c')-1}\mod c'$ where $\phi(c')$ is the euler totient function evaluated at $c'$. If $a'$ is not relatively prime to $c'$ then there is no solution. Answer is thus:

$f(a,b,c,k) = f(a',b',c',k) = [(c'-b')(a')^{\phi(c')-1}\mod c']+(k-1)\frac{a'c'}{\gcd(a',c')}$