Proofs
Regarding Primorial Patterns
by
Dennis R. Martin
DP Technology Corp.,
dennis.martin@dptechnology.com
BSME,
Department of
Mathematics,
Copyright © 2006 by Dennis R. Martin
ALL RIGHTS RESERVED
No part of this document may be reproduced, retransmitted, or redistributed by any means, without the expressed written consent of Dennis R. Martin.
This document is available in other formats. See www.primenace.com.
Abstract
Observations are made regarding the pattern of the composite numbers that have a particular prime factor for their lowest prime factor. It is subsequently proven that this pattern repeats over intervals equal to the primorial of that lowest prime factor such that the number and distribution of such composites is constant. The value of that constant composite to primorial ratio is proven to be related to the previous prime numbers and its constant composite to primorial ratio.
1 Introduction
It seems well known that the pattern of composite numbers repeats with a period equal to the primorial of each prime factor. Dickson [1] refers to remarks by H.J.S Smith in 1857 and papers by J. DeChamps published in 1907 regarding this property, and Weisstein [2] makes note of it. However, actual proofs of these properties do not seem to be readily available. This paper attempts to rectify that situation by starting from the ground up and deriving some general relationships and developing proofs based on them.
2 Singular
Identities
A prime number is a number greater than 1 that has no positive integer divisors other than 1 and itself.^{[3] }By the fundamental theorem of arithmetic, every positive integer greater than 1 can be uniquely represented by its prime divisors in what is called a prime factorization.^{[4, 5]} Since a prime p_{N} has no other positive integer divisors besides 1 and itself, the prime factorization of p_{N} is simply p_{N}. A positive integer greater than 1 which is not prime is a composite number.^{[6]}
By convention the number 1 is considered neither prime nor composite. Every positive integer greater than 1 is either a prime number or a composite number. For every positive integer greater than 1, then, one of the following statements must be true:
1. The prime p_{N} is a factor in its prime factorization.
2. The prime p_{N} is not a factor in its prime factorization.
If a number n has a prime factorization where p_{N} is a single factor, that is p_{N}^{i} is a factor and i = 1, and if p_{N}^{1} is the only factor other than 1, then n = p_{N} and it is prime. Otherwise it is a composite number which we can label C.
Lemma 1: For every composite number C having p_{N} as a factor, one of the following statements must be true:
1. The lowest prime factor of C
is smaller than p_{N}. That
is, p_{NJ} is the lowest
prime factor and p_{NJ} <
p_{N}.
2. The lowest prime factor is p_{N} and it is the lone prime factor,
i.e. p_{N}^{i} = C where i ≥ 2.
3. p_{N} is the lowest prime factor while the other factor is a larger prime p_{N+J} > p_{N} or a product of one or more larger primes such as (p_{N+J})^{k} or (p_{N+J}) • (p_{N+L}) or combinations of their higher powers.
Proof: If p_{N} is a
factor by itself, then it is of the form p_{N}^{i},
but i cannot be 1 because then the number would be prime, so i must be greater
than 1 and thus satisfy condition 2. If p_{N}
is not a factor by itself, then it must be combined with at least one other
prime. If any of the other primes in the prime factorization is less than p_{N} then condition 1 is
satisfied, otherwise all of them must be greater than p_{N}, in which is the case covered by condition 3.
Q.E.D.
3 Primorial Soup
The primorial is analogous to a factorial applied to the sequence of prime numbers.^{[7]} The primorial for the prime p_{N} is the product of all primes up to and including p_{N}, and it is denoted as p_{N}#. By the definition of factorial, p_{1}# = 2, and then for every prime greater than 2:
p_{N}# = p_{N} • p_{N–1}# (1)
What happens, though, if instead of just multiplying p_{N–1}# by p_{N} to get the next primorial value, we multiply all of the positive integers in the interval up to and including p_{N–1}# by p_{N}? What can we say about these numbers, and what about the other integers that we might need to fill in the new interval up to and including p_{N}#? What would happen if we were to add some multiple of p_{N}# onto all of them? What can we say about the lowest prime factors of those numbers?
For example, start with the number 1, and multiply it by the first prime p_{1} = 2. We now have an interval the width of the primorial p_{1}# = 2 containing the numbers 1 and 2. Add any multiple of 2 onto these two numbers. That is, let n be a nonnegative integer where n = 0, 1, 2, 3, 4, 5… The result of the addition is an interval of width p_{1}# = 2 containing the numbers 2n + 1 and 2n + 2. For those numbers, the statements that follow, where º indicates congruence, are always true.^{[8]}
(2n + 1) º 1 (mod 2)
(2n + 2) º 0 (mod 2)
Therefore within every interval of width p_{1}# = 2 we have one number that has p_{1} = 2 for its lowest prime factor and another number that does not have 2 for a factor. Except for the case where n = 0 and that other number is 1, that other number must either be prime or it must be a composite that has a higher prime p_{N+J} > p_{1} for its lowest prime factor. Essentially we have just found that every even number is evenly divisible by 2 and that every odd number is not.
Now take that first primorial and multiply it by the second prime, p_{2} = 3 and fill in the spaces in between. The result is an interval of width p_{2}# = 6 containing the numbers 1, 2, 3, 4, 5, 6. Add any multiple of 6 on to those numbers. The result will be an interval the width of the primorial p_{2}# = 6, still, containing the following numbers:
(6n + 1), (6n + 2), (6n + 3), (6n + 4), (6n + 5), (6n + 6)
Let
us factor these values. While we could factor a 3 from out of two of those
numbers, though, let us instead only factor the lowest prime factor possible
out of each. This factoring
produces:
(6n + 1) º 1 (mod 6)
2
• (3n + 1) º 2 (mod 6) º 0 (mod 2)
3
• (2n + 1) º 3 (mod 6) º 0 (mod 3)
2
• (3n + 2) º 4 (mod 6) º 0 (mod 2)
(6n + 5) º 5 (mod 6)
2
• (3n + 3) º 0 (mod 6) º 0 (mod 2)
Performing a lowest prime factorization like this allows us to more easily count the numbers within the primorial interval in terms of their lowest prime factor.
Out of every p_{2}# primorial interval, we can see that there are three numbers that have 2 for their lowest prime factor, one number that has 3 for its lowest prime factor (the 3 • (2n + 1) term), and two other numbers which do not have 2 or 3 as a factor at all. That there are three numbers that have 2 for their lowest prime factor makes sense because we multiplied the previous primorial by 3 and that primorial interval had one number that had 2 for its lowest prime factor. But notice also that the term that does have 3 for its lowest prime factor has the same form as the term that did not have 2 as a factor in that previous p_{1}# primorial interval. That is:
(2n + 1) º 1 (mod 2) ® 3 • (2n + 1) º 3 (mod 6) º 0 (mod 3)
To summarize what can be concluded so far:
a. 1 out of every 2 and 3 out of every 6 numbers have 2 for their lowest prime factor.
b. 1 out of every interval of 6 numbers has 3 for its lowest prime factor.
c. 4 numbers total out of every 6 have either 2 or 3 for their lowest prime factor.
d. 2 out of every 6 numbers do not have 2 or 3 as a factor. Ignoring the trivial case where one of those is 1, those two numbers individually are either prime or have a prime that is higher than 3 for their lowest prime factor.
The count in (d) can be calculated as the primorial value minus the count from (a) that have 2 for their lowest prime factor minus the count from (b) that has 3 for its lowest prime factor. But the count from (a) corresponds back to the count in the p_{1}# = 2 interval that had 2 for a lowest prime factor and the count from (b) matches the count from the previous p_{1}# = 2 interval which did not have 2 as a factor. Thus the count in (d) is directly related to counts in the previous primorial.
4 A
Preliminary Proof by Induction
By induction then, if we multiply the first interval of 6 by p_{3} = 5 and then add any multiple of p_{3}# = 5 • 6 = 30, we should expect the three numbers that had 2 as their lowest prime factor in the previous p_{2}# = 6 primorial to lead to 3 • 5 = 15 = 30 / 2 which have 2 as their lowest prime factor in each p_{3}# = 30 primorial interval. We should also expect the one that had 3 as its lowest prime factor in the previous to lead to 1 • 5 = 5 = 30 / 6 that have 3 as their lowest prime factor in this interval, and the 2 that had neither 2 nor 3 as a factor should now relate to two composites that have 5 for their lowest prime factor. That will leave 30 – 15 – 5 – 2 = 8 that have do not have 2, 3 or 5 as a factor. If not equal to 1, then each of those eight must either be prime themselves or must have a prime higher than 5 as their lowest prime factor.
Let us set about proving what has been implied by induction. Take the first 30 positive integers and add any multiple of p_{3}# = 30 onto them. The result is a set having the values {(30n + 1), (30n + 2), (30n + 3), (30n + 4), (30n + 5), (30n + 6), …(30n + 29), (30n + 30)}. Now factor the lowest prime factor possible out of each of them. The results of this lowest prime factorization including various relevant residues are shown in Table 1.
Table 1: Lowest Prime Factorization of Any Multiple of the p_{3}# = 5# = 30 Primorial Interval
Primorial Interval Member 
Lowest Prime Factorization 
Residues 

