# GCD Discrete Math: Proving GCD(a,b)=1

• MHB
• ssome help
In summary, GCD, or greatest common divisor, is a mathematical concept used in discrete math to analyze and prove properties of integers. This includes determining divisibility and primality, simplifying fractions, and finding common denominators. Proving GCD(a,b)=1 means showing that the greatest common divisor of two given integers is equal to 1, indicating that they are relatively prime. There are multiple methods to prove this, such as the Euclidean algorithm and prime factorization. Proving GCD(a,b)=1 is important in discrete math as it helps us understand integer relationships, solve problems, and is used in various algorithms and cryptography techniques.
ssome help
Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+

a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2
Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given
b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b, a+2b) = 3

Any assistance would be great.

ssome help said:
Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+

a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2
Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given
b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b, a+2b) = 3

Any assistance would be great.

Welcome to MHB, ssome help!

Nice problem. ;)

Did you try anything?
When you show something you tried, or if you explain where you are stuck, we can help you to solve and understand this.

The key fact to use here is that if d | x and d | y, then d divides any linear combination of x and y, i.e., d | (mx + ny) for any integer m and n.

Setting...

$\displaystyle x = a + b$

$\displaystyle y = a - b$ (1)

... solving (1) we obtain...

$\displaystyle a = \frac{x + y}{2}$

$\displaystyle b = \frac{x - y}{2}$ (2)

Now if x and y have a common factor different than 2, then x + y and x - y have the the same common factor and the same would be for a and b and that is a contradiction...

Kind regards

$\chi$ $\sigma$

a) To prove that GCD(a+b, a-b) = 1 or GCD(a+b, a-b) = 2, we first let D = GCD(a+b, a-b). This means that D divides both a+b and a-b. Therefore, D also divides their sum and difference, which are 2a and 2b respectively.

Using the given property, GCD(na,nb) = n * GCD(a,b), we can write D | 2a and D | 2b as D | GCD(2a,2b). Since GCD(a,b) = 1, we know that GCD(2a,2b) = 2 * 1 = 2. Therefore, D must divide 2.

This means that D = 1 or D = 2, since these are the only positive divisors of 2. Therefore, we can conclude that GCD(a+b, a-b) = 1 or GCD(a+b, a-b) = 2.

b) Similarly, we let D = GCD(2a+b, a+2b). This means that D divides both 2a+b and a+2b. Therefore, D also divides their sum and difference, which are 3a and 3b respectively.

Using the given property, GCD(na,nb) = n * GCD(a,b), we can write D | 3a and D | 3b as D | GCD(3a,3b). Since GCD(a,b) = 1, we know that GCD(3a,3b) = 3 * 1 = 3. Therefore, D must divide 3.

This means that D = 1 or D = 3, since these are the only positive divisors of 3. Therefore, we can conclude that GCD(2a+b, a+2b) = 1 or GCD(2a+b, a+2b) = 3.

## 1. What is GCD in discrete math?

GCD, or greatest common divisor, is a mathematical concept that refers to the largest positive integer that divides two or more given integers without leaving a remainder.

## 2. How is GCD used in discrete math?

GCD is used in discrete math to analyze and prove properties of integers, such as divisibility and primality. It is also used to simplify fractions and find common denominators.

## 3. What does it mean to prove GCD(a,b)=1?

Proving GCD(a,b)=1 means showing that the greatest common divisor of two given integers, a and b, is equal to 1. This indicates that the two numbers are relatively prime, meaning they have no common factors other than 1.

## 4. How do you prove GCD(a,b)=1?

There are several methods to prove GCD(a,b)=1, including the Euclidean algorithm, prime factorization, and using the properties of GCD. These methods involve manipulating the given integers to show that their GCD is equal to 1.

## 5. Why is proving GCD(a,b)=1 important in discrete math?

Proving GCD(a,b)=1 is important in discrete math because it allows us to understand and analyze the relationships between integers. It also helps us solve problems involving factors, divisibility, and prime numbers. Additionally, it plays a key role in various algorithms and cryptography techniques.

Replies
4
Views
1K
Replies
2
Views
1K
Replies
5
Views
1K
Replies
3
Views
973
Replies
5
Views
1K
Replies
1
Views
856
Replies
2
Views
1K
Replies
14
Views
1K
Replies
4
Views
1K
Replies
1
Views
1K