Browse · harp
Printsmc
number theory senior
Problem
Two farmers agree that pigs are worth dollars and that goats are worth dollars. When one farmer owes the other money, he pays the debt in pigs or goats, with "change" received in the form of goats or pigs as necessary. (For example, a dollar debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?
(A)
(B)
(C)
(D)
Solution
The problem can be restated as an equation of the form , where is the number of pigs, is the number of goats, and is the positive debt. The problem asks us to find the lowest x possible. and must be integers, which makes the equation a Diophantine equation. Bezout's Lemma tells us that the smallest for the Diophantine equation to have solutions is when is the GCD (greatest common divisor) of and . Therefore, the answer is
Final answer
C