Division Algorithm?

rhymin · 2013-03-26 16:08:48

I'm practicing some discrete math from a friend's textbook. My class isn't for a month, but I am struggling so far (I knew I would as I haven't taken a math course in several years). I'm working on exercises in the book and found these 2 problems to be quite confusing.

1) If a, b, c ∈ Z^+ and a|bc, does it follow that a|b or a|c?

2) For each of the following pairs, a, b ∈ Z^+, determine gcd(a, b) and express it as a linear combination of a, b.

231, 1820

Any help on how to solve these is greatly appreciated.

bobbym · 2013-03-26 17:31:00

Hi;

2)

I am not sure I understand the question.

a = 1820
b = 231

(1820,231) = 7

1820 t +231 s = 7

t = 8
s = -63

8a - 63b = 7

rhymin · 2013-03-26 18:12:31

I'm not sure, that is exactly how it is written in the textbook. What is s and t? And how did you decide that a = 1820, b = 231...when 231 was listed before 1820?

bobbym · 2013-03-26 18:14:42

The order of a and b is not important for the GCD or the linear relation.

rhymin · 2013-03-26 18:19:53

Thanks for replying so quickly Few questions:

What is GCD?

How did you get 7, 8a, -63s?

bobbym · 2013-03-26 18:30:12

The GCD is the greatest common divisor. What grade are you in?

rhymin · 2013-03-26 19:08:20

Thanks for the insult I guess.

Like I said, I haven't taken a math class in several years.

Bob · 2013-03-26 19:32:09

hi rhymin

Welcome to the forum.

rhymin wrote:

1) If a, b, c ∈ Z^+ and a|bc, does it follow that a|b or a|c?

I think the | symbol here means "is divisible by". Z+ means the positive integers or counting numbers.

So if a number 'a' is divisible by a number which is the product of b and c, what can you say about whether a is divisible by each of b and c separately.

eg. 42|6 and it is also true that 42|2 and 42|3

Will this always be true? A single counter example would suffice to show it is false. But I cannot think of one so let's see if I can prove it is true.

If a|bc => a = nbc where n is another positive integer. => a = (nb)c where nb is another positive integer => a|c

Also a = (nc)b because multiplication is commutative where nc is a positive integer => a|b

This is true for all a, b and c in Z+ where a|bc.

NOTE: The converse theorem is NOT true.

ie. If a|b and a|c , is it true that a|bc ?

counter example.

42|6 and 42|2 but 42 is not divisible by 12

rhymin wrote:

Thanks for the insult I guess.

Was there an insult somewhere? If you are referring to being asked about what grade you are in, that is a sensible question. At the start of the help section is a 'sticky' post that says what you should do when asking for help.

http://www.mathisfunforum.com/viewtopic.php?id=14654

"Tell us what level you are at. It will help avoid replies that are too easy or too hard for you to understand."

Bob

bobbym · 2013-03-26 21:09:33

Thanks Bob for saying that. Although you have covered it, I guess I have to respond personally.

Thanks for the insult I guess.

No insult intended. I can tailor the answer much better when I know the level of the questioner and what his needs are.

If I think someone is playing with math as a hobby as I do then I will reply in a way that is unacceptable to someone who is asking a homework question.

What book are you working out of?

Nehushtan · 2013-03-27 00:40:37

bob bundy wrote:

I think the | symbol here means "is divisible by".

No, it does not. It means divides, i.e. is a factor of. For example:.

rhymin wrote:

1) If a, b, c ∈ Z^+ and a|bc, does it follow that a|b or a|c?

. Is it true that or ?

Last edited by Nehushtan (2013-03-27 00:43:30)

Nehushtan · 2013-03-27 00:47:13

bobbym wrote:

Thanks Bob for saying that. Although you have covered it, I guess I have to respond personally.
Thanks for the insult I guess.
No insult intended. I can tailor the answer much better when I know the level of the questioner and what his needs are.
If I think someone is playing with math as a hobby as I do then I will reply in a way that is unacceptable to someone who is asking a homework question.
What book are you working out of?

rhymin posts on at least two other math forums (besides this one). From the questions Ive seen him/her ask, I would say he/she is a mature learner trying teaching himself/herself maths.

Agnishom · 2013-03-27 00:48:01

1. No, it doesn't follow
Counterexample: (4*4*3)|(4*4)*(3*3)
But (4*4*3) does not divide (4*4) neither does it divide (3*3)

bobbym · 2013-03-27 00:52:55

Nehushtan wrote:

rhymin posts on at least two other math forums (besides this one). From the questions Ive seen him/her ask, I would say he/she is a mature learner trying teaching himself/herself maths.

Hi;

I know that. I follow the other forums too. There still is a difference between someone learning book math and someone learning computational math. Providing and algorithmic or iterative answer to someone doing book math might just be fatal to them.

Nehushtan · 2013-03-27 01:16:32

Agnishom wrote:

1. No, it doesn't follow
Counterexample: (4*4*3)|(4*4)*(3*3)
But (4*4*3) does not divide (4*4) neither does it divide (3*3)

