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.

You would need $an+b$ to be a multiple of $c$. So how about $an+b=ck$ for all $k\in\mathbb{Z}$. — Laars Helenius, Nov 25 '16 at 22:43

Vidyanshu Mishra · Answer 1 · 2016-11-25T22:48:18.400

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

edited Nov 25 '16 at 22:48

answered Nov 25 '16 at 22:45

Vidyanshu Mishra

10,143

As I stated in the Question, this RHS is not an integer for all p. – Jerry Guern Nov 25 '16 at 22:47

Ross Millikan · Answer 2 · 2017-04-12T02:35:50.637

1

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.

edited Apr 12 '17 at 02:35

answered Nov 25 '16 at 23:00

Ross Millikan

374,822

Thanks but these are conditions on the answer, not an answer. – Jerry Guern Nov 25 '16 at 23:57
Yes it is an answer. You changed $k$ to $n$ in your edit. In the coprime case and using your new notation, $n_k=bc^{-1}+ka$ where the inverse is taken modulo $a$. That is an explicit formula of exactly the form you asked. – Ross Millikan Nov 26 '16 at 04:23
I edited the question to attempt to clarify it, since the first answers I got didn't address what I needed. Sorry if my first attempt was unclear. – Jerry Guern Nov 26 '16 at 05:02

Kitter Catter · Answer 3 · 2016-11-26T01:50:57.087

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

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.
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$.
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')}$

Simple integers problem

3 Answers3