Math Is Fun Forum

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?

BTW, I just wanted to confirm that this is correct?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Division Algorithm?

Hi;

Who is the author?

The linear diophantine equation ax+by = c where c = (a,b) is computed using the extended GCD algorithm or some other and then Bezouts identity is used to get them all.

---

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.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Division Algorithm?

hi rhymin

Sorry about the earlier muddle over the | symbol.  This next bit is my excuse.  Skip it if you like but it makes me feel better to have an excuse.

EXCUSE.  It must be 45 years since I last saw that symbol in some number theory at Uni.  What I should have done is looked it up rather than relying on a faulty memory.  But I think the symbol is poorly chosen.

REASON.  If we want to put "42 divided by 6" into symbols we can say 42 ÷ 6   or 42/6 or even

Now, division must have come long before the concept of "is it divible by" so someone must have made up that definition.  Now he/she could have defined " divides " or " is divisible by ".  The result is mathematically equivalent; it's all in the way you express the property.  So why, oh why, did this person choose " divides " which puts the first number second and the second number first and just to be really confusing invent the symbol | for it, when | is already heavily used in maths to mean other things, and looks a lot like the symbol for divided by \  ???

No wonder I got mixed up. 

END OF EXCUSE.

So, to make amends here is a method for creating the linear combination that doesn't require a computer.

We want integers s and t so that

Divide the larger number by the smaller ( 260/33)

Divide the larger number by the smaller (33/29)

Divide the larger number by the smaller (29/4)

When one of the 'coefficients' is 1 you can stop this process and jump to simultaneous equations.

Solving gives t = -25 and s = 197.

This pair are different from bobbym's pair but both sets of answers for s and t work.  There are, in fact, an infinite number of solutions so best wishes to any teacher who has to check them all. 

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
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

rhymin

Member

Registered: 2013-03-26

Posts: 20

Re: Division Algorithm?

Bob Bundy, no worries at all.  The confusion actually helped me more because I don't think I will ever forget it now because of this discussion.  Also, thank you so much for showing how you solved for that.

One more question:

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?

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Division Algorithm?

Q1 is no

and yes, that's a good example.

If p1, p2, and p3  are all different primes then you can make a suitable example like this

(p1 x p1) | (p1 x p2) x ( p1 x p3) but not (p1 x p1) | (p1 x p2) and  not (p1 x p1) | (p1 x p3)

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
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 25,002

Website

Re: Division Algorithm?

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

Yes, as long as it satisfies the condition. Remember that just one counterexample is ok to disprove anything

---

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