Consider $10$ distinct positive integers that are all prime to each other (that is, there is no a prime factor common to all), but such that any two of them are not prime to each other. What is the smallest number of distinct prime factors that may appear in the product of $10$ numbers?
Problem
Source: Lusophon 2016 CPLP P1
Tags: number theory, Prime factor, Product, coprime, positive integers
29.08.2018 09:28
Notice that $10$ is a triangular number. Thus, the desired $10$ numbers are of the form $p_1 p_2, p_1 p_3,p_1 p_4,p_1 p_5, p_2 p_3, p_2 p_4, p_2 p_5, p_3 p_4, p_3 p_5, p_4 p_5$ Thus, the answer is $\boxed{5}$
24.06.2024 22:31
I might be mistaken, but I think I have an example for $3$ primes. (clearly $2$ primes is not possible) Take: $2\mid a_{i}/\forall i\in[1; 9]$ $3\mid a_{j}/\forall j\in[2; 10]$ $5\mid a_{1}, 5\mid a_{10}$ And for them to be distinct just take different exponents. (Please correct me if I'm wrong)
29.06.2024 17:59
Let's prove that the smallest number of distict prime factors is $3$. If there were only one prime factor, all the $10$ numbers should be multiples of it and then they wouldn't be all prime to each other, contradiction. If there were only two distinct prime factors, say $p$ and $q$, there should be a number of the form $p^{x}$ or $q^{x}$, otherwise all the numbers would be multiples of $pq$, contradiction. WLOG suppose the number is of the form $p^{x}$. Since the other numbers aren't prime to $p^{x}$, they all must be multiples of $p$, but then they wouldn't be all prime to each other, contradiction. Now let's give an example for $3$ primes. Let $p$, $q$ and $r$ be distinct prime numbers. The example of ten numbers $pq$, $qr$, $rp$, $p^{2}q$, $q^{2}r$, $r^{2}p$, $pq^{2}$, $qr^{2}$, $rp^{2}$, $pqr$ works. With $p = 2$, $q = 3$ and $r = 5$, we get $6$, $15$, $10$, $12$, $45$, $50$, $18$, $75$, $20$, $30$.