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<m } or { r+1=m }

If { r+1<m }, 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s