This is the second note on simple NT proofs.This proof is about the Euclidean Algorithm which helps us to calculate the Greatest Common Divisor of humongous numbers.This proof is super\
simple but I bet you will like it.Let us take two positive integers′a′ and ′b′and calculate their gcd.
The Euclidean algorithm states that:gcd(a,b)=gcd(a−b,b) if a>b.
Let us say that the gcd(a,b)=x⟹ a=x∗p and b=x∗q.
Statement 1:gcd(p,q)=1i.e they
are co-prime.
Proof of statement 1:We will prove this by contradiction.Let us say that gcd(p,q)=r ⟹ p=r∗y and q=r∗z⟹ a=x∗r∗y and b=x∗r∗z⟹ gcd(a,b)=x∗r,which is a contradiction.Thus,′p′ and′q′ are co-prime.
Statement 2:gcd(a.b)=gcd(a−b,b)We know that a=x∗p and b=x∗q,substituting in the equation gives x=gcd(x(p−q),x(q)).This can be easily done if we prove that gcd((p−q),(q))=1.We do this by contradiction.Let us say that gcd((p−q),q)=t⟹ (p−q)=t∗m and q=t∗n ⟹ p−(t∗n)=t∗m ⟹ p=t∗(m+n) and from above we have:q=t∗n.But,this can′t happen as gcd(p,q)=1.Thus,gcd((p−q)(q)=1PROVED!!
P.S:This isn′t a copied proof.
</code>...<code>."> Easy Math Editor
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
Sort by:
Top Newest@Satvik Golechha @Krishna Ar please read this!!
Log in to reply