Diophantine Equation - Please Help!

[DivineNathicana]

*You don't need to read the entire problem in order to understand what I'm asking about. Just read the part in bold. Thank you!*

 

---------------------------------------------------------------------------------------------------------

 

"The Monkey and the Mangoes

 

Three men who had a monkey bought a pile of mangoes. At night one of the men came to the pile of mangoes while the others slept and, finding that there was just one more mango than could be exactly divided by three, tossed the extra mango to the monkey and took away one third of the remainder. Then he went back to sleep.

 

Presently another of them awoke and went to the pile of mangoes. He also found just one too many to be divided by three so he tossed the extra one to the monkey, took one third of the remainder, and returned to sleep.

 

After a while the third rose also, and he too gave one mango to the monkey and took away the whole number of mangoes which represented precisely one third of the rest.

Next morning the men got up and went to the pile. Again they found just one too many, so they gave one to the monkey and divided the rest evenly. What is the least number of mangoes with which this can be done?

 

Solution:

 

Let there be M mangoes to begin with. The first man discards one and leaves 2/3 of what remains, or(2M - 2)/3. The second man discards one = (2M - 5)/3 and leaves 2/3 of what remains = (4M - 10)/9. The third man discards one = (4M - 19)/9 and leaves 2/3 of what remains = (8M - 38)/27. This number must be a multiple of 3, plus 1 or (8M - 38)/27 = 3K + 1, with K an integer. This leads to the linear Diophantine equation in two variables 8M - 81K = 65. This equation can be reduced with the substitution K = 8p - 65 to the form M = 81p - 650, with p an integer. We choose the smallest value of p that will make M positive, which is p = 9, and we arrive at M = 79 mangoes."

 

---------------------------------------------------------------------------------------------------------

 

I get the entire problem except for the part in bold: "This equation can be reduced with the substitution K = 8p - 65". What's p? Why does K equal 8p-65? How does this help me solve the problem?

 

Thank you so much in advance for any answers!

 

- Alisa

[tom]

P is an integer like K

you choose p = (k + 65) / 8 which simplifies your equation

 

8M - 81 K = 65 <=> 8M - 81 ( 8 P - 65 ) = 65 <=> 8M - 81 * 8 P + 65 * 81 = 65 <=>

8M - 81 * 8P = -80 * 65 | :8 <=> M - 81P = -650 <=> M = 81P - 650

 

 

Another way to do this

 

8M - 81K = 65 <=> 8M = 81K + 65 <=> 8M = 80 K + K + 64 +1 <=> M = 10 K + 8 + + ( K + 1)/8

 

K>0

 

q=(K+1) / 8 is the smallest natural number possible. q can't be 0 ( because this means k = -1 ) so q is 1 and K = 7 ; this means 79 mangoes ;)

[DivineNathicana]

Thanks for replying!

 

P is an integer like K

you choose p = (k + 65) / 8 which simplifies your equation

 

8M - 81 K = 65 <=> 8M - 81 ( 8 P - 65 ) = 65 <=> 8M - 81 * 8 P + 65 * 81 = 65 <=>

8M - 81 * 8P = -80 * 65 | :8 <=> M - 81P = -650 <=> M = 81P - 650

 

How would I know to choose p=(k+65)? Like, where the hell do those numbers come from? Oh, and also, I don't get the entire part in bold. Woudn't it be

 

8M-81*8p MINUS 65*81 rather than PLUS? And I pretty much don't get anything after that. = / Can you please explain it again? Lol sorry for being slow. = )

 

- Alisa ;)

[MortenS]

well, here is how I approached this when looking at your problem:

 

You had 8M -81K = 65, which can be transformed to:

 

M = (81K + 65)/8

 

Not a nice equation if you are only interested in integers.

 

So, let K be substituted by a*p + b, where p is an integer, and a and b are two constants.

 

M = (81*(a*p + ;) +65)/8

 

M = (81*a*p + 81*b + 65)/8

 

Now comes the problem, how to choose a and b so that we can get rid of the denominator.

 

For 81*a*p, it is easy, we can choose a= 8, and we get rid of a and the denominator.

For 81*b + 65, it is perhaps not as obvious, but if you take a look at the number 81, it is very close to 80, if we could get (81*b+65) to be a multiple of 80, we can divide with 8.

 

Choosing b= -65 solves that problem.

 

There might be some other smart ways to get these two numbers as well.

[tom]

Thank you for posting . I couldn't explain it so clearly as you did. Only one objection . b = -65

[MortenS]

Opps that was a typo...I'll fix it...

[DivineNathicana]

Thanks, guys! Now I get it. Except for one small thing:

 

How do you know that the replacement for k must be in the form (ap+;)?

 

I mean, I see that it works out that way, but how would you know that it should be in that form? Is there any general rule or way to tell?

 

Thanks again,

Alisa

[MortenS]

Now I really would like to be a text book author. This is the time to write: It is left as an excercise to the reader.....

 

I can try to explain it...since 8M -81K=65 is a linear relation, any linear relation we put in place for K will not change the relation to a non-linear relation. If we however put in a nonlinear function for K, the whole equation changes to a non-linear equation.

[DivineNathicana]

Thank you so much! I actually get it now. = ) Your help is GREATLY appreciated, MortenS and tom. *hug* hehe I dub thee official saviors.

 

- Alisa

[MortenS]

I found an online tool that not only solve Diophantine equations, it also shows the calculations behind it.

 

See: Solving ax + bx = c