# Math help needed Diophantine Equations (indeterminate equations restricted)

## Recommended Posts

My dd, the one who "hates" math (really, she said today, she just hates getting answers wrong) is insisting on doing the "Extra for Experts" in The 1965 Dolciani on pages 393-395. She doesn't get it, even after we read a slightly longer explanation in the 1975 (the book she doesn't like). Aside from the fact that she doesn't like to learn math from me, she's 14 and not particularly patient with me, nor does she like my way of doing math. However, she will read any written explanation I can get.

She understands what an unrestricted equation is, and what restricting it does, but she doesn't "get" it well enough to solve the problems given. Here is the first problem.

A 55-yard cloth is cut into pieces 3 1/2 and 4 1/2 yards long, without remnants. How many pieces of each length are there?

I have their solution, but she still doesn't understand it all, particularly how they get the s. Here it is:

Let x= no. of 3 1/2 yd pieces and y= no. of 2 1/2 pieces, where x and y could equal (that funny roundish E-ish sign) {nonnegative integers}.

3 1/2x + 4 1/2y = 55; 7x + 9y = 110; x = 110 - 9y / 7 (can't do the fraction). She can do this part all by itself with no trouble. Here's the confusing part to her: Since 110 + 9 = 119 is 7*17, let y = 7s - 1, s (can equal) {nonnegative integers.)

It goes on from there. But that part alone confuses her. As for me, it's been over 3 decades since I've done anything like this, so I don't even "get" this one right now. On days like this it's hard to believe I was so good at math in high school.

NB if you solve this using a for x and b for y you'll really be her hero; she thinks x and y are boring, but not to worry, she'll understand x and y.

Signed,

the mother of a 14 yo ;)

Edited by Karin
##### Share on other sites

Hi Karin,

I'll take a stab at trying to explain:

Let a = number of pieces of 3 1/2 yard length fabric

Let b = number of pieces of 4 1/2 yard length fabric

Then (3 1/2)a + (4 1/2)b = 55

(7/2)a + (9/2)b = 55

7a + 9b = 110

Solving for a in terms of b:

7a = 110 - 9b

a = (110 - 9b) / 7

Now, 110 isn't divisible by 7, but I note that 119 is (since 119 = 7 * 17).

So I rewrite 110 as 119 - 9

a = (119 - 9 - 9b) / 7

a = [119 - 9(1+ b)] /7, factoring out the 9

a = 17 - 9(1+ b)/7, noting that 119/7 = 17

Since a must be an integer, and since 17 is a positive integer, this forces 9(1 + b)/7 to also be an integer.

Well, that can only happen if 9(1+b) is a multiple of 7.

But, the only way that can happen is if (1+ b) is a multiple of 7, since 9 certainly isn't.

Thus, 1 + b = 7s for some integer s (in fact, s must be a non-negative integer, since b is a non-negative integer)

or, b = 7s - 1

OK? this is where you left off... if you want to finish it off:

7a = 110 - 9b from up above

= 110 - 9(7s-1) substituting b = 7s - 1

= 110 - 63s + 9

= 119 - 63s

Now divide through by 7 to get

a = 17 - 9s and b = 7s - 1

Now pick some non-negative integer values for s and figure out a and b.

