So the statement you made is true, but does not prove what you want it to prove.

In summary, the conversation discusses the relationship between the integers s, t, a, and b and their greatest common divisor (gcd). It is concluded that if as+bt=6, then gcd(a,b)=6, but this does not necessarily mean that a and b are not relatively prime. The definition of two integers being relatively prime is also mentioned. However, using this argument to prove that a and b are not relatively prime does not work in all cases.
  • #1
roam
1,271
12
If there are integers s,t with as+bt=6, this implies that gcd(a,b)=6, right?

And if gcd(a,b)=6, does this necessarily mean that a and b are not relatively prime since their gcd is not 1? (I have read that two integers a and b are relatively prime if gcd(a,b)=1).
 
Mathematics news on Phys.org
  • #2
roam said:
If there are integers s,t with as+bt=6, this implies that gcd(a,b)=6, right?
No. It simply implies that gcd(a,b) divides 6. For instance take a=4, b =6, then gcd(a,b) = 2 but:
[tex]0a+1b = 6[/tex]

And if gcd(a,b)=6, does this necessarily mean that a and b are not relatively prime since their gcd is not 1? (I have read that two integers a and b are relatively prime if gcd(a,b)=1).
Yes, 6 divides them both so they have a common factor besides 1 (2,3,6 are all common factors). That gcd(a,b)=1 is actually a pretty common definition of integers being relatively prime.

By the way if you wanted to use this argument to prove that a and b are not relatively prime, then unfortunately that doesn't work. Consider for instance:
a = 2, b= 3
which are definitely relatively prime as they are both prime, but:
[tex]6b+(-6)a = 6[/tex]
 

FAQ: So the statement you made is true, but does not prove what you want it to prove.

What is the Greatest Common Divisor (GCD)?

The Greatest Common Divisor (GCD) is the largest positive integer that divides evenly into two or more numbers. It is also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

How is the GCD calculated?

The GCD can be calculated using various methods, including prime factorization, Euclid's algorithm, and the division method. The most efficient method is usually the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number until the remainder is 0. The last non-zero remainder is the GCD.

What is the significance of the GCD?

The GCD is an important concept in mathematics, particularly in number theory and algebra. It is used in a variety of applications, such as simplifying fractions, finding equivalent fractions, and solving equations with multiple variables. It is also used in cryptography, where it is used to calculate the public and private keys for encryption and decryption.

Can the GCD be negative?

No, the GCD is always a positive integer. This is because it represents the largest positive number that can divide evenly into two or more numbers. If the GCD were negative, it would not divide evenly into the numbers, making it not the greatest common divisor.

What is the relationship between GCD and LCM?

The GCD and LCM (Least Common Multiple) are two closely related concepts. The LCM is the smallest positive integer that is a multiple of two or more numbers, while the GCD is the largest positive integer that divides evenly into two or more numbers. The relationship between the two is that the product of the GCD and LCM of two numbers is equal to the product of the two numbers.

Back
Top