3

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?

TAPLON
  • 1,948
  • 1
    I think it should be that $ax\equiv d\pmod n$. – Mr Pie Feb 25 '18 at 22:42
  • 1
    a solution for a linear equation mod $n$ exists if and only if GCD$(a,n)$ divides $b$ – barmanthewise Feb 25 '18 at 22:43
  • 2
    For the problem as stated, your counterexample is correct. But if, in the statement of the problem, assuming $d>1$, you change $\gcd(b,d)\ne 1$ to $\gcd(b,d)=1$, the claim holds. So probably a typo. – quasi Feb 25 '18 at 22:46
  • Okay I figured it was a mistake, but I wanted to make sure I wasn't completely overlooking something since textbooks don't typically have a whole lot of typos. Thanks! – TAPLON Feb 25 '18 at 22:49
  • The claim also is true, and more precise, with $gcd(b,d)\ne d$. – Oscar Lanzi Feb 25 '18 at 22:51
  • 3
    @JustinStevenson The number of typos in a book is a decreasing function of the edition number, which hasn't limit $0$ even though it takes values on a discrete set. – egreg Feb 25 '18 at 23:05

1 Answers1

1

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$.

Oscar Lanzi
  • 39,403