Number Theory

Number bases

Decimal numbers are written in base 10: $2025=2\times 10^3+0\times 10^2+2\times 10^1+5\times 10^0$. For an arbitrary base $n$, $2025_n=2\times n^3+0\times n^2+2\times n+5\times n^0$, where the subscript $n$ denotes the base of the number. Binary (base 2) numbers use digits 0 and 1, while hexadecimal (base 16) numbers use digits 0-9 and A-F.

Divisibility

The notation $a|b$ means that $a$ divides $b$, or $a$ is a factor of $b$, or $b$ is a multiple of $a$.

Standard divisibility tests

A number is divisible by 3 if the sum of its digits is divisible by 3. A number is divisible by 4 if the last 2 digits are divisible by 4. A number is divisible by 5 if the last digit is divisible by 5. A number is divisible by 8 if the last 3 digits are divisible by 8. A number is divisible by 9 if the sum of the digits is divisible by 9. A number is divisible by 11 if the sum of digits with alternating signs is divisible by 11.

Prime divisibility algorithm

To test a large number $N$ for divisibility by prime $p$, let $N=10a+b$ or $100a+b$. Then, choose an $M$ and $k$ such $p|(N+kM)$. $k$ and $p$ must be coprime, so then $p|N⟺p|M$. Set up iteration $M_0=N$, $M_{n+1}=f(M_n)$, and iterate until $M$ is small enough to easily test for divisibility by $p$.

Division algorithm

The division algorithm (or Euclid’s division lemma) states that for any pair of integers $a$ and $b$ with $0<b\le a$, $a$ can be uniquely expressed as:

$$a=bq+r$$

Where $q$ is the quotient and $r$ is the remainder, with $0\le r<b$.

Modular arithmetic

From the division algorithm, a number $a$ can be expressed as $a=bq+r$, where $q$ is the quotient and $r$ is the remainder. In modular arithmetic, this can be written as $a\equiv r(\mathrm{mod}n)$.

Two numbers $a$ and $b$ are congruent modulo $n$ ($a\equiv b(\mathrm{mod}n)$) if they have the same remainder when divided by $n$. Equivalently, $a$ and $b$ are congruent modulo $n$ if their difference is divisible by $n$.

Rules

For $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$:

• $a+c\equiv b+d(\mathrm{mod}m)$: Adding congruent values to both sides works
• $a-c\equiv b-d(\mathrm{mod}m)$: Subtracting congruent values to both sides works
• $ac\equiv bd(\mathrm{mod}m)$: Multiplying congruent values to both sides works
• $a^k\equiv b^k(\mathrm{mod}m)$ for $k\in \mathbb{Z}$, $k\ge 0$: Raising to a power on both sides works
• If $f(x)$ is a polynomial in $x$ with integer coefficients, $f(a)\equiv f(b)(\mathrm{mod}m)$.
• If $a\equiv b(\mathrm{mod}m)$ and $a\equiv b(\mathrm{mod}n)$ and $m$ and $n$ are coprime, $a\equiv b(\mathrm{mod}mn)$

Note that generally division does not work. But, if $ka\equiv kb(\mathrm{mod}n)$, and $hcf(k,n)=1$, then $a\equiv b(\mathrm{mod}n)$. That is, you can divide by a value coprime to the modulo.

Solving linear congruences

A linear congruence is an equation of the form $ax\equiv b(\mathrm{mod}n)$. It has a solution if and only if $d|b$, where $d=\text{DeclareMathOperator}hcfhcf\text{hcf}(a,n)$. There are $d$ solutions given by: $x_1+\frac{n}{d}\times r$ Where $x_1$ is a solution found by inspection, and $r=0,1,2,\dots ,d-2$¹.

The conditions for solutions are:

• If $\text{hcf}(a,n)=1$, then the congruence has a unique solution.
• If $\text{hcf}(a,n)=d$ and $d$ does not divide $b$, the congruence has no solutions.
• If $\text{hcf}(a,n)=d$ and $d$ does divide $b$, there are $d$ solutions.

To find a solution $x_1$:

• If $a\ge n$ or $b\ge n$, replace them with their remainder modulo $n$.
• To change the sign of either side, both sides can be multiplied by $-1$, or multiples of $n$ added to either side.
• If $a$ and $b$ have a common factor that is coprime to $n$, this can be cancelled.
• If $a$, $b$, and $n$ all have a common factor, this can be cancelled (changing the modulo of the congruence). This happens when $\text{hcf}a,n|b$.
• Get the coefficient on $x$ to be 1.

Simultaneous linear congruences

Simultaneous linear congruences are a system of multiple linear congruences. They can be solved by rewriting the congruence in $x=na+b$ form, then substituting and solving as usual.

For two simultaneous linear congruences to have a solution:

• Each congruence individually must be solvable
• If $x\equiv a(\mathrm{mod}n)$ and $x\equiv b(\mathrm{mod}m)$ then there exists a solution only if $\text{hcf}(m,n)|(b-a)$. Proof
  • $x=k_{1}n+a$, $x=k_{2}m+b$
  • Equating gives $k_{1}n+a=k_{2}m+b$
  • Rearranging gives $(a-b)=k_{1}n-k_{2}m$.
  • The RHS has a factor of $\text{hcf}(m,n)$, so the LHS must as well.

For three simultaneous linear congruences to have a solution:

