Solving the coconut monkey problem using Extended Euclidian Algorithm

Martin Gardner's essay of the Monkey and the Coconuts [The Colossal Book of Mathematics, 2001, pp3-9] tells the story of five men and a monkey shipwrecked on a desert island with coconuts for food. The coconuts are split in a certain manner with the monkey getting a certain amount. The problem is solved using six equations which are ultimately reduced to one - A Diophantine equation with 2 unknowns:

Since the equation was too difficult to solve using the use of continued fractions, Gardner obtained the answer using a simple non Euclidian method. This page will calculate the answer using the extended Euclidian algorithm which will be explained during the course of the calculation. It will also be shown that a new sequence produced from certain values of x and y can be generated in Part II.

The Use of the Extended Euclidean Algorithm

The goal of the is to find the greatest common divisor (gcd) of the two integers 1034 and 15625. x and y are first placed on the left side of the equation followed by division of x by y to produce a quotient and a remainder (r). If the remainder is not 0 continue dividing each quotient by the remaider on the next subsequent line. So by first using the Euclidean algorithm we find that the gcd(1024,15625) = 1 at r = 0.

Once we obtain the gcd we work recursively backwards using the extended Euclidean algorithm to find x and y The yellow colored boxes correspond to the values obtained above.

1 = 10 − 3(3)

3 = 13 − 10(1)

1 = 10(1) − 3(13 − 10(1))
1 = 10(1) − 3(13) + 3(10)
1 = 4(10) − 3(13)
10 = 36 − 13(2)

1 = 4(36 − 13(2)) − 3(13)
1 = 144 − 8(13) − 3(13)
1 = 144 − 11(13)
13 = 229 − 36(6)

1 = 144 − 11(229) − 36(6))
1 = 144 − 2519 + 66(36)
1 = 4(36) − 2519 +66(36)
1 = 70(36) − 2519
36 = 265 − 229(1)

1 = 70(265 − 229(1)) − 2519
1 = 18550 − 70(229) − 2519
1 = 16031 − 70(229)
229 = 1024 − 265(3)

1 = 16031 − 70(1024 − 265(3))
1 = 16031 − 71680 + 210(265)
1 = −55649 + 210(265)
265 = 15625 − 1024(15)

1 = −55649 + 210(15625 − 1024(15))
1 = −55649 + 3281250 − 3150(1024)
1 = 3223601 − 3150(1024)

At this point we can multiply both sides of the equation by the number 11529 and rearrange:

11529 = 11529(3225601) − 3150(11529)(1024)
11529 = 37187953927 − 37187942400

It is important to note that the two large numbers are identical in the first 6 digits, viz., 371879, and, therefore, may be simplified by subtracting 37187900000 from the first number and adding it to the second.

11529 = (37187953927 − 37187900000) + (− 37187942400 + 37187900000)
11529 = 53921 − 42400

Dividing 53921 by 1024 and 42400 by 15625 affords the following quotients and remainders:
11529 = 52(1024) + 681 − 2(15625) − 11150

Rearranging and setting 229 and 265 to the values found above:

11529 = 52(1024) − 2(15625) − 10469
11529 = 52(1024) − 2(15625) − 10(1024) − 229
11529 = 42(1024) − 2(15625) − 229
11529 = 42(1024) − 2(15625) − 1024 + 265(3)
11529 = 41(1024) − 2(15625) + 265(3)
11529 = 41(1024) − 2(15625) + 3(15625 − 1024(15))
11529 = 41(1024) − 2(15625) + 3(15625) − 45(1024)
11529 = −4(1024) + 1(15625)

To generate the general equation add 15625n to −4 and subtract 1 from 1024n. Factor out -1 from y₀ to afford positive values:
x₀ = 1024(−4 + 15625n)
y₀ = 15625(1 − 1024n) = −15625(−1 + 1024n)
When n = 1 x₀ = 1024(15621) and y₀ = 15625(1023) as the minimum positive integer values for x and y in the Diophantine equation 1024(x) = 15625(y) + 11529.

THE MONKEY COCONUT PROBLEM USING EXTENDED EUCLIDEAN ALGORITHM (PART I)

Solving the Diophantine Equation 1024(x) = 15625(y) + 11529

Background

The Use of the Extended Euclidean Algorithm