{"id":7060,"date":"2025-12-12T15:27:30","date_gmt":"2025-12-12T20:27:30","guid":{"rendered":"https:\/\/creatureandcreator.ca\/?p=7060"},"modified":"2025-12-12T15:27:30","modified_gmt":"2025-12-12T20:27:30","slug":"prime-numbers-mysterious-building-blocks","status":"publish","type":"post","link":"https:\/\/creatureandcreator.ca\/?p=7060","title":{"rendered":"Prime Numbers: Mysterious Building Blocks"},"content":{"rendered":"
\"image_pdf\"<\/a>\"image_print\"<\/a><\/div>\n

\u00a0<\/p>\n

A prime number is one that can only be divided by 1 and itself. Prime numbers are the building blocks for all the natural numbers, each of which can be expressed as a unique product of primes. Although their primacy can be proven by demonstrating that they are not divisible by any other number, where the prime numbers occur among the natural numbers cannot be predicted. Prime numbers are as mysterious as they are essential. The illustration shows the 25 primes (yellow) that occur in the first 100 numbers.\u00a0<\/p>\n

<\/p>\n

Some Fundamentals<\/strong><\/p>\n

A \u201cprime number\u201d p<\/em> is a natural number (a positive integer) greater than 1 that is divisible only by 1 and itself. A \u201ccomposite number\u201d is any natural number greater than 1 that is not a prime. In positive terms, a composite number n<\/em> is divisible without remainder by two numbers between 1 and n<\/em>: n=ab. <\/em>\u00a0The two kinds of numbers can be illustrated graphically. Composite numbers of objects (blue) can be organized into repeating groups (factors), whereas prime numbers of objects (red) cannot:<\/p>\n

\"\"<\/a><\/p>\n

This idea is also illustrated in a delightful animation<\/a> of the \u201cFactor Conga\u201d by Stephen Von Worley<\/a>.<\/p>\n

The number 1 was sometimes considered prime, but nowadays 1 is viewed as a special number \u2013 \u201cunit\u201d or \u201cunity\u201d \u2013 because of two properties (Lamb, 2019). First is the \u201cmultiplicative identity\u201d characteristic: any number multiplied by 1 remains the same number. Second is the \u201cmultiplicative inverse\u201d characteristic. The multiplicative inverse of a number multiplied by the original number gives 1. The multiplicative inverse of any number greater than 1 is a fraction, e.g., the multiplicative inverse of 2 is 1\/2. The multiplicative inverse of 1 is the integer 1.\u00a0<\/p>\n

\u00a0<\/p>\n

Factorization<\/strong><\/p>\n

The determination of the numbers that when multiplied together give a composite number is called \u201cfactorization.\u201d The simplest algorithm involves \u201ctrial division:\u201d one divides each of the primes into the number to see which leaves no remainder, and repeats this with the quotient: The prime factors of 1540 are 2, 5, 7 and 11:\u00a0<\/p>\n

\"\"<\/a><\/p>\n

Pierre de Fermat (1601-1665) was a French mathematician and magistrate. He is probably most famous for his \u201clast theorem\u201d \u2013 that no three positive integers a<\/em>, b<\/em>, and c<\/em> satisfy the equation an<\/sup><\/em>+bn<\/sup><\/em>=cn<\/sup><\/em> for any integer value of n<\/em> greater than 2 \u2013 for which he claimed to have a \u201cmarvelous proof.\u201d A proof of the theorem was finally published by Andrew Wiles in 1994.<\/p>\n

However, Fermat also proposed a method for factorization based on the equation<\/p>\n

a2 <\/sup>\u2013 b2<\/sup> = (a + b)(a – b)<\/em><\/p>\n

This method works best if the number n<\/em> is the product of two nearby integers.<\/p>\n

Select a <\/em>as the next integer greater than sqrt(n).
Calculate b2<\/em> = a2<\/sup> -n. \u00a0<\/em>Increment a<\/em> until sqrt(b2<\/sup><\/em>) is an integer.
Return values a<\/em> +sqrt (b2<\/sup><\/em>) and a \u2013 sqrt (b2<\/sup><\/em>)<\/p>\n

For the number 5959, the following are the steps<\/a><\/p>\n

a\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/em>78\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 79\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 80
b2<\/sup> = a2<\/sup> -n<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 125\u00a0\u00a0\u00a0\u00a0\u00a0 282\u00a0\u00a0\u00a0\u00a0\u00a0 441
sqrt (b2<\/sup><\/em>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 11.2\u00a0\u00a0\u00a0\u00a0 16.8\u00a0\u00a0\u00a0\u00a0 21<\/p>\n

giving 80+21 (101) and 80-21 (59) as factors of 5959.<\/p>\n

Factorization leads to the \u201cFundamental Theorem of Arithmetic\u201d (also called the \u201cPrime Factorization Theorem\u201d) generally attributed to Euclid, a Greek mathematician who worked around 300 BCE in Alexandria:<\/p>\n

\"\"<\/a><\/p>\n

The sculpture of Euclid in the Oxford University Museum was made by Joseph Durham around 1860. Euclid was more famous for his geometry than for his contributions to number theory. On the scroll in his left hand is his proof of the \u201cPythagorean Theorem\u201d that the square on the hypotenuse of a right-angled triangle is equal to the sum of the squares on the other two sides. \u00a0<\/p>\n

Each number\u2019s set of the exponents for the primes provides a unique signature for each prime and composite number. As examples:<\/p>\n

11\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0, 0, 0, 0, 1
1540 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2, 0, 1, 0, 1
5959\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1<\/p>\n

(for the last example, 59 and 101 are the 17th<\/sup> and 26th<\/sup> primes).<\/p>\n

Euclid also proved that the number of primes is infinite. The proof posits a number p<\/em>n<\/sub> that is the largest of all primes. We can then form a number N<\/em> by multiplying all the primes up to an including p<\/em>n <\/sub>and adding 1.<\/p>\n

N = p1<\/sub> p2<\/sub> p3<\/sub> \u2026 pn <\/sub>+ 1<\/p>\n

Since every prime less than N divides once into N giving a quotient equal to the product of the other prime numbers and leaving a remainder of 1, N is prime. To postulate a number pn<\/sub> as the largest of all primes is impossible. Therefore, the number of primes is infinite.<\/p>\n

The natural numbers can be viewed as buildings with the primes having only one storey and the composite numbers having multiple storeys:<\/p>\n

\"\"<\/a><\/p>\n

As well as the prime factors one can also determine the greatest common divisor (GCD) of two numbers. Instead of calculating all the prime factors one can use Euclid\u2019s algorithm to determine the GCD of two numbers a<\/em>>b<\/em>. One iterates the following commands<\/p>\n

Divide b<\/em> into a<\/em> to give a quotient and remainder.
Replace a<\/em> with b<\/em> and b<\/em> with the remainder.<\/p>\n

until the remainder equals zero, in which case the current value of b is the GCD. The following illustration (modified from Wikipedia<\/a>) shows the algorithm graphically for 49 and 21 (GCD of 7) and for 46 and 21 (GCD 1):<\/p>\n

\"\"<\/a><\/p>\n

Two numbers are considered \u201crelatively prime\u201d or \u201ccoprime\u201d if their GCD is 1, e.g. 46 and 21.<\/p>\n

In 1742, the Prussian mathematician Christian Goldbach (1690-1764) conjectured that every even number greater than 2 can be represented as the sum of two prime numbers. This also meant that every odd number is the sum of two primes +1. Goldbach\u2019s conjecture is true for all natural numbers that have been examined, but has not yet been proven.<\/p>\n

The prime numbers therefore are the building blocks of arithmetic. Every number can be represented as the product of primes and every even number as the sum of two primes. Du Sautoy (2003, p 5) has called the primes the \u201cvery atoms of arithmetic,\u201d and likened the list of primes to the periodic table of the elements.<\/p>\n

\u00a0<\/strong><\/p>\n

Finding Primes<\/strong><\/p>\n

Various techniques have been proposed to identify which numbers are prime in a set of numbers. Erastosthenes, the chief librarian of the Library of Alexandria in the 3rd<\/sup> Century BCE, became famous for his remarkably accurate estimate of the circumference of the world (Nicastro, 2008). He also proposed an algorithm for identifying primes that is known as the \u201cSieve of Erastosthenes.\u201d The algorithm iteratively rejects as composite those numbers that are multiples of the prime numbers less than the square root of the maximum number to be evaluated. Thus, to examine the numbers between 1 and 100, one marks the multiples of 2, 3, 5, and 7. When the numbers are arrayed 10 by 10, the multiples of 2 and 5 form vertical lines (yellow and blue, with an overlap as green), and the multiples of 3 and 7 form sloping lines (red and dark blue). The unrejected numbers (circled) are primes.\u00a0<\/p>\n

\"\"<\/a><\/p>\n

As the range of numbers to be examined gets large such approaches to identifying primes become very time-consuming even for very fast computers. It would be wonderful if there were a simple equation to identify all the prime numbers. Unfortunately, there is no such formula (Mackinnon, 1987). Some formulae can identify some prime numbers.<\/p>\n

Fermat proposed that numbers of the form<\/p>\n

\"\"<\/a><\/p>\n

are prime. However, the formula only works for n<\/em> between 0 and 4. Leonhard Euler (1707-1783) came up with an intriguing formula<\/p>\n

n<\/em>2<\/sup> + n<\/em> +41<\/p>\n

but this only works for n between -1 and 39.<\/p>\n

Marin Mersenne (1588-1648) proposed that numbers of the form<\/p>\n

2p<\/sup><\/em> \u2013 1<\/p>\n

are prime when p <\/em>is prime. However, this only works for some primes: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89 …. Nevertheless, this formula serves to identify numbers as possible primes. The largest known prime number was found in this way. \u00a0<\/p>\n

Recently a formula involving 26 variables has been created that will provide positive and negative numbers when different combinations of integer variables are used for the variables. The positive numbers are primes (Jones et al, 1976). The calculations are laborious and there appears to be no clear logic behind the formula:<\/p>\n

\"\"<\/a><\/p>\n

Finding our whether a particular number is prime or composite is a time-consuming process. Basically, one need to determine the factors of the number. Various algorithms have been proposed to speed up the process. Some combine various approaches such as the sieve of Erastosthenes and Fermat\u2019s method based on the difference in squares. However, the process remains slow for very large numbers even on the fastest of computers.<\/p>\n

Modular Arithmetic<\/strong><\/p>\n

Important to any understanding of primes is an assessment of how clock numbers work. If a simple clock displays 1 to 12 hours on its face, amounts of time are considered to work in increments of 12. Therefore 6 hours later than 10 o\u2019clock shows as 4 o\u2019clock rather than 16, and a further 28 hours later shows as 8 o\u2019clock rather than 32 (or 44 if counting from the initial position:<\/p>\n

\"\"<\/a><\/p>\n

Carl Friedrich Gauss (1777-1855) first described this type of arithmetic in 1801. The idea is that numbers \u201cwrap around\u201d whenever a value called the \u201cmodulus\u201d is reached. The notation\u00a0<\/p>\n

a<\/em> \u2261 b<\/em> (mod m<\/em>)<\/p>\n

means that a<\/em> and b <\/em>are \u201ccongruent modulo m<\/em>\u201d or<\/p>\n

a= km + b<\/em><\/p>\n

where k<\/em> is a positive integer.<\/p>\n

The expression is related to but not the same as the operator \u201cmod\u201d (expressed without brackets) or \u201c%\u201d which gives the remainder when one number is divided by another, e.g. 7 mod 3 = 1. \u00a0<\/em><\/p>\n

One intriguing aspect of modular systems is that if a number added to by a number that is multiple of the modulus, the result is the original number. In a clock any number of complete rotations will not change the displayed time.\u00a0<\/p>\n

Given these concepts, we can consider Fermat\u2019s \u201cLittle Theorem,\u201d so called to distinguish it from his \u201cLast Theorem.\u201d For any integer a <\/em>where is p<\/em> is a prime and a<\/em> and p<\/em> are relatively prime to each other (have a GCD of 1) then, in modern notation<\/p>\n

ap<\/sup><\/em> \u2261 a<\/em> (mod p<\/em>)<\/p>\n

This expression means that any number raised to a power of a prime yields itself when considered in a system that is modular at the value of the prime. \u00a0In general, we make p<\/em>>a<\/em>. If p<\/em><a<\/em>, the procedure yields a<\/em> mod p <\/em>rather than a. We can try this theorem out on small numbers such as a<\/em> = 3 and p<\/em> = 5: ap<\/sup> = <\/em>243 which divided by 5 leaves a remainder of 3.<\/p>\n

Fermat proposed the theorem in 1640 but offered no proof. The theorem was proven by Gottfried Leibniz (1646-1716) in 1683 (see details in Wilson, 2020, pp 97-100).<\/p>\n

The theorem can also be expressed<\/p>\n

ap<\/sup><\/em>-1<\/sup> \u2261 1 (mod p<\/em>)<\/p>\n

In this format Fermat\u2019s Little Theorem serves as the basis for the \u201cFermat Primality Test.\u201d Any number n<\/em> that does not fulfil the criterion<\/p>\n

an<\/sup><\/em>-1<\/sup> \u2261 1 (mod n<\/em>)<\/p>\n

where a<\/em> is any integer greater than 1 and less than n<\/em>-1, is not prime. If it does fulfil the criterion, it is probably prime (a Fermat pseudoprime) and the test should be repeated with a different a. <\/em>To be absolutely sure one would have to test all values of a less than sqrt (n<\/em>). The test efficiently determines whether a number is composite, but it can be computationally expensive when determining that it is indeed prime. \u00a0<\/p>\n

\u00a0<\/strong><\/p>\n

Distribution of Primes<\/strong><\/p>\n

The prime numbers occur among the more common composite numbers with no regular pattern:<\/p>\n

\"\"<\/a><\/p>\n

The shortest gap \u2013 between 2 and 3 \u2013 occurs only once. Primes separated by 2 \u2013 twin primes \u2013 occur 8 times in the first 100 numbers. In 1849 Alphonse de Polignac (1826-1863) conjectured that for any number n<\/em> there are an infinite number of consecutive primes separated by n. <\/em>When n <\/em>is 2, this is the \u201ctwin prime conjecture\u201d (Neale, 2017). Neither the twin prime conjecture nor the more generalized de Polignac conjecture has been proven.<\/p>\n

The number of primes less than n<\/em> \u2013 the \u201cprime number counting function,\u201d customarily denoted as \u03c0(n<\/em>) \u2013 increases with increasing n<\/em> but the rate of increase decreases as n<\/em> increases. In 1792, at the age of 15, Gauss conjectured that the number was approximated by n<\/em>\/ln(n<\/em>), where \u201cln\u201d denotes the \u201cnatural logarithm\u201d (using the base of e<\/em> equal to 2.71828\u2026). This underestimates \u03c0(nx<\/em>), but the relative error decreases as x increases.<\/p>\n

Although it was not published until after his death, Gauss later refined his conjecture, suggesting that \u03c0(n<\/em>) is better approximated by the logarithmic integral of n:<\/p>\n

This estimate is the basis for the \u201cprime number theorem:\u201d as n<\/em> increases, \u03c0(n<\/em>) asymptotically approaches Li(n<\/em>). The following illustration shows the prime number counting function with the two different estimates for n<\/em> between 1-100 and 1-1000. There are 25 primes below 100 and 168 below 100. The actual function is a staircase, with steps occurring at each prime. The estimates are smooth functions. \u00a0<\/p>\n

\"\"<\/a><\/p>\n

The prime gap is the difference between two consecutive prime numbers<\/p>\n

gn<\/sub> = pn+1<\/sub> – pn<\/sub><\/p>\n

The minimum value of gn <\/sub>\u00a0is 2 for n>2. The average gap between primes increases as the natural logarithm of these primes, and therefore the ratio of the prime gap to the primes decreases (and is asymptotically zero). The ratio gn<\/sub><\/em>\/ln(pn<\/sub><\/em>) is called the \u201cmerit\u201d of a particular gap. There is no known maximal gap. The maximum recorded gap<\/a> of 8350 occurred for an 87-digit prime and has a merit value of 41.9. The maximum gap gn<\/sub><\/em> would have to be less than the prime counting function \ud835\udf0b(\ud835\udc5dn<\/sub><\/em>) (Lu & Deng, 2020) \u00a0\u00a0\u00a0<\/p>\n

\u00a0<\/p>\n

In 1763 Euler introduced what has come to be known as \u201cEuler\u2019s Totient Function.\u201d This function, nowadays denoted as \u03c6<\/em>(n<\/em>), counts the number of positive integers less than a given integer n<\/em> that are relatively prime to n<\/em>. When n is 12 \u03c6<\/em>(n<\/em>) is 4 (the numbers 1, 5, 7, 11) and when n is 13 \u03c6<\/em>(n<\/em>) is 12 (all numbers less than 13). The word \u201ctotient\u201d comes from the Latin tot <\/em>meaning \u201cthat many.\u201d The illustration<\/a> shows the function up to n of 1000. The upper boundary shows the value when n<\/em> is a prime and \u03c6<\/em>(n<\/em>) is n<\/em>-1.<\/p>\n

\"\"<\/a><\/p>\n

This function has some intriguing characteristics. Most importantly, for two integers a<\/em> and b<\/em><\/p>\n

\u03c6<\/em>(ab<\/em>) = \u03c6<\/em>(a<\/em>) \u03c6<\/em>(b<\/em>)<\/p>\n

Some sense of this characteristic can be obtained by considering a<\/em> as 6 and b <\/em>as 7: \u03c6<\/em>(6) is 2 (the numbers1 and 5) and \u03c6<\/em>(7) is 6 because 7 is prime. Therefore \u03c6<\/em>(42) is 12 (the numbers 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41).\u00a0<\/p>\n

\u201cEuler\u2019s Theorem,\u201d an extension of Fermat\u2019s Little Theorem (and sometimes called the \u201cFermat-Euler Theorem\u201d), states<\/p>\n

a\u03c6<\/sup><\/em>(n<\/em>)<\/sup> \u2261 <\/em>1 (mod n<\/em>)<\/p>\n

The proof of this generalization of Fermat\u2019s theorem is detailed in Wilson (2020, pp 103-108)<\/p>\n

\u00a0<\/strong><\/p>\n

Cryptography<\/strong><\/p>\n

For many years the study of primes was considered \u201cpure\u201d mathematics, in that the truths that it proved had no applications in the real world. The famous number theorist G. H. Hardy (1877-1947) claimed<\/p>\n

I have never done anything \u2018useful’. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world. (Hardy, 1940, p 90)<\/p>\n

Over the past half century, the idea of pure mathematics has changed. Prime numbers have become an essential part of real-world cryptography. All the information that is transmitted between buyer and seller when something is bought on the internet is kept safe from prying eyes by means of algorithms that use prime numbers. The most common algorithm was initially proposed by Ron Rivest, Adi Shamir and Leonard Adleman in 1977, and has come to be known as the \u201cRSA cryptosystem.\u201d The following illustration shows Rivest, Shamir and Adleman at theMassachusetts Institute of Technology:<\/p>\n

\"\"<\/a><\/p>\n

The following are the basic procedures of the RSA algorithm (Rivest et al, 1977; Crandall & Pomerance, 2005, pp 389-391; Watkins, 2014, pp 369-374; Wilson, 2020, 110-111):<\/p>\n

(i) generation of public keys<\/em>:<\/p>\n

Two different large prime numbers p<\/em> and q<\/em> are chosen. Nowadays these primes are approximately equal and each about 200 digits in length. A number N is calculated as the product of these two primes, and Euler\u2019s totient (T) is calculated for N. This equals the product of p \u2013 1 and q \u2013 1. Finally, a number E (\u201cencryption key\u201d) is chosen that is greater than 2, less than N-1 and coprime to T. The last characteristic can be ensured by using Euler\u2019s algorithm to show the T and E have 1 as their greatest common divisor (GCD). The number E is typically chosen as a prime number greater than either p or q.<\/p>\n

N <\/em>= pq
<\/em>T = \u03c6(pq) = <\/em>(p \u2212 <\/em>1)(q \u2013 <\/em>1)
Choose E <\/em>\u2208<\/em> [3, N \u2212 <\/em>2] and GCD(E, T) = 1<\/p>\n

The public keys are N and E; p<\/em> and q<\/em> (and T) are kept secret.\u00a0<\/p>\n

\u00a0<\/p>\n

(ii) encryption of the message<\/em><\/p>\n

The message (or part of a message) is coded into a large number M using a simple substitution cipher. For example, each letter could be represented as a two-digit numbers from 01 to 26. M is then encrypted to give the number C (\u201cciphertext\u201d) using public keys N and E according to the formula<\/p>\n

C \u2261 ME<\/sup> (mod N)<\/p>\n

The number M has increased dramatically, and the clock (modulus N) has revolved many times so that the clock face shows a number C completely different from M. E must be coprime to T to make sure that C does not return as the same number as M.<\/p>\n

(iii) decryption of the message<\/em><\/p>\n

To decrypt the message, we must calculate a number D (\u201cdecryption key\u201d) that is the modular multiplicative inverse of E<\/p>\n

DE \u2261 1 (mod T) or D = E-1<\/sup> mod T<\/p>\n

Finding the multiplicative inverse is a simple trial and error process. Iteratively increment k and then calculate (k*E) mod T until it equals 1, at which time D is made equal to k. In an example using small numbers, E of 7 and T of 72 (the totient for 7 and 13)<\/p>\n

k=1, 7mod72 is 7
k=2, 14mod72 is 14
\u2026
k=30, 210mod72 is 66
k=31, 217mod72 is 1, therefore D is 31.<\/p>\n

Having obtained D, we can decrypt the coded message to obtain the original message according to the formula<\/p>\n

M \u2261 CD <\/sup>(mod N)<\/p>\n

The number has again increased but after many revolutions the clock face now shows the same number as it was before the original encryption. Because D is the modular multiplicative inverse of E, when the clock wraps around because of E and then because of D it is the same as it the clock face had just stayed the same. \u00a0\u00a0\u00a0<\/p>\n

\u00a0<\/p>\n

(iv) example<\/em><\/p>\n

The following is an example using small numbers<\/p>\n

Let p=3 and q=11; N=pq=33<\/p>\n

T = (p-1)*(q-1) = 2*10 = 20<\/p>\n

Let E = 7, check GCD(7,20)=1<\/p>\n

Find D to ensure (D*E)mod20=1<\/p>\n

Determine D to be 3 because 3*7mod20=1<\/p>\n

Let M = 31<\/p>\n

Encrypt message as C=ME<\/sup>modN = 317<\/sup>mod33 =4<\/p>\n

Decrypt message as CD<\/sup>modN = 43<\/sup>mod33=31<\/p>\n

\u00a0<\/p>\n

(v) breaking the code<\/em>.<\/p>\n

In order to break the RSA code an outside observer would have to find D. This would require finding the two primes p<\/em> and q<\/em> that when multiplied together gave the public number. From p<\/em> and q<\/em> one would know T. Then one could derive D. Finding p<\/em> and q<\/em> would require factoring N, a computationally demanding task when N is very large. The RSA system remains safe provided that it takes longer to compute the factors of N than the length of time that the system uses any particular numbers p and q.<\/p>\n

\u00a0<\/p>\n

Zeta Function<\/strong><\/p>\n

In his studies of infinite series published in 1737, Euler proved a remarkable identity:<\/p>\n

\"\"<\/a><\/p>\n

The left side of the equation shows the sum of the reciprocals of all natural numbers raised to the power s. <\/em>The has become known as \u03b6(s<\/em>) or the \u201czeta function\u201d<\/p>\n

\u03b6(s<\/em>) = 1\/1s<\/sup> + 1\/2s<\/sup> + 1\/3s<\/sup> + 1\/4s<\/sup>\u2026.<\/em>+ 1\/n<\/em>s<\/sup><\/p>\n

The right side of the equation is a product of multiple terms each involving one of the prime numbers:<\/p>\n

\u03b6(s<\/em>) = 1\/(1-2-s<\/sup>) * 1\/(1-3-s<\/sup>) * 1\/(1-5-s<\/sup>) * 1\/(1-7-s<\/sup>) \u2026.<\/em>* 1\/(1-p-s<\/sup>)<\/p>\n

When s <\/em>is 2, the function is the sum of the reciprocals of all the natural numbers squared:<\/p>\n

\u03b6(2<\/em>) = 1\/12<\/sup> + 1\/22<\/sup> + 1\/32<\/sup> + 1\/42<\/sup>\u2026.<\/em>+ 1\/n<\/em>2<\/sup><\/p>\n

Euler demonstrated that \u03b6(2<\/em>) = \u03c02<\/sup>\/6. This was intriguing since the zeta equation now linked the natural numbers to the irrational number \u03c0. \u00a0Euler also proved that \u03b6(4) is \u03c04<\/sup>\/90 and \u03b6(6) is \u03c06<\/sup>\/945. Values of the function for odd values of s<\/em> have no clear formulation. \u00a0<\/p>\n

To prove his product function, Euler used a sieving approach<\/a> as illustrated below:<\/p>\n

\"\"<\/a><\/p>\n

In 1859 Bernhard Riemann considered Euler\u2019s zeta function using complex variables He made s<\/em>\u00a0=\u00a0\u03c3<\/em>\u00a0+\u00a0it<\/em>, where\u00a0\u03c3<\/em>\u00a0and\u00a0t<\/em>\u00a0are real numbers and i<\/em> is the square root of -1. Using values derived from this function he was able to adjust Euler\u2019s prime number theorem \u2013 as n<\/em> increases, \u03c0(n<\/em>) asymptotically approaches Li(n<\/em>) \u2013 so that it accurately represented the actual staircase function that is \u03c0<\/em>(n<\/em>).<\/p>\n

The Riemann Zeta Function is as complex as its variable, and I am afraid I find it impossible to understand. Both Derbyshire (2003) and Du Sautoy (2003) have written books about the function. In his original paper Riemann also proposed a hypothesis about the nontrivial zero-values of the function that appear on a line where the real value of the variable equals \u00bd. His hypothesis holds for all values of the function so far examined. However, the hypothesis is not yet proven. The Clay institute has offered a prize of 1\u00a0million dollars for the proof. I shall not be collecting this prize, but I shall enthusiastically applaud its winner.<\/p>\n

The following video<\/a> was made for Quanta Magazine by Alex Kontorivich about the Riemann Zeta Function and the Riemann Hypothesis.<\/p>\n

https:\/\/creatureandcreator.ca\/wp-content\/uploads\/2025\/12\/riemann-video.mp4<\/a><\/video><\/div>\n

\u00a0<\/p>\n

Epilogue<\/strong><\/p>\n

We can conclude with a quotation from Du Sautoy (2003, p 6) about the primes:<\/p>\n

Prime numbers present mathematicians with one of the strangest tensions in their subject. On the one hand a number is either prime or it isn’t. No flip of a coin will suddenly make a number divisible by some smaller number. Yet there is no denying that the list of primes looks like a randomly chosen sequence of numbers. Physicists have grown used to the idea that a quantum die decides the fate of the universe, randomly choosing at each throw where scientists will find matter. But it is something of an embarrassment to have to admit that these fundamental numbers on which mathematics is based appear to have been laid out by Nature flipping a coin, deciding at each toss the fate of each number. Randomness and chaos are anathema to the mathematician. Despite their randomness, prime numbers – more than any other part of our mathematical heritage – have a timeless, universal character. Prime numbers would be there regardless of whether we had evolved sufficiently to recognise them.<\/p>\n

In Paolo Gordano\u2019s 2010 novel The Solitude of the Primes<\/em>, the character Mattia muses<\/p>\n

Prime numbers are divisible only by one and by themselves. They stand in their place in the infinite series of natural numbers, squashed in between two others, like all other numbers, but a step further on than the rest. They are suspicious and solitary, which is why Mattia thought they were wonderful. Sometimes he thought that they had ended up in that sequence by mistake, that they\u2019d been trapped like pearls on a necklace. At other times he suspected that they too would rather have been like all the others, just ordinary numbers, but for some reason they weren\u2019t capable of it. (p 111)<\/p>\n

And we cannot leave the topic without some praise for the mathematicians that discovered so much about them. The following are portraits of some of these marvelous thinkers. They all contributed extensively to our knowledge beyond their work with the primes. Fermat worked with Pascal on the mathematics of probability; Gauss was the first to measure the earth\u2019s magnetic field; Euler proposed his \u201cidentity:\u201d<\/p>\n

ei\u03c0 <\/sup>+ 1 =0<\/p>\n

which united the logarithms, pi and imaginary numbers just like his product formula united the natural numbers, primes and pi; and Riemann worked on the non-Euclidean geometry that Einstein would use in his Theory of relativity.\u00a0<\/p>\n

\"\"<\/a><\/p>\n

References<\/strong><\/p>\n

Crandall, R. E., & Pomerance, C. (2005). Prime numbers: a computational perspective<\/em> (Second Edition). Springer.<\/p>\n

Derbyshire, J. (2003). Prime obsession: Bernhard Riemann and the greatest unsolved problem in mathematics<\/em>. Joseph Henry Press<\/p>\n

Du Sautoy, M. (2003). The music of the primes: searching to solve the greatest mystery in mathematics<\/em>. HarperCollins.<\/p>\n

Giordano, P. (2010). The solitude of prime numbers<\/em>. Penguin<\/p>\n

Hardy, G. H. (1940). A mathematician\u2019s apology<\/a>. Cambridge University Press.<\/p>\n

Jones, J. P., Sato, D., Wada, H., &Wiens, D., (1976). Diophantine representation of the set of prime numbers.<\/a> The American Mathematical Monthly<\/em>, 83, 449-464.<\/p>\n

Lamb, E. (2019). Why isn’t 1 a prime number? And how long has it been a number?<\/a> Scientific American Blog.<\/p>\n

Lu, Y.-P. & Deng, S.-F. (2020). An upper bound for the prime gap. arXiv:2007.15282<\/a><\/p>\n

Mackinnon, N. (1987). Prime number formulae. The Mathematical Gazette<\/em>, 71(456), 113\u2013114.<\/p>\n

Neale, V. (2017). Closing the gap: the quest to understand prime numbers<\/em>. Oxford University Press.<\/p>\n

Nicastro, N. (2008). Circumference: Eratosthenes and the ancient quest to measure the globe<\/em>. St. Martin’s Press.<\/p>\n

Riemann, G. F. B. (1859). \u00dcber die Anzahl der Primzahlen unter einer gegebenen Gr\u00f6sse. Monatsber. K\u00f6nigl. Preuss. Akad. Wiss. Berlin<\/em>, 671-680. English translation by D. R. Wilkins<\/a><\/p>\n

Rivest, R.L., Shamir, A., & Adleman, L. (1977). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems<\/em><\/a>(Technical report). MIT Laboratory for Computer Science.<\/p>\n

Watkins, J. J. (2014). Number theory: a historical approach<\/em>. Princeton University Press.<\/p>\n

Wilson, R. J. (2020). Number theory: a very short introduction<\/em>. Oxford University Press.<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"

\u00a0 A prime number is one that can only be divided by 1 and itself. Prime numbers are the building blocks for all the natural numbers, each of which can be expressed as a unique product of primes. Although their primacy can be proven by<\/p>\n","protected":false},"author":1,"featured_media":7056,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":194,"footnotes":""},"categories":[3,745],"tags":[1124,1131,1129,1123,1126,1122,1125,1121,1130,1127,1128],"class_list":["post-7060","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-history","category-mathematics","tag-bernhard-riemann","tag-erastosthenes","tag-euclid","tag-friedrich-gauss","tag-goldbachs-conjecture","tag-leonhard-euler","tag-number-theory","tag-pierre-de-fermat","tag-prime-number-theorem","tag-riemann-hypothesis","tag-twin-primes"],"_links":{"self":[{"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/posts\/7060","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7060"}],"version-history":[{"count":3,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/posts\/7060\/revisions"}],"predecessor-version":[{"id":7063,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/posts\/7060\/revisions\/7063"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=\/wp\/v2\/media\/7056"}],"wp:attachment":[{"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7060"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7060"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/creatureandcreator.ca\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7060"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}