Divisibility: Proving That a is Divisible by c

AI Thread Summary
To prove that if a divides bc, then a also divides c when a and b are relatively prime, it is essential to understand the implications of the greatest common divisor (gcd). The discussion emphasizes that since gcd(a, b) = 1, if a divides bc, it must follow that a divides c, not b. Participants suggest using examples and the division theorem to clarify the proof structure, highlighting that a mod bc = 0 does not directly imply a mod c = 0. The conversation also touches on the importance of understanding modular arithmetic and the need to manipulate expressions carefully to derive the necessary conclusions. Overall, the consensus is that a direct proof approach may be more effective than proving the contrapositive.
rooski
Messages
60
Reaction score
0

Homework Statement



let a and b be relatively prime positive integers.

if c is a positive integer and a | bc then prove that a | c

The Attempt at a Solution



I started by trying to prove the contra-positive. If a is not divisible by bc then a is not divisible by c.

it follows that a mod bc > 0 in this case.

Now suppose x = bc.

If a mod c is > 0 as well, then a mod c = a mod x.

It follows that a is equivalent to c mod x, or c mod bc.

Is this ample proof?
 
Last edited:
Physics news on Phys.org
For the contrapositive, you are assuming that a and b are relatively prime, with c being a positive integer. Now show that if a does not divide c, then a does not divide bc.

If might be simpler to prove the statement directly rather than trying to prove the contrapositive.
 
Hmm,

what if i were to say a mod bc = 0, and a mod c = 0?

I can then say a mod bc = a mod c... Right?

Should i be using the division theorem to somehow get a conclusion?
 
I don't think you are clear in what you need to prove.
Given: a and b are relatively prime positive integers, and c is a positive integer.
Prove: if a | bc then a|c

You can say a (mod bc) \equiv 0, since that's equivalent to saying a | bc, but you can't just say a (mod c) \equiv 0 (which is equivalent to saying a | c), because you have to show that.
 
Using the division theorem i can say a = bc + 0 (since the remainder is 0 in order for it to be divisible by bc). So i somehow have to manipulate a = bc to get simply a = c?

If -ac = b, and b is 0, then i can say a = c, and hence a is certainly divisible by c, right?
 
