Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

## #1 2013-03-27 15:08:48

rhymin
Member

Offline

### Division Algorithm?

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.

## #2 2013-03-27 16:31:00

bobbym
Administrator

Online

### Re: Division Algorithm?

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

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #3 2013-03-27 17:12:31

rhymin
Member

Offline

### Re: Division Algorithm?

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?

## #4 2013-03-27 17:14:42

bobbym
Administrator

Online

### Re: Division Algorithm?

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

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #5 2013-03-27 17:19:53

rhymin
Member

Offline

### Re: Division Algorithm?

Thanks for replying so quickly   Few questions:

What is GCD?

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

## #6 2013-03-27 17:30:12

bobbym
Administrator

Online

### Re: Division Algorithm?

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

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #7 2013-03-27 18:08:20

rhymin
Member

Offline

### Re: Division Algorithm?

Thanks for the insult I guess.

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

## #8 2013-03-27 18:32:09

bob bundy
Moderator

Offline

### Re: Division Algorithm?

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

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

## #9 2013-03-27 20:09:33

bobbym
Administrator

Online

### Re: Division Algorithm?

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?

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

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

Nehushtan
Power Member

Offline

### Re: Division Algorithm?

#### 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 23:43:30)

131 books currently added on Goodreads

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

Nehushtan
Power Member

Offline

### Re: Division Algorithm?

#### 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 I’ve seen him/her ask, I would say he/she is a mature learner trying teaching himself/herself maths.

131 books currently added on Goodreads

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

Agnishom
Real Member

Online

### Re: Division Algorithm?

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)

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'The whole person changes, why can't a habit?' -Alokananda

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

bobbym
Administrator

Online

### Re: Division Algorithm?

#### Nehushtan wrote:

rhymin posts on at least two other math forums (besides this one). From the questions I’ve 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.

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #14 2013-03-28 00:16:32

Nehushtan
Power Member

Offline

### Re: Division Algorithm?

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

Don’t think I’ve seen you before on the other forums though.

131 books currently added on Goodreads

## #15 2013-03-28 00:20:51

bobbym
Administrator

Online

### Re: Division Algorithm?

I have seen you.

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #16 2013-03-28 00:33:25

Agnishom
Real Member

Online

### Re: Division Algorithm?

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

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'The whole person changes, why can't a habit?' -Alokananda

## #17 2013-03-28 04:14:16

rhymin
Member

Offline

### Re: Division Algorithm?

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.

## #18 2013-03-28 04:15:37

rhymin
Member

Offline

### Re: Division Algorithm?

And thank you everyone for your replies!

## #19 2013-03-28 05:13:21

bob bundy
Moderator

Offline

### Re: Division Algorithm?

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

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

## #20 2013-03-28 06:46:58

rhymin
Member

Offline

### Re: Division Algorithm?

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?

## #21 2013-03-28 06:49:55

rhymin
Member

Offline

### Re: Division Algorithm?

#### 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!

## #22 2013-03-28 10:11:49

bobbym
Administrator

Online

### Re: Division Algorithm?

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

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #23 2013-03-28 10:21:13

rhymin
Member

Offline

### Re: Division Algorithm?

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.

## #24 2013-03-28 10:23:21

bobbym
Administrator

Online

### Re: Division Algorithm?

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.

In mathematics, you don't understand things. You just get used to them.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #25 2013-03-28 14:08:54

rhymin
Member

Offline

### Re: Division Algorithm?

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?

## Board footer

Powered by FluxBB