Inspired with this PROBLEM I am interested in those natural numbers that the set of their divisors can be partitioned into two sets with equal product. For example we can decompose divisors of $8$ into $\lbrace 1,8\rbrace$ and $\lbrace 2,4\rbrace$. Is the sequence of this numbers well-known? Is there any characterization for them ? Any suggestion would be helpful.
6
-
$\begingroup$ each prime has to be raised to an odd power $\endgroup$– Anthony QuasCommented Aug 25, 2013 at 19:23
-
1$\begingroup$ not so: for 16, we have {1,2,16} and {4,8}. $\endgroup$– Greg MartinCommented Aug 25, 2013 at 19:31
-
$\begingroup$ The product of all the divisors of $n$ equals $n^{\tau(n)/2}$, where $\tau(n)$ is the number of divisors of $n$. (This can be easily proved with a pairing argument.) If the divisors of $n$ can be partitioned in the desired way, it follows that the product of all divisors of $n$ is a perfect square. Therefore a necessary condition is that $n^{\tau(n)}$ be a perfect 4th power; in other words, either $\tau(n)$ is a multiple of 4, or $n$ is a 4th power. I suspect that this necessary condition is also sufficient. $\endgroup$– Greg MartinCommented Aug 25, 2013 at 19:35
-
$\begingroup$ So I guess that what I should have said is each prime should be raised to a power that is congruent to 2 or 3 modulo 4. $\endgroup$– Anthony QuasCommented Aug 25, 2013 at 19:42
-
$\begingroup$ Numbers whose divisors multiply to a square are tabulated at oeis.org/A048943 --- it says, $n$ is a 4th power, or $n$ has at least two prime factors with odd multiplicities, or $n$ has at least one prime factor with multiplicity 3 modulo 4. $\endgroup$– Gerry MyersonCommented Aug 26, 2013 at 0:02
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Gerry Myerson comments that $n$ can only satisfy this condition if it is a 4th power, or has at least two prime factors with odd multiplicities, or has at least one prime factor with multiplicity 3 modulo 4. This is also sufficient.
Case 1: If $n$ has two prime factors with odd multiplicities, say $p^a$ and $q^b$, then one of the sets in your partition is the set of divisors which have (a power of $p$ which ranges from 0 through $\frac{a-1}{2}$) XOR (a power of $q$ which ranges from 0 through $\frac{b-1}{2}$).
Case 2: If $n$ has at least one prime factor with multiplicity 3 modulo 4, say $p^a$, then one of the sets in your partition is the set of divisors which have a power of $p$ which is 0 or 3 (mod 4). Note that in this case, both of the sets in your partition contain the same number of divisors.
Case 3: If $n$ is a perfect fourth power, let its prime factors be $p_1<p_2<...<p_k$. Then call one of the sets in your partition $S$. A divisor is in $S$ if and only if it is $1$, or its lowest prime factor has multiplicity 0 or 1 (mod 4).
You can check that all of these constructions work out. It's easiest to think about this problem by trying to find a "balanced" partition of the lattice of $n$'s divisors.
