Can I Use Factor Sets to Solve GCD Problems?

In summary, the author attempts to prove that gcd(ac,b) is equal to gcd(c,b) by using factor sets. By showing that the two sets have the same intersection with B, it can be concluded that they have the same greatest common divisor. This is a reliable method for proving the equality of gcd.
  • #1
PsychonautQQ
784
10

Homework Statement


if 1 = gcd(a,b), show that gcd(ac,b) = gcd(c,b)

Homework Equations


None

The Attempt at a Solution


My attempt at a solution:

Let d = gcd(ac,b),
Let g = gcd(c,b),
I want to show that g|d and that d|g. I then went on to make a bunch of circular writing and get nowhere... I set up things like:

1 = ax + by
d = acw + bz --> 1 = (ac/d)w + (b/d)z
g = cn + bm --> 1 = (c/d)n + (b/d)m

Is my approach here a solid method? I can't think of any other way to show that gcd(ac,b) = gcd(c,b) besides assigning each of them a value and showing that they divide each other.
 
Physics news on Phys.org
  • #2
That seems to be a reliable method.
I prefer to work with factor sets:
Let A be the unique prime factor set of a, B be the unique prime factor set of b, and C be the unique prime factor set of c.
##A\cap B =\{1\}##
##AC=A \cup C##
##AC\cap B= (A \cup C) \cap B = (A\cap B) \cup (C \cap B) = 1 \cup (C \cap B) ##
A similar argument should apply with repeated prime factors and combinations to find the gcd.
 

What is the GCD Number Theory Problem?

The GCD (Greatest Common Divisor) Number Theory Problem is a mathematical problem that involves finding the largest positive integer that divides two or more given numbers without leaving a remainder. It is also known as the GCD or HCF (Highest Common Factor) problem.

How do you find the GCD of two numbers?

The most common method for finding the GCD of two numbers is by using the Euclidean algorithm. This involves dividing the larger number by the smaller number and finding the remainder. The remainder then becomes the new divisor, and the previous divisor becomes the new dividend. This process is repeated until the remainder becomes zero, and the last non-zero remainder is the GCD of the two numbers.

What is the importance of the GCD Number Theory Problem?

The GCD Number Theory Problem has practical applications in various fields, such as computer science, engineering, and cryptography. It is used in simplifying fractions, finding common denominators, and determining the highest possible number of equal-sized pieces that a given quantity can be divided into.

Can the GCD of two numbers be negative?

No, the GCD of two numbers is always a positive integer. This is because the GCD represents the largest positive number that can divide both numbers without leaving a remainder.

What is the relationship between the GCD and LCM (Least Common Multiple)?

The LCM of two numbers is the smallest positive integer that is divisible by both numbers without leaving a remainder. The relationship between the GCD and LCM is that the product of these two numbers is equal to the product of their GCD and LCM.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
798
  • Calculus and Beyond Homework Help
Replies
1
Views
867
  • Calculus and Beyond Homework Help
Replies
1
Views
929
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
935
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
839
Back
Top