Thanks, Agnishom.

I gave my own example in post #10. In general, if a is not a prime number, then a|bc does not imply a|b or a|c.

bobbym wrote:

I know that. I follow the other forums too. There still is a difference between someone learning book math and someone learning computational math. Providing and algorithmic or iterative answer to someone doing book math might just be fatal to them.

Okay.

Dont think Ive seen you before on the other forums though.

bobbym · 2013-03-27 01:20:51

I have seen you.

Agnishom · 2013-03-27 01:33:25

One more thing I would tell rhymin to note is:
If a|b and a|c then a|bc

rhymin · 2013-03-27 05:14:16

Bobby, sorry about that.

For now, I am teaching myself discrete math because it is a requirement in the information technology field. My friend is getting a degree in the same thing as me and let me use his old discrete math book, "Discrete and Combinational Mathematics".

I am still a bit confused because 2 people said a couple different things.

rhymin · 2013-03-27 05:15:37

And thank you everyone for your replies!

Bob · 2013-03-27 06:13:21

My apologies rhymin.

Nehushtan and Agnishom are right and I am wrong about what that symbol means.

Now you have three examples that show the original statement is false.

Bob

rhymin · 2013-03-27 07:46:58

So for problem #1, the answer is no.

And you can use any numbers to prove that, such as Nehushtan's example?

9|6 x 15 but 9 is not a factor of 6 or 15 Would that be a good way to explain that it is false?

rhymin · 2013-03-27 07:49:55

bobbym wrote:

Hi;
2)
I am not sure I understand the question.
a = 1820
b = 231
(1820,231) = 7
1820 t +231 s = 7
t = 8
s = -63
8a - 63b = 7

I'm still confused by this. Are t and s just random letters picked to help solve the problem? I also don't know where the 7 comes from unless you divide 1820 by 231 and leaving the remainder out. Is this called the quotient?

I'm not sure where 8a or -63b comes from either.

Any explanation is highly appreciated!

bobbym · 2013-03-27 11:11:49

Hi;

a and b are given and t and s were calculated.

The question asks for a linear relationship between a,b and gcd(a,b).

rhymin · 2013-03-27 11:21:13

What is the easiest way to figure out the GCD of 2 large numbers besides manually trying to divide by random numbers? I see now 7 is the GCD.

Sorry, but I just don't get how 8a and -63b were calculated.

I looked up Linear Relationship - A statistical term used to describe the relationship between a variable and a constant. Linear relationships can be expressed in a graphical format where the variable and the constant are connected via a straight line or in a mathematical format where the independent variable is multiplied by the slope coefficient, added by a constant, which determines the dependent variable.

But that is just adding to the confusion a bit. Sorry, I know this can be frustrating as I'm not very smart in this area.

bobbym · 2013-03-27 11:23:21

What textbook are you working out of?

You can compute it or you can use a program or you can use a site. Which do you prefer?

Sorry, but I just don't get how 8a and -63b were calculated.

I never waste time using a hand method to do what a machine can do better unless asked. First the GCD and then I will show how to calculate it.

rhymin · 2013-03-27 15:08:54

The textbook is Discrete and Combinational Mathematics.

Ahh, i see that Euclid's algorithm is a way to find the GCD. Awesome.

Could you please shine some light on the second part of the problem?

Math Is Fun Forum

#1 2013-03-26 16:08:48

Division Algorithm?

#2 2013-03-26 17:31:00

Re: Division Algorithm?

#3 2013-03-26 18:12:31

Re: Division Algorithm?

#4 2013-03-26 18:14:42

Re: Division Algorithm?

#5 2013-03-26 18:19:53

Re: Division Algorithm?

#6 2013-03-26 18:30:12

Re: Division Algorithm?

#7 2013-03-26 19:08:20

Re: Division Algorithm?

#8 2013-03-26 19:32:09

Re: Division Algorithm?

#9 2013-03-26 21:09:33

Re: Division Algorithm?

#10 2013-03-27 00:40:37

Re: Division Algorithm?

#11 2013-03-27 00:47:13

Re: Division Algorithm?

#12 2013-03-27 00:48:01

Re: Division Algorithm?

#13 2013-03-27 00:52:55

Re: Division Algorithm?

#14 2013-03-27 01:16:32

Re: Division Algorithm?

#15 2013-03-27 01:20:51

Re: Division Algorithm?

#16 2013-03-27 01:33:25

Re: Division Algorithm?

#17 2013-03-27 05:14:16

Re: Division Algorithm?

#18 2013-03-27 05:15:37

Re: Division Algorithm?

#19 2013-03-27 06:13:21

Re: Division Algorithm?

#20 2013-03-27 07:46:58

Re: Division Algorithm?

#21 2013-03-27 07:49:55

Re: Division Algorithm?

#22 2013-03-27 11:11:49

Re: Division Algorithm?

#23 2013-03-27 11:21:13

Re: Division Algorithm?

#24 2013-03-27 11:23:21

Re: Division Algorithm?

#25 2013-03-27 15:08:54

Re: Division Algorithm?

Board footer