Number theory (Further Pure 2)

Explanation

• The division theorem says that for integers $a$ and $b$ with $b>0$ there are unique integers $q$ and $r$ with $a=qb+r$ and $0\le r<b$; $q$ is the quotient and $r$ the remainder.
• The Euclidean algorithm applies it repeatedly: replace the pair $(a,b)$ by $(b,r)$ and repeat until the remainder is zero, at which point the last non-zero remainder is $\gcd(a,b)$.
• The algorithm works because $\gcd(a,b)=\gcd(b,r)$ whenever $a=qb+r$, which follows because any common divisor of $a$ and $b$ divides $r=a-qb$, and any common divisor of $b$ and $r$ divides $a=qb+r$.
• It terminates because the remainders form a strictly decreasing sequence of non-negative integers.
• Set the working out as a column of division statements: each line is a mark, and the same lines are read backwards later to produce Bezout's identity.

Explanation

• Bezout's identity states that for any integers $a$ and $b$, not both zero, there exist integers $x$ and $y$ with $ax+by=\gcd(a,b)$. The constructive proof is to run the Euclidean algorithm forwards and then read it backwards, substituting each remainder in terms of the two numbers above it until only $a$ and $b$ remain.
• The pair $(x,y)$ is not unique: adding $\dfrac{b}{\gcd(a,b)}$ to $x$ while subtracting $\dfrac{a}{\gcd(a,b)}$ from $y$ gives another solution, and every solution arises this way.
• Two consequences are examined constantly.
• First, $ax+by=c$ has integer solutions exactly when $\gcd(a,b)$ divides $c$.
• Second, if $\gcd(a,n)=1$ then $ax+ny=1$ for some $x$, so $ax\equiv1$ modulo $n$ and $x$ is the multiplicative inverse of $a$ modulo $n$.

Explanation

• Two integers $a$ and $b$ are congruent modulo a positive integer $n$, written $a\equiv b$ modulo $n$, when $n$ divides $a-b$; equivalently they leave the same remainder on division by $n$. Congruence modulo $n$ is reflexive, symmetric and transitive, so it splits the integers into $n$ residue classes.
• The key properties are that congruences may be added, subtracted and multiplied: if $a\equiv b$ and $c\equiv d$ modulo $n$ then $a+c\equiv b+d$, $a-c\equiv b-d$ and $ac\equiv bd$ modulo $n$.
• Raising to a power follows from repeated multiplication, so $a\equiv b$ gives $a^{k}\equiv b^{k}$.
• Division is the exception: $ac\equiv bc$ modulo $n$ permits cancelling $c$ only when $\gcd(c,n)=1$.
• The standard technique for a large power is to find a small exponent at which the base becomes congruent to $1$ or to $-1$, then reduce the exponent modulo that period.

Explanation

• Fermat's Little Theorem states that if $p$ is prime and $p$ does not divide $a$, then $a^{p-1}\equiv1$ modulo $p$.
• An equivalent form that needs no restriction on $a$ is $a^{p}\equiv a$ modulo $p$ for every integer $a$, since when $p$ divides $a$ both sides are congruent to $0$.
• The theorem turns a large power into a small one: to evaluate $a^{N}$ modulo a prime $p$, divide $N$ by $p-1$ and keep only the remainder, because $a^{N}=\left(a^{p-1}\right)^{q}a^{r}\equiv a^{r}$.
• It also gives inverses free of charge: if $p\nmid a$ then $a\times a^{p-2}=a^{p-1}\equiv1$, so $a^{p-2}$ is the multiplicative inverse of $a$ modulo $p$.
• Note that $p-1$ need not be the least exponent giving $1$; the true order of $a$ always divides $p-1$, which is why reducing modulo $p-1$ is safe even when a shorter cycle exists.

Explanation

• Divisibility tests all come from reducing the base $10$ modulo the divisor. Since $10\equiv1$ modulo $3$ and modulo $9$, every power of ten is congruent to $1$, so a number is congruent to its digit sum modulo $3$ and modulo $9$; that gives the digit-sum tests.
• Since $10\equiv-1$ modulo $11$, the powers of ten alternate between $1$ and $-1$, so a number is congruent to the alternating sum of its digits taken from the units end; that gives the test for $11$.
• For $2$, $4$ and $8$, note that $100$ and $1000$ are divisible by $4$ and $8$ respectively, so only the last one, two or three digits matter.
• A number is divisible by a product of coprime factors exactly when it is divisible by each factor, which is how the test for $6$ is built from the tests for $2$ and $3$.
• Always state the congruence for $10$ that your test rests on; that is where the marks are.

Explanation

• A linear congruence $ax\equiv b$ modulo $n$ has a solution if and only if $d=\gcd(a,n)$ divides $b$, and when it does there are exactly $d$ solutions modulo $n$.
• The method is to divide the whole congruence, modulus included, by $d$ to obtain $\dfrac{a}{d}x\equiv\dfrac{b}{d}$ modulo $\dfrac{n}{d}$, which has a unique solution because the new coefficient and modulus are coprime; find it by multiplying by the inverse of $\dfrac{a}{d}$, obtained from Bezout's identity or by inspection.
• The $d$ solutions modulo $n$ are then that residue together with the residues obtained by adding $\dfrac{n}{d}$ repeatedly.
• For a pair of simultaneous congruences with coprime moduli, substitute the general form of one into the other: write $x=a_{1}+n_{1}t$, impose the second congruence on $t$ and solve for $t$, which gives a single residue class modulo $n_{1}n_{2}$.

Explanation

• Two principles underpin every counting question. The multiplication principle says that if a choice can be made in $m$ ways and then a second, independent choice in $k$ ways, there are $mk$ ways in total.
• The addition principle says that mutually exclusive cases are counted by adding. From these, the number of ways to arrange $n$ distinct objects in a row is $n!$, the number of ordered selections of $r$ from $n$ is $^{n}P_{r}=\dfrac{n!}{\left(n-r\right)!}$, and the number of unordered selections is $^{n}C_{r}=\dfrac{n!}{r!\left(n-r\right)!}$.
• When objects repeat, divide by the factorial of each repeat count: $n$ objects with repeat counts $n_{1},n_{2},\dots$ arrange in $\dfrac{n!}{n_{1}!n_{2}!\cdots}$ ways.
• For arrangements in a circle, fix one object and arrange the rest, giving $\left(n-1\right)!$.
• Restrictions are handled either by treating a block of objects that must stay together as a single item, or by subtracting the unwanted arrangements from the total.