0
$\begingroup$

I was trying to understand the proof to the GCD theorem. It seems like I'm missing sommething though. I was reading it in this wikiproof article and the first proof uses the GCD with remainder theorem. I didn't really understand it, so I tried to read the proof

gcd{a,b}∖a∧gcd{a,b}∖b            GCD is a common divisor    
gcd{a,b}∖(a−qb)          Common Divisor Divides Integer Combination 
gcd{a,b}∖r           as r=a−qb  
gcd{a,b}≤gcd{b,r}            Definition of gcd{b,r} as the greatest common divisor of b and r   

The argument works the other way around:

gcd{b,r}∖b∧gcd{b,r}∖r            GCD is a common divisor    
gcd{b,r}∖(qb+r)          Common Divisor Divides Integer Combination 
gcd{b,r}∖a           as a=qb+r  
gcd{b,r}≤gcd{a,b}            Definition of gcd{a,b} as the greatest common divisor of a and b   

Thus  gcd{a,b}=gcd{b,r}

Before we get to how the "argument works the other way around", I didn't understand the last step

gcd{a,b}≤gcd{b,r}

, how do we know the gcd of b,r is greater than that of a,b. Thanks.

$\endgroup$
0
$\begingroup$

First, let's imagine that we have some quantity $q$ such that both of these statements hold: \begin{align} q \backslash r \\ q \backslash b \end{align} That is, $q$ divides $r$, and also $q$ divides $b$. This means that $q$ is a common divisor of $b$ and $r$. Then, because the $\gcd$ means the greatest common divisor, we have: $$q \leq \gcd\left\{b,r\right\}$$


Now the statement you asked about has this statement directly above it: $$\gcd \left\{a,b\right\}\backslash r$$ That says that $\gcd \left\{a,b\right\}$ is a divisor of $r$. But since $\gcd \left\{a,b\right\}$ is also by definition of $\gcd$ a divisor of both $a$ and of $b$, what we have is the situation where $\gcd \left\{a,b\right\}$ is a common divisor of $b$ and $r$. Therefore $$\gcd\left\{a,b\right\} \leq \gcd\left\{b,r\right\}$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Because, if words have a meaning, the g.c.d. of $a$ and $r$ is the greatest common divisor of $a$ and $r$, and precisely, you've established that $\gcd(a,b)$ is a common divisor of $a$ and $r$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.