Mathematics

Cryptography

Hail the Queen of Mathematics!

What is special about these numbers: 6, 28, 496 and 8128? What is the nature of the relationship between the following pairs of "amicable," numbers, as they are rather exotically denoted: 220 and 284, 17296 and 18416, 9 363 584 and 9 437 056? Why are the numbers 2, 3, 5, 7 drawn from a special infinite series referred to as the "atoms of arithmetic?" These numbers, and many other kinds besides, are the subject of what Carl Friedrich Gauss (1777 – 1855) – one of the greatest Mathematicians to have ever lived – liked to call the Queen of Mathematics. An enviable position, particularly considering that many see Mathematics as the Queen of the Sciences. In specialist circles, this field is known by the more prosaic title of Number Theory.

As with so many fields of knowledge, the Greeks were likely the first people to study the properties and relationships of numbers in a systematic and rigorous manner. The first group of numbers above – 6, 28 and so on – are called perfect numbers­ and were studied by Pythagoras, especially for their supposed mystical qualities, and none other than the father of geometry, Euclid. Perfect numbers are defined as those numbers that are equal to the sum of their proper divisors[1]. For instance, the proper divisors of 6 are 1, 2 and 3, which sum to 6; and we also observe, 28 = 1 + 2 + 4 + 7 + 14.

Al-Hasan ibn al-Haytham (d. 1040, Cairo) is most noted for his contributions in the field of optics. As was the case for many of the scholars that Islamic civilization has bequeathed, ibn al-Haytham's intellectual curiosity motivated him to conduct explorations in a huge array of subjects, including number theory. Specifically, he attempted to characterize the set of perfect numbers, which he sets out in his unpublished work Analysis and Synthesis. Euclid had already proved in the Elements the elegant result that if 2^k – 1 is prime[2], then 2^k–1 .(2^k – 1 ) is a perfect number[3], for any integer k greater than 1.  As an application of this theorem, take k = 3. Then, 2³ – 1 = 7 is a prime number and 2².(2³ – 1) = 28 is the second perfect number. The interesting question is whether all the perfect numbers can be generated by Euclid's formula. This question is not as straightforward as it sounds; in actual fact, it still remains an open question amongst mathematicians! It is quite typical of many mathematical theorems that they go in one direction and not the other, and Euclid's theorem on perfect numbers is an example of that. Now, Ibn al-Haytham was interested in demonstrating the converse result. He wasn't entirely successful – we can forgive him this shortfall given that the problem has eluded some of the best mathematicians. However, there are suggestions in Analysis and Synthesis ­that he was the first to attempt the proof of the partial result that every even perfect number is of the form 2^k–1 .(2^k – 1 ) where 2^k – 1 is prime. The world had to wait seven centuries before Leonhard Euler provided a complete, correct and economic proof of the converse theorem.

Before we leave Ibn al-Haytham, we should note that he appears to be the first person to discover and use what came to be known as Wilson's theorem, which states that if p is prime, then[4] 1 + (p – 1)! is divisible by p. The indications are that the first proof of this theorem was produced by Lagrange in 1771 and, as remarked by O'Connor and Robertson, "it is more than 750 years after al-Haytham before number theory surpasses this achievement of Arabic mathematics." The kind of problems for which ibn al-Haytham employed Wilson's theorem is illustrated in Opuscula:

"To find a number such that if we divide by two, one remains; if we divide by three, one remains; if we divide by four, one remains; if we divide by five, one remains; if we divide by six, one remains; if we divide by seven, there is no remainder."

Ibn al-Haytham describes a general method to solve the problem above, which, for the given example, produces the solution, (7 – 1)! + 1. We can see, invoking Wilson's theorem, that this number is divisible by the prime number 7, and that it clearly leaves the reminder 1 when divided by any of 2, 3, 4, 5 and 6. (Observe (7 – 1)! + 1 = 6.5.4.3.2 + 1.)

