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

You are not logged in.

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

### Re: Division Algorithm?

Thanks for replying so quickly   Few questions:

What is GCD?

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

### Re: Division Algorithm?

Thanks for the insult I guess.

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

Offline

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

bob bundy
Registered: 2010-06-20
Posts: 8,323

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

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 913
Website

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

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 913
Website

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

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,850
Website

### 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'
I'm not crazy, my mother had me tested.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 913
Website

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Division Algorithm?

I have seen you.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,850
Website

### 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'
I'm not crazy, my mother had me tested.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

### Re: Division Algorithm?

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.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

### Re: Division Algorithm?

And thank you everyone for your replies!

Offline

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

bob bundy
Registered: 2010-06-20
Posts: 8,323

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

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

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

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### 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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

rhymin
Member
Registered: 2013-03-26
Posts: 20

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

Offline