Showing that an arithmetic function is multiplicative

Question

Let $f$ be an arithmetic function that counts the number of consecutive integers between $1$ and $n$ (inclusive) such that both integers are coprime to $n$. More formally,

$$ f(n) = \sum_{\substack{1 \leq t \leq n \\ (t,n)=1 \\ (t+1,n)=1}}1. $$

An immediate observation is that $f(n)=0$ when $n$ is even. After playing around with this function, I suspect that it is multiplicative. That is, if $(a,b)=1$, then $f(ab)=f(a)f(b)$. However, I am unable to prove this.

Is this function really multiplicative or are there counterexamples?

Also, what happens when we modify $f$ so that it counts the number of consecutive triplets that are all coprime to $n$?

Answer 1

Suppose $\gcd(m,n)=1$

Then let $(i,i+1)$ be a good pair for $m$ and let $(j,j+1)$ be a good pair for $n$. The Chinese Remainder theorem gives us a unique $k$ with $1≤k≤mn-1$ such that $$k\equiv i\pmod m\quad \&\quad k\equiv j \pmod n$$

Clearly we have $$k+1\equiv i+1\pmod m\quad \&\quad k+1\equiv j+1 \pmod n$$

So $(k,k+1)$ is a good pair for $mn$.

It remains to be shown that every good pair for $mn$ arises this way. But if $(k,k+1)$ is a good pair for $mn$ then remark that $tm<k<\left((t+1)m-1\right)$ for some $t$ so $(k\pmod m,(k+1)\pmod m)$ is a good pair for $m$ (and similarly for $n$) and we are done.

Answer 2

Let $m$ and $n$ be coprime positive integers. Chinese reminder theorem gives us a ring isomorphism

$$ g: \mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \\ x\pmod{mn} \mapsto (x\pmod m, x\pmod n). $$

For integer $k$, define $A_k \subset \mathbb{Z}/k\mathbb{Z}$ as

$$ A_k = \{t \in \mathbb{Z}/k\mathbb{Z} \, | \, \gcd(t, k) = 1 \land \gcd(t + 1, k) = 1\}. $$

Note that $x \in A_k$ if and only if both $x$ and $x + 1$ are units in the ring $\mathbb{Z}/k\mathbb{Z}$ i.e. $x \in A_k$ if and only if there exist $y \in \mathbb{Z}/k\mathbb{Z}$ and $z \in \mathbb{Z}/k\mathbb{Z}$ such that

$$ xy = 1 \pmod k \\ (x + 1)z = 1 \pmod k. $$

Since $g$ preserves inverses, we see that $t \in A_{mn}$ if and only if $g(t) = (t_1, t_2)$ with $t_1 \in A_m$ and $t_2 \in A_n$. Thus, $g$ restricted to $A_{mn}$ is a bijection between $A_{mn}$ and $A_m \times A_n$. Therefore, $|A_{mn}| = |A_m| |A_n|$.

Multiplicativity of $f$ follows since $f(k) = |A_k|$.

---

Using the result above and the observation that $f(p^k) = p^{k-1}(p - 2)$ for prime $p$, one can derive a formula for $f(n)$ where $n = p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$

$$ f(n) = \prod_{i=1}^r p_i^{k_i-1} (p_i - 2) = n \prod_{i=1}^r \left(1 - \frac{2}{p_i}\right) $$

which is reminiscent of a similar formula for the Euler totient function.

Answer 3

Yes.

We can restrict to values $(a,b)$ such that $a,b>2$ are odd and coprime. Now we use the following observations:

• $f(n)$ counts the number of points $(x,y)$ with coordinates in the ring $\Bbb Z/n$ such that $$ \tag{$C(n)$} x(x+1)y=1\ . $$
• If $u,v$ are invertible modulo $n$, then we can use alternatively (set e.g. $x=ux'$, etc.) $$ \tag{$C(n;u,v)$} x(x+u)y=v\ . $$
• $\Bbb Z/ab\cong (\Bbb Z/a)\times(\Bbb Z/b)$, $x\cong(x',x'')$ in the category of rings. (Chinese Remainder Theorem, CRT.)
• We need an explicit isomorphism. So we write $1=as+bt$ in $\Bbb Z/ab$, where $(a,b)=(s,b)=(t,a)=(s,t)=1$.
• The explicit ring isomorphism from the CRT is $(x',x'')\to x:=btx'+asx''$. (So $(1',1'')\to 1$.) The converse morphism is the canonical projection.
• Let $(x,y)$ be a solution modulo $ab$. Then with $x=btx'+asx''$ we have $$ 1=x(x+1)y=(btx'+asx'')(btx'+asx''+as+bt)y\ , $$ and reading this modulo $a$, respectively modulo $b$ we obtain solutions in $\Bbb Z/a$ and $\Bbb Z/b$ for the equations $C(a;1,1/(bt)^2=1)$ and $C(b; 1, 1/(as)^2=1)$.
• Conversely, let us start with a solution $(x', ?')$ modulo $a$, and a solution $(x'',?'')$ modulo $b$ for the equations above, the corresponding $x$ leads to a solution modulo $ab$.

$\square$

---

Note: Since for a prime $p$ we have $f(p^k)=(p-2)p^{k-1}$, we have in general for a number $N$ with prime factor decomposition $$ N=p_1^{k_1}p_2^{k_2}\dots p_r^{k_r} $$ the formula $$ f(N) =N \left(1-\frac 2{p_1}\right) \left(1-\frac 2{p_2}\right) \cdots \left(1-\frac 2{p_r}\right) \ . $$