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

I've recently come upon the following (seemingly) simple observation:

Claim: A positive integer $k = d d^{\prime} > 1$ has the opposite parity of $\text{gcd}(d+1,d^{\prime}+1)$ for any pair of distinct divisors $d$ and $d^{\prime}$ of $k$.

There are substantially simple proofs (see comments), and one proof follows from the formula: \begin{eqnarray} \text{gcd}(a,b) = a + b - ab + 2 \sum_{k=1}^{a-1} \lfloor \tfrac{kb}{a} \rfloor. \end{eqnarray}

Corollary: Given a multiplicative arithmetic function $f \colon \mathbb{N} \to \mathbb{N}$ and a pair of coprime integers $a$ and $b$, \begin{eqnarray} f(ab) + 1 \equiv \text{gcd}(f(a)+1,f(b)+1) \mod 2. \end{eqnarray}

Question: Do either of these simple results have any neat use(s) or interesting application(s)?

(NB: The purpose of this post is not so much about finding simple (or simpler) proofs, but rather more about determining possible applications.)


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

I don't have an answer for the applications question (so feel free to vote me down, I guess?), but the proof is much simpler conceptually if you do it in cases:

Let $k = ab$, and if a is odd and b is even, then the product is even and the divisors swap parity when you add one, so they don't have a factor of two in common. If they're both even, then the product is even but $a+1$ and $b+1$ are odd, so the gcd is odd. If they're both odd, then the product is odd but $a+1$ and $b+1$ are both even so the gcd is even.

share|cite|improve this answer
Conceptual proofs are always preferable! But, as you surmised, the question is about applications. – user02138 Nov 1 '10 at 20:08

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.