# Power of $2$ Divisibility Problem

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)$.

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$.
• @user02138: No; see the addition I just made. The product may be divisible by arbitrarily large powers of $2$. – Arturo Magidin Nov 8 '10 at 3:35
• @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. – Arturo Magidin Nov 8 '10 at 3:39