I am trying to prove gcd$(8,20) = 4$

Question

I am trying to prove $\gcd(8,20) = 4$.

I am not quite sure how to go about it, but I think I need to prove that $\gcd(8,20)$ is not equal to $1$. I have also set up $S = \{k \in \mathbb{N} : k = 8x + 10y \text{ for some } x, y \in \mathbb{Z}\}$. I am trying to somehow show that $4 \in S$.

Any suggestions on how I can prove my approaches? This was a personal challenge exercise, so I am just trying to further my learning. I did take a look at other relevant posts on here, but they are too complex or advanced in comparison to where I am at. I just learnt how to do basic proofs with axioms and proofs for natural numbers. This exercise is given near the end of practice exercises after introduction on the Well Ordering Principle and [GCD].

Thanks for any help or solutions posted!

Answer 1

If $d$ divides both $a$ and $b$, then $d=\gcd(a.b)$ iff $\gcd ({a\over d}, {b\over d})=1.$ Therefore, you only need to find integers $x$ and $y$ so that $2x+5y=1.$

Answer 2

Since working with specific numbers, you may prove by division into cases, showing every number greater than 4 will not divide both, or use an algorithm that has been proven to give correct results, such as the Euclidean algorithm: https://en.wikipedia.org/wiki/Euclidean_algorithm.

Answer 3

Let us first state division Algorithm: Let a, b are two integers > 0. Then there is unique integer q and r such that ${b=aq+r}$ where ${0 \leq < r <a}$ , so ${20 = 8 \cdot 2 + 4}$

• Theorem: Let a ,b are two integers > 0, and suppose ${b=aq+r}$ for some integers q and r. then GCD(b, a)= GCD(a,r) -> GCD(20,8)=GCD(8,4), r divides a, hence GCD=4