Unipal Initiative - Free Competition Math Courses, From Students For Students

Solvability

The equation $ax+by=c$ has integer solutions if and only if:

\gcd(a,b) \mid c

If it’s solvable, the extended Euclidean algorithm produces one particular solution $(x_0, y_0)$ , and every other solution is generated by shifting along the line:

x = x_0 + \dfrac{b}{g}t, \qquad y = y_0 - \dfrac{a}{g}t \qquad (t \in \mathbb{Z}, \ g=\gcd(a,b))

Applied problems: non-negativity

Many AMC Diophantine problems (coin combinations, ticket counts) restrict solutions to nonnegative integers. After parameterizing the general solution, translate $x \geq 0$ and $y \geq 0$ into a bounded range for the parameter $t$ , then count the integers in that range.

Worked example

Problem: A store sells pens for \$4 and notebooks for \$7. In how many ways can a customer spend exactly \$51, buying at least one of each?

Solution: We need $4p + 7n = 51$ with $p, n \geq 1$ . Since $\gcd(4,7)=1 \mid 51$ , solutions exist. Find one by inspection: try small $n$ values until $51-7n$ is divisible by 4:

n=1: 44/4=11 \ \checkmark

So $(p,n)=(11,1)$ is one solution. The general solution shifts by $(x,y)\to(x-7t, y+4t)$ (since $b/g=7, a/g=4$ ):

p = 11-7t, \qquad n = 1+4t

Need $p \geq 1 \Rightarrow t \leq \tfrac{10}{7} \Rightarrow t \leq 1$ , and $n \geq 1 \Rightarrow t \geq 0$ . So $t \in \{0, 1\}$ — exactly 2 ways.

Practice problems

1.Does $6x+9y=100$ have integer solutions? Explain.

2.Find one integer solution to $3x+5y=1$ .

3.How many pairs of nonnegative integers $(x,y)$ satisfy $5x+3y=45$ ?

4.A vending machine accepts only \$2 and \$3 items and a customer spends exactly \$23 buying at least one of each. How many (quantity-of-\$2, quantity-of-\$3) combinations work?

Linear Diophantine Equations

Solvability

Applied problems: non-negativity

Practice problems