You are not logged in.

- Topics: Active | Unanswered

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

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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

Thanks for replying so quickly Few questions:

What is GCD?

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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

Thanks for the insult I guess.

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

Offline

**bob bundy****Moderator**- Registered: 2010-06-20
- Posts: 7,661

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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:

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

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

Offline

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.

Offline

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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

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

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.

Offline

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

And thank you everyone for your replies!

Offline

**bob bundy****Moderator**- Registered: 2010-06-20
- Posts: 7,661

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

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

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

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

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 = -638a - 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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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

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

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,731

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.****No great discovery was ever made without a bold guess. **

Offline

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

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