Number Theory

Number bases

Decimal numbers are written in base 10: .
For an arbitrary base , , where the subscript 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 means that divides , or is a factor of , or is a multiple of .

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 for divisibility by prime , let or .
Then, choose an and such . and must be coprime, so then .
Set up iteration , , and iterate until is small enough to easily test for divisibility by .

Division algorithm

The division algorithm (or Euclid's division lemma) states that for any pair of integers and with , can be uniquely expressed as:

Where is the quotient and is the remainder, with .

Modular arithmetic

From the division algorithm, a number can be expressed as , where is the quotient and is the remainder. In modular arithmetic, this can be written as .

Two numbers and are congruent modulo () if they have the same remainder when divided by . Equivalently, and are congruent modulo if their difference is divisible by .

Rules

For and :

: Adding congruent values to both sides works
: Subtracting congruent values to both sides works
: Multiplying congruent values to both sides works
for , : Raising to a power on both sides works
If is a polynomial in with integer coefficients, .
If and and and are coprime,

Note that generally division does not work. But, if , and , then . That is, you can divide by a value coprime to the modulo.

Solving linear congruences

A linear congruence is an equation of the form . It has a solution if and only if , where . There are solutions given by:
Where is a solution found by inspection, and ^[1].

The conditions for solutions are:

If , then the congruence has a unique solution.
If and does not divide , the congruence has no solutions.
If and does divide , there are solutions.

To find a solution :

If or , replace them with their remainder modulo .
To change the sign of either side, both sides can be multiplied by , or multiples of added to either side.
If and have a common factor that is coprime to , this can be cancelled.
If , , and all have a common factor, this can be cancelled (changing the modulo of the congruence). This happens when .
Get the coefficient on 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 form, then substituting and solving as usual.

For two simultaneous linear congruences to have a solution:

Each congruence individually must be solvable
If and then there exists a solution only if .
Proof
- ,
- Equating gives
- Rearranging gives .
- The RHS has a factor of , 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 is a such that there is a solution to:

If the congruence has no solutions, then is a quadratic non-residue. All the quadratic residues mod 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 , if and , then .
Alternatively, if is a prime and , must divide at least one of or .

Integer combinations

An integer combination of integers and is any integer of form for integer values of and . If and , then :

If then for some
If then for some

Because is a factor of and , any integer combination of and is a multiple of . We can now use this result to prove coprimality.

If for some and , then , implying and are coprime if . The converse is also true:

Assume and are coprime.
This means has a unique solution. Suppose this solution is .
. This means for some .
Rearranging, we get for some and . Thus, there is some integer combination of and equal to 1.

These two results give us:

Two integers and are coprime if and only if there are two integers and such that .
The highest common factor of and can be found by finding the smallest possible integer written as ^[2].

Fermat's Little Theorem

Fermat's Little Theorem states that for prime , for any integer , is a multiple of :

Alternatively, Fermat's Little Theorem also states that for prime and coprime:

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

Order of modulo

The order of modulo is the smallest integer such that . This only exists if and . Fermat's little theorem states that would satisfy this congruence, but is not necessarily the least value of . Also, ^[3].

The binomial theorem

The modular binomial theorem states that:

Proof
Consider the binomial expansion:

Consider the binomial coefficient for all values of other than and :

This coefficient will have a factor of from the numerator (provided and ). Thus, all the 'middle' terms of the expansion will be congruent to 0 mod , giving the desired result.

Footnote on solving linear congruences
Once you have one solution the rest is fairly simple - the whole thing just means adding multiples of to get the other solutions. Try it out a few times, and take a look at the exercises on Integral.↩︎
Footnote on finding highest common factor using
No proof provided, but its kinda obvious? has to have a factor of , so the smallest (nonnegative, integer) value of is going to be itself.↩︎
Footnote on , the order of modulo dividing .
This result actually isn't trivial?
so for some integer .
By Fermat's Little Theorem, so . (this actually isn't fully sound but whatever)↩︎