Please check if my proof has any error! I'm very happy to receive any suggestion to improve my proof. Many thanks for your help.
Definition:
$m \text{ divides } n \Leftrightarrow \exists p, n=pm$.
We denotes $(m \text{ divides } n)$ by $m \mid n,$ and $(m \text{ does not divide } n)$ by $m \not \mid n$.
Lemma 1:
$a \mid b$ and $a \not \mid c \implies a \not \mid (b+c)$
Proof:
Assuming the contrary, we have $a \mid (b+c)$. This implies $b+c=xa$. Since $a \mid b$, then $b=ya$. So we have $ya+c=xa$.
Clearly, $x \geq y$. So $x=y+r$. Substituting this into equation $ya+c=xa$, we have $ya+c=(y+r)a \implies c=ra \implies a \mid c$ (contradiction).
Thus $(a \mid b$ and $a \not \mid c) \implies a \not \mid (b+c)$.
Lemma 2:
$0<m<n \implies n \not \mid m$
Proof:
Assuming the contrary, $n \mid m \implies m=pn$.
If $p=0$, then $n=m=0$ (contradiction).
If $p \geq 1$, then $m=pn \geq n$ (contradiction).
Thus, $0<m<n \implies n \not \mid m$.
Theorem:
$(m \not \mid n \wedge m \neq 0) \Leftrightarrow (\exists p, 0<q<m \text{ s.t } n=pm+q)$
Proof:
- We prove $(\exists p, 0<q<m \text{ s.t } n=pm+q) \implies (m \not \mid n \wedge m \neq 0)$.
$m \mid pm$ and $m \not \mid q$ (Applying Lemma 2 for $0<q<m$) $\implies m \not \mid (pm+q)$, or $m \not \mid n$ (This is due to Lemma 1).
$0<q<m \implies m \neq 0$.
Thus $\exists p, 0<q<m \text{ s.t } n=pm+q \implies m \not \mid n \wedge m \neq 0$.
- We prove $(m \not \mid n \wedge m \neq 0) \implies (\exists p, 0<q<m \text{ s.t } n=pm+q)$.
Let $T=\{n \in \mathbb{N} \mid m \not \mid n \wedge m \neq 0 \implies \exists p, 0<q<m \text{ s.t } n=pm+q\}$.
$\forall n \in \mathbb{N}, 0=0.m \implies \forall n \in \mathbb{N}, m \mid 0$. Thus $0 \in T$.
Assuming $k \in T$. This implies ($m \not \mid k \wedge m \neq 0 \implies \exists p, 0<q<m \text{ s.t } k=pm+q)$.
Assuming $m \not \mid k+1$ and $m \neq 0$. We have two possible cases: $m \mid k$ and $m \not \mid k$.
a. $m \mid k$
$m \not \mid k+1 \implies m \neq 1$ [Since $\forall (k+1), 1 \mid (k+1)$].
$m \neq 0 \wedge m \neq 1 \implies m>1$ or $1<m$
$m \mid k \implies k=xm \implies (k+1)=xm+1$ in which $0<1<m$.
Thus $(k+1) \in T$.
b. $m \not \mid k$
$(k \in T \wedge m \not \mid k \wedge m \neq 0) \implies \exists p, 0<q<m \text{ s.t } k=pm+q$.
$\implies \exists p, 0<q<m \text{ s.t } (k+1)=pm+(q+1)$.
$\implies \exists p, 0<q+1<m+1 \text{ s.t } (k+1)=pm+(q+1)$.
Since $(k+1)=pm+(q+1)$ and $m \not \mid k+1$, then $(q+1) \neq m$.
$(q+1) \neq m \wedge 0<q+1<m+1 \implies 0<q+1<m$.
As a result, $\exists p, 0<q+1<m \text{ s.t } (k+1)=pm+(q+1)$.
Thus $(k+1) \in T$.
By principle of induction, $T=\mathbb{N}$, or equivalently $(m \not \mid n \wedge m \neq 0) \implies (\exists p, 0<q<m \text{ s.t } n=pm+q)$.
Combining results from 1. and 2. , we have $(m \not \mid n \wedge m \neq 0) \Leftrightarrow (\exists p, 0<q<m \text{ s.t } n=pm+q)$.