Modulo
p_{3}# 
Modulo
p_{2}# 
Modulo Lowest
p_{N} 

30n + 1 
(30n + 1) 
1
(mod 30) 
1 (mod 6) 

30n + 2 
2 • (15n + 1) 
2
(mod 30) 
2 (mod 6) 
0
(mod 2) 
30n + 3 
3 • (10n + 1) 
3
(mod 30) 
3 (mod 6) 
0
(mod 3) 
30n + 4 
2 • (15n + 2) 
4
(mod 30) 
4 (mod 6) 
0
(mod 2) 
30n
+ 5 
5 • (6n + 1) 
5 (mod 30) 
5 (mod 6) 
0 (mod 5) 
30n + 6 
2 • (15n + 3) 
6
(mod 30) 
0 (mod 6) 
0
(mod 2) 
30n + 7 
(30n + 7) 
7
(mod 30) 
1 (mod 6) 

30n + 8 
2 • (15n + 4) 
8
(mod 30) 
2 (mod 6) 
0
(mod 2) 
30n + 9 
3 • (10n + 3) 
9
(mod 30) 
3 (mod 6) 
0
(mod 3) 
30n + 10 
2 • (15n + 5) 
10
(mod 30) 
4 (mod 6) 
0
(mod 2) 
30n + 11 
(30n + 11) 
11
(mod 30) 
5 (mod 6) 

