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

Congruences, primes and integers

Definitions

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

Representation

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, .

Highest common factor

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 .

Coprime integers

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.

Euclidean algorithm

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 .

  1. Divide into and get a quotient and remainder:

  1. Divide into :

  1. Divide into :

  1. Divide into :

  1. 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.

Bézout's identity

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.

Divisibility of common factors

.

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 .

Lowest common multiple

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 .

Prime factorisation

Fundamental Theorem of Arithmetic

Let be an integer with . 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 .

Divisors of an integer

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 .

Finding the and of two numbers (in prime representation)

Let be integers with prime factorisations:

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

Congruence of integers

Definition

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

Example: and

Identities

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 .

Arithmetic modulo

The set of integers modulo is denoted as :

Multiplicative inverses

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

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

Chinese remainder theorem

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):

 ++
++
 ++
++

Which is what we want, so we can leave the section.

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:

 ++
++

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 .

Fermat's little theorem

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.