
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 abc, does it follow that ab or ac?
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
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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?
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
Re: Division Algorithm?
Thanks for replying so quickly Few questions:
What is GCD?
How did you get 7, 8a, 63s?
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
Re: Division Algorithm?
Thanks for the insult I guess.
Like I said, I haven't taken a math class in several years.
 bob bundy
 Moderator
Re: Division Algorithm?
hi rhymin
Welcome to the forum.
rhymin wrote:1) If a, b, c ∈ Z^+ and abc, does it follow that ab or ac?
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. 426 and it is also true that 422 and 423
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 abc => a = nbc where n is another positive integer. => a = (nb)c where nb is another positive integer => ac
Also a = (nc)b because multiplication is commutative where nc is a positive integer => ab
This is true for all a, b and c in Z+ where abc.
NOTE: The converse theorem is NOT true.
ie. If ab and ac , is it true that abc ?
counter example.
426 and 422 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
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 Nehushtan
 Power Member
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 abc, does it follow that ab or ac?
. Is it true that or ?
Last edited by Nehushtan (20130327 23:43:30)
134 books currently added on Goodreads
 Nehushtan
 Power Member
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.
134 books currently added on Goodreads
 Agnishom
 Real Member

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' 'Who are you to judge everything?' Alokananda
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 Nehushtan
 Power Member
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.
134 books currently added on Goodreads
 bobbym
 Administrator
Re: Division Algorithm?
In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
 Agnishom
 Real Member

Re: Division Algorithm?
One more thing I would tell rhymin to note is: If ab and ac then abc
'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' 'Who are you to judge everything?' Alokananda
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.
Re: Division Algorithm?
And thank you everyone for your replies!
 bob bundy
 Moderator
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
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?
96 x 15 but 9 is not a factor of 6 or 15 Would that be a good way to explain that it is false?
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!
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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.
 bobbym
 Administrator
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof.
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?
