Integral Solutions & Diophantine Equations | CAT & MBA CET Quant Vault

The Bodhi Vault / Quant Vault / Integral Solutions & Diophantine Equations

DEFINITION

One-Line Definition

A Linear Diophantine Equation is an equation of the form $ax + by = c$ where $a, b, c$ are given integers ($a, b \ne 0$) and we seek strictly integer values for $x$ and $y$ ($x, y \in \mathbb{Z}$).

Golden Condition: Integer solutions exist $\iff \gcd(a, b) \mid c$.

CORE INTUITION ⚡

Solution Motion & Bounds

Understanding Diophantine behavior relies on 3 key principles:

• Step Balance: As $x$ increases in steps of $\frac{b}{d}$, $y$ decreases in steps of $\frac{a}{d}$.
• Finite Non-Negative Range: Restricting $x \ge 0, y \ge 0$ creates upper & lower bounds on parameter $k$, producing a finite number of valid pairs.
• McNugget Threshold: For co-prime $a, b$, the largest unrepresentable positive integer is $ab - a - b$.

Always check $\gcd(a, b)$ solvability before finding initial solution pairs!

💡 WHY THIS CONCEPT MATTERS & REAL-LIFE APPLICATIONS

Diophantine equations appear in CAT, MBA CET, and SNAP exam questions involving currency combinations, vendor transactions, and integer word problems. Click below to explore connected Quant Vault topics:

Linear Equations Quadratic Equations Polynomials Inequalities & Modulus Maxima & Minima

Where Is This Used in Real Life & Business?

🪙 Currency Denomination & Coin Exchange

📦 Inventory & Container Unit Packaging

🔐 Cryptography & RSA Modulo Arithmetic

🏭 Factory Shift Scheduling & Resource Allocations

1 Solvability Test & Bézout's Identity

Before spending time solving $ax + by = c$, test for integer solvability using the GCD Solvability Criterion:

