I am trying to prove a section of the Euclidean Algorithm for greatest common factors which states:
$\gcd(m, n) = \gcd(n, r) = \gcd(r, n \text{ mod } r)$, where $r =m \text{ mod } n$
Prove that: $n \text{ mod } r < \frac{n}{2}$ (assuming all variables are integers)
My first approach was to use division into cases to solve this proof but later I thought about using the quotient remainder theorem. If someone could guide me through this proof it would be greatly appreciated. Thank you in advance!
First, we must assume that $n \not \mid m$, since $n \pmod{0}$ is undefined. Also, assume that $n,m \geq 0$. Note that $r = m \pmod{n} \in \{ 1, 2, \dots , n-1\}$. To show that $ n \pmod{r} < \frac{n}{2}$, we proceed by cases. Suppose that $r < \frac{n}{2}$, then $n \pmod{r} < \frac{n}{2}$ Suppose that $r > \frac{n}{2}$. By the division algorithm, we have that $n = r + n-r : n - r < r$, Since $r > \frac{n}{2} , n-r = n \pmod{r} < \frac{n}{2}$. If $n$ is even, then $r = \frac{n}{2} \implies n \equiv 0 \pmod{r}$. If $n$ is odd, then $r = \frac{n}{2}$ cannot occur. Let me know if you have questions.
EDIT:
The proof case 3 cases $$ \begin{cases} r < \frac{n}{2} & \text{ Done because any residue of r is less than } \frac{n}{2} \\ r = \frac{n}{2} & \begin{cases} n \text{ is even } & \text{ Done because } n \pmod{r} = 0 \\ n \text{ is odd } & \text{ Done because } \frac{n}{2} \text{ is not an integer so r cannot take that value} \end{cases} \\ r > \frac{n}{2} & \text{ Done because } n = r + n-r : n - r = n\pmod{r} < \frac{n}{2}, \text{ since } r > \frac{n}{2} \end{cases} $$