Integer Constraints via Diophantine Equations

In this article, we study a simple yet instructive example of a linear Diophantine equation arising from a coin-counting problem.

Despite its elementary appearance, this problem showcases how number theory naturally encodes discrete constraints, a theme that appears repeatedly in optimization, algorithms, and quantitative finance.

This idea mirrors feasibility checks in optimization, algorithms, and quantitative modeling.

Problem

A man has $4.55 in change composed entirely of 10-cent coins and 25-cent coins.

  1. What is the maximum number of coins he can have?
  2. What is the minimum number of coins he can have?
  3. Is it possible for the number of 10-cent coins to equal the number of 25-cent coins?

Solution

Let

  • $x$ = number of 10-cent coins
  • $y$ = number of 25-cent coins

The total value in cents gives the equation

\[10x + 25y = 455.\]

Existence of Solutions

Let $d = \gcd(a,b)$. A fundamental result in number theory states that there exist integers $u,v$ such that $au + bv = d.$ (This is a consequence of the Euclidean algorithm.)

If $d \mid c$, say $c = dk$, then multiplying the identity by $k$ gives

\[a(ku) + b(kv) = dk = c.\]

Thus $(x,y) = (ku,kv)$ is an integer solution.

Conversely, if $ax + by = c$ has an integer solution, then every common divisor of $a$ and $b$ must divide the left-hand side, hence must divide $c$. In particular, $\gcd(a,b)$ divides $c$.

Therefore, a linear Diophantine equation $ax + by = c$ has integer solutions if and only if

\[\gcd(a,b) \mid c.\]

Euclidean Algorithm

Applying the Euclidean algorithm,

\[\begin{aligned} 25 &= 10(2) + 5, \\ 10 &= 5(2). \end{aligned}\]

Hence, $\gcd(10,25) = 5.$

Since $5 \mid 455$, integer solutions exist.

Solution via Back Substitution

From the first equation,

\[5 = 25 - 10(2).\]

Multiply both sides by $91$,

\[455 = 91(25) - 182(10).\]

This gives a particular integer solution,

\[x_0 = -182, \qquad y_0 = 91.\]

General Integer Solution

Let $d = \gcd(a,b)$.
If $(x_0,y_0)$ is one solution of $ax+by=c$, then all integer solutions are given by

\[x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t, \qquad t \in \mathbb{Z}.\]

To see why, suppose $(x,y)$ is any other solution. Then

\[a(x - x_0) + b(y - y_0) = 0.\]

Hence

\[a(x - x_0) = -b(y - y_0).\]

Since $a$ and $b$ share greatest common divisor $d$, one can show that

\[x - x_0 = \frac{b}{d}t, \qquad y - y_0 = -\frac{a}{d}t\]

for some integer $t$. Substituting these expressions back verifies that all such pairs satisfy the original equation.

In our case, $a=10$, $b=25$, and $d=5$, so

\[\frac{b}{d} = 5, \qquad \frac{a}{d} = 2.\]

Therefore the general integer solution of $10x + 25y = 455$ is

\[\boxed{ \begin{aligned} x &= -182 + 5t, \\ y &= 91 - 2t, \end{aligned} \qquad t \in \mathbb{Z}. }\]

Non-Negativity Constraints

Since coin counts must be non-negative,

\[x \ge 0 \;\Rightarrow\; -182 + 5t \ge 0 \;\Rightarrow\; t \ge 36.4,\] \[y \ge 0 \;\Rightarrow\; 91 - 2t \ge 0 \;\Rightarrow\; t \le 45.5.\]

Hence,

\[37 \le t \le 45.\]

Maximum and Minimum Number of Coins

The total number of coins is $x + y = (-182 + 5t) + (91 - 2t) = -91 + 3t.$

Therefore, the total number of coins is increasing in $t$.

It follows that:

  • the minimum number of coins occurs at the smallest admissible value of $t$,
  • the maximum number of coins occurs at the largest admissible value of $t$.

At $t = 37$ (minimum $t$),

\[x = 3, \quad y = 17, \quad x + y = 20.\]

At $t = 45$ (maximum $t$),

\[x = 43, \quad y = 1, \quad x + y = 44.\]

Equal Numbers of Coins

Let $x = y$. Then, $-182 + 5t = 91 - 2t$ which gives $7t = 273 \;\Rightarrow\; t = 39.$

Substituting $t = 39$, we have $x = y = 13.$

Thus, the answer is yes.

Final Answer

  • Maximum number of coins: $\boxed{44}$
  • Minimum number of coins: $\boxed{20}$
  • Equal numbers of coins possible: $\boxed{\text{Yes}}$

Note: The procedure of checking $\gcd(a,b)\mid c$, performing back substitution, and parameterising all solutions is the standard approach to linear Diophantine equations. This mirrors feasibility checks in integer optimization, cryptography, and algorithmic design.