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



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.

  • 2
    $\begingroup$ Conceptual proofs are always preferable! But, as you surmised, the question is about applications. $\endgroup$ – user02138 Nov 1 '10 at 20:08

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.