Number Theory I

and more generally with the integers:

Divisibility

a,b Z

a b

a b

7 35,  -3 21,  4 0   and (a + 1) a² - 1 for any integer a

but

7 33,  -3 22,  0 4.

If a b then we also say: a is a divisor (or factor) of b, or that: b is a multiple of a. For example, if b = 12 then the divisors (factors) of b are

a {±1, ±2, ±3, ±4, ±6, ±12}.

Aside: Don´t confuse the divides symbol: (which is a vertical stroke with a little space around it) with the slash symbol: / (which separates the numerator and denominator of a fraction). Also, note that despite the symmetry of the symbol: the symbol cannot be used in reverse, i.e. a b and b a mean different things (in fact, if they are both true then a = ± b).

Property 1. If a b and a c then a bx + cy for any integers x,y.

Proof: Suppose a b and a c. Then b = aq and c = ar for some integers q,r. So, for any integers x,y,

and qx + ry is an integer, and hence a bx + cy.

Summary of divisibility terms

a 0

• a divides b.
• a b.
• a is a divisor of b.
• a is a factor of b.
• b = aq for some integer q.
• b/a is an integer.
• b is divisible by a.
• b is a multiple of a.

Prime numbers

Aside: Notice that 1 is neither prime nor composite. In fact, 1 is called a unit (the technical term for a number that divides all integers).

Such a factorisation is called a prime decomposition.

Aside: If we were to include 1 as a prime then 74844 = 1⁵.2².3⁵.7.11, say, would be ``another prime decomposition''. Excluding 1 as a prime ensures the uniqueness of prime decompositions.

Fundamental theorem of arithmetic. Any natural number n, other than 1, can be written uniquely as follows:

where k is a natural number, each p_i is a prime number and 1 < p₁ < p₂ < ... < p_k, and each e_i is a natural number.

A fundamental property of primes is expressed in the following result:

Euclid's Lemma. If a prime p divides ab then p a or p b.

How can we decide whether a given, possibly quite large, natural number n is prime? Well ... if n is composite then n = ab for some natural numbers a,b such that neither a nor b is 1 or n; and either a = b = n or one of a or b is less than n. Thus, to show n is prime we need only show it has no prime divisors less than or equal to n.

Example 1. 97 is prime, since

• 2, 3, 5, 7 are the primes less than 10;
• 97 < 100 and 100 = 10² (we don´t need to find square - roots exactly!); and
• none of 2, 3, 5, 7 divides 97.

Remark. The primes less than 100 are:

This is easy to check, because at most we need only check divisibility by 2, 3, 5 and 7. Incidentally, there are 25 of them!

Greatest common divisor

Aside: If (a,b) = 1 then a,b are said to be relatively prime or coprime.

Aside: The difficulty of finding prime decompositions is exploited in many encryption algorithms.

Division Algorithm. For integers a,b with a 0 there exist integers q (the quotient) and r (the remainder) such that

b = aq + r and 0 r < a.

Essentially q,r are the numbers that make the following division work:

Let´s apply the Division Algorithm to a few examples:

Aside: Observe that r = 0 precisely when a b; and that r > 0 if a b.

• d also divides a - bm for any integer m;
• d = (a - bm,b) for any integer m;
• there are integers x,y such that d = ax + by.

Example 2. To find the gcd of 234 and 180, perform the following steps.

1. Draw 3 parallel vertical lines.
2. Write 234 and 180 in the two internal columns.
3. Divide the smaller number 180 into the larger 234. Write the quotient in the column adjacent to 234, and the remainder below 234.
4. Repeatedly divide back and forth in a similar way to Step 3. until one number divides (evenly) into the other. At this point that number is the gcd.

Here 180 was divided into 234, it went once remainder 54; then 54 was divided into 180, it went 3 times remainder 18; and 18 divides 54 (so we stop) ... and so 18 is the gcd of 234 and 180. \par Working backwards we can also find x,y such that 234x + 180y = 18:

So x = 4 and y = -3 is one possibility. All pairs x,y satisfy

for some integer t.

Aside: To see the existence of other pairs x,y satisfying 234x + 180y = 18, observe that

18	= 4.180 - 3.234
	= 4.180 - 3.234 + (234.180/18 )t -(234.180/18 )t
	= (4 + 234/18 t).180 + ( - 3 - 180/18 t).234
	= (4 + 13t).180 + ( - 3 - 10t).234.

Diophantine equations

What if the right - hand side of the above equation is not d? i.e. can we still solve

for x,y when c d? The question is answered by the theorem, below.

Aside: Equations of the form: ax + by = c are examples of Diophantine Equations (after Diophantus, an ancient Greek who was the first known to study them).

Lemma. If , are non - zero relatively prime integers then all integer solutions of X + Y = 0 for X,Y are of form

X	= t,
Y	= - t,

where t Z.

Proof: Assume , Z, , 0 and (,) = 1. Rearranging X + Y = 0, we obtain

Y = - X.

So - X, and since (,) = 1 we must have X, i.e. X = t for some integer t, whence Y = - t.

Theorem. Let a,b,c Z with a,b not both zero, and suppose d = (a,b). Then ax + by = c has a solution for x,y if and only if d c. Moreover, if a,b are both non - zero, d c, and x₀,y₀ is one solution of ax + by = c then all possible solution pairs are of form

x	= x0 + t
y	= y0 - t

where = a/d, = b/d and t Z. (A `starting solution' x₀,y₀ is

where q = c/d and x´,y´ is a solution of ax + by = d and may be obtained by applying the Euclidean Algorithm to a,b.)

Proof: If there is a solution then ax + by = c for some integers x,y. Now d a and d b, so d ax + by = c by Property 1. Now we prove the converse direction. Suppose d c (so that c = dq for some integer q). From the Euclidean Algorithm we can find integers x´,y´ such that

Hence

That is, a solution of ax + by = c exists (since x₀ = x´q, y₀ = y´q is a solution). Now let us find the general solution when solutions exist. Suppose x,y is a solution. Then we have

whence on subtracting the equations we obtain

and on dividing by d, we get

(x - x₀) + (y - y₀) = 0,

where = a/d, = b/d and we have , relatively prime and both non - zero. So by the lemma the general solution for x - x₀, y - y₀ is given by

x - x0	= t,
y - y0	= - t,

where t Z, which on rearranging gives the general solution stated in the theorem.

Aside: When giving the general solution in the case where d c, the theorem required that both a,b be non - zero ... but if one checks the given solutions still work if one or other of a,b is zero. So why include the restriction? ... The trouble is there are other solutions, e.g. suppose b = 0, i.e. we wish to solve ax + 0.y = c where d = a c. Then the solution for x is correct but notice it is just a complicated way of writing x = c/a, but y is allowed to be any integer (whereas the solution `suggests' some integers don't work ... depending on what choice you take for y₀).