Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
I deleted a duplicate of this post (posted 9 seconds later). – Jonas Meyer Nov 8 '10 at 3:26
This is a very nice and simple argument. Can we sharpen the result at all? – user02138 Nov 8 '10 at 3:32
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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