Direct Proof

Prove: if $a \mid b$ and $b \mid c$ then $a \mid c$. Proof. Since $a \mid b$, $b = ak$ for some integer $k$; since $b \mid c$, $c = bm$ for some integer $m$. Then $c = (ak)m = a(km)$, and $km$ is an integer, so $a \mid c$. $\blacksquare$

Prove: for real $x, y$, $x^2 + y^2 \ge 2xy$. Proof. $(x - y)^2 \ge 0$ because squares are non-negative. Expanding, $x^2 - 2xy + y^2 \ge 0$, so $x^2 + y^2 \ge 2xy$. $\blacksquare$ (Written forwards. It was found backwards: start from the goal, subtract, recognize a square.)

Prove: for real $a, b \ge 0$, $\dfrac{a + b}{2} \ge \sqrt{ab}$. Proof. Because $a, b \ge 0$, the numbers $x = \sqrt a$ and $y = \sqrt b$ are real. Apply the previous inequality to them: $x^2 + y^2 \ge 2xy$, that is, $a + b \ge 2\sqrt{ab}$. Divide by $2$. $\blacksquare$

Case 1: $n = 2k$. Then $n^2 + n = 4k^2 + 2k = 2(2k^2 + k)$, even. Case 2: $n = 2k + 1$. Then $n^2 + n = n(n + 1) = (2k + 1)(2k + 2) = 2(2k + 1)(k + 1)$, even. Both cases give even; every integer is in one of them. $\blacksquare$

Claim: every perfect square leaves remainder $0$ or $1$ on division by $4$. Case $n = 2k$: $n^2 = 4k^2$, remainder $0$. Case $n = 2k + 1$: $n^2 = 4(k^2 + k) + 1$, remainder $1$. $\blacksquare$ Consequence: a sum of two squares leaves remainder $0$, $1$ or $2$, never $3$. So $4003$, which leaves remainder $3$, is not a sum of two squares — proved without trying a single pair.

Claim: if $3 \mid a^2 + b^2$, then $3 \mid a$ and $3 \mid b$. First, cases on $a$ mod $3$: if $a = 3k$ then $a^2 = 9k^2$ leaves remainder $0$; if $a = 3k \pm 1$ then $a^2 = 9k^2 \pm 6k + 1$ leaves remainder $1$. So each of $a^2, b^2$ leaves remainder $0$ or $1$, and their sum leaves $0$, $1$ or $2$. It leaves $0$ only when both leave $0$, which happens only when $3 \mid a$ and $3 \mid b$. $\blacksquare$

Prove: if $7 \mid a$ and $7 \mid b$, then $7 \mid 3a - 5b$. Proof. Write $a = 7k$ and $b = 7m$. Then $3a - 5b = 21k - 35m = 7(3k - 5m)$, a multiple of $7$. $\blacksquare$

Prove: $\gcd(n, n + 1) = 1$ for every positive integer $n$. Proof. Let $d$ be a positive common divisor. By the combination rule $d$ divides $(n + 1) - n = 1$, so $d = 1$. $\blacksquare$

Prove: for every positive integer $n$, the fraction $\dfrac{5n + 3}{3n + 2}$ is in lowest terms. Proof. Let $d$ divide both $5n + 3$ and $3n + 2$. Then $d$ divides $3(5n + 3) - 5(3n + 2) = 15n + 9 - 15n - 10 = -1$. So $d = 1$, and the numerator and denominator have no common factor. $\blacksquare$

Claim: the difference of the squares of two consecutive odd numbers is divisible by $8$. Proof. Let the numbers be $2k + 1$ and $2k + 3$, with $k$ an integer. Then $(2k + 3)^2 - (2k + 1)^2 = (4k^2 + 12k + 9) - (4k^2 + 4k + 1) = 8k + 8 = 8(k + 1)$, which is divisible by $8$. $\blacksquare$ (Check: $7^2 - 5^2 = 24 = 8\cdot3$.)