Discrete Mathematics

Class 22: Prime Detectives


Here’s the updated (and final) schedule for the rest of the semester:

  • Problem Set 9: due on Friday, 1 December at 6:29pm. (This will be posted on 19 November.)
  • Problem Set Omega (this is optional, and not like the others, hence it uncountable number): due on Monday, 4 December at 11:59pm.
  • Final Exam: Thursday, 7 December, 9am-noon (in the normal lecture room)

Challenge Solution

Connor Roos’ solution to the challenge problem about the minimum number of NAND operations (using gates, not formulas) is here: Description (PDF), Code (Java).

Exam 2 Solutions

The solutions for Exam 2 are here: PDF. Please read these carefully and come to office hours with any questions you have, especially if you had difficulties on any of the exam problems.


G. H. Hardy, A Mathematician’s Apology, 1940.

A man (sic - Hardy’s quote, unfortunately, but typical for 1940, uses sexist language throughout, but I will leave it as written, but “man” here means “person”, and “he” and “his” are not meant to be limited to males) who sets out to justify his existence and his activities has to distinguish two different questions. The first is whether the work which he does is worth doing; and the second is why he does it, whatever its value may be. The first question is often very difficult, and the answer very discouraging, but most people will find the second easy enough even then. Their answers, if they are honest, will usually take one or other of two forms; and the second form is a merely a humbler variation of the first, which is the only answer we need consider seriously.

(1) ‘I do what I do because it is the one and only thing that I can do at all well. I am a lawyer, or a stockbroker, or a professional cricketer, because I have some real talent for that particular job. I am a lawyer because I have a fluent tongue, and am interested in legal subtleties; I am a stockbroker because my judgment of the markets is quick and sound; I am a professional cricketer because I can bat unusually well. I agree that it might be better to be a poet or a mathematician, but unfortunately I have no talent for such pursuits.’

I am not suggesting that this is a defence which can be made by most people, since most people can do nothing at all well. But it is impregnable when it can be made without absurdity, as it can by a substantial minority: perhaps five or even ten percent of men can do something rather well. It is a tiny minority who can do something really well, and the number of men who can do two things well is negligible. If a man has any genuine talent he should be ready to make almost any sacrifice in order to cultivate it to the full.

There is also what I call the ‘humbler variation’ of the standard apology; but I may dismiss this in a very few words.

(2) ‘There is nothing that I can do particularly well. I do what I do because it came my way. I really never had a chance of doing anything else.’ And this apology too I accept as conclusive. It is quite true that most people can do nothing well. If so, it matters very little what career they choose, and there is really nothing more to say about it. It is a conclusive reply, but hardly one likely to be made by a man with any pride; and I may assume that none of us would be content with it.

A man’s first duty, a young man’s at any rate, is to be ambitious. Ambition is a noble passion which may legitimately take many forms; there was something noble in the ambitions of Attila or Napoleon; but the noblest ambition is that of leaving behind something of permanent value — …

There are many highly respected motives which may lead men to prosecute research, but three which are much more important than the rest. The first (without which the rest must come to nothing) is intellectual curiosity, desire to know the truth. Then, professional pride, anxiety to be satisfied with one’s performance, the shame that overcomes any self-respecting craftsman when his work is unworthy of his talent. Finally, ambition, desire for reputation, and the position, even the power or the money, which it brings. It may be fine to feel, when you have done your work, that you have added to the happiness or alleviated the sufferings of others, but that will not be why you did it. So if a mathematician, or a chemist, or even a physiologist, were to tell me that the driving force in his work had been the desired to benefit humanity, then I should not believe him (nor should I think the better of him if I did). His dominant motives have been those which I have stated, and in which, surely, there is nothing of which any decent man need be ashamed.

If intellectual curiosity, professional pride, and ambition are the dominant incentives to research, then assuredly no one has a fairer chance of satisfying them than a mathematician. His subject is the most curious of all—there is none in which truth plays such odd pranks. It has the most elaborate and the most fascinating technique, and gives unrivalled openings for the display of sheer professional skill. Finally, as history proves abundantly, mathematical achievement, whatever its intrinsic worth, is the most enduring of all.

A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. … The mathematician’s patterns, like the painter’s or the poet’s must be beautiful; the ideas like the colours or the words, must fit together in a harmonious way. Beauty is the first test: there is no permanent place in the world for ugly mathematics.

The fact is that there are few more ‘popular’ subjects than mathematics. Most people have some appreciation of mathematics, just as most people can enjoy a pleasant tune; and there are probably more people really interested in mathematics than in music. Appearances suggest the contrary, but there are easy explanations. Music can be used to stimulate mass emotion, while mathematics cannot; and musical incapacity is recognized (no doubt rightly) as mildly discreditable, whereas most people are so frightened of the name of mathematics that they are ready, quite unaffectedly, to exaggerate their own mathematical stupidity.