📌 The Solvability Rule (Bézout's Theorem):

$$\text{Let } d = \gcd(|a|, |b|). \quad \text{Integer solutions exist } \iff d \text{ divides } c \quad (c \pmod d = 0).$$

If $\gcd(a, b)$ does NOT divide $c$, the equation has zero integer solutions.

Worked Example 1: Solvability Check

Question: Which of the following equations has valid integer solution pairs $(x, y)$?

(A) $14x + 21y = 45$ (B) $12x + 15y = 81$

• For (A): $\gcd(14, 21) = 7$. Does 7 divide 45? No! $45 \pmod 7 = 3 \ne 0 \implies$ No integer solutions.

• For (B): $\gcd(12, 15) = 3$. Does 3 divide 81? Yes! $81 / 3 = 27 \implies$ Infinitely many integer solutions exist!

2 General Parameterized Solution Formula

If $(x_0, y_0)$ is any single initial integer solution to $ax + by = c$, then all infinitely many integer solutions $(x, y)$ are generated by the Parametric Formula:

📌 General Solution Equations:

$$x = x_0 + k \cdot \left(\frac{b}{d}\right)$$ $$y = y_0 - k \cdot \left(\frac{a}{d}\right)$$

where $d = \gcd(a, b)$ and $k$ is any arbitrary integer ($k \in \mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$).

⚡ How Step Motion Works

Notice that as $x$ increases in steps of $\frac{b}{d}$, $y$ decreases in steps of $\frac{a}{d}$ (or vice versa). The product of the step sizes balances out: $a \cdot \left(\frac{b}{d}\right) = b \cdot \left(\frac{a}{d}\right)$.

3 Counting Non-Negative & Positive Solutions

Competitive exam questions usually restrict solutions to non-negative integers ($x \ge 0, y \ge 0$) or positive integers ($x > 0, y > 0$).

🎯 4-Step Algorithm to Count Non-Negative Solutions

Step 1: Solvability Check

Compute $d = \gcd(a, b)$. Verify if $d \mid c$. If not, answer is 0.

Step 2: Base Solution $(x_0, y_0)$

Find the smallest non-negative integer $x_0 \ge 0$ by testing $x = 0, 1, 2, \dots, \frac{b}{d}-1$ until $(c - ax) \pmod b = 0$.

Step 3: Boundary Inequality

Set up $x = x_0 + k \cdot \frac{b}{d} \ge 0$ and $y = y_0 - k \cdot \frac{a}{d} \ge 0$ to solve for integer bounds on $k$.

Step 4: Count Values of $k$

Total non-negative solutions = $k_{\max} - k_{\min} + 1$.

🚀 CAT Super Shortcut Formula for $ax + by = c$

$$\text{Number of Non-Negative Solutions} = \left\lfloor \frac{c}{a \cdot b} \right\rfloor \text{ or } \left\lfloor \frac{c}{a \cdot b} \right\rfloor + 1$$

For co-prime $a, b$, the number of non-negative solutions is always either $\lfloor c / (ab) \rfloor$ or $\lfloor c / (ab) \rfloor + 1$.

4 Frobenius Coin Theorem (Chicken McNugget Theorem)

The Frobenius Coin Problem asks: Given coin denominations $a$ and $b$ where $\gcd(a, b) = 1$, what is the largest monetary amount that CANNOT be paid exactly using non-negative counts of these coins?

📌 Chicken McNugget Formulas (for $\gcd(a, b) = 1$):

$$\text{1. Largest Unrepresentable Number (Frobenius Number): } g(a, b) = a \cdot b - a - b$$

$$\text{2. Total Count of Unrepresentable Positive Integers: } N = \frac{(a - 1)(b - 1)}{2}$$

Worked Example 2: McNugget Theorem Application

Question: A restaurant sells chicken nuggets in packs of 7 and 11. What is the maximum number of nuggets that CANNOT be bought?

$a = 7, b = 11 \implies \gcd(7, 11) = 1$.
$g(7, 11) = (7 \times 11) - 7 - 11 = 77 - 18 = 59$.

Thus, 59 nuggets is the largest quantity that cannot be bought!

⚠️ COMMON MISTAKES TO AVOID

❌ Mistake 1: Forgetting to test GCD Solvability first

Attempting to find solutions for $14x + 21y = 45$ without checking $\gcd(14, 21) = 7 \nmid 45$ wastes time. Always test $\gcd(a, b) \mid c$ first!

❌ Mistake 2: Mixing up step directions for positive coefficients

In $ax + by = c$ with $a, b > 0$, as $x$ increases, $y$ MUST decrease! Do not add steps to both variables simultaneously.

❌ Mistake 3: Applying McNugget Formula when GCD ≠ 1

The Chicken McNugget formula $ab - a - b$ is valid ONLY when $\gcd(a, b) = 1$. If $\gcd(a, b) > 1$, infinitely many numbers are unrepresentable.

🚀 CAT & MBA CET DIOPHANTINE SHORTCUTS

⚡ Shortcut 1: Modulo Test for Base Solution

To find smallest $x_0 \ge 0$ for $ax + by = c$, test $ax \equiv c \pmod b$. For example, $5x + 8y = 120 \implies 5x \equiv 120 \equiv 0 \pmod 8 \implies x_0 = 0$.

⚡ Shortcut 2: Solution Count Bounds Rule

For co-prime $a, b$, the number of non-negative solutions to $ax + by = c$ is always $\lfloor c / (ab) \rfloor$ or $\lfloor c / (ab) \rfloor + 1$.

⚡

Interactive Diophantine Equation Solver

Enter coefficients $a, b$ and constant $c$ to compute GCD, test solvability & count all non-negative integer solution pairs $(x \ge 0, y \ge 0)$!

Coefficient a (for x):

Coefficient b (for y):

Constant c:

🎯 PRACTICE QUESTIONS (DIFFICULTY LEVEL-WISE)

EASY • LEVEL 0 NON-NEGATIVE SOLUTION COUNT

How many non-negative integral solutions $(x \ge 0, y \ge 0)$ exist for $5x + 8y = 120$?

MODERATE • LEVEL 1 POSITIVE INTEGER SOLUTIONS

Find the number of positive integer solutions ($x > 0, y > 0$) for $3x + 4y = 100$.

HARD • LEVEL 2 FROBENIUS COIN THEOREM

A restaurant sells chicken nuggets in packs of 7 and 11. What is the maximum number of nuggets that CANNOT be bought?

❓ FREQUENTLY ASKED QUESTIONS

Q: How to find the initial base solution (x₀, y₀) quickly under time pressure?

Use modulo arithmetic! For $ax + by = c$, test $ax \equiv c \pmod b$. Check $x = 0, 1, 2, \dots$ until $(c - ax)$ is divisible by $b$. Since step size is $b / \gcd(a,b)$, you will find $x_0$ within very few trials.

Q: What is the Chicken McNugget Theorem and when can it be used?

The Chicken McNugget Theorem (Frobenius Coin Problem) states that for two positive co-prime integers $a$ and $b$ ($\gcd(a, b) = 1$), the largest integer that CANNOT be expressed as $ax + by$ for non-negative integers $x, y \ge 0$ is $g(a, b) = ab - a - b$.

Q: How do positive solutions (x > 0, y > 0) differ from non-negative solutions (x ≥ 0, y ≥ 0)?

Non-negative solutions allow $x=0$ or $y=0$ (e.g. buying 0 units of an item). Positive solutions strictly require $x \ge 1$ and $y \ge 1$. This changes the parameter $k$ boundary conditions during counting.

Q: What happens if gcd(a, b) does not divide c?

By Bézout's Identity, if $\gcd(a, b)$ does NOT divide $c$, then $ax + by = c$ has **zero integer solutions**. You can immediately conclude 0 solutions without further calculation.

🔗 RELATED QUANT TOPICS

PREVIOUS CONCEPT

← Maxima & Minima

⏮️

NEXT CONCEPT

Algebraic Identities →

⏭️

PARENT MODULE

Quant Vault Index

📚