Real Numbers: Euclidean Algorithm

Euclid's Division Lemma

Given positive integers a and b, there exist unique integers q and r satisfying:

a = bq + r, where 0 ≤ r < b

This is essentially a restatement of the long division process:

• Dividend = Divisor × Quotient + Remainder

Proving Irrationality

A classic Class 10 problem is proving that √2, √3, or √5 is irrational. This is done using the method of Contradiction.

1. Assume √2 is rational (a/b where a,b are co-prime).
2. Square both sides: 2 = a²/b² ⇒ 2b² = a².
3. This implies 2 divides a.
4. Substitute a = 2c... proves 2 also divides b.
5. Contradiction! (They share a factor of 2, so not co-prime).