Divisibility Proof: Let a, b, c be integers. Suppose that a | b and c | b...

[BigNate]

Hello,

I am having issues proving the following proof. Can someone please help me? I need to use Euclid's Lemma, which states "Suppose gcd(a, b) = 1 and that a divides bc. Then a divides c.

I need to prove the following:
Let a, b, c be integers. Suppose that a | b and c | b. Suppose also that gcd(a, c) = 1. Prove that ac | b.

Here is what I have so far:
Suppose a | b
Definition of divide tells us a | kb for all integers k
Suppose c | b
Given gcd(a, c) = 1 and a | b and a | c, we know a and c are relatively prime
***Here is where I get stuck. I have a hint that I need to use Euclid's Lemma stated above. Can someone please help me finish off this proof?

Thanks in advance for your time!

 

[ksdhart2]

Hello,

I am having issues proving the following proof. Can someone please help me? I need to use Euclid's Lemma, which states "Suppose gcd(a, b) = 1 and that a divides bc. Then a divides c.

I need to prove the following:
Let a, b, c be integers. Suppose that a | b and c | b. Suppose also that gcd(a, c) = 1. Prove that ac | b.

Here is what I have so far:
Suppose a | b
Definition of divide tells us a | kb for all integers k
Suppose c | b
Given gcd(a, c) = 1 and a | b and a | c, we know a and c are relatively prime
***Here is where I get stuck. I have a hint that I need to use Euclid's Lemma stated above. Can someone please help me finish off this proof?

Thanks in advance for your time!

I have a method of tackling the proof, but I'm not 100% sure if it explicitly uses Euclid's lemma. My method involves collecting as much information I can from the givens and then just trying simple test cases to see what more information I can suss out.

We're given that a | b and c | b. That means that b = ka, for some integer k; and b = lc, for some integer l. Equivalently, it tells us that a is a factor of b, as is c. Now, at this point, let's just try some test cases. Let a = 2 and c = 3. What potential values can b take on that make the givens true (ignore for a moment the third given that a and c are coprime)? What if a = 2 and c = 4? a = 3 and c = 5? a = 5 and c = 10? What did you notice about b? Note that in some cases a and c are coprime and in others, they're not. How does that change the nature of b? How does that help you out with your main proof?