Prime Numbers & Primality

A positive integer $n>1$ is prime if its only positive divisors are 1 and $n$; otherwise it is composite.

• $1$ is neither prime nor composite — it has exactly one divisor.
• $2$ is the only even prime, which is why parity arguments are so powerful here.
• There are 25 primes below 100, and 15 below 50.
• Two numbers are coprime (relatively prime) when their HCF is 1; neither needs to be prime.

To test $n$: divide by each prime $p$ with $p \le \sqrt{n}$. If none divides $n$, then $n$ is prime.

• Only primes need testing, since any composite divisor carries a smaller prime one.
• Useful square-root landmarks: $\sqrt{400}=20$, $\sqrt{900}=30$, $\sqrt{1600}=40$, $\sqrt{2500}=50$.

So a three-digit number needs primes only up to 31, and a number below 2500 only up to 47.

The argument in its usual forms:

• Odd total. A sum of two primes is odd only if one of them is even, i.e. equals 2.
• Odd count. Three odd primes sum to an odd number; if the target is even, one prime is 2.
• Even product. If a product of primes is even, one factor is 2.
• Both sum and difference prime. If $x$ and $y$ are odd primes then $x+y$ and $x-y$ are both even, and they cannot both be 2 — so one of $x, y$ is 2.

$a$ and $b$ are coprime when $\gcd(a,b)=1$.

• Consecutive integers are always coprime: any common divisor divides their difference, which is 1.
• If $p$ is coprime to both $q$ and $r$, it is coprime to $qr$ — no new prime factor appears in a product.
• Euclid's lemma: if a prime $p$ divides $qr$ then $p \mid q$ or $p \mid r$. This needs $p$ prime: $4 \mid 2\times 6$ but $4$ divides neither.
• If $a \mid cd$ and $\gcd(a,c)=1$, then $a \mid d$.

The distinction that matters is direction:

• Every prime greater than 3 is of the form $6n\pm1$ — that direction is true.
• But a number of the form $6n\pm1$ need not be prime. The converse fails, and confusing the two directions is the whole trap.

Twin primes are pairs differing by 2; a prime triple spaced by 2 exists only once, as $3,5,7$.

Every integer above 1 factorises into primes in exactly one way (the fundamental theorem of arithmetic). Procedure: try $2, 3, 5, 7, 11, 13, \ldots$ in turn, dividing out each prime as many times as it goes, and stop when the remaining quotient is less than the square of the next prime — the quotient is then prime. The alternating-sum test for 11 is worth having ready here, because 11 is the first divisor that no other quick rule catches.