Skip to the content.

23 Jan 2020 - Aditi Kathpalia

Suppose P, the set of primes is finite and p is the largest prime. We have assumed a contradiction to the fact that the set P is infinite. Numbers of the form 2s1 are called Mersenne numbers, where s is a prime. Let us consider the Mersenne number 2p1 . Then two cases arise:

Case 1: 2p1 is a prime.

We know that 2p1>p as p>1. If that is the case, there is a contradiction to the assumption that p is the largest prime. Hence the assumption is false and the set P is infinite.

Case 2: 2p1 is not a prime.

For this case we show that a prime factor q of 2p1 is greater than p, which again is a contradiction to the fact that the set P is finite (with p being the largest prime).

Since q|2p1, 2p10(modq) or
\(2p1(modq)\) To explain congruence and modular arithmetic (the notations of and mod) as well as some amount of group theory (which will be used in the proof), we take a detour and then come back to the proof.

Detour

Congruence is a statement about divisibility. It is defined as follows:

If an integer, m, not zero, divides the difference ab, we say that a is congruent to b modulo m and write it as ab(modm). If ab is not divisible by m, we say that a is not congruent to b modulo m and write it as ab(modm).

In other words, we can say that a and b leave the same remainder when divided by m.

For e.g. - 35(mod2), 100(mod5), 513(mod3).

ab0(modm), ab(modm) and ba(modm) are equivalent statements.

Groups

A group G is a set of elements a,b,c, together with a single valued binary operation such that,

  1. the set is closed under the operation, i.e. if a,bG then abG.

  2. the associative law holds, namely, a(bc)=(ab)c::a,b,cG.

  3. the set has a unique identity element, e. That is,

    :eG s.t. :aG,:ae=ea=a.

  4. each element in G has a unique inverse in G.

:aG,::a1G, s.t. aa1=a1a

There is an extra condition for an abelian/ commutative group, which is as follows:

ab=ba: pair of elements {a,b}G .

Examples - (Z,+) is a group, (R,×) , where R=R0 is a group

Other groups can be formed by taking congruences modulo m.

Additive group modulo 6 is as depicted below:

0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4

A multiplicative group modulo 3 is as given below:

× 1 2
1 1 2
2 2 1

Now we define the order of an element of a group as well as a cyclic group.

Let G be any group, finite or infinite, and a an element of G. If as=e (e is identity element of the group) for some positive integer s, then a is said to be of finite order. If a is of finite order, the order of a is the smallest positive integer r such that ar=e. If there is no positive integer s such that as=e, then a is said to be of infinite order.

A group G is said to be cyclic if it contains an element a such that the powers of a

a3,a2,a1,a0=e,a,a2,a3,

comprise the whole group; such an element a is said to generate the group and is called a generator.

The order of a group is equal to the number of elements in the group.

Now, let us get back to the proof.

We construct a multiplicative group modq, (Zq,) where q is the prime number considered before. The group Zq consists of elements {1,2,,q1}. We prove that for any prime q, Zq is a multiplicative group, by showing that it satisfies the axioms of a group:

  1. Closure: If a,bZq, then abZq

    Since q is a prime and contains only integers less than itself, gcd(a,q)=1 and gcd(b,q)=1.

    Now, according to Bezout’s identity, if a and q are integers with gcd(a,q)=d, then :x,yZ such that ax+qy=d. More generally, any integers of the form ax+qy are multiples of d.

    Thus, in our case, the below equations are satisfied. \(ax0+qy0=1\)

bx1+qy1=1

From Eqs. GCD1 and (GCD2), we get,

​ \((ax0+qy0)(bx1+qy1)=1ax0bx1+ax0qy1+qy0bx1+qy0qy1=1ab(x0x1)+q(ax0y1+y0bx1+qy0y1)=1\)

​ Based on Eq. GCD3, it can be said that gcd(ab,q)=1. Hence abZq.

  1. Identity: \(1 \cdot a= a \cdot 1=a \: \forall \: a \in \mathbb{Z_q}^\ast\)

  2. Associativity: holds for multiplication and also for modular multiplication.

  3. Inverse: From Eq. GCD1, we have ax0+qy0=1. Taking modulo q on both sides, we get ax0=1:(modq). It can also be visualized as x0a+qy0=1. Thus, gcd(x0,q)=1. From this, it can be said that x0=a1Zq.

    To show the uniqueness of the a1, let us consider x0Zq such that x0x0 and ax0=1:(modq). Thus, ax0=ax0:(modq). Multiplying with a1 on RHS, we get: \(x_{0}'=x_0 \: (\mod q)\) Since x0Zq, 1x0<q. So the above equation is impossible for x0x0. Hence, a unique inverse exists.

Thus, we have proved that Zq is a multiplicative group. Moreover, it is a proved theorem that Zq is a cyclic group for any prime q. We omit the proof for this here.

From Eq. 1, if we consider the group Zq, with 2 being an element of the group; we can observe that p is the order of 2. Since p is prime, there can be no positive integer c<p for which 2c1:(modq) holds.

Now, according to a special case of Lagrange’s theorem, if a group G has a cyclic group as its subgroup, then,

The order of an element of a finite group G is a divisor of the order of the group.

Proof: Let the element a be a generator of the group and have order r. Then, \(e, a, a^2, a^3, \ldots, a^{r-1}\) are r distinct elements of G and belong to a set A. All other powers of a merely repeat the above elements.

If these r elements do not exhaust the group, there is some other element, say b2. Then it can be proved that \(b_2, b_2a, b_2a^2, \ldots, b_2a^{r-1}\) are r distinct elements all different from r elements of A and belong to a set B.

This is because if

  1. b2as=b2at, then as=at (by multiplying on the left by b12)

    But a has order r and the considered powers of a are less than r, not allowing any of the powers to be equivalent.

  2. b2as=at , then b2=ats . This would mean that b2 would be among the considered powers of a and is not distinct.

If G is not exhausted by the sets A and B, then there exists another element b3 that gives rise to r new elements: \(b_3,b_3a,b_3a^2, \ldots, b_2a^{r-1}\) all different from the elements in A and B, with the same argument as for the previous set.

This process of obtaining new elements b2,b3, must terminate since G is finite. So if the last batch of new elements is, say, \(b_k,b_ka,b_ka^2, \ldots, b_ka^{r-1}\) then the order of the group is kr and r|kr. Hence, it is proved that the order of an element of a finite group is a divisor of the order of the group.

Now, if we consider for our group Zq, since p is the order of element 2 in the group and q1 is the order of the group, it can be said that p|(q1). This means that p(q1). Hence, p<q.

Thus, we have proved that a prime q>p. This is a contradiction to the fact that P is a finite set with p being the largest prime. Hence, it is proved that the number of primes is infinite.