Divisibility: Proving That a is Divisible by c

[rooski]

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?

 

[Mark44]

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.

 

[rooski]

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?

 

[Mark44]

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.

 

[rooski]

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?

 

[Mark44]

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.

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?

 

[rooski]

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

 

[Mark44]

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.

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!

 

[Mark44]

Off topic, but your user name suggests you are Russian. In Cyrillic, it's русский, which means Russian (masc.).

 

[rooski]

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?

 

[Mark44]

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.

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?

 

[rooski]

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

 

[Mark44]

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.

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

 

[rooski]

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?

 

[Mark44]

Show that if f(k₁) = f(k₂), then k₁ = k₂.

 

[rooski]

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?

 

[Mark44]

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 ax₁ (mod b) = ax₂ (mod b), then (ax₁ - ax₂) (mod b) = 0.

What does this say about ax₁ - ax₂?

 

[rooski]

No, it makes no sense to divide by "1 mod b".

If ax₁ (mod b) = ax₂ (mod b), then (ax₁ - ax₂) (mod b) = 0.

What does this say about ax₁ - ax₂?

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?

 

[Mark44]

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.

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.

What options does that leave me?

 

[rooski]

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.

 

[Mark44]

What are you trying to do? Are you working on the "onto" part?

 

[rooski]

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

 

[Mark44]

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."

 

[rooski]

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?

 

[Mark44]

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).

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.