0
$\begingroup$

When finding the solutions of $$ax \equiv b\pmod{n}$$ I've been given an algorithm which starts by testing that the $\text{gcd}(a, n)|b$.

How can I show (for understanding better the topic) that if $b$ is not a multiple of $\text{gcd}(a,n)$, the congruence above can't have any solution?

$\endgroup$
1
  • $\begingroup$ $3x\equiv 8\pmod{15}$ has no solution...You can check it by putting $x$ infinitely many times..!!! $\endgroup$
    – Empty
    Sep 9, 2015 at 15:50

3 Answers 3

1
$\begingroup$

Lets look at it the other way, and show that if the equation has a solution, $b$ is a multiple of $\gcd(a,n)$.

Let $x$ be such a solution ; then there is $k$ such that $ax = nk+b$, or $a x - n k = b$.

But $\gcd(a,n)$ divides the LHS, so it divides the RHS.

$\endgroup$
1
$\begingroup$

Note that $ax \equiv b \pmod m$ is the same as saying that there is some integer $y$ so that $ax + my = b$. If $d$ divides both $a$ and $m$, then it divides the left hand side, and thus divides $b$.

$\endgroup$
1
$\begingroup$

Just a quick idea as I saw this. It follows from $ax \equiv b\ ({\rm mod}\ n)$ that $n | (b - ax)$, that is $b - ax = kn$, from which it follows that $b = kn + ax$. That is, $b$ is a linear combination of $n$ and $a$. The gcd is the smallest element of the set of all such linear combinations.

Hope this helps.

$\endgroup$

You must log in to answer this question.

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