Is this a mistake in my book?

99 Views Asked by At

In my Abstract Algebra book I am asked to answer the following question.

Let $gcd(a,n)=d$ and $gcd(b,d) \neq 1$. Prove that $ax \equiv b \space(mod \space n)$ does not have a solution.

As soon as I read this it struct me as false since I studied this stuff in Number Theory, I came up with the following counter example. Let $a=24$ $n=10$ $b=6$ then $d=gcd(24,10)=2$ and $gcd(2,6)=2 \neq 1$ yet $x=4$ is a solution.

Am I missing something with this question or is it just wrong?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, you are right. They mistyped in the book. We will never know what was meant, but the comments give a couple possibilities. Both $ gcd(b,d)=1$ and $gcd(b,d)\ne d$ would have worked.

When $gcd(b,d)=d$ we have multiple solutions. We can think of this case as "hogging" all the solutions. In your example $24x\equiv 6 \bmod 10$ is solved by $x\equiv 4$ and also $x\equiv 9$.