Archive for December, 2011

Euclid’s Algorithm

December 30, 2011

Suppose that a and b are integers with b non-zero.  If there is an integer q such that a = qb, then we say that b divides a.

We can visualise the real numbers as lying in increasing order from left to right along a line.  If b is some non-zero integer, then the integers qb, where q runs through all the integers, divide the number line into segments of length |b| and all real numbers other than the qb lie inside one of these segments. Thus we can regard the following as self-evident:

Proposition (The Division Identity): If s is some real number and b is a non-zero integer, then either s = qb for some integer q (b divides s) or there is a unique integer q such that qb < s < qb + |b|.

Any integer that divides each of the integers m and n is called a common divisor or common factor of m and n. If m,n are not both zero we can assume that the set of all common divisors of m and n has a greatest member which is unique and call it the greatest common divisor of m and n and denote it as (m,n) or gcd(m,n). It is clear from the definition that: (m,n) = (|m|, |n|).

An algorithm for finding the gcd of two positive integers was given in Euclid’s Elements around 300 BC. Suppose the integers are n1, n2 with n1 > n2. It is easy to see as a consequence of the Division Identity that either n1 = q1n2 and consequently n2 = (n1, n2), or n1 = q1n2 + n3 with n2 > n3 > 0. We iterate this process to obtain a set of relations

ni = qini+1 + ni+2 (1 < i< k)

nk=qknk+1

The process must terminate because the ni form a descending, finite sequence of positive numbers and if it has not terminated beforehand, the condition ni+2 = 1 forces it to terminate at the next step.

Now nk+1 = (nk, nk+1) and if nk+1 = (ni, ni+1) then nk+1 = (ni-1, ni) (i > 1) because certainly nk+1 divides both these latter numbers and if there were a larger number that divided both of them it would also be a common divisor of ni and ni+1, generating a contradiction.   Thus nk+1 = (n1, n2).

We can obtain a measure of the efficiency of the Euclidean algorithm. Suppose there are k ≥ 3 steps, and that i < k. If ni+1 ≤ ni/2 then since ni+2 < ni+1 then ni+2 ≤ ni/2. If ni+1 > ni/2 then since 1 = ni+2/ni +qini+1/ni we must have qi = 1 and ni+2 ≤ ni/2 also. Hence when 2j + 1 < k we have

\displaystyle \frac {n_{2j+1}}{n_{1}}=\frac {n_{2j+1}}{n_{2j-1}} ... \frac{n_3}{n_1} < \left( \frac{1}{2} \right)^j

Set 2j + 1 = k – s where s = 1 or 2 depending whether k is even or odd. Then

\displaystyle k = s + 1 + \frac {2}{\ln 2} \left( \ln n_{1} - \ln n_{k-s} \right) < 2 \frac{\ln n_{1}} { \ln 2} + 3

Forms of Proof

December 27, 2011

Ideally, mathematical proofs would start with statements that are known, or assumed to be, true and proceed through a series of steps to a final theorem. At each step a new statement would be shown to be true as a consequence of previous statements. However, in number theory in particular, it is often necessary to resort to less direct methods of proof.

Suppose P and Q are certain statements. If the truth of P implies that Q is true, we cannot assume the converse, that is, that Q implies that P is true. For example x = 1 implies that x2 = 1, but if x2 = 1, x is not necessarily 1. If the converse does happen to be true, we say that “P is true if and only if Q is true”, or that the statements P and Q are logically equivalent. For example, as can be easily shown, n is odd if and only if n2 is odd for all integers n.

Although the statement “If P is true then Q is true” does not imply its converse, it does imply the contrapositive, namely “If Q is false then P is false”. For example if x2 ≠ 1 then x ≠ 1. In number theory, propositions are often proved by proving the contrapositive.

If the truth of P implies Q is true, then the truth of Q is a necessary condition for P to be true, that is, P cannot be true unless Q is true, and it is not possible for P to be true if Q is false. If the truth of Q implies P is true, then Q is a sufficient condition for P to be true. That is, instances of Q being true can provide us with instances of P being true, but not necessarily all such instances. If Q is both necessary and sufficient then it is the logical equivalent of P. P is true on precisely those occasions when Q is true.

Reductio ad absurdum is a variant of the contrapositive. Suppose P is a proposition that it is desired to prove true. This method of proof starts with the proposition that P is false and shows that this leads to a conclusion that is either known to be false, or contradicts the proposition that P is false. This is considered to negate the proposition that P is false and hence prove that P is true.

As an example of its use (and also the use of the contrapositive), we prove that √2 is irrational. Start by assuming the contrary, that is, that √2 = p/q for some positive integers p, q . Because a number can be represented as a fraction in infinitely many ways, assume that it is possible to cancel out common multiples of 2 from p and q until at least one of p and q is odd (it is not necessary to assume that this process results in p and q being unique). p2 = 2q2 so p2 is even. But if p is odd p2 is odd so p must be even. Thus p2 = 4k2 for some positive integer k. Thus q2 is even, so q is even, a contradiction. Therefore our starting proposition must be false.

Infinite descent is a specific form of reductio ad absurdum. It was used by Pierre de Fermat around 1640 to prove that there are no non-zero integer solutions to the equation x4 + y4 = z4 where z,y,z are positive integers, and has been widely used in other problems. It assumes the negative of the proposition, that is that there is a solution for some z, and shows that the existence of a solution for any value of z implies the existence of a solution for a smaller value of z, which is impossible because there is a least value of z (i.e. 1) beyond which no further solutions can exist.

Suppose that there is a (finite or infinite) sequence of propositions P1, P2, and so on. The Principle of Induction states that if P1 is true and if we can demonstrate that if Pk were true for any given k then Pk+1 would be true, then all of P1, P2, … are true.

It is sometimes more practical to use the following corollary. If P1 is true and if we can demonstrate that if for any given k, Pi were true for all 1 ≤ i ≤ k, then Pk+1 would be true, then all of P1, P2, … are true.

For let P’k be the proposition that Pi is true for all 1 ≤ i ≤ k. If P1 is true then P’1 = P1 is true. If the truth of P’k implies the truth of Pk+1 then it implies the truth of P’k+1. Therefore by induction all the P’ are true and so all the P are true.

Walter Ledermann – Encounters of a Mathematician

December 8, 2011

For about 20 years from the 1940s the Edinburgh publisher Oliver and Boyd published a series of very high standard pocket-sized texts in mathematics and mathematical physics entitled ‘University Mathematical Texts.’

Among my favourites, purchased as an undergraduate and still referred to forty years later, was ‘Finite Groups’ by Walter Ledermann.

For years Ledermann remained a name on a bookcover for me, until, through the magic of the internet, I chanced upon his reminisces, which begin here, full of warmth and humour.

Ledermann was a German Jew who was lucky enough to emigrate to Britain in the early 1930s, and to be able to follow his chosen career as a mathematician until he was well into his eighties.  The account of his PhD student from Afghanistan is particularly humorous and touching.