Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
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... –  Daved 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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.