In a Republic Day parade, 594 cadets are to march behind a band of 189 players. Both groups must march in the same number of columns, and every column must be full. What is the greatest number of columns possible?

**Method**: proof by contradiction.

1. Suppose $\sqrt{2}$ IS rational. Then $\sqrt{2}=\frac{p}{q}$ for some integers $p,q$ (with $q$ ≠ 0) and gcd$(p$, q) = 1 (lowest terms).
2. Square both sides: $2=\frac{p^2}{q^2}$ → $p^2=2q^2$.
3. So $p^2$ is EVEN, hence $p$ is even. Write $p=2k$.
4. Substitute: $(2k{)}^2=2q^2$ → $4k^2=2q^2$ → $q^2=2k^2$.
5. So $q^2$ is even, hence $q$ is even.
6. But then BOTH $p$ and $q$ are even — they share a factor of 2 — contradicting gcd$(p$,q) = 1.
7. Contradiction → $\sqrt{2}$ is NOT rational. ∎

The same proof technique works for $\sqrt{3},\sqrt{5},\sqrt{7}$, … (any prime under the root).