Even and Odd Integers; Divisibility

Parity is the smallest fact in mathematics that pays off the most often. Whether a number is even or odd is a single bit of information, but that one bit decides whether equations are solvable, whether games can be won, whether $\sqrt{2}$ is rational (it is not, and the proof is one parity argument). Divisibility is the same idea sharpened: instead of asking "is this a multiple of 2?" we ask "is this a multiple of $n$?" for any $n$ we like.

Definitions you can prove things with

An integer is even if it can be written as $2k$ for some integer $k$. It is odd if it can be written as $2k + 1$. These are not visual descriptions — they are algebraic forms, and that is what makes them useful for proofs. To show that the sum of two odd numbers is even, write the odds as $2m+1$ and $2n+1$, add them: $2m + 2n + 2 = 2(m + n + 1)$. The result has the form $2k$. Done.

The parity table

Memorise the rules, then forget them — the proofs above (and below for multiplication) recover any rule in a few seconds from the $2k$ and $2k+1$ definitions.

(Set the modulus to 2 in the widget above and type an integer — the clock face shows even (0) and odd (1) as two halves, and the hand sweeps to the right one. Change the modulus to 3, 5, or 12 to see divisibility by other numbers the same way.)

Divisibility: a generalised parity

We say $a$ divides $b$, written $a \mid b$, if there exists an integer $q$ with $b = aq$. Examples: $3 \mid 12$ because $12 = 3 \cdot 4$; $5 \mid 0$ because $0 = 5 \cdot 0$; but $3 \nmid 7$ because no integer $q$ gives $7 = 3q$.

Divisibility behaves the way you would hope: if $a \mid b$ and $a \mid c$, then $a$ also divides every "linear combination" $bm + cn$. And divisibility is transitive: $a \mid b$ and $b \mid c$ together force $a \mid c$. (When $a \mid b$ we call $a$ a divisor of $b$.)

The division algorithm — the engine

For any integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that $a = bq + r$ with $0 \leq r < b$. Every divisibility statement, every congruence-class argument, every modular-arithmetic identity that you will ever meet rests on this one theorem.

Try it

• Write the form $2k+1$ for the odd numbers $7, -3, 99$. What is $k$ in each case?
• Prove from the $2k$ form that the square of any even integer is divisible by $4$.
• Apply the division algorithm to $a = -23$, $b = 5$: find the unique $(q, r)$ with $0 \leq r < 5$.
• Is $6 \mid 9$? Is $9 \mid 6$? Why is divisibility not symmetric?

Try it in code

A trap to watch for

It is tempting to reverse the linear-combination rule: if $a \mid (b + c)$, surely $a \mid b$ and $a \mid c$? The converse is false. Try $a = 2$, $b = 1$, $c = 1$: then $b + c = 2$ and $2 \mid 2$, but $2 \nmid 1$. The brain makes the mistake because addition feels symmetric — if a factor "survives" the sum, it must have been present in each piece. It need not. The correct one-way statement: $a \mid b$ and $a \mid c$ together force $a \mid (bm + cn)$ for any integers $m, n$, but a divisor of the sum tells you nothing about the parts. The fix: before splitting a divisibility statement across an addition, write out the actual integer quotients explicitly.

What you now know

You can classify integers by parity and divisibility using algebraic forms (not visual hunches), and you can use the division algorithm to convert any divisibility question into a clean arithmetic test. The next section moves beyond $\mathbb{Z}$ to the rational numbers $\mathbb{Q}$, where division stops failing and the four laws keep working.

Quick check

References

• Lang, S. (1971). Basic Mathematics. Springer. Chapter 1, §4 — even / odd / divisibility framed as the first step into number theory.
• Hardy, G. H. and Wright, E. M. (2008). An Introduction to the Theory of Numbers, 6th ed. Oxford. Chapter 2 — the division algorithm proved cleanly with the well-ordering principle.
• Niven, I., Zuckerman, H., and Montgomery, H. (1991). An Introduction to the Theory of Numbers, 5th ed. Wiley. Chapter 1 — divisibility, GCD, and the Euclidean algorithm.