30n + 12 
2 • (15n + 6) 
12
(mod 30) 
0 (mod 6) 
0
(mod 2) 
30n + 13 
(30n + 13) 
13
(mod 30) 
1 (mod 6) 

30n + 14 
2 • (15n + 7) 
14
(mod 30) 
2 (mod 6) 
0
(mod 2) 
30n + 15 
3 • (10n + 5) 
15
(mod 30) 
3 (mod 6) 
0
(mod 3) 
30n + 16 
2 • (15n + 8) 
16
(mod 30) 
4 (mod 6) 
0
(mod 2) 
30n + 17 
(30n + 17) 
17
(mod 30) 
5 (mod 6) 

30n + 18 
2 • (15n + 9) 
18
(mod 30) 
0 (mod 6) 
0
(mod 2) 
30n + 19 
(30n + 19) 
19
(mod 30) 
1 (mod 6) 

30n + 20 
2 • (15n + 10) 
20
(mod 30) 
2 (mod 6) 
0
(mod 2) 
30n + 21 
3 • (10n + 7) 
21
(mod 30) 
3 (mod 6) 
0
(mod 3) 
30n + 22 
2 • (15n + 11) 
22
(mod 30) 
4 (mod 6) 
0 (mod
2) 
30n + 23 
(30n + 23) 
23
(mod 30) 
5 (mod 6) 

30n + 24 
2 • (15n + 12) 
24
(mod 30) 
0 (mod 6) 
0
(mod 2) 
30n
+ 25 
5 • (6n + 5) 
25 (mod 30) 
1 (mod 6) 
0 (mod 5) 
30n + 26 
2 • (15n + 13) 
26
(mod 30) 
2 (mod 6) 
0
(mod 2) 
30n + 27 
3 • (10n + 9) 
27
(mod 30) 
3 (mod 6) 
0
(mod 3) 
30n + 28 
2 • (15n + 14) 
28
(mod 30) 
4 (mod 6) 
0
(mod 2) 
30n + 29 
(30n + 29) 
29
(mod 30) 
5 (mod 6) 

