# Generating primes from other primes

For a natural number $n$ let $M$ be an $n$ by $n$ matrix w/$0$'s on diagonal and natural numbers off diagonal and let $p_1, p_2, \dots, p_n$ be a set of prime numbers.

Note then, that

$$p=\sum_{i=1}^n (\pm) \prod_{j=1}^n p_i^{m_{ij}}$$

is not divisible by any of the primes $p_1, p_2, \dots, p_n$.

Questions: Is there a finite set of primes that would generate (a) all co-primes to the set, (b) all other primes in this fashion (varying $M$ and signs).

Example: $p_1 = 2$, $p_2=3$,

$$2+3 = -2^2 + 3^2 =5,$$ $$2^2+3 = 2^4 - 3^2 = 7,$$ $$2^3+3 = -2^4+ 3^3 = 11,$$ $$2^2+ 3^2 = 13,$$ $$\dots,$$ $$? =37.$$

What restriction on $M$ and signs would produce only primes for a set $p_1, p_2, \dots, p_n$?

-

Intuitively, the answer to the first two questions is no and the last is that there is no restriction on $M$ and signs that will produce only primes. The fundamental reason is that powers get very far apart when the exponent is large.

Pick your set $\{p_1,p_2,p_3,\ldots p_n\}$. It is finite and has a maximum. Now pick a prime and a composite that are about $10^{100^n}$ times the largest one. It is quite unlikely that you can express them this way. We could calculate how many powers of the primes are less that this and find it is small compared to the number of numbers to express. This will not be rigorous-there could be some cancellation between larger powers of the primes that brings it back into range.

For the last, note that $2^5+3=35$. You just need to find one prime that $2$ is a primitive root of and you will be able to find a multiple of that prime.

-
Thank you for sharing your intuition. I wonder if the rigorous answer depends on precise distribution of primes and if the statement is weaker or stronger than Goldbach's conjecture... – DVD May 13 '13 at 22:38
@Daved: I think it is weaker than Goldbach's conjecture-you are adding many more than two primes. – Ross Millikan Jun 11 '13 at 12:34