• If all three moduli are coprime then there will be a unique solution.
• If each pair of linear congruences has a solution then there will be a solution.

Quadratic residues

A quadratic residue mod $n$ is a $q$ such that there is a solution to:

$$x^2\equiv q(\mathrm{mod}n)$$

If the congruence has no solutions, then $q$ is a quadratic non-residue. All the quadratic residues mod $n$ can be found using a table. Such a table has symmetry in the values.

Prime numbers

Fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or a unique product of primes.

Euclid’s lemma

A pair of integers are coprime if they have no common factors other than 1. Euclid’s lemma states that:

• For any integers $r,a,b$, if $r|ab$ and $\text{hcf}(r,a)=1$, then $r|b$.
• Alternatively, if $p$ is a prime and $p|ab$, $p$ must divide at least one of $a$ or $b$.

Integer combinations

An integer combination of integers $b$ and $c$ is any integer of form $bx+cy$ for integer values of $m$ and $n$. If $a|b$ and $a|c$, then $a|(bx+cy)$:

• If $a|b$ then $b=k_{1}a$ for some $k_1$
• If $a|c$ then $c=k_{2}a$ for some $k_2$
• $bx+cy=k_{1}a+k_{2}a=a(k_1+k_2)⟹a|(bx+cy)$

Because $\text{hcf}(b,c)$ is a factor of $b$ and $c$, any integer combination of $b$ and $c$ is a multiple of $\text{hcf}(b,c)$. We can now use this result to prove coprimality.

If $bx+cy=1$ for some $x$ and $y$, then $\text{hcf}(b,c)=1$, implying $b$ and $c$ are coprime if $bx+cy=1$. The converse is also true:

• Assume $b$ and $c$ are coprime.
• This means $bx\equiv 1(\mathrm{mod}c)$ has a unique solution. Suppose this solution is $n$.
• $bn\equiv 1(\mathrm{mod}c)⟹bn-1\equiv 0(\mathrm{mod}c)$. This means $bn-1=kc$ for some $k$.
• Rearranging, we get $nb-kc=1$ for some $n$ and $k$. Thus, there is some integer combination of $b$ and $c$ equal to 1.

These two results give us:

• Two integers $b$ and $b$ are coprime if and only if there are two integers $x$ and $y$ such that $bx+cy=1$.
• The highest common factor of $b$ and $c$ can be found by finding the smallest possible integer written as $bx+cy$².

Fermat’s Little Theorem

Fermat’s Little Theorem states that for prime $p$, for any integer $a$, $a^p-a$ is a multiple of $p$:

$$a^p\equiv a(\mathrm{mod}p)\text{for prime }p$$

Alternatively, Fermat’s Little Theorem also states that for prime $p$ and $a,p$ coprime:

$$a^{p-1}\equiv 1(\mathrm{mod}p)\text{for prime }p,\text{hcf}(a,p)=1$$

It does not follow that if this result is true that $p$ is necessarily prime. If $x$ is a composite number and this result is true, then $x$ is a pseudo-prime.

Order of $a$ modulo $p$

The order of $a$ modulo $p$ is the smallest integer $n$ such that $a^n\equiv 1(\mathrm{mod}p)$. This only exists if $\text{hcf}(a,p)\equiv 1$ and $a\ne 1$. Fermat’s little theorem states that $p-1$ would satisfy this congruence, but $p-1$ is not necessarily the least value of $n$. Also, $n|(p-1)$³.

The binomial theorem

The modular binomial theorem states that:

$$(a+b{)}^p=a^p+b^p(\mathrm{mod}p)\text{for prime }p$$

Proof Consider the binomial expansion:

$$(a+b{)}^p=a^p+(\genfrac{}{}{0ex}{}{p}{1})a^{p-1}b+\cdots +(\genfrac{}{}{0ex}{}{p}{p-1})a{b}^{p-1}+b^p$$

Consider the binomial coefficient $\left(\genfrac{}{}{0ex}{}{p}{k}\right)$ for all values of $k$ other than $0$ and $p$:

$$\left(\genfrac{}{}{0ex}{}{p}{k}\right)=\frac{p!}{(p-k)!k!}$$

This coefficient will have a factor of $p$ from the numerator (provided $k\ne 0$ and $k\ne p$). Thus, all the ‘middle’ terms of the expansion will be congruent to 0 mod $p$, giving the desired result.

Footnotes

1. Footnote on solving linear congruences Once you have one solution $x_1$ the rest is fairly simple - the whole $\frac{n}{d}\times r$ thing just means adding multiples of $\frac{n}{d}$ to get the other solutions. Try it out a few times, and take a look at the exercises on Integral. ↩

2. Footnote on finding highest common factor using $bx+cy$ No proof provided, but its kinda obvious? $bx+cy$ has to have a factor of $\text{hcf}(a,b)$, so the smallest (nonnegative, integer) value of $bx+cy$ is going to be $\text{hcf}(a,b)$ itself. ↩

3. Footnote on $n$, the order of $a$ modulo $p$ dividing $p-1$. This result actually isn’t trivial? $a^n\equiv 1(\mathrm{mod}p)$ so $a^{nq}\equiv 1(\mathrm{mod}p)$ for some integer $q$. By Fermat’s Little Theorem, $a^{p-1}\equiv 1$ so $nq=p-1$. (this actually isn’t fully sound but whatever) ↩