When s = 0, you get a = 17 and b= -1 (reject since b can't be negative)

When s= 1, you get a = 8 and b = 6 (yay! this one works)

When s= 2 or greater, you get a negative value for a (reject again)

So the only answer is a = 8 and b = 6, and we're (FINALLY) done!

{Little side note: Why did I rewrite 110 as 119 - 9 way up at the top? This is the tricky part. It's true that 119 is divisible by 7, but so are lots of other numbers. For instance, I could have written 110 = 112 - 2, since 112 is divisible by 7. Then I would have proceeded as above till I arrived at this step:

a = (112 - 2 - 9b)/7 and then I'd have a problem, because I couldn't factor out that 9 like I did above. So the reason I chose 119 is not only because it's divisible by 7, but also because (119-110) is a multiple of 9. }

These are not simple problems AT ALL; they require quite a bit of advanced reasoning...you won't encounter these in a typical high school algebra course.

I would normally solve this kind of problem using modular arithmetic - there is a straightforward approach once you've mastered that technique. Your daughter would learn how to do this if she ever should study number theory - and she'd learn a lot more about Diophantine equations in such a course, too. (Art of Problem Solving School offers such courses btw - my kids liked them)

hth,

~Kathy

##### Share on other sites

A 55-yard cloth is cut into pieces 3 1/2 and 4 1/2 yards long, without remnants. How many pieces of each length are there?
The book's solution required you to be able to use your number sense to see that 110=119-9 and that 119 was divisible by 7. I was not familiar enough with these problems for that to work for me, so I found a general solution that works *without* requiring magical number sense:

Let a = the number of 3.5yd pieces and b = the number of 4.5yd pieces, where a and b are elements in {the nonnegative integers}.

3.5a + 4.5b = 55;

7a + 9b = 110;

7a = 110 - 9b;

a = (110 - 9b)/7;

For a to be a nonnegative integer, (110-9b) must represent a nonnegative multiple of 7. Let b = cx + d, where c and d are elements of {the real numbers} and x is an element of {the integers} such that cx + d >= 0:

110 - 9(cx + d) = 7t, where t is an element of {the nonnegative integers};

110 - 9cx -9d = 7t;

(110 - 9d) - 9cx = 7t;

t = [(110 - 9d) - 9cx]/7.

Because t is an element of {the nonnegative integers}, [(110 - 9d) - 9cx]/7 must also be an element of {the nonnegative integers}.

Thus, we need to find a d such that (110 - 9d)/7 is an element of {the nonnegative integers}, a c such that 9c/7 is an element of {the nonnegative integers}, and all x such that (110 - 9d) >= 9cx and cx + d >= 0.

To find d:

Let (110 - 9d)/7 = 1;

110 - 9d = 7;

-9d = 7 - 110;

-9d = -103;

d = 103/9

([(110 - 9d)/7] can be any nonnegative integer you like. (110 - 9d)/7 = 17 gives d = -1, like the book's solution.)

To find c:

Let 9c/7 = 1;

c = 7/9

([9c/7] can be any nonnegative integer you like. 9c/7 = 9 gives c = 7, like the book's solution.)

To find x:

(110 - 9d) >= 9cx;

(110 - 9*103/9) >= 9*7/9*x;

(110 - 103) >= 7x;

7 >= 7x;

1 >= x;

AND

cx + d >= 0;

7x/9 + 103/9 >= 0;

7x + 103 >= 0;

7x >= -103;

x >= -103/7;

x >= -14;

SO

-14 <= x <= 1;

c = 7/9 and d = 103/9 gives b = 7x/9 + 103/9. Substituting this in the expression for a:

a = [110 - 9(7x/9 + 103/9)]/7;

a = (110 - 7x - 103)/7;

a = (7 - 7x)/7;

a = 1 - x

Thus, a and b are expressed in terms of x by the following equations:

a = 1 - x

and

b = 7x/9 + 103/9

To get the solution:

X = -14, a = 1, b = 103/9, invalid;

(so on and so forth through -13 <= x <= -8, which are all invalid, but I'm too lazy to type them all out)

X = -7, a = 8, b = 6;

(so on and so forth through -6 <= x <= 1, which are all invalid, but I'm too lazy to type them all out)

With the values for c and d used in the book's solutions:

c = 7 and d = -1 gives b = 7x - 1. Substituting this in the expression for a:

a = [110 - 9(7x - 1)]/7;

a = (110 - 63x + 9)/7;

a = (119 - 63x)/7;

a = 17 - 9x

Thus, a and b are expressed in terms of x by the following equations:

a = 17 - 9x

and

b = 7x - 1

X = 0, a = 17, b = -1, invalid;

X = 1, a = 8, b = 6;

X = 2, a = -1, b = 13, invalid;

##### Share on other sites

Thanks for the link and the two solutions. I'll have dd read these. The Art of Problem Solving--could I buy a book or would we need to take a course with them? I've never looked into this, but I suspect it would be a very good idea.

##### Share on other sites

You could either take the Intro to Number Theory course online or just use the AoPS textbook.

My dd took the online course when she was fourteen, and she loved it and learned a lot. It's a great first course in their series of classes, and very appropriate for a student with a good grounding in algebra like your daughter.

The textbooks come bundled with solution manuals which have every problem worked out in helpful detail. Your daughter could work through it herself if that's what she prefers - mine have done that with some of their texts.

~Kathy

##### Share on other sites

Here's another explanation for her.

http://mathforum.org/library/drmath/view/51595.html

She has read this link and does not understand the process they used to get the gcf (greatest common factor.) My brain simply isn't working in this direction right now (perhaps because it's a bad allergy time, perhaps that part of my brain has atrophied from 30+ years of not doing Algebra). However, one way or another we'll get this.

##### Share on other sites

Perhaps if she thinks of it as remotely similar to completing the square? Where you add or subtract from both sides to make the constant at the end of the quadratic equation what you want to be able to factor it?

Here, she rewrites a number (like 110) to make it factor (119-9)?

##### Share on other sites

Hope this helps with the factoring.

We proceed to find gcd(12378,3054):

12378 = 4*3054 + 162

3054 = 18*162 + 138

162 = 1*138 + 24

138 = 5*24 + 18

24 = 1*18 + 6

18 = 3*6 + 0

So gcd(12378,3054) is indeed 6.

To get the greatest common factor of 12378 and 3054, they took the bigger number (12378) and divided it by the smaller number (3054) and got 4 with a remainder of 162. They then wrote an equation that represented this:

12378 = 4 x 3054 + 162

Then they took the larger divisor (3054) and divided it by the remainder (162) to get 18 with a remainder of 138. They wrote this as an equation too.

3054 = 18 x 162 + 138

Repeating this process, they took the larger divisor (162) and divided it by the remainder (138) to get 1 with a remainder of 24. They wrote it as an equation.

162 = 1 x 138 + 24

Repeating the process again, they took the larger divisor (138) and divided it by the remainder (24) to get 5 with a remainder of 18.

138 = 5 x 24 + 18

Repeating the process again, they took the larger divisor (24) and divided it by the remainder (18) to get 1 with a remainder of 6

24 = 1 x 18 + 6

Repeating the process again, they took the larger divisor (18) and divided it by the remainder (6) to get 3, with a remainder of zero.

18 = 3 x 6 + 0

The second to last remainder is the greatest common factor.

She can tell how many times to repeat the process by going until she gets to a remainder of 0.

Edited by In The Great White North
##### Share on other sites

Hope this helps with the factoring.

She can tell how many times to repeat the process by going until she gets to a remainder of 0.

Thanks! I'm printing your reply out as I type this. We are going to get this sooner or later, and this forum, once again, is such a help.

##### Share on other sites

Dd now understands the factoring part, but still not how to solve these, nor where that s comes from in the solution guide for Dolciani. I'm going to have her review the two solutions with a and b (thanks again for taking the time to solve those). Perhaps someone else will post with some new way of explaining it. This is the most stumped she's ever been.

##### Share on other sites

Dd now understands the factoring part, but still not how to solve these, nor where that s comes from in the solution guide for Dolciani. I'm going to have her review the two solutions with a and b (thanks again for taking the time to solve those). Perhaps someone else will post with some new way of explaining it. This is the most stumped she's ever been.

Mathematicians often employ what is called parameterization. Essentially, one does not like the way a problem looks, so one rewrites the problem. This equation was rewritten with the parameter s in order to cancel the troublesome 7 in the denominator. Where did it come from? Thin air? It seems that way, but essentially one choose a parameter so that the troublesome piece is eliminated. It takes observation and experience before parameters become obvious.

Kathy noted in her previous post:

Well, that can only happen if 9(1+b) is a multiple of 7.

But, the only way that can happen is if (1+ b) is a multiple of 7, since 9 certainly isn't.

Thus, 1 + b = 7s for some integer s (in fact, s must be a non-negative integer, since b is a non-negative integer)

or, b = 7s - 1

I'll flesh this out a bit. As was noted, 9(1 + b) must be equal to 7 times an integer. 9 is not a factor of 7, so (1 + b) must be divisible by 7. The parameter s did not come out of thin air: it is a logical consequence.

Tell your daughter that if this is not obvious, do not fret. She will see more parameters in the years ahead--it does get easier!

##### Share on other sites

Mathematicians often employ what is called parameterization. Essentially, one does not like the way a problem looks, so one rewrites the problem. This equation was rewritten with the parameter s in order to cancel the troublesome 7 in the denominator. Where did it come from? Thin air? It seems that way, but essentially one choose a parameter so that the troublesome piece is eliminated. It takes observation and experience before parameters become obvious.

Kathy noted in her previous post:

I'll flesh this out a bit. As was noted, 9(1 + b) must be equal to 7 times an integer. 9 is not a factor of 7, so (1 + b) must be divisible by 7. The parameter s did not come out of thin air: it is a logical consequence.

Tell your daughter that if this is not obvious, do not fret. She will see more parameters in the years ahead--it does get easier!

Thanks--I should have read more closely:o. With what Kathy has done and what you've written we'll see what we can do. I've printed all of the posts, and dd is going to reread it all. I'm thankful for all the mathy people here who are so patient to help us.

Dd does rewrite problems sometimes, I think, or is leaning that way. If she doesn't like the way Dolciani does something, she'll do it her way. Most of the time she prefers to use decimals over fractions, too, and will convert things to decimals. I remember rewriting things, but that skill is long gone. This parameter thing is great, and I'm sure sooner or later she'll understand it.

Edited by Karin
##### Share on other sites

Update:

My dd is working on this today. She was ill one day, then she read all the posts. She had some of it, but not all, so I asked my brother, who is not a mathematician, but a physicist. This helped only a bit more. She's still struggling through this, but I thought you might enjoy seeing how he did it and some of his (humourous, IMO) remarks. How he did another one is even more interesting, and I'm going to post it separately because I didn't post that problem. He did that one very differently than this and the book. This one is close to the other solutions.

Interesting problem. I have come across these on occasion, but don't claim to be an expert. Here is my interpretation of the problem. You can just let Name read this if you want.

Let's start at 7x+9y = 110, where x and y are positive integers. Our main objective is to narrow down the possibilities for each of x and y. Clearly x is less than 15, and y is less than 12. That is still 180 pairs to check! Can we do better?

We can solve for x (or y), ( which is always a good idea since the solution might be nice and easy)

x = (110-9y)/7

Ok, clearly this isn't easy, 9 and 110 give fractions when divided by 7. However, let's see if we can simplify the equation using what we have

x = 110/7 - 9y/7

110 isn't divisible by 7, but 119 is, so rewrite

x = (110 +9)/7 - 9/7 - 9y/7

x=17 - (9/7)(1+y)

Is this better? Well we realize that x must be an integer, so the second term must be an integer, it t. We can also surmise that t is less than 17. Why? If t is less than 17, then

9/7(1+y)<17, so y< 12...hmm not much help, but at least the numbers are smaller, so we continue and see what happens...

So x = 17- t, with t =9/7(1+y)

or 1+y = 7/9 t, once again 1+y is an integer, so 7/9t is an integer. The only way 7/9 t is an integer is if t is evenly divisible by 9. Mathematicians are lazy, so let's call t=9s, where s is yet another

positive integer. We note that as t was limited, so is 9s. Specifically 9s<17, so clearly s =1 or 0. Aha! That has really narrowed down our search!

1+y = 7s, or y = 7s-1. We note here that s can't be 0 since y would then be negative.

So we have the following result:

x = 17 - ( 9s), where x is positive integer. Now s can only be 0 or 1, but s can't be 0. Therefore s =1, y = 6 and x = 8. Check the answer

7(8)+9(6) = 110

yehaaa! it works!

We have two things that we come back to: finding integer terms and reducing the numbers which are allowed. In this case we did some fancy footwork to get rid of the 110 by adding 9. What if we had chosen a number other than 119 i.e. added a number that was not 9. Well try it and see...for example 112 is divisible by 7 as well? What happens if we use that instead?

x = (110+2)/7 -2/7 - 9y/7

x = 16 -2/7 -9y/7

so in this case, 2/7 - 9y/7 = t

2+9y=7t, where t<16.

y = (7t - 2)/9...we see that this is not much help at all, so the fact that we added the coefficient of y (i.e. 9) is important in the solution.

Ideally, the attempts we make will keep narrowing down the possible integers, but realize that we may in the end only get so far, and we might have to simply brute force the answer by trying the possible values.

##### Share on other sites

Here's the problem from the text:

This "Chinese Problem of a Hundred Fowl," dates at least the sixth century: If a rooster is worth 5 yuan, a hen is worth 3 yuan, and 3 chicks are worth 1 yuan, how many of each, 100 in all, would be worth 100 yuan? Assume that at least 5 roosters are required.

The text's solution uses the same type of technique as people here did for the other problem to solve this. Perhaps physicists think differently than mathematicians (but perhaps not) because my db-the-physicist got the same right answers this way:

This one really fowled me up..

Let r be the number of roosters...what are the limits of r?

(5<=r<20)

h is the number of hens, h <33, and c is the number of chicks c<300

we have two limits on these integers. First the total number of fowl foul must be 100

r+h+c=100

second, the total cost must be 100, so

5r + 3h + c/3 = 100

Since r and h have the smallest possiblities, let's elliminate c, so

14r+8h = 200

There is a common factor of 2, so

7r+4h = 100

As usual, solve for a variable

h = (100-7r)/4

In this case, we note 100 is divisible by 4

h = 25 - 7r/4

so we must have 7r/4 is an integer, 7r/4 = k. Due to the fact r is positive, h>0, and k is less than 25. Due to the fact that 5<=r<=20, k must be larger than 8.75. Finally k must also be divisible by 7. So we need values that are divisible by 7, greater than 8, that leaves 14 or 21. therefore 7r/4 = 14, means r = 8 or 7r/4 = 21, r = 12.

At this point it is simplest to try them out

r h c Number \$

8 11 81 100 100

12 4 84 100 100

Ok, I'm a little surprised there are two answers....

##### Share on other sites

This one really fowled me up..

:lol::lol::lol:

##### Share on other sites

I ran the first one by ds(17), who came up with the answer in about a minute using ratios! So much for all the factoring and substitutions!

I can't wait to see what he does with the chickens. :D

##### Share on other sites

I ran the first one by ds(17), who came up with the answer in about a minute using ratios! So much for all the factoring and substitutions!

I can't wait to see what he does with the chickens. :D

I hadn't wanted to mention that my daughter solved the first one ... in her head! Don't ask me how she did it. My brain isn't up to that these days (if it ever was).

Edited to add that I did ask her how she did it. She said she used trial and error to find the answer.

Regards,

Kareni

Edited by Kareni
##### Share on other sites

Fun!

One intuitive way to look at Karin's original problem, written in the form

7a + 9b = 110,

is to subtract 9's from 110 until you reach a multiple of 7:

110, 101, 92, 83, 74, 65, 56...bingo!

I've subtracted six 9's from 110 and got 56, which is eight 7's.

So the answer is a=8 and b=6.

But the problem is that all Diophantine equations are not so intuitive, nor do they always have just one solution (witness Karin's brother's Chinese problem). So mathematicians often solve them with factoring and parameters to write a proof that they've found all the answers, and to come up with a pretty formula for those answers.:001_smile:

Another well-known equation, the Pythagorean theorem

x^2 + y^2 = z^2,

can be thought of as another Diophantine equation if we restrict ourselves to only looking for positive integer solutions, since it has more unknowns (x, y, z) than equations (just one equation).

It turns out that if you go through a mathematical proof (sparing the details!), you can express all of the solutions in terms of two parameters, r and s:

x = r^2 - s^2

y = 2rs

z = r^2 + s^2 , where r and s must be relatively prime with r > s.

For instance, if you choose r= 2 and s= 1, you get

x = 3, y = 4, z = 5, or the 3-4-5 right triangle, which everyone knows.

But the real beauty of this approach is that it also generates all of the (positive integer) solutions of the Pythagorean theorem, i.e., all right triangles with integer sides! You could choose r = 4 and s = 3 and get x = 7, y = 24, and z = 25. And you could keep going on and on...

~Kathy (who has a book on Diophantine equations she's been struggling to get through for a few years now, and is enjoying this topic:001_smile:)

##### Share on other sites

Fun!

Another well-known equation, the Pythagorean theorem

~Kathy (who has a book on Diophantine equations she's been struggling to get through for a few years now, and is enjoying this topic:001_smile:)

This discussion reminds me of how fun math was back when I was mathy. I really ought to apply myself and relearn Algebra and to learn Geometry.

My ds learned the basis of the Pythagorean theory with letter tiles! We were trying out MEP 4. We ended up doing MEP 3, but I thought it a clever way to introduce the concept at a young age, so that it won't be totally foreign when it comes up later.

How was it done? by finding out all the ways to write a word if you can move one step to the right or one step down. I'll give my own made up examples. It won't show up prefectly here because it spaces according to letter size.

in

n

wet

et

t

rain

ain

in

n

drive

rive

ive

ve

e

and so on. If go to the end of each word and count up all the ways to get there, you get the numbers in the Pythaorean triangle and can see the pattern.

##### Share on other sites

Today I received 2 more emails from my db who was talking with a friend of his who does a lot more of this than he does. So now I have even more ammo. I don't feel comfortable posting someone elses comments to my db, but hopefully it helps her more.

Kathy, is that an advanced book on Diophantine equations? I'm guessing it's waayyy too much for us right now. Dd is struggling along. She needed help with each of the first 4 problems yesterday, and will do the other 4 today. However, she is only 14 and her logic ability is developing now, so I've ordered some Murderous Maths books, one of which includes some of these types of problems. This is for fun because they're inexpensive, not for serious work. I have a feeling I won't care much for the humour but that my dc will. Some days they need a break from rigourous math, but don't tell them I said that;).

##### Share on other sites

This discussion reminds me of how fun math was back when I was mathy. I really ought to apply myself and relearn Algebra and to learn Geometry.

My ds learned the basis of the Pythagorean theory with letter tiles! We were trying out MEP 4. We ended up doing MEP 3, but I thought it a clever way to introduce the concept at a young age, so that it won't be totally foreign when it comes up later.

How was it done? by finding out all the ways to write a word if you can move one step to the right or one step down. I'll give my own made up examples. It won't show up prefectly here because it spaces according to letter size.

in

n

wet

et

t

rain

ain

in

n

drive

rive

ive

ve

e

and so on. If go to the end of each word and count up all the ways to get there, you get the numbers in the Pythaorean triangle and can see the pattern.

How fun! Looking for patterns and connections is what attracts me to mathematics. I've got to get a look at MEP sometime after hearing so many good things about it.

Today I received 2 more emails from my db who was talking with a friend of his who does a lot more of this than he does. So now I have even more ammo. I don't feel comfortable posting someone elses comments to my db, but hopefully it helps her more.

what a nice brother you have:)

Kathy, is that an advanced book on Diophantine equations? I'm guessing it's waayyy too much for us right now. Dd is struggling along. She needed help with each of the first 4 problems yesterday, and will do the other 4 today.

An Introduction to Diophantine Equations by Tito Andreescu & Dorin Andrica (couldn't find it anywhere online).

My ds won it in a math contest when he was 14, but couldn't make any sense out of it at the time. I've been working on it for a while now, but find it extremely challenging - "introduction" my foot!

However, she is only 14 and her logic ability is developing now, so I've ordered some Murderous Maths books, one of which includes some of these types of problems. This is for fun because they're inexpensive, not for serious work. I have a feeling I won't care much for the humour but that my dc will. Some days they need a break from rigourous math, but don't tell them I said that;).

Sounds like a great plan - I'm impressed with how hard she's been working on this stuff. All of us need a mental break now & again. Has she read The Number Devil yet (lots of patterns and number theory ideas there)?

~Kathy

##### Share on other sites

Has she read The Number Devil yet (lots of patterns and number theory ideas there)?

~Kathy

No, I hadn't heard of it. So many books, so little time!

##### Share on other sites

No, I hadn't heard of it. So many books, so little time!

Karin, I cannot tell you how many copies of this book I have given as a gift. Seconding Kathy's recommendation for The Number Devil!

Jane

##### Share on other sites

Karin, I cannot tell you how many copies of this book I have given as a gift. Seconding Kathy's recommendation for The Number Devil!

Jane

Who is the author? I found a book by this title in the library, but it's under Accelerated Reader." It's by Enzensberger. I've put a hold on it, but want to be sure this is it. The full title is The Number Devil: a mathematical adventure.

##### Share on other sites

Who is the author? I found a book by this title in the library, but it's under Accelerated Reader." It's by Enzensberger. I've put a hold on it, but want to be sure this is it. The full title is The Number Devil: a mathematical adventure.

Yes! Hans Magnus Enzensberger.

You can take a peek in Google Books.

##### Share on other sites

Yes! Hans Magnus Enzensberger.

You can take a peek in Google Books.

Thanks Kathy and Jane. I'll take a peek, but I'm going to also get it from the library, since I just sent a cheque for Murderous Math, and really want to buy some other math books this year.

##### Share on other sites

Just when you thought this thread was done, I found out that it was my db who wrote that awesome final explanation after he chatted with his friend. Here it is, and since it was the final thing that helped dd get it better (she still hasn't mastered this, but it will come back to her this summer in Murderous Maths and later somewhere.)

Idea 1

First of all we go waaaay back in math to when there were just integers. When you were learning division with integers, 8/5 did NOT equal 1.6, it was 1 times plus 3 remainder because 1(5) + 3 =8. We revisit this simple idea and

we make up a new operation (related to division), its called "mod". It only works for integers, and it returns the remainder. So for example

7 mod 5 = 2 (7 divided by 5 = 1 plus remainder 2)

31 mod 8 = 7

101 mod 10 =1

A couple of things to note about the mod is that it can only have values of 0 up to 1 less the value. For example

any number mod 5 can only equal 0, 1, 2, 3, or 4. Can you figure out why? why is

37 mod 6 = 7 just plain silly?

A really useful one is mod 2. We know anything mod 2 is either 0 or 1. This allows us to easily determine if an intetger is even or odd. N mod 2 = 1 means that N is odd. N mod 2 =0 means N is even. These ideas are

really important when computers are programmed.

We can easily see that 81 mod 9 =0, but a more useful result is 9j mod 9=0 if j is an integer. Try it for a few values of j and see...

What about (9j+3)mod 9 = 3. Is this true or false?

======================================

Idea 2

All integers that are evenly divisible by 7 can be written as 7 times k, where k is another integer. Of course we can use any integer other than 7. Examples

10, 20, 30, 40 50 ...= 10i where i=1,2,3,4... What is the mod 10 of all these numbers? Why it is zero!

What about integers that are not evenly divisible? Suppose we have an integer N that has N mod 7 = 3. This means that if I divide N by 7, I have 3 left over. but

I can make an integer like that if I use the recipe 7k + 3, where k=0,1,2,..... Look what happens when we divide 7k+3 by 7. (7k+3) = 7k/7 + 3/7, well that is just k + 3 remainder, just like N mod 7 = 3 says.

Let's try this with 45. 45 mod 7 =3, so we expect 45 = 7k +3. Well 7k + 3 gives integers:3, 10,17,24,31,38,45....

Note that we can easily solve for k, but that is not usually what we want to do.

Try a couple of others

55 mod 8 = 7, so 55 = 8k + 7 Check: 8k + 7 gives integers 7, 15, 23, 31, 39, 47, 55, ....

13 mod 2 = 1 so 13 can be written as:

29 mod 5 = 4 so...

================

Now let's combine these two ideas to solve our diophantine equations.

We have already seen 7x + 9y = 110, where x and y are positive integers. Since both are positive, we know y < 12 and x <15. Still, that's a lot of numbers to go through. Let's see what mod has to offer. Let's take the mod 9 of both sides. We choose 9 because we know 9y mod 9 =0, since 9y is evenly divisible by 9 if y is an integer.

7x mod 9 + 9y mod 9 = 110 mod 9

7 x mod 9 + 0 = 2

so we see that 7x mod 9 =2. Which means that when we divide the integer 7x by 9, we get remainder 2. Now we use idea 2. Idea two says that if 7x mod 9 =2, then 7x must be an integer that can be written as 9k +2

Note that if we divide (in the integer sense) (9k+2)/9, we get k plus 2 remainder....

So 7x = 9k+2

or x = (9k+2)/7 where k=0,1,2...

Since x < 15, k <11. Okay, so we have done a whole lot, but the numbers are easier. But the statement is pretty exclusive

7x = 9k +2

If we use mod 7 now...

7x mod 7 = (9k+2) mod 7

0 = (9k+2) mod 7

What this statement says is we have to find a value of k that results in 9k+2 being evenly divisible by 7 (i.e no remainder!). It is easy to calculate the values for 9k+2

k = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ....

9k+2=2, 11, 20, 29, 38, 47, 56, 65, 74, 83, ...

But we need the one that is evenly divisible by 7...so that helps a LOT. So which value of k is it?

56 of course! but this is k =6, so x = 56/6 = 8. Going back to the original equation 7x = 9k+2 = 56, so we get 56 + 9y = 110, so y = 6 just as before.

Now you will certainly notice that this method doesn't do quite a good a job as the previous "trick". But in this case, there is no "trick" to know, and everything proceeds a bit more logically.

I suspect the two methods are in fact closely related, but I will need to think on it a bit. One can also use the modulus to narrow things down a bit more. If you mod 2 the whole equation and note that the modulus

is always positive, the you will find 7x and 9y are even. In this case, you can mod 18 the equation and find 7x mod 18 = 2, or 7x = 18 k + 2, which limits k nicely 7x = 2, 20, 38, 56...done

##### Share on other sites

Sounds like a great plan - I'm impressed with how hard she's been working on this stuff. All of us need a mental break now & again. Has she read The Number Devil yet (lots of patterns and number theory ideas there)?

~Kathy

I got this from the library and my 11 yo read it. At first she said it was boring, but then she kept reading it on her own and by the time she was done she liked it. She didn't seem to remember much of the math. My 14 yo has yet to read it; she's a bit turned off by the title, but I told her to at least look at the stuff on Pascal's triangle becuase of all the cool patterns you can see in it (that would at least get her in it.)

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.