We now steer our journey back in time and away from Cairo, where Ibn al-Haytham carried out his most seminal work, to the previous century and peer into the celebrated House of Wisdom in Baghdad during the time of the 'Abbasid Caliph, al-Mu'tadid. On his travels to Harran (now in Turkey), Mohammed bin Musa bin Shakir, one of the Banu Musa brothers, who already had gained a reputation for sponsoring and personally undertaking remarkable studies in the sciences, spotted the linguistic talents and scholarly potential of Thabit bin Qurra (d. 901, Baghdad). Thabit accompanied his future patron to Baghdad where he would complete ingenious and penetrating investigations in not only mathematics, but " … logic, psychology, ethics, the classification of sciences, the grammar of the Syriac language, politics, the symbolism of Plato's Republic … religion and the customs of the Sabians." Thabit's contribution to mathematics was summarized aptly by Rashed, who reports that he " … played an important role in preparing the way for such important discoveries as the extension of the concept of number to (positive) real numbers, integral calculus, theorems in spherical trigonometry, analytic geometry and non-Euclidean geometry. In astronomy, Thabit was one of the first reformers of the Ptolemaic system, and in mechanics he was a founder of statics."

Like his Greek predecessors, Thabit was fascinated by the properties of numbers and, in particular, brought to bear his intellectual prowess on characterizing certain pairs of numbers which shared a special relationship. He dedicated a whole treatise, On the determination of amicable numbers by an easy method, to the subject. This relationship was solemnized by describing these pairs as amicable numbers. Two numbers, say m and n, are amicable, if the sum of the proper divisors of one is equal to the other number. That is, if we denote the sum of the proper divisors of n as S(n), then m and n are amicable[5] if S(n) = m and conversely, S(m) = n.

The Muslims admired the Greeks for much of the rigour, beauty and organization they brought to the sciences. In particular, following on from the Greeks, Muslim mathematicians understood the importance of founding their explorations on proof. It is through proof that mathematics enjoys the enviable quality of unassailable certainty. Much of the beauty and flair – qualities we normally associated with a great work of art – which mathematicians find in their work is often captured by the proof of an important and deep theorem. While much of mathematics is concerned with explorations and discovery in a strange and wonderful land, proof is describing to others how to trace the steps to share the experience. The celebrated Cambridge mathematician, G. H. Hardy, put it vividly: "I have always thought of a mathematician as in the first instance an observer, a man who gazes at a distant range of mountains and notes down his observations." It is proof that gives mathematics almost a spiritual quality. Marcus du Sautoy captures some of the feeling:

"There is an amazing feeling of exhilaration at discovering a way to reach the summit of some distant peak which has been visible for generations. It is like creating a wonderful story or a piece of music which truly transports the mind from the familiar to the unknown … Even those who follow in the trail of the first pioneer will experience something of the sense of spiritual elevation that accompanied the first moment of epiphany at discovering a new proof."

Thabit followed the work of Euclid and Nichomacus on perfect numbers, but, like the best students, did not stop at the knowledge gained from his teachers, noting, " … neither of these authors either mentioned or showed interest in [amicable numbers]." Thabit was not merely satisfied in observing the delights in the landscape of numbers which led him to amicable numbers. He was keen to paint the landscape in all its glory and lay down the signposts for others who wish to make the same journey:

"Since the matter of [amicable numbers] has occurred to my mind, and since I have derived a proof for them, I did not wish to write the rule without proving it perfectly because they have been neglected by [Euclid and Nicomachus]. I shall therefore prove it after introducing the necessary lemmas."

Thabit first gives nine lemmas[6] before he states and proves his theorem:

for n > 1, let p_n = 3.2ⁿ – 1 and q_n = 9.2^2n-1 – 1. If p_n-1, p_n and q_n are prime numbers then a = 2ⁿ p_n-1 p_n and b = 2ⁿ q_n  are amicable numbers.

