Mathematical Methods for Physics and Engineering : A Comprehensive Guide

PRELIMINARY ALGEBRA

The prime integerspiare labelled in ascending order, thusp 1 =1,p 2 =2,p 5 =7,etc.

Show that there is no largest prime number.

Assume, on the contrary, that there is a largest prime and let it bepN.Considernowthe
numberqformed by multiplying together all the primes fromp 1 topNand then adding
one to the product, i.e.

q=p 1 p 2 ···pN+1.

By our assumptionpNis the largest prime, and so no number can have a prime factor
greater than this. However, for every primepi,i=1, 2 ,...,N, the quotientq/pihas the
formMi+(1/pi)withMian integer and 1/pinon-integer. This means thatq/picannot be
an integer and sopicannot be a divisor ofq.
Sinceqis not divisible by any of the (assumed) finite set of primes, it must be itself a
prime. Asqis also clearly greater thanpN, we have a contradiction. This shows that our
assumption that there is a largest prime integer must be false, and so it follows that there
is no largest prime integer.
It should be noted that the given construction forqdoes not generate all the primes
that actually exist (e.g. forN=3,q= 7 rather than the next actual prime value of 5, is
found), but this does not matter for the purposes of our proof by contradiction.

1.7.3 Necessary and sufficient conditions

As the final topic in this introductory chapter, we consider briefly the notion

of, and distinction between, necessary and sufficient conditions in the context

of proving a mathematical proposition. In ordinary English the distinction is

well defined, and that distinction is maintained in mathematics. However, in

the authors’ experience students tend to overlook it and assume (wrongly) that,

having proved that the validity of propositionAimplies the truth of proposition

B, it follows by ‘reversing the argument’ that the validity ofBautomatically

implies that ofA.

As an example, let propositionAbe that an integerNis divisible without

remainder by 6, and propositionBbe thatNis divisible without remainder by

2. Clearly, ifAis true then it follows thatBis true, i.e.Ais a sufficient condition

forB; it is not however a necessary condition, as is trivially shown by takingN

as 8. Conversely, the same value ofNshows that whilst the validity ofBis a

necessary condition forAto hold, it is not sufficient.

An alternative terminology to ‘necessary’ and ‘sufficient’ often employed by

mathematicians is that of ‘if’ and ‘only if’, particularly in the combination ‘if and

only if’ which is usually written as IFF or denoted by a double-headed arrow

⇐⇒. The equivalent statements can be summarised by

AifBAis true ifBis trueor B=⇒A,

Bis a sufficient condition forAB=⇒A,

Aonly ifBAis true only ifBis trueor A=⇒B,

Bis a necessary consequence ofAA=⇒B,