Proving the GCD Property: A Challenge for Algebra Students

In summary, the problem statement is to prove that for any integers m and n, the greatest common divisor d is equal to am+bn, where a and b are also integers. The use of induction and the Euclidean algorithm are suggested for the proof. However, the individual has attempted to use the iterative algorithm but has not been successful. They are unsure how to incorporate induction into the proof and are seeking assistance.
  • #1
kntsy
82
0
urgent algebra GCD Proof problem

Homework Statement


let d=gcd(m,n). Prove that d=am+bn, where a,b are integers.


Homework Equations


use of induction and euclidean algorithm.


The Attempt at a Solution


i know when d being a generator and d=am+bn where m,n are generators, then d=gcd(m,n).
But i got stuck when proving the converse(which is the problem statement above).

I use the iterative algorithm(i.e. "n=qm+r";gcd(m,n)=gcd(m,r) and so on) but just does not work. And i do not know how to use "induction" in this proof.

Thank you for helping me.
 
Physics news on Phys.org
  • #2


Use the Euclidean algorithm.
 

FAQ: Proving the GCD Property: A Challenge for Algebra Students

1. What is the GCD in algebra?

The GCD, or greatest common divisor, in algebra is the largest number that divides evenly into two or more numbers.

2. What is the purpose of finding the GCD in algebra?

Finding the GCD in algebra is useful for simplifying fractions, factoring polynomials, and solving equations.

3. How do you prove the GCD in algebra?

To prove the GCD in algebra, you can use the Euclidean algorithm, which involves finding the remainder when dividing the larger number by the smaller number and repeating the process until the remainder is 0.

4. Can the GCD be negative in algebra?

Yes, the GCD can be negative in algebra. This typically occurs when working with negative numbers or when using the extended Euclidean algorithm.

5. Is the GCD commutative in algebra?

Yes, the GCD is commutative in algebra, meaning that the order in which you find the GCD of two numbers does not matter. This can be proven using the distributive property of multiplication.

Similar threads

Can anyone please review/verify this proof of greatest common divisor?
Replies
2
Views
1K
Proving an integer is composite
Replies
13
Views
914
Finding GCD with Fibonacci: Base Case
Replies
1
Views
1K
Order of a^m when gcd(m,n) = 1
Replies
2
Views
2K
[Abstract Algebra] GCD and Relatively Prime Proof
Replies
5
Views
2K
Modular Congruence and GCD Proof
Replies
1
Views
1K
How to prove that d|c in gcd(ac,b) = gcd(c,b) if gcd(a,b) = 1?
Replies
1
Views
1K
Number theory GCD relatively prime question
Replies
5
Views
1K
Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers
Replies
4
Views
1K
Let d = gcd(a, b), prove kd = gcd(ka, kb)
Replies
1
Views
8K

Hot Threads

Recent Insights

Back
Top