How should I solve this Diophantine equation word problem?

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    Word problem
Math100
Messages
813
Reaction score
229
Homework Statement
Alcuin of York, 775. One hundred bushels of grain are distributed among 100 persons in such a way that each man receives 3 bushels, each woman 2 bushels, and each child 1/2 bushel. How many men, women, and children are there?
Relevant Equations
None.
Proof: Let x be the number of men, y be the number of women
and z be the number of children.
We need to find the solutions in the non-negative integers
for the Diophantine equation 3x+2y+0.5z=100 such that
x+y+z=100.

From x+y+z=100, we have that z=100-x-y.
Substituting z=100-x-y into the Diophantine equation
3x+2y+0.5z=100 and multiplying it by 2 produces:
5x+3y=100.

Applying the Euclidean Algorithm produces:
5=1(3)+2
3=1(2)+1
2=2(1)+0.

Now we have that gcd(5, 3)=1.
Note that 1##\mid##100.
Since 1##\mid##100, it follows that the Diophantine equation
5x+3y=100 can be solved.

Then we have 1=3-1(2)
=3-1(5-1(3))
=2(3)-1(5)

And now I'm stuck on this problem. I know I need to find the x0 and y0 in order to seek the general solution of the Diophantine equation. How should I go from here?
 
Last edited by a moderator:
Physics news on Phys.org
From ##3x +2y = 100## you could do some modulo arithmetic.

PS It shold be ##5x +3y = 100##, of course!

There are lots of solutions.
 
Last edited:
The modern version of this problem has bitcoins instead of bushels.
 
But this problem is from the section of Diophantine equations. Would it still be okay to do some modulo arithmetic without doing the back substitution for the Diophantine equation 5x+3y=100?
 
Math100 said:
But this problem is from the section of Diophantine equations. Would it still be okay to do some modulo arithmetic without doing the back substitution for the Diophantine equation 5x+3y=100?
Modulo arithmetic is as Diophantine as it gets!
 
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
Back
Top