A very simple,yet elegant NT proofIIA\ very\ simple,yet\ elegant\ NT\ proof---II

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 integersa and band calculate their gcd.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(ab,b) if a>b.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=xp and b=xq.Let\ us\ say\ that\ the\ gcd(a,b)=x\\ \Longrightarrow\ a=x*p\ and\ b=x*q. Statement 1:Statement\ 1:gcd(p,q)=1gcd(p,q)=1i.e they are co-prime. Proof of statement 1:Proof\ of\ statement\ 1:\\We will prove this by contradiction.Let us say that gcd(p,q)=r  p=ry and q=rzgcd(p,q)=r\ \Longrightarrow\ p=r*y\ and\ q=r*z a=xry and b=xrz\Longrightarrow\ a=x*r*y\ and\ b=x*r*z gcd(a,b)=xr,\Longrightarrow\ gcd(a,b)=x*r,which is a contradiction.Thus,p'p' andq'q' are co-prime. Statement 2:gcd(a.b)=gcd(ab,b)Statement\ 2:gcd(a.b)=gcd(a-b,b)We know that a=xp and b=xq,substituting in the equation gives x=gcd(x(pq),x(q)).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((pq),(q))=1.This\ can\ be\ easily\ done\ if\ we\ prove\ that \ gcd((p-q),(q))=1.We do this by contradiction.Let us say that gcd((pq),q)=t (pq)=tm and q=tn  p(tn)=tm  p=t(m+n) and from above we have:q=tn.But,this cant happen as gcd(p,q)=1.We\ do\ this\ by\ contradiction.\\Let\ us\ say\ that\ gcd((p-q),q)=t\\\Longrightarrow\ (p-q)=t*m\ and\ q=t*n\\\ \Longrightarrow\ p-(t*n)=t*m\ \Longrightarrow\ p=t*(m+n)\ and\ from\ above\ we\ have\\:q=t*n.But,this\ can't\ happen\ as\ gcd(p,q)=1.Thus,gcd((pq)(q)=1Thus,gcd((p-q)(q)=1PROVED!!PROVED!! P.S:This isnt a copied proof.P.S:This\ isn't\ a\ copied\ proof.

Note by Adarsh Kumar
4 years, 10 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

@Satvik Golechha @Krishna Ar please read this!!

Adarsh Kumar - 4 years, 10 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...