📐 Euclidean Division

Euclidean division is the process of dividing one integer by another to obtain a quotient and a remainder, satisfying:

$$ a = bq + r \quad \text{where} \quad 0 \le r < |b| $$

This is not fractional division—it’s about decomposing integers.

Let’s divide $a = 17$ by $b = 5$:

$$ 17 = 5 \cdot 3 + 2 $$

✅ Check: $0 \le 2 < 5$

Dividend $a$	Divisor $b$	Quotient $q$	Remainder $r$	Equation
17	5	3	2	$17 = 5 \cdot 3 + 2$
-17	5	-4	3	$-17 = 5 \cdot (-4) + 3$
23	-4	-6	-1	$23 = (-4) \cdot (-6) + (-1)$

ℹ️ The remainder always satisfies $0 \le r < |b|$, regardless of the signs of $a$ or $b$.

Uniqueness: For any integers $a$ and $b \ne 0$, there exists a unique pair $(q, r)$ such that: $$ a = bq + r \quad \text{with} \quad 0 \le r < |b| $$
Used in:
- Modular arithmetic: $a \mod b = r$
- Euclidean algorithm for GCD
- Integer division logic in programming

function euclidean_division(a, b):
    q = floor(a / b)
    r = a - b * q
    return (q, r)

🧠 floor(a / b) ensures the remainder is non-negative and less than |b|.

Consider adding a number line diagram showing: