Proof of cancellation law for multiplication of natural numbers.

Question

The cancellation law for the multiplication of natural numbers is:

$$\forall m, n\in\mathbb N, \forall p\in\mathbb N-\{0\}, m\cdot p=n\cdot p\Rightarrow m=n.$$

Is it possible to show this using induction?

I tried to define $$X=\{n\in\mathbb N: \forall m\in\mathbb N, \forall p\in\mathbb N-\{0\}, m\cdot p=n\cdot p\Rightarrow m=n\}.$$

It is easy to verify that $0\in X$ but I'm not able to show that if $n\in X$ then $n+1\in X$.

My attemp: Suppose $$m\cdot p=n\cdot p\Rightarrow m=n$$ for all $m\in\mathbb N$ and $p\in\mathbb N-\{0\}$. Supposing

$$m\cdot p=(n+1)\cdot p$$ we should show $m=n+1$. But:

$$m\cdot p=(n+1)\cdot p=n\cdot p+p,$$ and I can't see how to use the induction hypothesis.

Well, I could try to prove this after trichotomy. If it were the case that $m\neq n+1$ then $m>n+1$ or $m<n+1$. In the first case we would have $m=n+1+r$ for some $r\in\mathbb N-\{0\}$. Then:

$m\cdot p=(n+1+r)\cdot p=(n+1)\cdot p+r\cdot p.$Since $r, p\in \mathbb N-\{0\}$ it would follow $$m\cdot p>(n+1)\cdot p,$$ which contradicts $$m\cdot p=(n+1)\cdot p.$$ Is there another way to do this proof?

Answer 1

Hint

You have : $m⋅p=(n+1)⋅p$.

But you know that $(n+1) \ne 0$ and the assumption is that $p \ne 0$. Thus $m⋅p=(n+1)⋅p \ne 0$ and from it and $p \ne 0$ we have that $m \ne 0$.

To say that $m \ne 0$ means that $m=z+1$ for some $z$. Thus, from $m⋅p=(n+1)⋅p$ we get :

$(z+1)⋅p=zp+p=np+p$.

Now we apply the (previous proved : by induction) cancellation law for sum to get : $zp=np$.

On it we apply the induction hypotheses to conclude with :

$z=n$.

From it we get : $z+1=n+1$, i.e.

$m=n+1$.

Answer 2

If you have proved trichotomy and enough laws for addition, then you could do something like:

Assume $n\ne m$, then without loss of generality $m>n$ which is to say, $m=n+k$ for some $k\ge 1$. We then have $ (n+k)p = np $ -- but by induction on $k$ this is impossible.