Linear Diophantine

🎯 Linear Diophantine Equations: The Treasure Hunt for Whole Numbers

Imagine you have a treasure chest that can only be opened with whole coins—no cutting coins in half! That’s what Diophantine equations are all about.

🌟 What is a Diophantine Equation?

Think of it like this: You’re at a fair with only whole tickets. You can’t tear a ticket in half!

A Diophantine equation is a math puzzle where we only want whole number answers (like 1, 2, 3… or -1, -2, -3…). No fractions. No decimals. Just clean, complete numbers.

Why “Diophantine”?

Named after Diophantus, an ancient Greek mathematician who loved puzzles with whole numbers. He lived around 250 AD—that’s almost 1,800 years ago! 🏛️

🎪 LINEAR Diophantine Equations

What Makes It “Linear”?

Linear means our numbers are simple—no squares, no cubes, just plain numbers multiplied together.

Linear:     3x + 5y = 22  ✅
Not Linear: x² + y = 10  ❌

The Standard Form

Every linear Diophantine equation looks like this:

ax + by = c

Where:

• a, b, c = known whole numbers
• x, y = the mystery numbers we want to find

🍎 Real-Life Example: The Apple Problem

You have $22 to spend. Apples cost $3 each. Bananas cost $5 each.

3x + 5y = 22

• x = number of apples
• y = number of bananas

Can you spend exactly $22 buying only whole fruits? 🤔

🔑 The Secret Key: GCD (Greatest Common Divisor)

Before solving, we need a magic tool: the GCD.

What is GCD?

The biggest number that divides two numbers evenly.

GCD(12, 8) = 4
Because: 12 ÷ 4 = 3 ✓
         8 ÷ 4 = 2 ✓

The Golden Rule 🏆

A linear Diophantine equation ax + by = c has a solution ONLY if GCD(a, b) divides c evenly.

graph TD
    A["Start: ax + by = c"] --> B["Find GCD of a,b"]
    B --> C{Does GCD divide c?}
    C -->|Yes ✓| D["Solution EXISTS!"]
    C -->|No ✗| E["NO solution possible"]

Example: Does a Solution Exist?

Equation: 6x + 9y = 15

1. Find GCD(6, 9) = 3
2. Does 3 divide 15? → 15 ÷ 3 = 5 ✓
3. Yes! A solution exists!

Equation: 6x + 9y = 17

1. Find GCD(6, 9) = 3
2. Does 3 divide 17? → 17 ÷ 3 = 5.67… ✗
3. No solution possible!

🛠️ HOW TO SOLVE: Step-by-Step

Let’s solve: 3x + 5y = 22

Step 1: Check if Solution Exists

• GCD(3, 5) = 1 (they share no common factors)
• Does 1 divide 22? → Yes! (1 divides everything)
• ✅ Solution exists!

Step 2: Find ONE Solution (Trial Method)

Try small values:

Found! x = 4, y = 2

Check: 3(4) + 5(2) = 12 + 10 = 22 ✓

Step 3: Find ALL Solutions

Once you have one solution, you can find infinitely many!

The Magic Formula:

x = x₀ + (b/d) × t
y = y₀ - (a/d) × t

Where:

• (x₀, y₀) = your first solution
• d = GCD(a, b)
• t = any whole number (…-2, -1, 0, 1, 2…)

For Our Example:

• First solution: x₀ = 4, y₀ = 2
• a = 3, b = 5, d = GCD(3,5) = 1

x = 4 + 5t
y = 2 - 3t

Infinite solutions! 🎉

🧮 The Extended Euclidean Algorithm

For bigger numbers, use this powerful method!

What is it?

A way to “work backwards” from the GCD to find x and y.

Example: Solve 35x + 15y = 5

Step 1: Find GCD using Euclidean Algorithm

35 = 15 × 2 + 5
15 = 5 × 3 + 0

GCD = 5 ✓ (and 5 divides 5, so solution exists!)

Step 2: Work Backwards

From: 35 = 15 × 2 + 5

Rearrange: 5 = 35 - 15 × 2

So: 5 = 35(1) + 15(-2)

Solution: x = 1, y = -2

Check: 35(1) + 15(-2) = 35 - 30 = 5 ✓

🎯 Positive Solutions Only

Sometimes we need only positive answers (can’t buy -3 apples!).

Example: 3x + 5y = 22 (Positive Solutions)

General solution: x = 4 + 5t, y = 2 - 3t

For both x AND y positive:

x > 0  →  4 + 5t > 0  →  t > -0.8
y > 0  →  2 - 3t > 0  →  t < 0.67

So: -0.8 < t < 0.67

Only whole number in this range: t = 0

Only positive solution: x = 4, y = 2

You can buy 4 apples and 2 bananas! 🍎🍌

🎮 Quick Practice

Problem 1:

Does 4x + 6y = 9 have a solution?

Problem 2:

Find one solution for 7x + 3y = 20

🏆 Key Takeaways

graph TD
    A["Linear Diophantine: ax + by = c"] --> B["Step 1: Find GCD"]
    B --> C["Step 2: Check if GCD divides c"]
    C --> D["Step 3: Find one solution"]
    D --> E["Step 4: Write general solution"]
    E --> F["Step 5: Find specific solutions needed"]

Remember These Rules:

1. ✅ Solution exists only if GCD(a,b) divides c
2. 🔢 Once you find one solution, you can find infinitely many
3. 📐 General formula: x = x₀ + (b/d)t, y = y₀ - (a/d)t
4. ➕ For positive-only solutions, find valid range for t

🌈 Why This Matters

Diophantine equations appear everywhere:

• 🪙 Making change with specific coin values
• 📦 Packing boxes of fixed sizes
• 🔐 Cryptography and computer security
• 🎵 Music theory and rhythm patterns

You’ve just learned a tool that mathematicians have used for almost 2,000 years! 🎉

“The solution exists only when the pieces fit perfectly—like a puzzle waiting to be solved.” 🧩