Divisibilty vs. division, for negative divisors

Question

I'm learning some basic number theory from Strayer's 'Elementary Number Theory.' I've arrived at what seems to be a very basic problem, albeit complete with a nasty twist:

---

Let $a,b,c \in \mathbb Z$ with $c \neq 0$. Prove that $a\mid b$ if and only if $ac\mid bc$.

---

The proof is trivial when $c>0$.
What has me confused is the case when $c<0$. If $a\mid b$, then $b=aq$ where $q \in \mathbb Z$ and $a>0$. Multiplication by $c$ on $b=aq$ yields $bc=(ac)q$, where clearly $ac<0$.

This is my problem. The 'division algorithm,' as it's been taught in the early stages of this book (and number theory in general) doesn't allow for the divisor to be negative. If we fix $c$ to $q$ by saying $bc=a(cq)$, we avoid the issue of a negative divisor, but then we can only say $a|bc$. Similarly, if we negate the negative quality of $c$, perhaps by saying $bc=(-ac)(-q)$, then still we can only say $-ac\mid bc$.

What am I missing here? Surely Strayer meant what he said - that is, $c \neq 0$ - and not something that would make more sense like $c>0$. Any help would be greatly appreciated!

Answer 1

The division algorithm isn't the definition of divisibility. It's simply a statement that unique divisors and remainder pairs exist.

The definition is that $a|b $ if there exists an integer $m $ so that $am=b $. Sign has nothing to do with it. (And if you want to get technical neither $a $ nor $b $ need to be integers at all.)

A few notes: $a|b \iff \pm a| \pm b $ for all possible combinations of signs. The reason why should be obvious.

Also, if the division principal requires the the divisor can't be negative there is nothing that says the quotient or the dividend can't. For example: to divide $-19$ by $7$ and getting $-19=-3*7+2$ or $-19\equiv 2\pmod 7$ is perfectly acceptable.

Answer 2

This proof doesn't depend on the sign of $c$:

$a|b$ means there is some $k$ such that $ak=b$. Then multiply by $c$ to conclude that there's an integer, namely $k$, such that $(ac)k = bc$, so $ac | bc$. The converse is equally straightforward.

On your other point: you can do the division algorithm with a negative divisor $d$. What it asserts is that there is a quotient $q$ and a remainder $r$ between $0$ and $d-1$ such that $\ldots$. It's OK for the quotient to be negative.

Answer 3

The definition of the divisibility relation doesn't require the stronger property of (Euclidean) division with smaller remainder. $\,a$ divides $b\,$ is defined in a commutative ring $R$ as follows

$$ a\mid b \ \ {\rm in}\ \ R\iff ar = b\ \ {\rm for\ some}\ \ r\in R$$

Then $\ a\mid b\iff ac\mid bc\,$ follows immediately by multiplying the equation by $c$ or cancelling $\,c\,$ (assuming $c$ is cancellable, which here in $\,\Bbb Z\,$ follows by $\,c\neq 0)$

See this answer for links on how signs are handled in algorithms for division with remainder.

Note: Analogous remarks hold for divisibility vs. division by zero: $\,b/0\,$ is undefined but $\ 0\mid b\iff b = 0,\ $ e.g. $\, a = b \pmod{\! 0}\!\iff\! 0\mid a-b \!\iff\! a = b;\,$ i.e. structurally $\,\Bbb Z = \Bbb Z/0 = $ integers $\!\bmod 0\,$ (the utility of which will be clearer when one studies quotient rings, e.g. factoring out by a prime ideal.)