According to Hogendijk, Thabit was probably the first to discover the pair of amicable numbers, 17296 and 18416. The study of amicable numbers was transferred in the 13^th and 14^th centuries from the Muslims to the court of Robert of Anjou in Naples via manuscripts in Hebrew written by Samuel bin Yehuda. Muslim interest in perfect and amicable numbers continued with Al-Farisi (d. 1320, Iran) who provided a new proof of Thabit's theorem, in which he introduced important new ideas related to factorization and combiantorics.  Crucially, Al-Farisi bases his attack on one of most important results in number theory – the Fundamental Theorem of Arithmetic. This states that all numbers can be uniquely factorized into powers of prime numbers. The result inspires the analogy of prime numbers as the "atoms" or building blocks of all numbers. According to Rashed, Al-Farisi notes and attempts to prove the theorem. The amicable pair 17296 and 18416, which are known as Euler's amicable pair, were actually obtained several centuries earlier by Al-Farisi. He also conducted investigations into integer solutions of the equation x⁴ + y⁴ = z⁴, observing correctly that no such solutions exist. This equation is a special case of the legendary class of equations that are the subject of Fermat's Last Theorem[7]. Much later, in the 17^th century, Mohammed Baqir Yazdi computes the amicable pair 9 363 584 and 9 437 056, still many years before Euler's work.

In closing it is worth considering the value of what might appear to some to be a rather pointless flirt and play with abstract objects. This question was taken up by Hardy in his poignant and charming essay, "A Mathematicians Apology." He makes the rather bold assertion that any mathematics that is actually "useful," in the sense that is has some practical value or consequence – for better or worse – is likely to turn out to be quite dull. The most interesting mathematics – and number theory fits into this category – embodies beauty, economy and perfection. According to Hardy, "Mathematics is not a contemplative by a creative subject," and primarily, mathematicians, like painters or poets, are creators of patterns. Above all, the mathematician's patterns must be beautiful: "There is no permanent place in the world for ugly mathematics." For Hardy, "Immortality may be a silly word, but probably a mathematician has the best chance of whatever it may mean." The kind of mathematics described here brings pleasure and delight to the practitioner, who undertakes his study, as Henri Poincare puts it, "… not because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful. If Nature were not beautiful, it would not be worth knowing, and if Nature were not worth knowing, life would not be worth living." Mathematics is concerned with abstract, transcendent quantities that enjoy, as many mathematicians would see, an independent perfect existence of their own, immutable and pure. It is therefore not surprising that Muslim scholars were drawn and enraptured by the mathematics that they inherited and subsequently developed from the civilizations they encountered – the Greek, the Indian and the Chinese. Islam generally discourages an obsession with the physical form. Rather than acting as a constraint, this unleashed the fully creative faculty and imagination of the great scholars and scientists. Mathematics provided fertile ground for their intellectual pursuits, and as they navigated the mathematical tapestry, they experienced both humility and exhilaration at the prospect that somehow they were in contact with the Divine Kingdom.

As it turns out, number theory does actually serve very useful purposes, especially today, when security is of paramount concern. Specifically, prime numbers – very large ones consisting of over a hundred digits – are at the root of the encryption system that ensures our most valued personal information is splattered across the Internet in a secure and reliable manner. This encryption scheme is called RSA after its three inventors – Ron Rivest, Adi Shamir and Leonard Adleman. The distribution of the prime numbers is the subject of the Riemann Hypothesis, which is viewed as probably the most important unsolved problem in mathematics. If the relationship between encryption and the primes does not convince the utilatarians amongst us of the importance of esoteric branches of mathematics, perhaps the $1 million on offer as a prize by the Clay Institute for proving the Riemann Hypothesis will pique our interest.

[1] A divisor, a, of the number n divides n exactly to leave no remainder. Of course, trivially, n always exactly divides n. The set of proper divisors do not include this trivial case.

[2] A number p is prime if and only if it possesses exactly two divisors: 1 and itself, p.

[3] Note that a number n raised to the power of a positive integer k – written n ^k – is computed by multiplying n by itself k times.

[4] Recall that n! = n x (n – 1) x … 2 x 1.

[5] Using this notation, a number, n, is perfect if S(n) = n. One could say that amicability is just short of perfection.

[6] Often the proof of complex theorems are very involved and are normally preceded by intermediate results, called lemmas, which also must be proved.

[7] Fermat's Last Theorem states that there are no integer solutions to the equation xⁿ + yⁿ = zⁿ for all n > 2. The theorem was stated by the French mathematician Pierre de Fermat who left us with the tantalizing suggestion (in the margin) that he knew a delightful proof but did not have sufficient room in which to write it down. It would be 350 years later in 1994 before Andew Wiles produced a correct and complete proof.

by: Mahbub Gani, Fri 02 September, 2005