Mathematical proof

[pinion9]

This is for a class, so please don't do all the work for me. I just need a good starting point, and was also wondering if/how this could be done by induction. Essentially the problem pertains to Euclid's algoritm. I need to prove that gcd(m,n) = gcd(m, m mod n)

Again, not highly technical, but it has been a while since I had to prove anything. Please give me a good starting point.

Thanks.

 

[icelazer]

One way you might start:

let y = (m,n) = (m, m mod n) => m < n => y | m and y | n and y maximum that does so
assume y = (m,n) != (m, m mod n) =>
y !| m or y!| m mod n or y not maximum that does so
prove y | m and y | m mod n and y is the maximum that does so since m <= m mod n

 

[arcas]

I think a proof by contradiction might be simpler. That is, given m and n, assume that gcd(m, m mod n) < gcd(m, n) then show the contradiction. Similarly, assume that gcd(m, m mod n) > gcd(m, n) and do the same.

 

[Mday]

Originally posted by: arcas
I think a proof by contradiction might be simpler. That is, given m and n, assume that gcd(m, m mod n) < gcd(m, n) then show the contradiction. Similarly, assume that gcd(m, m mod n) > gcd(m, n) and do the same.

yeah, but if he has to do it by induction, the fact that a proof by contradiction is simpler to state doesnt help.

 

[arcas]

Doh. I didn't see the 'induction' part. Apologies.

 

[intangir]

If x divides m and x divides n, then x divides the difference of m and n.

 

[Kyteland]

Originally posted by: pinion9
This is for a class, so please don't do all the work for me. I just need a good starting point, and was also wondering if/how this could be done by induction. Essentially the problem pertains to Euclid's algoritm. I need to prove that gcd(m,n) = gcd(m, m mod n)

Again, not highly technical, but it has been a while since I had to prove anything. Please give me a good starting point.

Thanks.

Are you sure that you stated that right? Shouldn't it be gcd(m,n) = gcd(n, m mod n) where m>n?

Just a simple contradiction:
gcd(8,3) = 1
gcd(8,8%3) = gcd(8,2) = 2
2 != 1

whereas:
gcd(8,3) = 1
gcd(3,8%3) = gcd(3,2) = 1
1 = 1

Using the correct equation should count as a good starting point. 😉

 

[pinion9]

You are correct. Sorry about the typo. gcd(m,n) = gcd(n, m mod n) where m>n is correct.