# Parity of $k = d d^{\prime} > 1$ vs $\text{gcd}(d+1,d^{\prime} +1)$ for distinct divisors $d$ and $d^{\prime}$

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 Answer

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. – user02138 Nov 1 '10 at 20:08
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9083676338195801, "perplexity_flag": "head"}