It is undeniable that a good deal of elementary mathematics—and I use the word ‘elementary’ in the sense in which professional mathematicians use it, in which it includes, for example, a fair working knowledge of the differential and integral calculus—has considerable practical utility. These parts of mathematics are, on the whole, rather dull; they are just the parts which have the least aesthetic value. The ‘real’ mathematics of the ‘real’ mathematicians, the mathematics of Fermat and Euler and Gauss and Abel and Riemann, is almost wholly ‘useless’ (and this is as true of ‘applied’ as of ‘pure’ mathematics). It is not possible to justify the life of any genuine professional mathematician on the ground of the ‘utility’ of his work.

But here I must deal with a misconception. It is sometimes suggested that pure mathematicians glory in the uselessness of their work, and make it a boast that it has no practical applications. The imputation is usually based on an incautious saying attributed to Gauss, to the effect that, if mathematics is the queen of the sciences, then the theory of numbers is, because of its supreme uselessness, the queen of mathematics—I have never been able to find an exact quotation. I am sure that Gauss’s saying (if indeed it be his) has been rather crudely misinterpreted. If the theory of numbers could be employed for any practical and obviously honourable purpose, if it could be turned directly to the furtherance of human happiness or the relief of human suffering, as physiology and even chemistry can, then surely neither Gauss nor any other mathematician would have been so foolish as to decry or regret such applications. But science works for evil as well as for good (and particularly, of course, in time of war); and both Gauss and less mathematicians may be justified in rejoicing that there is one science at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean.

We have concluded that the trivial mathematics is, on the whole, useful, and that the real mathematics, on the whole, is not; that the trivial mathematics does, and the real mathematics does not, ‘do good’ in a certain sense; but we have still to ask whether either sort of mathematics does harm. It would be paradoxical to suggest that mathematics of any sort does much harm in time of peace, so that we are driven to the consideration of the effects of mathematics on war. It is every difficult to argue such questions at all dispassionately now, and I should have preferred to avoid them; but some sort of discussion seems inevitable. Fortunately, it need not be a long one.

There is one comforting conclusions which is easy for a real mathematician. Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years. It is true that there are branches of applied mathematics, such as ballistics and aerodynamics, which have been developed deliberately for war and demand a quite elaborate technique: it is perhaps hard to call them ‘trivial’, but none of them has any claim to rank as ‘real’. They are indeed repulsively ugly and intolerably dull; even Littlewood could not make ballistics respectable, and if he could not who can? So a real mathematician has his conscience clear; there is nothing to be set against any value his work may have; mathematics is, as I said at Oxford, a ‘harmless and innocent’ occupation.

The trivial mathematics, on the other hand, has many applications in war. The gunnery experts and aeroplane designers, for example, could not do their work without it. And the general effect of these applications is plain: mathematics facilitates (if not so obviously as physics or chemistry) modern, scientific, ‘total’ war.

It is not so clear as it might seem that this is to be regretted, since there are two sharply contrasted views about modern scientific war. The first and the most obvious is that the effect of science on war is merely to magnify its horror, both by increasing the sufferings of the minority who have to fight and by extending them to other classes. This is the most natural and orthodox view. But there is a very different view which seems also quite tenable, and which has been stated with great force by Haldane in Callinicus. It can be maintained that modern warfare is less horrible than the warfare of pre-scientific times; that bombs are probably more merciful than bayonets; that lachrymatory gas and mustard gas are perhaps the most humane weapons yet devised by military science; and that the orthodox view rests solely on loos-thinking sentimentalism. It may also by urged (though this was not one of Haldane’s theses) that the equalization of risks which science was expected to bring would be in the long range salutary; that a civilian’s life is not worth more than a soldier’s, nor a woman’s more than a man’s; that anything is better than the concentration of savagery on one particular class; and that, in short, the sooner war comes ‘all out’ the better.

I do not know which of these views is nearer to the truth. It is an urgent and a moving question, but I need not argue it here. It concerns only the ‘trivial’ mathematics, which it would be Hogben’s business to defend rather than mine. The cases for his mathematics may be rather more than a little soiled; the case for mine is unaffected.

Indeed, there is more to be said, since there is one purpose at any rate which the real mathematics may serve in war. When the world is mad, a mathematician may find in mathematics an incomparable anodyne.

Number Theory

Definition: $a$ divides $b$ ($a\, |\, b$) iff there is an integer $k$ such that $ak = b$.

Definition: A prime is a number greater than 1 that is divisible only by itself and 1.

Theorem: There are infinitely many prime numbers.

Prove by contradiction (and well ordering principle):

# ##

Fundamental theorem of arithmetic: every positive number $n$ can be written uniquely as a product of primes: $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$ where $pi \le p{i + 1}$.

Groups and Rings

$R$ is an Abelian group with respect to binary operation $P$ if it is:

  • associative: $\forall a, b, c \in R. (a P b) P c = a P (b P c)$.
  • commutative: $\forall a, b \in R. a P b = b P a$.
  • has an identity: $\exists z \in R . \forall a \in R . a P z = a$.
  • every element has an inverse with respect to that identity: $\forall a \in R . \exists w \in R . a P w = z$.

Which of these are Abelian groups:

  • $R = \mathbb{N}, P = +$.
  • $R = \mathbb{N}, P = \times$.
  • $R = \mathbb{Z}, P = +$.
  • $R = \mathbb{Q}, P = \times$.
  • $R = { T, F}, P = NAND$.