Waste less time on Facebook — follow Brilliant.
×

A simple proof?

Given:\[a=b\times q+r,0\leq r < b\].Yes,that is the division equation.Try to prove that,\[GCD(a,b)=GCD(b,r)\].Try not to use any theorem for solving this.Just use simple Algebra.This is from my class \(10^{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
2 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

To prove :- If \( a=bq+r \), then \( (a,b)=(b,r) \), where \( (x,y) \) denotes GCD of x and y. Proof:- Let \( (a,b)=d \) and \((b,r)=e \). Then, (a,b) =\( d \Rightarrow d|a \) and \( d|b \Rightarrow d|a \) and \( d|qb \Rightarrow d|(a-qb) \Rightarrow d|r \). Hence, \( d|r\) and \( d|b \Rightarrow \boxed{d|(b,r)} \). Similarly, (b,r) = \( e \Rightarrow e|b \) and \( e|r \Rightarrow e|bq \) and \( e|r \Rightarrow e|(bq-r) \Rightarrow e|a \). Hence, \( e|a \) and \( e|b \Rightarrow \boxed{e|(a,b)} \). We see from the boxed expressions that \( (a,b)|(b,r) \) and \( (b,r)|(a,b) \Rightarrow (a,b) = (b,r) \). Q.E.D. Karthik Venkata · 2 years, 3 months ago

Log in to reply

@Karthik Venkata 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 · 2 years, 3 months ago

Log in to reply

@Curtis Clement Thanks a lot for your suggestion sir 👍 ! The book is really awesome for beginners 💎 ! Karthik Venkata · 2 years, 3 months ago

Log in to reply

@Karthik Venkata Very nice proof!But how did you come up with it so fast?Have you seen similar problems before? Adarsh Kumar · 2 years, 3 months ago

Log in to reply

@Adarsh Kumar Yeah, I am pretty familiar with these kind of problems ! I came across problems involving proofs of gcd while doing number theory... Karthik Venkata · 2 years, 3 months ago

Log in to reply

@Karthik Venkata So,is this your own?Do u have any NT books? Adarsh Kumar · 2 years, 3 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 · 2 years, 3 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 · 2 years, 3 months ago

Log in to reply

@Karthik Venkata Oh!Thanx for the recommendations!Thanx a lot!!Grateful! Adarsh Kumar · 2 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...