1

I'm in a discrete structures class and I'm having trouble with formulating ideas as to what I need to prove. Here's the question:

Suppose you are trying to prove that, If a, b, and c are integers for which a divides b and b divides c, then a divides c. What, if anything, is wrong with each of the following key questions?

a. How can I show that a divides b and b divides c?

b. How can I show that a divides c?

c. How can I show that an integer divides another integer?

And here's what I've come up with:

a) if a divides b then the equation can be written as 
(1) b = ka
and if b divides c this can be written as 
(2)c = kb
solving each equation for k will give
(1) k = b/a
(2) k = b/c
if you let the two equal each other. it will give b/a = b/c which is not equal. Thus, that is what is wrong with this question.


b) There is nothing wrong with this key question.

c) If a,b,c do not have values associated with them you can not divide an integer by an integer.

I have no idea if these are right or if I am even on the right path to answering these questions correctly. What do you think would correctly answer a,b,c for this question?

Rebecca J. Stones
  • 26,845
Mdjon26
  • 111
  • 2
  • Your problem is that you are using $k$ for what could very well be different constants. Always use different letters whenever the objects are independent (might be different). – vonbrand Feb 10 '14 at 22:06

2 Answers2

1

There is a problem. $a\mid b$ is not the same as $b=ka$. Instead it means that there exists some $k$ (which may depend on $a$ and $b$) such that $b=ka$. Thus "the" $k$ you pick for $a$ and $b$ may be a drifferent one from tha for $b$ and $c$. So maybe rather write $b=k_1a$ and $c=k_2b$. Substituting give $c=k_2k_1a$ and you are done.

Back to the original problem statement

a) confuses me. You do not want to show that $a$ divides $b$ and $b$ divides $c$. Instead, this can be assumed as given. Rather, you might ask: What does it mean that $a$ divides $b$ and $b$ divides $c$? (And that is precisely what we did above: There exists an integr $k$ such that $b=ka$)

b) Good key question! (And the answer is of course: By exhibiting an integer $k$ such that $c=ka$; which is what we did with $k:=k_2k_1$).

c) is just a more general formulation of b), isn't it?

Hagen von Eitzen
  • 374,180
  • So, do you think if I were to do that. It would be the correct answer for (a)? What about (b) and (c) ? – Mdjon26 Feb 10 '14 at 21:30
0

Are you familiar with mathematical logic symbolism ?

We use natural language "paraphrases", that you can easily translate into formulas.

(a) and (b) Saying that "$a$ divides $b$" means that there exists a $k$ such that :

$b = ka$.

The same for "$b$ divides $c$", but you cannot assume that $k$ is the same as before; so you need to use $l$ :

$c = lb$.

So, substituing, you will have :

$c = (lk)a$.

But $lk$ is a number, call it $m$; so that again : "there exists a number $m$ such that :

$c = ma$, i.e. "$a$ divides $c$".

(c) Saying that an integer $a$ divides another integer $b$ is simply to say that there exists a third integer $k$ such that $b=ka$ i.e.

$a|b$ iff $\exists k (b=ka)$.

So, in order to prove that $a$ divides $b$, you must find a number $k$ and "show" that $k \times a$ is equal to $b$.

Mauro ALLEGRANZA
  • 94,169