30n + 30 
2 • (15n + 15) 
0
(mod 30) 
0 (mod 6) 
0
(mod 2) 
As expected there are 15 numbers within each interval of 30 that have 2 as their lowest prime factor. All of them relate to a value within a primorial interval of the previous prime. That is, all of them are congruent to either 2 or 4 or 0 (mod 6).
There are 5 numbers within each interval of 30 that have 3 as their lowest prime factor. Those 5 relate to a specific value within a primorial interval of p_{2}# = 6 in that all of them have a residue of 3 (mod 6).
Then there are 2 numbers (as highlighted in bold in Table 1) within each interval of 30 that have 5 as their lowest prime factor. Those two are directly related to the two factors that did not have 2 or 3 as a factor within the primorial of the previous prime. They are the values with residues of 1 (mod 6) and 5 (mod 6):
(6n + 1) º 1 (mod 6) ® 5
• (6n + 1) º 1 (mod 6) º 0 (mod 5)
(6n + 5) º 5 (mod 6) ® 5
• (6n + 5) º 5 (mod 6) º 0 (mod 5)
Finally that leaves 8 numbers within each interval of 30 that do not have 2, 3, or 5 as a factor. The results for the primorial p_{3}# = 30 match what we predicted by induction from p_{2}#. Let us now generalize this as a theorem and prove it for any primorial.
5 Deriving
the General Theorems
Theorem 1: Over any interval equal to the primorial p_{N}# of a particular prime p_{N}, the count of the numbers having p_{N} as their lowest prime factor is constant, as is the count of the numbers having any prime p_{NJ }that is less than p_{N} as their lowest prime factor a constant as well.
Proof: Let the sequence of numbers a_{0}, a_{1}, a_{2}, … a_{m2}, a_{m1} represent all of the integers within any interval of the primorial p_{N}# such that a_{i} Î {a} and (n • p_{N}# + A) < a_{i} ≤ ((n + 1) • p_{N}# + A), where n is a nonnegative integer and A is an integer offset. Since we are only concerned with prime factors, and 1 has no prime factors, let us also stipulate that 1 ≤ A ≤ p_{N}# so that all a_{i }> 1.
Divide every integer in the interval by the primorial value. Since every integer is unique, each one will have a unique residue with respect to the primorial. That is, each will produce an integer residue going from 0 up to the primorial value minus 1 with the primorial as the modulus.
p_{N}#  {a} ® [ º {0, 1, 2, 3 … (p_{N}# – 2), (p_{N}# –1)} (mod p_{N}#) ]
The entity on the right is a residue system. Because each integer value from zero up to the modulus minus 1 is represented as a residue, this is a complete residue system.^{[9]}
Label this residue system {r}_{N}. Since the primorial is a factorial product of the previous lower primes, let us divide those residues by the primorial value of the next lower prime. Since each residue is unique within the range from 0 up to the original primorial, each new residue with respect to the primorial of the previous prime will be unique within an interval of that primorial, and the number of subintervals of that primorial will be equal to the value of the original prime p_{N} that we started with. Thus each lower residue system with the lower primorial value as the modulus will be repeated a number of times equal to the value of that original, next higher prime.
p_{N1}#  {a} ® [ º {0, 1, 2, 3 … (p_{N1}# – 2), (p_{N1}# –1)} (mod p_{N1}#) ] x p_{N}
Label the new residue system in brackets as {r}_{N1}. There are p_{N} of these {r}_{N1 }residue systems within each p_{N}# primorial, and each of them is a complete residue system. We can continue by dividing all of these residue systems by p_{N2}# to produce the {r}_{N2} system in brackets below:
p_{N2}#  {a} ® [ º {0, 1, 2, 3 … (p_{N2}# – 2), (p_{N2}# –1)} (mod p_{N2}#) ] x (p_{N} • p_{N1})
There are (p_{N} • p_{N1}) of these {r}_{N2} residue systems within the original p_{N}# primorial. This process can continue all the way down to p_{1}# = 2, where the complete residue system labeled {r}_{1} is [ º {0, 1} (mod 2) ]. There would be (p_{N} • p_{N1} • p_{N2} •... • p_{2}) = (p_{N}# / 2) of these {r}_{1} residue systems within an interval of p_{N}#.
We can use {r}^{N}_{L} to represent the count of complete residue systems {r}_{L} that have for their modulus the primorial p_{L}# of a lower prime p_{L} < p_{N} within an interval of the primorial p_{N}#.
{r}^{N}_{L} = p_{N}# / p_{L}# (2)
There is always just one complete residue system {r}_{N} within an interval of p_{N}#, thus {r}^{N}_{N} = 1, and there would be (p_{N}# / p_{1}#) = (p_{N}# / 2) = {r}^{N}_{1} instances of the {r}_{1 }residue system within p_{N}#. All of the values from the original p_{N}# primorial interval that are congruent to 0 (mod 2) have p_{1} = 2 as their lowest prime factor. There would be (p_{N}# / 2) = {r}^{N}_{1} such values. Only those values that are congruent to 1 (mod 2) can have a higher prime number p_{H} > p_{1 }as their lowest prime factor.
Let r_{N} represent the ratio of numbers within the primorial for p_{N} that have p_{N} as their lowest prime factor. There is only one value that is congruent to 0 (mod 2) in each interval of p_{1}# = 2, therefore r_{1} = 1. That means that there is always one number in each interval of 2 that is not a multiple of 2. That is the value that is congruent to 1 (mod 2) and its count can be calculated as p_{1}# – r_{1} = 2 – 1 = 1. Theorem 1 definitely applies to the first prime and its primorial.
For an interval of p_{2}# = 6, the residue system {r}_{2} contains {0, 1, 2, 3, 4, 5} (mod 6). There must be r_{1} • {r}^{2}_{1} = r_{1} • (p_{2}# / p_{1}#) = 3 numbers within that interval that have 2 as their lowest prime factor. Those three are congruent to {0, 2, 4} (mod 6). Another way to think of this is that, since initially multiplying the primorial of 2 by p_{2} = 3 generates the primorial of 6, there must be three multiples of 2 within that 6, because there is always one multiple of 2 within each interval of 2.
When the value congruent to 0 (mod 2) in an interval of 2 is multiplied by 3 in generating an interval of 6, the result is congruent to 0 (mod 6) and since 6 is divisible by 2, it is still congruent to 0 (mod 2). An even number times any positive integer is always an even number. So while there are two multiples of 3 in each interval of 6, one of them must have 2 as its lowest prime factor. The other one corresponds back to a value that was congruent to 1 (mod 2) in the interval of 2, the count of which was p_{1}# – r_{1}. When it is multiplied by 3 the result is congruent to 3 (mod 6) and hence to 0 (mod 3). That there is one such value means r_{2} = 1 = p_{1}# – r_{1}.
The count of what is left, then, is p_{2}# – r_{1} • (p_{2}# / p_{1}#) – r_{2} = 6 – 3 – 1 = 2. There are two numbers in each multiple of 6 that do not have 2 or 3 as their lowest prime factor. They are the numbers congruent to 1 or 5 (mod 6). Those numbers are each either a composite that has a prime greater than p_{2} as their lowest prime factor or they themselves are prime. When an interval of 6 is multiplied by p_{3} = 5 to initially generate an interval of p_{3}# = 30, it is these two values and only these two values that can produce composites that have 5 as their lowest prime factor.
The other four numbers in the interval of 6 will, when multiplied by 5, result in composites that still have 2 or 3 as a prime factor. This implies that r_{3} = 2 = p_{2}# – r_{1} • (p_{2}# / p_{1}#) – r_{2}.
Since p_{2}# = p_{2} • p_{1}#, we can factor p_{2} from the first two terms on the right side of that expression:
r_{3} = p_{2} • (p_{1}# – r_{1} • (p_{1}# / p_{1}#)) – r_{2} = p_{2} • (p_{1}# – r_{1}) – r_{2}
But r_{2} = (p_{1}# – r_{1}), so substituting yields:
r_{3} = p_{2} • r_{2} – r_{2 }= r_{2} • (p_{2} – 1) = 1 • (3 – 1) = 2
An interval of p_{3}# = 30 would contain {r}^{3}_{1 }= (p_{3}# / p_{1}#) = 15 instances of the {r}_{1 }residue system, {r}^{3}_{2 }= (p_{3}# / p_{2}#) = 5 instances of the {r}_{2 }residue system, and of course {r}^{3}_{3 }= (p_{3}# / p_{3}#) = 1 instance of the {r}_{3 }residue system. Thus there would be r_{1} • {r}^{3}_{1 }= 15 numbers that have 2 as their lowest prime factor, r_{2} • {r}^{3}_{2} = 5 numbers that have 3 as their lowest prime factor, and r_{3} • {r}^{3}_{3 }= 2 numbers that have 5 as their lowest prime factor. The numbers that are left do not have 2, 3, or 5 as a factor. When this interval of p_{3}# = 30 is multiplied by p_{4} = 7 to generate an interval of p_{4}# = 210, it is these numbers that will have p_{4} = 7 as their lowest prime factor:
r_{4} = p_{3}# – r_{1} • {r}^{3}_{1} – r_{2} • {r}^{3}_{2} – r_{3} • {r}^{3}_{3} = p_{3}# – S (r_{L} • {r}^{3}_{L})_{ }{for L = 1 to 3
In this case, r_{4} = 30 – 15 – 5 – 2 = 8. The factorization of those 8 numbers is shown in Table 2.
Table 2: Factorization of Any p_{4}# = 210 Primorial Interval for the Lowest Prime Factor p_{4} = 7
Primorial Interval Member 
Lowest Prime Factorization 
Residues 

Modulo
p_{4}# 
Modulo
p_{3}# 
Modulo
p_{2}# 

210n + 7 
7 • (30n + 1) 
7
(mod 210) 
1 (mod 30) 
1 (mod 6) 
210n + 49 
7 • (30n + 7) 
49
(mod 210) 
7 (mod 30) 
1 (mod 6) 
210n + 77 
7 • (30n + 11) 
77
(mod 210) 
11 (mod 30) 
5 (mod 6) 
210n + 91 
7 • (30n + 13) 
91
(mod 210) 
13 (mod 30) 
1 (mod 6) 
210n + 119 
7 • (30n + 17) 
119
(mod 210) 
17 (mod 30) 
5 (mod 6) 
210n + 133 
7 • (30n + 19) 
133
(mod 210) 
19 (mod 30) 
1 (mod 6) 
210n + 161 
7 • (30n + 23) 
161
(mod 210) 
23 (mod 30) 
5 (mod 6) 
210n + 203 
7 • (30n + 29) 
203
(mod 210) 
29 (mod 30) 
5 (mod 6) 
The count of the numbers that do not have a prime p_{N} or lower as their lowest prime factor within an interval of p_{N}# represents the count of the numbers that will have p_{N+1} as their lowest prime factor in an interval of p_{N}# • p_{N+1} = p_{N+1}#. The previous expression can be generalized as:
r_{N+1} = p_{N}# – S (r_{L} • {r}^{N}_{L})_{ }{for L = 1 to N (3)_{ }
From
equation (2) we have {r}^{N}_{L}
= p_{N}# / p_{L}#, and from equation (1) we
have p_{N}# = p_{N} • p_{N1}#, so p_{N}
can be factored from all of the terms on the right of equation (3) similar to
what was done with r_{3}, which
leads to r_{N+1} = r_{N} • (p_{N} – 1), or alternatively, with N > 1:
r_{N} = r_{N1} • (p_{N1} – 1) (4)
Thus r_{N} is a constant for all p_{N}# intervals. Solving equation (4) for r_{4} gives r_{4} = r_{3} • (p_{3} – 1) = 2 • (5 – 1) = 8, which is in agreement with what we arrived at previously. Not only have we proven that r_{N} is a constant, but we have proven that it is related to previous values of r.
Q.E.D.
This relationship also corresponds to the local minima of Euler’s totient (phi) function and appears in the OnLine Encyclopedia of Integer Sequences as A005867.^{[10]}
Obviously there are no numbers less than p_{N} that can have p_{N} as a factor, and since p_{N} itself is prime, it is not necessary to consider any primorial intervals that start at p_{N} or lower. It is the intervals that start at p_{N} + 1 and above that are important. In those intervals, the numbers represented by r_{N} all must be composite; therefore we can refer to r_{N} as the composite to primorial ratio. The interval that starts at p_{N} + 1 would complete its first full primorial interval at p_{N} + p_{N}#. Because in some ways we can think of composite numbers as molecules composed of their constituent prime factor atoms and arranged in a lattice across their primorial interval, this value shall be called the first atomic boundary and labeled a_{N}. If we make a function T_{N}(x) to count the number of composites that have p_{N} as their lowest prime factor, then we can say that r_{N }= T_{N}(a_{N}). Table 3 lists these values for the first twelve primes.
Table
3: Composite to Primorial Ratio and Ratio Summation for the First Twelve Primes
N 
p_{N} 
p_{N}# 
a_{N} = p_{N}# + p_{N} 
r_{N }= T_{N}(a_{N}) 
Σ (Numerator) 
1 
2 
2 
4 
1 
1 
2 
3 
6 
9 
1 
4 
3 
5 
30 
35 
2 
22 
4 
7 
210 
217 
8 
162 
5 
11 
2310 
2321 
48 
1830 
6 
13 
30030 
30043 
480 
24270 
7 
17 
510510 
510527 
5760 
418350 
8 
19 
9699690 
9699709 
92160 
8040810 
9 
23 
223092870 
223092893 
1658880 
186597510 
10 
29 
6469693230 
6469693259 
36495360 
5447823150 
11 
31 
200560490130 
200560490161 
1021870080 
169904387730 
12 
37 
7420738134810 
7420738134847 
30656102400 
6317118448410 
Now that we have a proof that the count of the numbers having p_{N} as their lowest prime factor is constant over any interval of p_{N}#, what can we say about the pattern of those numbers?
Theorem 2: The pattern of the numbers having p_{N} as their lowest prime factor repeats over intervals of the primorial p_{N}#.
Proof: Again let the sequence of numbers a_{0}, a_{1}, a_{2}, … a_{m2}, a_{m1} represent all the integers within any interval of the primorial p_{N}# such that a_{i} Î {a} and (n • p_{N}# + A) < a_{i} ≤ ((n + 1) • p_{N}# + A), where n is a nonnegative integer and A is an integer offset where 1 ≤ A ≤ p_{N}# so that all a_{i }> 1.
When the primorial p_{N}# is divided into {a}, the resulting residue system {r}_{N} is a complete residue system. This means that each residue r_{i} in {r}_{N} can be mapped to exactly one of the integers in {a}. Map the residue r_{0} = 0 to a_{0}, and the residue r_{1} = 1 to a_{1}, and so on, up to r_{m1} = m – 1, which maps to a_{m1}. The result of this mapping is that a_{i} º i (mod p_{N}#) for all i where 0 ≤ i ≤ m – 1 and where m represents the modulus p_{N}# so that m – 1 = p_{N}# – 1.
Let n = n + 1 so that a new sequence {a¢} is generated for the next primorial interval. That is, let a_{0}¢, a_{1}¢, a_{2}¢, … a_{m2}¢, a_{m1}¢ represent all the integers within the next primorial interval such that ((n + 1) • p_{N}# + A) < a_{i}¢ ≤ ((n + 2) • p_{N}# + A) for all a_{i}¢.
This means that a_{i}¢ = a_{i} + p_{N}# for all i where again 0 ≤ i ≤ m – 1 and m – 1 = p_{N}# – 1. Since a_{i} º i (mod p_{N}#) for all i and p_{N}# º 0 (mod p_{N}#), this implies that a_{i}¢ º i (mod p_{N}#) for all i, meaning that the residues for the next primorial interval can be mapped to the integers within the primorial in the exact same order every time.
As shown in the proof of theorem 1, the numbers that have p_{N} as their lowest prime factor have residue modules the primorial p_{N}# that relates to a specific residue in the previous p_{N1}# primorial. For example, the numbers that are 0 (mod 5) within a primorial of 5# = 30 and thus have p_{3} = 5 for their lowest prime factor have residues of 1 or 5 (mod 6). Since those residues are mapped in the same order for every interval, the numbers that have p_{N} as their lowest prime factor occur in the same order in every interval as well. This can easily be seen in Table 1 where the residues modulo p_{3}# = 30 would repeat in the same order for the next n + 1 interval.
Q.E.D.
Theorem 3: The pattern of the numbers having p_{N} as their lowest prime factor is symmetrical within intervals of the primorial p_{N}#.
Proof: Again let the sequence of numbers a_{0}, a_{1}, a_{2}, … a_{m2}, a_{m1} represent all the integers within any interval of the primorial p_{N}# such that a_{i} Î {a} and (n • p_{N}# + A) < a_{i} ≤ ((n + 1) • p_{N}# + A), where n is a nonnegative integer and A is an integer offset where 1 ≤ A ≤ p_{N}# so that all a_{i }> 1.
Then once again divide the primorial p_{N}# into {a} and map the resulting residues r_{0} = 0 to a_{0}, and r_{1} = 1 to a_{1}, and so on, up to r_{m1} = m – 1 to a_{m1}, such that a_{i} º i (mod p_{N}#) for all i.
Now pair up the members of the interval based on the residues. Pair a_{0} with a_{m1}, a_{1} with a_{m2}, and so on, such that for each pair (a_{j}, a_{k}) the sum j + k = m – 1. Since a_{j} º j (mod p_{N}#) and a_{k} º k (mod p_{N}#), then by the properties of congruence, (a_{j} + a_{k}) º (j + k) (mod p_{N}#) º (m – 1) (mod p_{N}#).^{[11] }Since m – 1 = p_{N}# – 1, that is equivalent to saying (a_{j} + a_{k}) º (–1) (mod p_{N}#).
Now suppose we pair up the members of the interval again, but this time pair a_{0} with a_{1}, then a_{2} with a_{m1}, and a_{3} with a_{m2}, and so on, such that for each pair (a_{j}, a_{k}) either the sum j + k = 1 or the sum j + k = m + 1. Since m represents the modulus p_{N}#, that is equivalent to saying (a_{j} + a_{k}) º 1 (mod p_{N}#).
Likewise it is possible to produce pairs (a_{j}, a_{k}) for every residue r_{i} in the original complete residue system so that (a_{j} + a_{k}) º r_{i} (mod p_{N}#). We can say that the residue system {r} is invariant under this pairwise transformation.
We can also invert the residue system by subtracting each a_{i} from ((n + 1) • p_{N}# + A) + 1 to generate a new sequence {a¢}. Dividing the primorial p_{N}# into {a¢} will result in the complete residue system {r¢}, where r_{i}¢ = m – r_{i}. For example, we previously noted that an interval for the primorial p_{2}# = 6 contains the values (6n + 1), (6n + 2), (6n + 3), (6n + 4), (6n + 5), and (6n + 6) which produces the residue system {1, 2, 3, 4, 5, 0} (mod 6). Subtract these values from (6n + 7) and the results are the values 6, 5, 4, 3, 2, 1 which produces the residue system {0, 5, 4, 3, 2, 1} (mod 6), which is the inverse of the original residue system. So we can also say that the residue system {r} is invariant under inversion.
That {r} is invariant under these transformations allows us to conclude that the pattern is symmetrical. That symmetry can readily be seen in Table 1.
Q.E.D.
Conclusions
The technique of characterizing composites by their lowest prime factor over primorial intervals potentially has several useful applications. It is hoped that these proofs can help in the development of such applications.
Acknowledgments
I
am grateful to the following individuals for their assistance and advice: Dr.
Peter Gibson, The University of Alabama in
References:
1.
Dickson, Leonard E. “History
of the Theory of Numbers Volume I: Divisibility and Primality”.
2.
Weisstein, Eric W.
"
3. Eric W. Weisstein. “Prime Number.” From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/PrimeNumber.html
4. Eric W. Weisstein. “Fundamental Theorem of Arithmetic.” From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html
5. Eric W. Weisstein. “Prime Factorization.” From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/PrimeFactorization.html
6. Eric W. Weisstein. “Composite Number.” From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/CompositeNumber.html
7. Eric W. Weisstein. “Primorial.” From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/Primorial.html
8. Eric W. Weisstein. “Congruence.” From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/Congruence.html
9.
Eric W. Weisstein. “Complete
Residue System.” From MathWorldA
Wolfram Web Resource. http://mathworld.wolfram.com/CompleteResidueSystem.html
10. Sloane, N. J. A. Sequence A005867 in "The OnLine Encyclopedia of Integer Sequences."
11. Eric W. Weisstein. “Congruence.” From MathWorldA Wolfram Web
Resource. http://mathworld.wolfram.com/Congruence.html
Bibliography:
Caldwell, Chris K. “The Prime Pages”, http://primes.utm.edu/.
Crandall, R. and Pomerance, C. Prime
Numbers: A Computational Perspective, 2nd ed.
Dickson, Leonard E. “History of the Theory of Numbers
Volume I: Divisibility and Primality”.
Guy, Richard K. “Unsolved Problems in Number Theory, Third
Edition”.
Riesel, H. Prime
Numbers and Computer Methods for Factorization, 2nd ed.