4

Suppose I have a prime sequence which start with 3, 5, 7, 11.... and I multiply the first 16 prime numbers. Will the result of the multiplication be divisible by any composite number or a product of composite numbers ?

CodeWeed
  • 143
  • 2
    Try this out for the first $3$ primes. Find all the divisors. Then for the first $4$ primes. You should see the pattern. The proof is an easy consequence of the fundamental theorem of arithmetic. You can look that up if you have to. – Ethan Bolker Aug 12 '17 at 00:07
  • @EthanBolker I was actually looking for a proof or something related to it. Just to be sure. – CodeWeed Aug 12 '17 at 00:31
  • Because the result is square-free, it has exactly $2^{16} = 65536$ divisors, and all but $16$ are composite (including $1$). – Dan Brumleve Aug 12 '17 at 02:42
  • @DanBrumleve Thanks – CodeWeed Aug 12 '17 at 07:58

2 Answers2

4

The product of the first sixteen primes is $961380175077106319535$ (I looked it up in the OEIS, but I could just as easily have used a computer's calculator).

Obviously this number is not divisible by any even integer. However, it is divisible by these composite numbers: $$15, 21, 33, 39, 51, 57, 69, 87, 93, 111, 123, 129, 141, 159, 177$$

And that's just the composite numbers that are divisible by $3$ and one other prime. This product is also divisible by the following composite numbers:

$$35, 55, 65, 85, 95, 115, 145, 155, 185, 205, 215, 235, 265$$

This drives home the point that $961380175077106319535$ is divisible by composite numbers. There's no need to continue listing this number's composite divisors with two prime factors. Unless you really want to.

But let's move on to its divisors that are divisible by four primes, such as $1155$. Since $1155 \mid 961380175077106319535$ and $$1155 = 15 \times 77 = 21 \times 55 = 33 \times 35,$$ it follows that $961380175077106319535$ is divisible by composite numbers that are themselves products of composite numbers.

We can keep going with this until you're tired, the only limitation is that we just have sixteen primes to work with.

David R.
  • 1,236
  • 2
  • 12
  • 33
2

Think of it this way: 3 is prime, right? And so is 5. But $3 \times 5 = 15$, which is composite. That's the product of the first two odd primes.

So we see that 3 and 5 are prime, and so is 7. But $3 \times 5 \times 7 = 105$, which is composite. Obviously 105 is divisible by 15.

Instead of $3 \times 5 \times 7$, we could have done $15 \times 7$ to get the same answer. And then to multiply in the next prime we can do $105 \times 11 = 1155$. This number is divisible by 15 and 105.

Then we go on to $1155 \times 13 = 15015$. This number is divisible by 15, 105 and 1155.

Of course 15015 has lots of other divisors, but I'm choosing to focus on those numbers we can call "half primorials." A primorial is the product of consecutive primes starting with 2. A half primorial is the product of consecutive odd primes starting with 3.

Only the first primorial and the first half primorial are prime. The rest are composite, and more importantly to your question, each primorial is divisible by all smaller primorials and half primorials, and each half primorial is divisible by all smaller half primorials, almost all of which are composite.

Robert Soupe
  • 14,663