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.


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

  • $\begingroup$ I deleted a duplicate of this post (posted 9 seconds later). $\endgroup$ – Jonas Meyer Nov 8 '10 at 3:26
  • 1
    $\begingroup$ This is a very nice and simple argument. Can we sharpen the result at all? $\endgroup$ – user02138 Nov 8 '10 at 3:32
  • 1
    $\begingroup$ @user02138: No; see the addition I just made. The product may be divisible by arbitrarily large powers of $2$. $\endgroup$ – Arturo Magidin Nov 8 '10 at 3:35
  • 2
    $\begingroup$ @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. $\endgroup$ – Arturo Magidin Nov 8 '10 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.