GCD question

  • Thread starter Avichal
  • Start date
  • #1
292
0

Main Question or Discussion Point

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:

Answers and Replies

  • #2
841
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 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:
  • #3
292
0
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?
 
  • #4
841
0
Not a homework question at all. Anyways, what is a?
a is a number coprime to y such as 1 mod y
 
  • #5
292
0
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?
 
  • #6
841
0
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.
 
  • #7
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.
 

Related Threads for: GCD question

  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
3
Replies
59
Views
11K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
15
Views
8K
Top