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 2s−1 are called Mersenne numbers, where s is a prime. Let us consider the Mersenne number 2p−1 . Then two cases arise:
Case 1: 2p−1 is a prime.
We know that 2p−1>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: 2p−1 is not a prime.
For this case we show that a prime factor q of 2p−1 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|2p−1, 2p−1≡0(modq) or
\(2p≡1(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 a−b, we say that a is congruent to b modulo m and write it as a≡b(modm). If a−b is not divisible by m, we say that a is not congruent to b modulo m and write it as a≢b(modm).
In other words, we can say that a and b leave the same remainder when divided by m.
For e.g. - 3≡5(mod2), 10≡0(mod5), 5≢13(mod3).
a−b≡0(modm), a≡b(modm) and b≡a(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,
-
the set is closed under the operation, i.e. if a,b∈G then a⊕b∈G.
-
the associative law holds, namely, a⊕(b⊕c)=(a⊕b)⊕c:∀:a,b,c∈G.
-
the set has a unique identity element, e. That is,
∃:e∈G s.t. ∀:a∈G,:a⊕e=e⊕a=a.
-
each element in G has a unique inverse in G.
∀:a∈G,:∃:a−1∈G, s.t. a⊕a−1=a−1⊕a
There is an extra condition for an abelian/ commutative group, which is as follows:
a⊕b=b⊕a:∀ pair of elements {a,b}∈G .
Examples - (Z,+) is a group, (R∗,×) , where R∗=R−0 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
…a−3,a−2,a−1,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,…,q−1}. We prove that for any prime q, Zq∗ is a multiplicative group, by showing that it satisfies the axioms of a group:
-
Closure: If a,b∈Zq∗, then a⋅b∈Zq∗
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′,y′∈Z such that a′x′+q′y′=d. More generally, any integers of the form a′x′+q′y′ are multiples of d.
Thus, in our case, the below equations are satisfied. \(ax0+qy0=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 a⋅b∈Zq∗.
-
Identity: \(1 \cdot a= a \cdot 1=a \: \forall \: a \in \mathbb{Z_q}^\ast\)
-
Associativity: holds for multiplication and also for modular multiplication.
-
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=a−1∈Zq∗.
To show the uniqueness of the a−1, let us consider x′0∈Zq∗ such that x′0≠x0 and ax′0=1:(modq). Thus, ax′0=ax0:(modq). Multiplying with a−1 on RHS, we get: \(x_{0}'=x_0 \: (\mod q)\) Since x′0∈Zq∗, 1≤x′0<q. So the above equation is impossible for x′0≠x0. 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 2c≡1:(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
-
b2as=b2at, then as=at (by multiplying on the left by b−12)
But a has order r and the considered powers of a are less than r, not allowing any of the powers to be equivalent.
-
b2as=at , then b2=at−s . 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 q−1 is the order of the group, it can be said that p|(q−1). This means that p≤(q−1). 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.