# Show that gcd(a,b) is the smallest positive element in the set {ma+nb}

• docnet
In summary, the conversation discusses the set of natural numbers being an abelian group and the proof that ##\gcd(a,b)## is the smallest positive element in the set ##\{ma+nb|m,n\in\mathbb{Z}\}##. It explains that if ##a## and ##b## are relatively prime, then ##1## is the smallest positive element, and if they are not relatively prime, then ##\gcd(a,b)## is the smallest positive element. The conversation also mentions that the set ##\mathbb{Z}## is closed under multiplication and addition. It provides a hint for finding the correct solution and clarifies that the integers ##m, n## in line (1) are different
docnet
Gold Member
Homework Statement
let ##a,b\in\mathbb{N}##. Show that ##gcd(a,b)## is the smallest positive element in the set ##\{ma+nb|m,n\in\mathbb{Z}\}##.
Relevant Equations
(1) If ##a## and ##b## are relatively prime, then tere are integers ##m## and ##n## such that ##ma+nb=1##

(2) If ##a>b## then ##gcd(a-b,b)=gcd(a,b)##
##m##, ##n##, ##a##, and ##b## are in ##\mathbb{Z}##. The set of natural numbers is an abelian group, so ##\{ma+nb|m,n\in\mathbb{Z}\}## is a subset of ##\mathbb{Z}##.

##a ## and ##b## are either relatively prime or not relatively prime.

If ##a ## and ##b## are relatively prime, then there are integers ##m## and ##n## such that ##ma+nb=1##. ##1## is the smallest positive element in ##\mathbb{Z}##. So, ##1## is the positive smallest positive element in ##\{ma+nb|m,n\in\mathbb{Z}\}##.

If ##a ## and ##b## are not relatively prime, then there is an integer ##c## that commonly divides ##a## and ##b##. So ##a=\tilde{a}c## and ##b=\tilde{b}c##, where ##\tilde{a}## and ##\tilde{b}## are relatively prime integers.
\begin{align}ma+nb=&m\tilde{a}c+n\tilde{b}c\\
=&c(m\tilde{a}+n\tilde{b})\end{align}
##\tilde{a}## and ##\tilde{b}## are relatively prime, so there exist integers ##m## and ##n## such that ##m\tilde{a}+n\tilde{b}=1##, And because they are relatively prime, ##gcd(\tilde{a},\tilde{b})=1##,
\begin{align}=& c\cdot gcd(\tilde{a},\tilde{b})=gcd(a,b)=c\end{align}
##1## is the smallest positive element in ##\{m\tilde{a}+n\tilde{b}|m,n\in\mathbb{Z}\}## so
##c\cdot 1 =gcd(a,b)## is the smallest positive element in ##c\cdot \{m\tilde{a}+n\tilde{b}|m,n\in\mathbb{Z}\}=\{ma+nb|m,n\in\mathbb{Z}\}##.

docnet said:
Homework Statement:: let ##a,b\in\mathbb{N}##. Show that ##gcd(a,b)## is the smallest positive element in the set ##\{ma+nb|m,n\in\mathbb{Z}\}##.
Relevant Equations:: (1) If ##a## and ##b## are relatively prime, then tere are integers ##m## and ##n## such that ##ma+nb=1##

(2) If ##a>b## then ##gcd(a-b,b)=gcd(a,b)##

The set of natural numbers is an abelian group
docnet said:
If a and b are not relatively prime, then there is an integer c that commonly divides a and b.
Later the proof says ##c = \gcd(a, b)##.

What are ##m, n## in line (1)?
docnet said:
so there exist integers m and n such that ma~+nb~=1,
are these the same ##m, n## as before?Hint: Let ##ma + nb## be an arbitrary positive element in ##\lbrace xa + yb \vert x, y \in \mathbb{Z} \rbrace## and define ##d = \gcd(a, b)##. Then ##d \vert ma + nb##. (why?).

docnet
fishturtle1 said:
Oh no. The correct statement was "The set ##\mathbb{Z}## is closed under multiplication and addition, so the element ##ma+nb## for any ##a,b,n,m\in\mathbb{Z}## is also in ##\mathbb{Z}##.

fishturtle1 said:
Later the proof says ##c = \gcd(a, b)##.
I am confused. Is this not true when ##a## and ##b## are not co-prime?
fishturtle1 said:
are these the same ##m, n## as before?
No. They are different integers than before.
fishturtle1 said:
Hint: Let ##ma + nb## be an arbitrary positive element in ##\lbrace xa + yb \vert x, y \in \mathbb{Z} \rbrace## and define ##d = \gcd(a, b)##. Then ##d \vert ma + nb##. (why?).
Okay, I will try to come up with the correct solution using this hint. Thank you.

## 1. What is gcd(a,b) and how is it related to the set {ma+nb}?

The greatest common divisor (gcd) of two integers, a and b, is the largest positive integer that divides both a and b without leaving a remainder. The set {ma+nb} represents all possible integer combinations of a and b, where m and n are also integers.

## 2. How does the statement "gcd(a,b) is the smallest positive element in the set {ma+nb}" show that gcd(a,b) is the smallest common factor of a and b?

Since the set {ma+nb} contains all possible integer combinations of a and b, the smallest positive element in this set must also be the smallest positive integer that divides both a and b without leaving a remainder. This is exactly what gcd(a,b) represents, making it the smallest common factor of a and b.

## 3. Can you provide an example to illustrate this statement?

Let a = 12 and b = 18. The gcd(12,18) = 6, as 6 is the largest integer that divides both 12 and 18 without leaving a remainder. Now, the set {ma+nb} would contain all possible integer combinations of 12 and 18, such as 12+18=30, 2(12)+3(18)=90, etc. The smallest positive element in this set is 6, which is exactly the value of gcd(12,18).

## 4. How does the concept of Euclidean algorithm relate to this statement?

The Euclidean algorithm is a method for finding the gcd of two integers. It involves repeatedly dividing the larger number by the smaller number until the remainder is 0. The last non-zero remainder is the gcd of the two numbers. This algorithm essentially shows that the gcd is the smallest positive element in the set {ma+nb}, as it is the last non-zero remainder obtained through the division process.

## 5. Is this statement always true for all pairs of integers a and b?

Yes, this statement is always true for all pairs of integers a and b. This is because the concept of gcd is based on the fundamental principle that the greatest common divisor of two numbers is the largest positive integer that divides both numbers without leaving a remainder. Therefore, the smallest positive element in the set {ma+nb} will always be the gcd of a and b.

• Precalculus Mathematics Homework Help
Replies
3
Views
959
• Calculus
Replies
3
Views
409
• Precalculus Mathematics Homework Help
Replies
1
Views
843
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
943
• Precalculus Mathematics Homework Help
Replies
0
Views
649
• Precalculus Mathematics Homework Help
Replies
5
Views
913
• Precalculus Mathematics Homework Help
Replies
8
Views
1K