Proving Linear Manipulation to Reduce to GCD of Two Numbers

Click For Summary

Discussion Overview

The discussion revolves around proving that a linear manipulation of two numbers can reduce them to their greatest common divisor (gcd). Participants explore the relationship between linear combinations of co-prime numbers and their ability to yield the gcd, with examples provided to illustrate the concept.

Discussion Character

  • Homework-related
  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • One participant proposes that if two numbers m and n can be expressed as m = gx and n = gy, where g is their gcd and x and y are co-prime, then proving that a linear combination of x and y can produce 1 would suffice to demonstrate the relationship to the gcd.
  • Another participant suggests examining multiples of x with respect to y and an additional number a, which is coprime to y.
  • A later reply clarifies that a is defined as a number coprime to y such that a ≡ 1 (mod y).
  • One participant expresses frustration about their progress and seeks guidance on how to prove that a linear combination of two co-prime numbers results in one.
  • Another participant notes a mathematical observation regarding the modular relationship between x and y, suggesting that distinct numbers can be generated under certain conditions.
  • One participant introduces the Euclidean Algorithm as a method for finding the gcd and mentions that the steps can be reversed to express the gcd as a linear combination of the original numbers.

Areas of Agreement / Disagreement

Participants express differing views on whether the original question is a homework problem. There is no consensus on the specific approach to proving the linear combination aspect, and multiple perspectives on the methodology remain present.

Contextual Notes

Some participants reference specific mathematical properties and relationships, but the discussion does not resolve the assumptions or steps necessary to prove the initial claim. The exploration of the Euclidean Algorithm introduces an alternative method without reaching a definitive conclusion on the original question.

Avichal
Messages
294
Reaction score
0
Given two numbers m and n, I need to prove that if a linearly manipulate them I can reduce them to their gcd.
example:- 5 and 3. 3+3-5=1 which is their gcd.

For that I assumed m as gx and n as gy where g is their gcd and x&y are co-prime. So if I am able to prove that linear combination of x&y(any co-prime numbers) can produce 1 then I am done.

Am I making a simple question too complicated?
Anyways thank you
 
Last edited:
Physics news on Phys.org
Avichal said:
Given two numbers m and n, I need to prove that if a linearly manipulate them I can reduce them to their gcd.
example:- 5 and 3. 3+3-5=1 which is their gcd.

For that I assumed m and gx and n as gy where is g is their gcd and x&y are co-prime. So if I am able to prove that linear combination of x&y(any co-prime numbers) can produce 1 then I am done.

Am I making a simple question too complicated?
Anyways thank you
Looks like a homework question. No you stated exactly what you must do. Not too complicated at all. Try looking at multiples of x with respect to y+a.
 
Last edited:
ramsey2879 said:
Looks like a homework question. No you stated exactly what you must do. Not too complicated at all. Try looking at multiples of x with respect to y+a.
Not a homework question at all. Anyways, what is a?
 
Avichal said:
Not a homework question at all. Anyways, what is a?
a is a number coprime to y such as 1 mod y
 
Well I'm going nowhere. I need to prove that linear combination of x&y(two co-prime numbers) gives one for some specific combination, right? How do I proceed with that?
 
Avichal said:
Well I'm going nowhere. I need to prove that linear combination of x&y(two co-prime numbers) gives one for some specific combination, right? How do I proceed with that?
Note that x == (1+y)x mod y. Let 1 <=i,j <y and assume ix-jx = 0 mod y Since y > i,j and y does not divide x then i must equal j. Therefore there must be y-1 distinct numbers N between 0 and y such that N ==kx mod y. and 1 must be one of them.
 
There is a method of finding the GCD of two numbers it is called the Euclidean Algorithm. Once the GCD is found the steps of the algorithmn can be reversed to find the GCD as a linear combination of the two numbers. Try searching for Euclidean Algorithm.
 

Similar threads

Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Clarifications needed for an exercise in Hungerford's abstract algebra
  • · Replies 23 ·
Replies
23
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Localizing single variable quotient polynomial ring at a prime ideal
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Questions about non existence of GCDs vs (coimages, cokernels)
  • · Replies 12 ·
Replies
12
Views
1K
Undergrad Linear combination of two numbers
  • · Replies 2 ·
Replies
2
Views
5K
Undergrad Uniqueness of reduced row echelon form (proof verification)
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Confused about small detail in rank-nullity theorem
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Wronskian: null space equals the span of independent functions
  • · Replies 23 ·
Replies
23
Views
2K
Graduate Prove gcd(m,n)=1 implies gcd(2m+n,2n)=1 (n odd)
  • · Replies 1 ·
Replies
1
Views
5K