1
$\begingroup$

If $an+b$ is divisible by $c$. Then for which values of $x$ will $a(n+x)+b+1$ be divisible by $c$?
$a$, $b$, $c$, $n$, $x$ are all non-negative integers.

$\endgroup$
2
  • $\begingroup$ Please, try to make the titles of your questions more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. $\endgroup$ Commented Jun 9, 2015 at 8:23
  • 1
    $\begingroup$ What can you say about the difference of $a(n+x)+b+1$ and $an+b$? $\endgroup$ Commented Jun 9, 2015 at 8:24

1 Answer 1

1
$\begingroup$

As suggested in the comments, if $c\mid an+b$, then $$c\mid a(n+x)+b+1 $$$$\iff c\mid a(n+x)+b+1-an-b=ax+1$$

$$\iff ax\equiv -1\pmod{\! c}$$

If $(a,c)=d>1$, then $d\mid -1$, impossible.

So necessarily $(a,c)=1$. It turns out it is sufficient for $x$ to exist.

$a^{-1}$ exists mod $c$, so $ax\equiv -1\iff x\equiv -a^{-1}\pmod{\! c}$.

Expressed without modular arithmetic, we have $$c\mid ax+1\iff a(-x)+ck=1$$

for some integer $k\in\Bbb Z$.

Such integer pair $(-x,k)$ exists iff $(a,c)=1$ by Bezout's lemma.

$\endgroup$
4
  • $\begingroup$ Cannot understand the last line. $\endgroup$ Commented Jun 9, 2015 at 9:03
  • $\begingroup$ @ShubhamAvasthi Edited. $\endgroup$
    – user26486
    Commented Jun 9, 2015 at 9:10
  • $\begingroup$ What do you mean by (a,c) ? $\endgroup$ Commented Jun 12, 2015 at 8:10
  • $\begingroup$ @ShubhamAvasthi $\gcd(a,c)$. That is a very usual notation for gcd. $\endgroup$
    – user26486
    Commented Jun 12, 2015 at 12:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .