A simple proof?

Given:a=b×q+r,0r<ba=b\times q+r,0\leq r < b.Yes,that is the division equation.Try to prove that,GCD(a,b)=GCD(b,r)GCD(a,b)=GCD(b,r).Try not to use any theorem for solving this.Just use simple Algebra.This is from my class 10th10^{th} textbook,it was just written as a statement and no proof was given.I came up with one which I will post afterwards.

Note by Adarsh Kumar
4 years, 4 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}

Comments

Sort by:

Top Newest

To prove :- If a=bq+r a=bq+r , then (a,b)=(b,r) (a,b)=(b,r) , where (x,y) (x,y) denotes GCD of x and y. Proof:- Let (a,b)=d (a,b)=d and (b,r)=e(b,r)=e . Then, (a,b) =dda d \Rightarrow d|a and dbda d|b \Rightarrow d|a and dqbd(aqb)dr d|qb \Rightarrow d|(a-qb) \Rightarrow d|r . Hence, dr d|r and dbd(b,r) d|b \Rightarrow \boxed{d|(b,r)} . Similarly, (b,r) = eeb e \Rightarrow e|b and erebq e|r \Rightarrow e|bq and ere(bqr)ea e|r \Rightarrow e|(bq-r) \Rightarrow e|a . Hence, ea e|a and ebe(a,b) e|b \Rightarrow \boxed{e|(a,b)} . We see from the boxed expressions that (a,b)(b,r) (a,b)|(b,r) and (b,r)(a,b)(a,b)=(b,r) (b,r)|(a,b) \Rightarrow (a,b) = (b,r) . Q.E.D.

Karthik Venkata - 4 years, 4 months ago

Log in to reply

Very nice proof!But how did you come up with it so fast?Have you seen similar problems before?

Adarsh Kumar - 4 years, 4 months ago

Log in to reply

Yeah, I am pretty familiar with these kind of problems ! I came across problems involving proofs of gcd while doing number theory...

Karthik Venkata - 4 years, 4 months ago

Log in to reply

@Karthik Venkata So,is this your own?Do u have any NT books?

Adarsh Kumar - 4 years, 4 months ago

Log in to reply

@Adarsh Kumar Not my own bro, I just remember seeing this proof in some book ! Btw this is really important one, it is the basis of the Euclids Algorithm ! For good books, check out David A. Santos books, they are available in pdf format freely, and they are really good books to follow 🎓 📱 !

Karthik Venkata - 4 years, 4 months ago

Log in to reply

@Karthik Venkata Oh!Thanx for the recommendations!Thanx a lot!!Grateful!

Adarsh Kumar - 4 years, 4 months ago

Log in to reply

@Karthik Venkata Yes,yes this is really an important one!It is the basis of Euclid's Algorithm,that is how I came across this.It must be in your book also.Check it!

Adarsh Kumar - 4 years, 4 months ago

Log in to reply

I completed the proof in the same way - I personally remember the proof from "Elementary Number Theory " by Jones - It's a great book :)

Curtis Clement - 4 years, 4 months ago

Log in to reply

Thanks a lot for your suggestion sir 👍 ! The book is really awesome for beginners 💎 !

Karthik Venkata - 4 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...