Given the number of all positive divisors of an unknown positive integer and the product of those divisors, how can one find the unknown integer?
Sunday, April 22, 2012
Please email your solutions to puzzles@cotpi.com.
6 comments
Credit
This is an original puzzle from cotpi.
Post a comment
quasi solved this puzzle:
Theorem. Let \(n\) be a positive integer. Let \(k\) be the number of all positive divisors of \(n\). Let \(m\) be the product of all positive divisors of \(n\). Then \(n = m^{\frac{2}{k}}\).
Proof. If \(n\) is not a perfect square, the \(k\) positive divisors of \(n\) can be grouped in \(\frac{k}{2}\) pairs \((a, b)\) with \(a \lt b\) and \(ab = n\). It follows that the product of the factors of n is \(n^{\frac{k}{2}}\).
If \(n\) is a perfect square, the \(k - 1\) positive integer factors of \(n\) other than \(\sqrt{n}\) can be grouped in \(\frac{k - 1}{2}\) pairs \((a, b)\) with \(a \lt b\) and \(ab = n\). The product of those factors is \(n^{\frac{k - 1}{2}}\), hence the product of all the factors is \(n^{\frac{k - 1}{2}} \sqrt{n}\), which simplifies to \(n^{\frac{k}{2}}\).
In both cases, \(m = n^\frac{k}{2}\), hence \(n = m^\frac{2}{k}\).
Gabriel Elpers solved this puzzle:
Suppose there are \(D\) divisors of the natural number \(N\) and that \(P\) is the product of all the divisors. For every divisor \(d\) there is a unique quotient \(q\) such that \(dq = N\). The product of all divisors and their quotients is \(P^2\) since each divisor appears in this expression exactly twice. Rearranging the factors so that each divisor is paired with its quotient, we see that \(P^2 = N^D\). Therefore, \(N = P^{\frac{2}{D}}\).
Siddhesh Chaubal solved this puzzle:
Consider the case in which the number of divisors of the positive integer \(n\) is even. Let it be \(2k\) where \(k\) is a positive integer. Then the product of all divisors is \(n^k\), since each divisor of \(n\) has corresponding to it another divisor of \(n\) such that their product is \(n\). Since there are \(k\) such pairs, their product is \(n^k\). Thus the \(k\)th root of the product is \(n\).
Now consider the case in which the number of divisors is odd. Let it be \(2k + 1\) where \(k\) is a non-negative integer. Then, the number is a perfect square. The product of all divisors in this case is \(n^k \sqrt{n}\), i.e. \(\sqrt{n}^{2k + 1}\). To find \(n\), take the \((2k + 1)\)th root of the product and square it.
Gnanasenthil G solved this puzzle:
Theorem. Let \(n\) be a positive integer, let the number of all positive divisors of \(n\) be \(k\), and let the product of all positive divisors of \(n\) be \(m\). Then \(m = n^{\frac{k}{2}}\).
Proof. Let \(A\) be the set of all positive divisors of \(n\). When a positive integer is divided by its divisor it gives a quotient which is another divisor of the positive integer.
If \(n\) is a perfect square, there is an element \(x \in A\) such that \(x^2 = n\), so this element doesn't pair with a different element in \(A\) such that their product is \(n\). In this case, \(|A|\) is an odd number since for every other element in \(A\), there exists another element in \(A\) such that their product is \(n\). We have \(\sqrt{n}\) and \(\frac{k - 1}{2}\) pairs of numbers in \(A\) such that the product of the numbers in each pair is \(n\). Thus, the product of all elements in \(A\) is
\begin{equation*} m = \sqrt{n} \cdot n^{\frac{k - 1}{2}} = n^{\frac{k}{2}}. \end{equation*}
If \(n\) is not a perfect square, \(|A|\) is even since each element in \(|A|\) has a pair in \(A\) such that their product is \(n\). In this case, we have \(\frac{k}{2}\) pairs of numbers in \(A\) such that the product of the numbers in each pair is \(n\). Thus, the product of all elements in \(A\) is
\begin{equation*} m = n^{\frac{k}{2}}. \end{equation*}
Nilabja Ray solved this puzzle:
Let \(n\) be the positive integer, \(k\) be the number of all positive divisors of \(n\) and \(m\) be the product of those divisors.
Unless \(n\) is a perfect square, \(k\) is even, i.e. \(k = 2l\) for a positive integer \(l\). There are \(l\) pairs of divisors and the product of the two numbers in each pair is \(n\). Therefore, the product of all \(l\) pairs is
\begin{equation*} m = n^l = n^{\frac{k}{2}}. \end{equation*}
If \(n\) is a perfect square, \(k\) is odd, i.e. \(k = 2l + 1\) for a non-negative integer \(l\). One of the divisors is \(\sqrt{n}\) and there are \(l\) pairs of divisors and the product of the two numbers in each pair is \(n\). Therefore
\begin{equation*} m = n^{l + \frac{1}{2}} = n^{\frac{k}{2}}. \end{equation*}
Tim Ophelders solved this puzzle:
Let \(D\) be the unknown set of divisors of an unknown positive integer \(A\). The goal is to find \(A\), given \(N = |D|\) and \(P = \prod D\).
Let \(D_\lt\), \(D_\gt\) and \(D_=\) be the sets of numbers in \(D\) smaller, greater and equal to \(\sqrt A\), respectively. Their union is again \(D\).
\[ D_\lt \cup D_\gt \cup D_= = D. \]
Note that there is a bijection between \(D_\lt\) and \(D_\gt\).
\[ d \in D_\lt \Longleftrightarrow \frac Ad \in D_\gt. \]
Let \(m = |D_\lt| = |D_\gt|\). Then \(|D| = |D_=| + |D_\lt| + |D_\gt| = |D_=| + 2m = N\). Note that \(|D_=|\) has the same parity as \(N\), and \(m = \frac{N - |D_=|}{2}\), so
\[ D_= = \begin{cases} \emptyset & \text{ if } N \text{ is even} \\ \{\sqrt{A}\} & \text{ if } N \text{ is odd}. \end{cases} \] \[ \prod D_= = \begin{cases} 1 & \text{ if } N \text{ is even} \\ \sqrt{A} & \text{ if } N \text{ is odd}. \end{cases} \] \[ (\prod D_\gt) \cdot (\prod D_\lt) = \prod_{d \in D_\gt} d \cdot \frac{A}{d} = \prod_{d \in D_\gt} A = A^m \] \[ P = (\prod D_\gt) \cdot (\prod D_\lt) \cdot (\prod D_=) = \begin{cases} A^{\frac{N}{2}} & \text{ if } N \text{ is even} \\ A^{\frac{N - 1}{2}} \sqrt{A} = A^{\frac{N}{2}} & \text{ if } N \text{ is odd}. \end{cases} \] Therefore, \(P = A^{\frac{N}{2}}\), so \(A = \sqrt[N]{P^2}\).