Help with Proof: GCD(a,bk) = GCD(a,k)

  • Thread starter Hells_Kitchen
  • Start date
  • Tags
    Proof
In summary, the conversation discusses the relationship between gcd(a,b) and gcd(a,bk) when gcd(a,b) equals 1. The participants suggest that both gcd(a,bk) and gcd(a,k) divide k, but are unable to make further progress in proving it. They propose expressing a and k as products of primes and consider whether k*b adds any additional factors of a to the gcd.
  • #1
Hells_Kitchen
62
0
Hi there can someone help me on this one:
If gcd(a,b)=1 then gcd(a,bk) = gcd(a,k)

I have arrived at the conclusion that gcd(a,bk) gcd(a,k) both divide k but from here I do not get anywhere.

I would like some hints on this please.
 
Physics news on Phys.org
  • #2
Hi, I think it is sufficient to prove that gcd(a,bk) and gcd(a,b) divide each other.
 
  • #3
Hells_Kitchen said:
Hi there can someone help me on this one:
If gcd(a,b)=1 then gcd(a,bk) = gcd(a,k)

I have arrived at the conclusion that gcd(a,bk) gcd(a,k) both divide k but from here I do not get anywhere.

I would like some hints on this please.
could be that they both equal 1, for instance if k = b but think of expressing both a and k in the form of a product of primes. Since the gcd(a,k) is the product of the prime factors that are common to a and k or 1 if there are no common factors other than 1, and gcd(a,b), which is the product of the prime factors that are common to b and a, is 1, does k*b add any other factors of a?
 
Last edited:

FAQ: Help with Proof: GCD(a,bk) = GCD(a,k)

What is GCD(a,bk)?

GCD(a,bk) stands for the greatest common divisor between a and bk, where b and k are both integers.

What does GCD(a,k) mean?

GCD(a,k) represents the greatest common divisor between a and k, where a and k are both integers.

How is GCD(a,bk) related to GCD(a,k)?

GCD(a,bk) and GCD(a,k) are related because the GCD of two numbers will always be a factor of both numbers. So, the GCD(a,k) will also be a factor of GCD(a,bk). In simpler terms, GCD(a,k) is a subset of GCD(a,bk).

Why is it important to understand the proof of GCD(a,bk) = GCD(a,k)?

Understanding the proof of GCD(a,bk) = GCD(a,k) can help in solving various mathematical problems and in understanding the concept of greatest common divisors better. It is also a fundamental concept in number theory and is used in various mathematical applications.

Can you explain the proof of GCD(a,bk) = GCD(a,k) in simple terms?

Sure! The proof involves using the basic definition of greatest common divisor and the properties of divisibility. We can break down GCD(a,bk) into GCD(a,k) * GCD(a,b). Since GCD(a,k) is a factor of both a and k, it will also be a factor of GCD(a,k) * GCD(a,b). This shows that GCD(a,k) is a common divisor of a and bk. Since it is the greatest common divisor, it is also the largest common divisor. Therefore, GCD(a,k) = GCD(a,bk).

Similar threads

I Understanding the Results of gcd(x,n)
Replies
8
Views
1K
MHB Properties of gcd's and relatively prime integers
Replies
2
Views
2K
Can anyone please review/verify my proofs for gcd problem?
Replies
4
Views
1K
Can anyone please review/verify/check this number theory proof?
Replies
12
Views
1K
MHB Does Z[root(-3)] Qualify as a GCD Domain?
Replies
1
Views
2K
MHB Ideals and GCDs in k[x] .... .... Cox Et al: "Ideals, Varieties and Algorithms"
Replies
3
Views
1K
Proving an integer is composite
Replies
13
Views
997
Proving LCM Formula and GCD for Non-Integers
2
Replies
59
Views
13K
MHB How Do GCDs Coincide in Principal Ideals According to Rotman's Proposition 3.41?
Replies
1
Views
1K
MHB GCDs of Polynomials: Reading Rotman's Corollary 3.58
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top