Wednesday, November 18, 2009

Primorial

The primorial is the product of primes less than or equal to a number n.

Definition: Primorial: n#


The primorial n# is defined as follows:



Example:

1# = 1

3# = 3*(2#) = 3*2*(1#)=3*2

6# = 5# = 5*3*2



Theorem: if n≥ 1, then n# is less than 4n

Proof:

(1) It is true for (n=1 and n=2)

For n=1, 1#=1 is less than 4.

For n=2, 2#=2 is less than 42 = 16

(2) If n is even and n is greater than 2, then n is composite and we have:

n# = (n-1)# which is proven if we show that (n-1)# is less than 4n-1 since 4n-1 is less than 4n.

(3) To complete the proof, we show that n# is less than 4n if n is odd:

(a) By the inductive hypothesis, we can assume that it is true for all integers less than n and we assume that n is an odd integer where n=2x+1 and x ≥ 1 so that n ≥ 3.

(b) Now, we note that 4m = (1+1)2m = (2-1)*(1+1)2m+1 = (1/2)(1+1)2m+1

(c) Using the Binomial Theorem (see here), we note that:

(1+1)2m+1 = ∑ (i=0, 2m+1) (2m+1!)/[(i!)(2m+1-i)!]

(d) So,

(1/2)(1+1)2m+1 = (1/2) ∑ (i=0, 2m+1) (2m+1)!/[(i!)(2m+1-i)!]

is greater than:

(1/2) [(2m+1)!/(m!)(m+1)! + (2m+1)!/(m+1)!(m)!] = (2m+1)!/(m!)(m+1)!

(e) So, from (b) and (d), we can conclude that:

4m is greater than (2m+1)!/(m!)(m+1)!

since 4m = (1/2)(1+1)2m+1 which is greater than (2m+1)!/(m!)(m+1)!

(f) Each prime p that is greater than m+1 and less than 2m+1 divides (2m+1)!/(m+1)!(m!) since:

(2m+1)!/(m+1)!(m!) is an integer. [see Lemma 5, here]

Let u = (2m+1)!/(m+1)!(m!)

(2m+1)! = u(m+1)!(m!)

Since p does not divide (m+1)! and does not divide (m!), by Euclid's Generalized Lemma (see Corollary 2.1, here), p must divide u.

(g) This gives us:




From the definition of primorial [see Definition above], step #3f above, and step #3e above.

(h) From the inductive hypothesis in step #3a, we can assume that:

(m+1)# is less than 4m+1

(i) So, we have (using step #3g above):

n# = (2m+1)# which is less (m+1)#*4m

(j) Using step #3h above, we have:

(2m+1)# is less than 4m+1*4m = 42m+1

QED

References

No comments: