# $a \equiv b \pmod n$ solveable - which necessary and sufficient conditions ?

For given $n\in \Bbb N, n \ge2, a,b \in \Bbb Z$ give necessary and sufficient conditions such that $$a\equiv b\pmod n$$ is solveable.

First I thought that it would be sufficient if $b$ would be a multiple of $a$, so for $c\in \Bbb Z$ we'd have $a= b \cdot c$.

For the necessary part I have no clue, I mean if the $gcd(a,n)=1$ so it's solveable for each $b \in \Bbb Z$, but this had been already be talked about in the lecture, so it's not that what it's asked for.

Any hint for which part I should pay attention to ?

• What does "solveable" mean here? Solve for which variable? The equation holds iff a and b differ by a multiple of n.
– TMM
May 18, 2017 at 11:05
• (So your first remark of a being a multiple of b is clearly wrong, unless you made a mistake in copying the question.)
– TMM
May 18, 2017 at 11:07
• @TMM: It means that you can solve the equation $n|(a-b)\in\Bbb Z$ May 18, 2017 at 11:07
• @TMM: English isn't my first language, should it be $a$ is a multiple of $b$ ? May 18, 2017 at 11:10
• No, multiples are all wrong. As I said, a and b must differ by a multiple of n. This might even mean that a and b are coprime, depending on n.
– TMM
May 18, 2017 at 13:19

The congruence holds if and only if the gcd of $a$ and $n$ is a divisor of $b$.
• This is not true. Let $a = 4$, $b = 8$ and $n = 6$. Then $\gcd(4,6) = 2$ which is a divisor of $8$ but $4 \not\equiv 8 \pmod 6$. May 18, 2017 at 12:17