LEGACY Number Theory

Definition

Number theory is the study of systems and properties of numbers, particularly and .

A-Level Further Pure 2

Divisibility

Given two integers where , then we can say ( divides or is divisible by ) if an integer exists such that . If does not divide , it is denoted as . (This definition applies for negative divisors)

Divisibility rules

Division Algorithm

The division algorithm is a more rigorous way of defining division in the integers and is as follows:

Given that s.t with , To find the quotient and remainder for any two integers

1. Begin with values and
2. Set equal to the greatest integer that is
3. Set
4. ( is called the dividend, the divisor, the quotient, and the remainder)

Greatest Common Divisor and Bézout’s Identity

The greatest common divisor of and () is the greatest such that and .

You can find by using prime factors; however, a faster way for large numbers , is the Euclidean algorithm:

1. Apply the division algorithm to , to get . If , then and
2. If , then repeat the algorithm with and to get . If , then
3. If , then keep repeating the algorithm until you get where , then

Bezout’s Identity

The identity states that given

You can figure out and by going through the Euclidean Algorithm backwards and collecting like terms.

Coprime

Two integers , are coprime if so by Bezout’s Identity s.t

Modular Arithmetic

Modular arithmetic is a system of arithmetic restricted to the remainders.

Congruence

Definition , , , such that

Properties

Let and , with and

Number Bases

You can represent a number with digits in base as:

Divisibility Tests

In base 10 a number is divisible by

• 3 sum of digits is divisible by 3
• 4 last 2 digits are divisible by 4
• 9 sum of digits is divisible by 9
• 11 alternating sum of digits (starts with )

Solving Congruence Equations

Equations with modular arithmetic are given in terms called congruence equations and their answers are usually given in terms of least residues. The set of least residues is

Since a solution represents an infinite number of solutions, you can write a general solution as:

Congruence Equation Properties

Let ,

• the equation has no solutions
• the equation has solutions in the set of least residues

Multiplicative Inverses

A multiplicative inverse of is such that However You can find by using Bezout’s Identity Proof

Fermat’s Little Theorem

is prime and

Congruence equations with prime modulo can be solved with Fermat’s Little Theorem is prime ^ has one solution.

Combinatorics

If a set contains elements, then the total number of possible subsets of is . There are ! different ways of placing items in order. The number of possible permutations of items taken from a set of items, where , is given by

The number of permutations of items, of which are identical is given by The number of permutations of items, of which are identical, are identical, and so on, is given by

The number of possible combinations of items (in any order) taken from a set of items, where , is given by

---