2
$\begingroup$

Suppose $A$ is a set of $2n$ positive integers { $a_{i}$ } with $a_{i} \geq 2$ which can be partitioned into at most $r \leq n$ coprime pairs. The following fact is true: For all $A$ and every $n \geq 1$, $$ \prod_{i = 1}^{2n} (a_{i} - 1) \equiv 0 \pmod{2^{r}}. $$ For example, the set {$2,3,5,6$} can be partitioned into two coprime pairs $(2,3)$ and $(5,6)$, so $2^{2} = 4$ divides $1 \cdot 2 \cdot 4 \cdot 5 = 40$. The set {$2,4,8,16$} cannot be partitioned into coprime pairs (i.e., $r = 0$), so the result above is not particularly interesting.

Question: Can this result be sharpened? References are welcome.

Thanks!

(Update) I think the above result can be generalized to the following: Suppose $A$ is a set of $2n$ positive integers { $a_{i}$ } with $a_{i} \geq 2$ which can be partitioned into at most $r \leq n$ pairs with odd greatest common divisor. Then $2^{r}$ divides $\prod_{i = 1}^{2n} (a_{i} - 1)$.

1 Answers 1

4

Each pair contains at most one even number, since the two numbers have odd gcd. That means that at least one $a_i-1$ for each pair is even, so the product is divisible at least $2^s$, where $s$ is the number of pairs with odd gcd.

Added: As far as sharpening the result, take a set of $2n$ Fermat numbers, numbers of the form $F_k=2^{2^k}+1$. If $k\neq\ell$, then $F_k$ and $F_{\ell}$ share no common factor, so if you take $2n$ of them, say $F_{k_1},\ldots,F_{k_{2n}}$ with $k_1\lt k_2\lt\cdots\lt k_{2n}$, then you can divide them into $n$ coprime pairs; your product will equal $2^{2^{k_1}+\cdots+2^{k_{2n}}}$. So you can make this product divisible by arbitrarily large powers of $2$ for a fixed value of $n$ and $r$.

  • 0
    I deleted a duplicate of this post (posted 9 seconds later).2010-11-08
  • 1
    This is a very nice and simple argument. Can we sharpen the result at all?2010-11-08
  • 1
    @user02138: No; see the addition I just made. The product may be divisible by arbitrarily large powers of $2$.2010-11-08
  • 2
    @user02138: The result *is* applicable when $r=0$: it's just that the conclusion is trivial; the empty product is, by definition, equal to $1$, and any two numbers are congruent modulo $2^0=1$. The point is that you claimed the product *must* be odd, and that is false.2010-11-08