11.4k views
4 votes
If gcd(a,b)=1 then prove that gcd(ac,b)=gcd(c,b)

User Pykiss
by
6.1k points

2 Answers

0 votes

Final answer:

To prove that gcd(ac,b) = gcd(c,b) when gcd(a,b) = 1, we need to show that both sides of the equation have the same set of common divisors.

Step-by-step explanation:

To prove that gcd(ac,b) = gcd(c,b) when gcd(a,b) = 1, we need to show that both sides of the equation have the same set of common divisors.

Let d be a common divisor of ac and b. Since d divides ac, it must also divide a. And since d divides b, gcd(a,b) must also divide d. But we know that gcd(a,b) = 1, so the only common divisor of a and b is 1. Therefore, d must be 1.

By the same reasoning, any common divisor of c and b must also be a common divisor of ac and b. Therefore, gcd(ac,b) must equal gcd(c,b).

User Eslam Soliman
by
6.9k points
3 votes
HINT: (a,b) = 1 means that there is some x and y such that ax + by = 1

perhaps start by writing d=gcd(ac,b) and e=gcd(b,c) and then show that d|e and e|d


User Casey Fleser
by
6.6k points