2
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ I know something called the Euclidean algorithm. I am not sure what Division Algorithm means, or what it accomplishes... $\endgroup$
    – Will Jagy
    Dec 15, 2018 at 1:32
  • $\begingroup$ @Will It's a common name for Euclidean Division (with Remainder) (algorithm) $\endgroup$ Dec 15, 2018 at 1:35
  • $\begingroup$ @Bill fair enough. What I was thinking about was that the algorithm I had in mind really does use positive numbers throughout, but there are other settings (such as polynomials with rational coefficients) which are fairly familiar, where there is an (extended) Euclidean algorithm, but there is not a natural restriction to, well, positivity. Or, say, Gaussian integers for example. Oh, right, and that is why divisibility is not restricted to positive numbers. $\endgroup$
    – Will Jagy
    Dec 15, 2018 at 1:46
  • $\begingroup$ @Bill Oh, well, from your link it is a single division, not all of Euclidean. $\endgroup$
    – Will Jagy
    Dec 15, 2018 at 1:54
  • 1
    $\begingroup$ @Will Yes, sometimes the denotation is ambiguous, i.e. a single division step vs. complete Euclidean gcd algorithm (remainder sequence) $\endgroup$ Dec 15, 2018 at 2:16

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Great insight Bill. I always love an algebraic approach. $\endgroup$ Dec 15, 2018 at 18:49
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Excellent answer, thank you. $\endgroup$ Dec 15, 2018 at 18:49
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you Ethan. I think on this one I was way overthinking things. $\endgroup$ Dec 15, 2018 at 18:50

You must log in to answer this question.

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