1
$\begingroup$

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

Thanks!

1 Answers 1

3

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
    Conceptual proofs are always preferable! But, as you surmised, the question is about applications.2010-11-01