# Proof that $a|b \iff ac|bc$

I have to prove, using the concept of divisibility (and no division), that if $c\ne 0$ then $a\mid b \leftrightarrow ac\mid bc$. I first proved $a \mid b \to ac\mid bc$, then got stuck on the opposite process. Here's what I did on the first part (please assume all numbers to be integers): $$a\mid b$$ $$b=ka$$ $$bc=kac$$ $$ac\mid bc$$ Is this right?
As for $ac\mid bc \implies a\mid b$, I can't figure out a way to remove $c$ from $b$ without messing everything on $a$'s side.

Googling for an answer, I only found solutions that used division itself, which was of no help. Thanks in advance for your help!

• @Dzoooks for the first half... yes... the OP is having difficulties in performing the second half. Read the question more carefully. – JMoravitz Jun 23 '18 at 22:28
• Are you sure you understood correctly that you should use "no division"? – Phira Jun 23 '18 at 22:29
• Can you use that if a product is zero, then one of the factors is zero? – Michael Burr Jun 23 '18 at 22:29
• @Phira division is frowned upon for questions at this level pertaining to divisibility properties. – JMoravitz Jun 23 '18 at 22:29
• @Phira I assume that the distinction here is to avoid the operation of division, not the properties of division. – Michael Burr Jun 23 '18 at 22:32

## 4 Answers

Although this is a bit of a cheat (it's barely avoiding division), you could do the following:

Sketch:

Suppose that $ac\mid bc$. Then there is some integer $k$ so that $ack=bc$. Therefore, by factoring $c(ak-b)=0$. Since $c\not=0$, you can conclude something about the other factor...

Can you take it from here?

Let $ac | bc$. Then there is some $k \in \mathbb{Z}$ such that $ack = bc$. Then $(ak - b)c = 0$. As $c \neq 0$ by assumption, we have $ak - b = 0$, so $ak = b$, so $a | b$.

The property of $\mathbb Z$ that $ab = 0$ implies $a = 0$ or $b = 0$ is essential to this result, so hopefully using this is allowed.

You want to go through your equivalences backwards and of course, you need to divide by $c$. So, the actual question is: How to write the division without calling it division?

$bc=kac \Leftrightarrow c(b-ka)=0$, so since $c$ is not zero you get $b=ka$.

• "So, the actual question is: How to write the division without calling it division?" I honestly think another legitimate question is why the heck can't we do division? – fleablood Jun 24 '18 at 1:48
• @fleablood hahah yes, very much so :) – Mr Pie Jun 24 '18 at 23:44

Strong Hint:\begin{align}ac&=bc\\ \Leftrightarrow\quad \bigg(\frac 1c\bigg)ac&= \bigg(\frac 1c\bigg)bc \\ \Leftrightarrow\space\, \bigg(\frac 1c\cdot c\bigg)a&= \bigg(\frac 1c\cdot c\bigg)b \\ \Leftrightarrow\quad\quad\:\, 1\cdot a&=1\cdot b \\ \Leftrightarrow\quad\quad\quad\,\,\, a&=b\end{align} This is known as the $\color{green}{\text{Multiplicative Cancellation Law}}$.

• This would apparently not be and acceptable answer as multiplying be the multiplicative inverse is the equivalent (often the very definition) of division and, for inexplicable, unfathomable and unexplained reasons, division is not allowed. Which isn't to say, your answer isn't the correct one (it clearly is) but that it will not be acceptable by the OP's bizarre and weird class for bizarre and weird reasons. I really do wish it would be explained why division is not being acceptable. – fleablood Jun 24 '18 at 1:48
• I do not understand what you mean. This answer is directly from Modern Mathematics by J. B. Fitzpatrik and L. Watson. Also, the OP can just change the equals sign to the divisibility sign and what follows is desired. That was what my hint was trying to imply. – Mr Pie Jun 24 '18 at 2:58
• My point is the OP said "and no division" and "solutions that used division itself, which was of no help" and "yes, the professor made it clear since day 1 of the course that we shouldn't use division". My point is 1) given that division is not allowed this proof won't satisfy to OP and 2) Why the #### does the OP think division is not allowed? That make absolutely NO sense at all!.... in any event, I think your answer is perfect and I'm sur Fitzpatrik and Watson don't worry about "You can not use division". But the OP and professor will not like it. – fleablood Jun 24 '18 at 5:50
• @fleablood ok, now I understand your point $-$ and yes I very much agree. But I can't blame the OP if his/her professor asked for no division, even though the professor's requirements does not make much sense. – Mr Pie Jun 24 '18 at 23:39