Congruences, primes and integersDefinitionsRepresentationHighest common factorCoprime integersEuclidean algorithmBézout's identityDivisibility of common factorsLowest common multiplePrime factorisationFundamental Theorem of ArithmeticDivisors of an integer Finding the and of two numbers (in prime representation)Congruence of integersDefinitionIdentitiesArithmetic modulo Multiplicative inversesChinese remainder theoremFermat's little theorem

Let . We say divides if for some . When divides , we write .

The integer is called the quotient, and is the remainder.

Example: If and , then the equation is .

The quotient is and the remainder .

Example: Let and suppose that and . Then for any .

Proof: Let and with . Then for :

Hence, .

Let . A **common factor** of and is an integer that divides both and . The **highest common factor** (or greatest common divisor) of and , written , is the largest positive integer that divides both and .

Example: and .

Two integers and are said to be coprime if their highest common factor is . For example, and are coprime.

Note that coprime integers need not be prime.

The **Euclidean algorithm** is a step-by-step method for calculating the common factors of two integers. Like most algorithms, the definition of the euclidean algorithm can be often displayed as pseudocode, but it may be easier to look at an example:

Example: Find .

First, we write , and let .

- Divide into and get a quotient and remainder:

- Divide into :

- Divide into :

- Divide into :

- Divide into :

We stop here as we have reached a remainder of .

We now claim that .

To prove this, we work backwards. Step 5 shows that , hence Step 4 shows that , and so on, until Step 2 shows that and Step 1 shows that .

Therefore our claim that was right.

Example: From the previous example, we know that , so by Bézout's identity . To find such integers and , we use the steps from the Euclidean algorithm that we performed to find previously. We start from the penultimate step:

Step 4:

Step 3:

Step 2:

Step 1:

Thus, we have found our integers and . Note that there will be many other values of and which will also work.

.

Proof: Let . By Bézout's identity, . If is a common factor of and , then divides (any linear combination of and . By the same idea as the second example in the Representation section above), and hence divides .

Let . A **common multiple** of and is an integer which is a multiple of both and . The **lowest common multiple** of and , written , is the smallest positive integer that is a multiple of both and .

Let be an integer with . Then:

is equal to a product of prime numbers:

where is a prime and .

This prime factorisation of is unique. In other words, if:

where the s and s are all primes such that and , then

Alternatively, it may be the case that some of the s are equal to each other. If we collect these up, we obtain a prime factorisation of form:

Where and .

Let where s are prime, and and the s are positive integers. If divides , then:

with .

Example: The only divisors of are the numbers , where and .

Let be integers with prime factorisations:

where the are distinct primes and all . Note that some of the and can be 0. Then:

Let . For , if divides we write and say is congruent to modulo .

Example: and

Let be a positive integer. The following are true :

Suppose and . Then:

If and is a positive integer, then .

Example: Find the remainder when is divided by .

The remainder is .

The set of integers modulo is denoted as :

The **multiplicative inverse** of an integer is another integer such that .

If and , then has a multiplicative inverse (and it is unique ).

Let be pairwise coprime positive integers greater than and be arbitrary integers. Then the system:

has a unique solution modulo .

Example:

We will work out the sum in three sections:

+ + + + Consider the first section, . We want to ignore the other sections (when considering the first section), by making them congruent to . We can do this by including in their sections, since .

+ + + + Do the same for sections and (by multiplying):

+ + + +

+ + + +

- In , we would have:
Which is what we want, so we can leave the section.

- In , we would have:
But we need . If we multiply by , we get . We can then multiply by to get .

So we need to add and to the middle section:

+ + + +

- In , we would have:
But we need . If we multiply by , we get as required, so we need to add a to the last section in the table:

+ + + + Giving us . Note that this isn't the only solution. We could have where is any positive or negative integer. A nicer looking solution would be when , we have .

Let be a prime number, and let be an integer that is not divisible by . Then

Example: , and .

Example: Find .

Fermat's Little Theorem tells us that . Dividing into , we get , so:

So we only need to work out , which can be done by the method of successive squares.