# Euclid’s algorithm

Euclid’s algorithm:

Theorem 1 Euclid’s algorithm: Given ${ m,n \in \: \mathfrak{N} }$ , ${ m \neq 0 }$, then there exist ${ q,r\in \: \mathfrak{N} }$ , ${ 0 \leq r < m }$ such that ${ n = mq+r }$.

Proof: We prove the statement using the principle of mathematical induction.

Denote ${ \mathcal{P} (n): \; n=mq+r }$

Fix m.

Clearly, ${ \mathcal{P} (0): \; 0=m0+0 }$ is true.

Suppose, ${ \mathcal{P} (n) }$ is true i.e. there exist m,r with ${ 0 \leq r < m }$ such that ${ \mathcal{P} (n): \; n=mq+r }$ is true.

Consider ${ n' = n+1 =mq+r+1 }$.

Since ${ 0 \leq r < m }$, ${ 0 \leq (r+1) < m+1 }$. Hence, ${ r+1 or ${ r+1=m }$

If ${ r+1, then ${ n' = mq+\hat{r} }$, where ${ \hat{r}=r+1 }$.

Hence, there exist ${ q,\hat{r} \in \mathfrak{N} }$, ${ 0 \leq \hat{r} < m }$ such that ${ \mathcal{P} (n') }$ is true.

Now, if ${ r+1=m }$, then ${ n' = mq+m }$.

${ n' = m \hat{q} +0 }$.

${ n' = m \hat{q} +\hat{r} }$, ${ \hat{r} =0 }$.

Hence, there exist ${ \hat{q},\hat{r} \in \mathfrak{N} }$, ${ 0 \leq \hat{r} < m }$ such that ${ \mathcal{P} (n') }$ is true.

By the principle of mathematical induction, ${ \mathcal{P} (n) }$ is true for all ${ n\: \mathfrak{N} }$. $\Box$