Last edited:
rooski said:
Using the division theorem i can say a = bc + 0 (since the remainder is 0 in order for it to be divisible by bc).
No. As I already said, you are given that a | bc (or equivalently, a \equiv 0 (mod bc). This doesn't mean that a = bc.

For example, 5 | 50, but 5 \neq 50.

What you can say is that if a | bc, then bc = ka for some integer k.
rooski said:
So i somehow have to manipulate a = bc to get simply a = c?

If -ac = b, and b is 0, then i can say a = c, and hence a is certainly divisible by c, right?
 
ugh I'm so lost. I want to take ak = bc and somehow work it out so that i find that ak = c, but how can i do that?

should i be focusing more on modulus division in this question, or should i be manipulating with algebra?

what bothers me most about these proofs is that there's no set method for solving them, you're just supposed to somehow come up with a solution out of thin air. :S
 
I don't think you need the modulus stuff in this problem. Focus on what the basic terminology means; e.g., a | bc means that bc = k*a for some integer k, and what it means for two integers to be relatively prime.

It might be helpful to cook up a few examples using numbers. These won't do for a proof, but it might help you get some better understanding of how the proof would need to go.

1. Let a = 5 and b = 9, and let c = 6

Here a and b are relatively prime, and c > =

Does 5 | 54 ? No. Do we need to show that 5 | 6? No, since the condition that a | bc isn't met.
2. Let a = 5 and b = 9, as before, and let c = 8
Does 5 | 72? No. Do we need to show that 5 | 8? No, since the condition that a | bc isn't met.

3. Let a = 5 and b = 9, as before, and let c = 10
Does 5 | 90? Yes. Does 5 | 10? Yes.

rooski said:
what bothers me most about these proofs is that there's no set method for solving them, you're just supposed to somehow come up with a solution out of thin air. :S
Proofs involve a different way of thinking than you are probably used to, so in one respect, they are harder. On the other hand, you know what the answer is, and it's just a matter of getting to it!
 
Off topic, but your user name suggests you are Russian. In Cyrillic, it's русский, which means Russian (masc.).
 
  • #10
Since a | bc then it follows that a | b or a | c. Since gcd(a,b) = 1 then it follows a | b is false.

Thusly we conclude a | c.

That makes perfect sense to me, but is it ample proof?

Is there a theorem i have to cite for this?
 
  • #11
rooski said:
Since a | bc then it follows that a | b or a | c.
No, you can't conclude this. For example, 6 | 3*4, but 6 doesn't divide 3 and 6 doesn't divide 4.
rooski said:
Since gcd(a,b) = 1 then it follows a | b is false.

Thusly we conclude a | c.

That makes perfect sense to me, but is it ample proof?

Is there a theorem i have to cite for this?
 
  • #12
But 3 and 6 are not relatively prime, right?

Let's do an example with a = 5, b = 7 and c = 10. a and b are relatively prime, and a = bc. It follows that a | c because of the constraints given by the question (namely, gcd(5,7) = 1). I think i have a solid answer here! :D
 
  • #13
rooski said:
But 3 and 6 are not relatively prime, right?
Right. That means you need to say that a and b are relatively prime first before you can conclude that a | bc ==> a |b or a|c.
rooski said:
Let's do an example with a = 5, b = 7 and c = 10. a and b are relatively prime, and a = bc. It follows that a | c because of the constraints given by the question (namely, gcd(5,7) = 1). I think i have a solid answer here! :D
 
  • #14
Ah, gotcha.

A similar question to this gives me a set S with a function f : S -> S defined as f(k) = ak mod b. Both a and b are relatively prime, and S = { 0, 1 ... b - 1 }

I have to show that it is one-to-one. I know that mod can never give more than 1 answer for what you supply it so what can i do to prove it's 1-to-1?
 
Last edited:
  • #15
Show that if f(k1) = f(k2), then k1 = k2.
 
  • #16
Okay so...

ax1 mod b - ax2 mod b = 0

What sort of operations can i do now? I need to get rid of "mod b" so would i divide the whole left side by "1 mod b" or something?
 
  • #17
rooski said:
Okay so...

ax1 mod b - ax2 mod b = 0

What sort of operations can i do now? I need to get rid of "mod b" so would i divvide the left side by "1 mod b" or something?
No, it makes no sense to divide by "1 mod b".

If ax1 (mod b) = ax2 (mod b), then (ax1 - ax2) (mod b) = 0.

What does this say about ax1 - ax2?
 
  • #18
Mark44 said:
No, it makes no sense to divide by "1 mod b".

If ax1 (mod b) = ax2 (mod b), then (ax1 - ax2) (mod b) = 0.

What does this say about ax1 - ax2?

Ah that makes sense.

To prove it is Onto, i would have to take y = ax mod b and find what it means in terms of x.

I find that i have a harder time figuring out what manipulations i can do on equations with mod in them. I cannot divide both sides by ax because that would leave "1 mod b" which isn't proper.

What options does that leave me?
 
  • #19
rooski said:
Ah that makes sense.

To prove it is Onto, i would have to take y = ax mod b and find what it means in terms of x.
For a given y value, show that there is an x in S such that f(x) = y.
rooski said:
I find that i have a harder time figuring out what manipulations i can do on equations with mod in them. I cannot divide both sides by ax because that would leave "1 mod b" which isn't proper.
You seem to be thinking that ax (mod b) means ax * (mod b). At least that's what it seems like to me. In a way that's like thinking that
\frac{sin x}{x} = sin

IOW, that sin x means sin * x, which it doesn't.

If you have an equation ax = 1 (mod b), think about what this means and how it's defined.

This is the same (equivalent to) ax - 1 = 0 (mod b), which is the same as saying ax - 1 = k*b for some integer k.


rooski said:
What options does that leave me?
 
  • #20
Hrm, so i must find a value k so that a * k mod b == 1, correct?

then i will have a * k * x mod b <==> x mod b, i think.
 
  • #21
What are you trying to do? Are you working on the "onto" part?
 
  • #22
Yeah. A friend told me that i should be "finding a value k so that a * k mod b == 1" although all this has really done is make me more confused. :p
 
  • #23
I don't see how that does you any good. What you need to show is that for any number y in S = {0, 1, 2, ..., b - 1}, there is a number k in S such that y = f(k). That's the definition of "onto."
 
  • #24
So I've got here:

y = ak mod b
y - ak === 0 (mod b)
=> b | (y - ak)
=> y - ak = nb for some integer n.

Could i say n is zero, then say y = ak? Or is that a misstep?
 
  • #25
rooski said:
So I've got here:

y = ak mod b
y - ak === 0 (mod b)
=> b | (y - ak)
=> y - ak = nb for some integer n.
Now solve for k. To prove that your function f(k) = ak (mod b), you are trying to show that for any number y in S = {0, 1, 2, ..., b - 1}, there is a number k in S such that f(k) = ak (mod b).
rooski said:
Could i say n is zero, then say y = ak? Or is that a misstep?
No, it just says that for some n, y - ak = nb. You can't assume any particular value for n.
 
Back
Top