Find the smallest positive integer $n$ for which there exist $n$ different positive integers $a_{1}, a_{2}, \cdots, a_{n}$ satisfying $\text{lcm}(a_1,a_2,\cdots,a_n)=1985$, for each $i, j \in \{1, 2, \cdots, n \}$, $gcd(a_i,a_j)\not=1$, the product $a_{1}a_{2} \cdots a_{n}$ is a perfect square and is divisible by $243$, and find all such $n$-tuples $(a_{1}, \cdots, a_{n})$.
Problem
Source:
Tags: number theory, least common multiple, greatest common divisor, prime factorization
MellowMelon
16.11.2007 16:29
The problem doesn't make sense with $ 1985$, since the first and third conditions can't be satisfied simultaneously. Judging from the topic description, $ 1995$ was meant, and here's the solution assuming that. $ n = 7$: $ 15,21,57,105,285,399,665$ is the only sequence that satisfies every condition up to permutation. First, since the least common multiple of all the numbers is $ 1995 = 3 \cdot 5 \cdot 7 \cdot 19$, every $ a_i$ must be the product of some subset of $ \{3,5,7,19\}$. By the second condition, the subset must be nonempty. The third condition requires that the product of all elements of the sequence is divisible by $ 3^5$, but since it also must be a perfect square it must actually be divisible by $ 3^6$. Since each element of the sequence can have at most one $ 3$ in the prime factorization, this gives $ n = 6$ as a lower bound (for now). Suppose $ n = 6$ works. All elements must then be divisible by $ 3$, so the second condition is trivially satisfied. There are now $ 8$ possible numbers to choose for the $ 6$ elements of the sequence: The product of any subset of $ \{5,7,19\}$ times $ 3$. We notice that the product of all $ 8$ of these elements is a perfect square, so in order for the product of the $ 6$ elements of the sequence to be a square we must omit two distinct elements whose product is a perfect square. But since every prime has an exponent of $ 0$ or $ 1$ in these $ 8$ numbers, the product of two of them is a perfect square if and only if they are the same number. Contradiction. $ n = 6$ is not possible. $ n = 7$ is, however. In this case we have $ 6$ elements divisible by $ 3$. The final element is not divisible by $ 3$, since if it were the product would have $ 3^7$ in the prime factorization and not be a perfect square. Let $ a_7$ be the number not divisible by $ 3$. If $ a_7$ is prime, then the second condition requires that all numbers be divisible by $ a_7$, and then the product of the sequence has $ a_7^7$ in the prime factorization, so it can't be a square. So $ a_7$ has to be a product of at least two elements of $ \{5,7,19\}$. Suppose $ a_7$ is the product of two of these, which we will call $ q$ and $ r$, and is not divisible by one of them, which we will call $ p$. That is, $ a_7 = qr$. Of the other $ 6$ elements divisible by $ 3$, we can choose four that are divisible by $ p$: $ 3p, 3pq, 3pr, 3pqr$. But including one of them, $ 3p$, contradicts the second condition. So we only have three choices of numbers divisible by $ p$. Because the product of all sequence elements must be a perfect square, we can only select two of the numbers. Now we need $ 4$ more numbers divisible by $ 3$ in the sequence. We can only choose from $ 3, 3q, 3r, 3qr$, so we must have them all. But including $ 3$ and $ qr$ in the sequence contradicts the GCD condition. Thus, $ a_7$ must be $ 5 \cdot 7 \cdot 19$. So $ a_7 = 5 \cdot 7 \cdot 19$. For the other $ 6$ elements of the sequence, we can only select the product of any subset of $ \{5,7,19\}$ times $ 3$ as before. But notice that one of these, $ 3$, contradicts the GCD condition since $ a_7$ is not divisible by $ 3$. So we only can select from seven elements. The product of these seven elements and $ a_7$ is $ 3^7 5^5 7^5 19^5$. So for this to be a perfect square we have to divide out $ 1995 = 3 \cdot 5 \cdot 7 \cdot 19$, and this is the element we omit. So the other $ 6$ elements must be $ 3 \cdot 5,\ 3 \cdot 7,\ 3 \cdot 19,\ 3 \cdot 5 \cdot 7,\ 3 \cdot 5 \cdot 19,\ 3 \cdot 7 \cdot 19$. This gives the unique sequence described in the first paragraph, and we're done. (edit: typo)
Peter
16.11.2007 16:44
Yes, I think you're right on the 1995.