0
$\begingroup$

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 ?

$\endgroup$
5
  • 1
    $\begingroup$ What does "solveable" mean here? Solve for which variable? The equation holds iff a and b differ by a multiple of n. $\endgroup$
    – TMM
    May 18, 2017 at 11:05
  • $\begingroup$ (So your first remark of a being a multiple of b is clearly wrong, unless you made a mistake in copying the question.) $\endgroup$
    – TMM
    May 18, 2017 at 11:07
  • $\begingroup$ @TMM: It means that you can solve the equation $n|(a-b)\in\Bbb Z$ $\endgroup$
    – pinkpanther5
    May 18, 2017 at 11:07
  • $\begingroup$ @TMM: English isn't my first language, should it be $a$ is a multiple of $b$ ? $\endgroup$
    – pinkpanther5
    May 18, 2017 at 11:10
  • $\begingroup$ 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. $\endgroup$
    – TMM
    May 18, 2017 at 13:19

1 Answer 1

Reset to default
-1
$\begingroup$

The congruence holds if and only if the gcd of $a$ and $n$ is a divisor of $b$.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Darth Geek
    May 18, 2017 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.