I was trying to prove that (the slow version of) Euclid's algorithm is correct when I realized that I had to prove that gcd(a,b) = gcd(a-b,b) for a>b. I then I realized that I had to prove that when a=b gcd(a,b)=a.
It seems intuitively obvious that the gcd of a number with itself is just that number itself, since a number obviously divides itself. But I realized that I also needed to prove that there is no bigger number that divides n other than n itself. I thought this should be obvious but actually I could not find a proof of it online. This is my attempt to prove that the gcd of a number is itself (please tell me if there is a shorter proof):
Suppose there is a natural number d that divides the natural number n with d > n. Then we have natural numbers k and s such that:
sd = n since d divides n d = n + k since d is greater than n s(n+k) = n sn + sk = n sn - n + sk = 0 s(n-1) + sk = 0 There are 2 possible cases: 1. n-1 = 0. Then s(n-1) = 0. As s >= 1 and k >= 1, sk >= 1 (I realize that I will have to prove this too at some point...). But we have sk = 0 >= 1, a contradiction. 2. n-1 >= 1. Then s(n-1) >= 1. Then s(n-1) + sk >= 2. But we already have s(n-1) + sk = 0, a contradiction.
My question is:
Is it really necessary to prove such facts and if not, how can I avoid getting bogged down in such details?