A variant version of Euler's phi function

Question

The original Euler's phi function goes like this. $$\phi(n)=n\prod_{p|n} (1-1/p)$$ But I want to prove a modified version of it.

$\psi(n) $ : The number of $x$s when $1\le x \le n$ , $x\bot n$ and $(x+1) \bot n$. Then, for $n \ge 3 $ $$\psi(n)=n\prod_{p|n} (1-2/p)$$ where $p$ are distinct primes.

Until now I go by, if $n=p^k$ for some prime $p$, then

$$1\cdot p ,\ 2\cdot p,\ ...,\ p^{k-1}\cdot p \quad $$ and $$1\cdot p-1 ,\ 2\cdot p-1,\ ...,\ p^{k-1}\cdot p-1 \quad $$

so total $2\cdot p^{k-1}$ of numbers are not coprime to $n$, therefore $$\psi(n)=p^k-2p^{k-1}$$

But I don't get to prove $\psi $ is multiplicative with regard to coprime numbers.

How can I prove this?

Answer 1

We have that $\Psi (n)=|\{x\in [n]:(x,n)=1 \wedge (x+1,n)=1\}|.$
Let $n=p_1^{\alpha _1}\cdots p_k^{\alpha _k}.$ Consider the set $$A_j=\{x\in [n]:p_j|x\},$$ notice that this captures the property $(x,n)\neq 1.$ Notice also that $(x+1,n)$ is captured also with these sets because $(n,n+1)=1$ so imagine that we want the opposite, all the numbers minus the ones that do not have that property, check that the negation of the property is $(x,n)>1$ or $(x+1,n)>1.$

Then we have that $$\Psi (n)=n-\sum _{l=1}^k(-1)^{l-1}2^l\sum _{1\leq a_1<a_2<\cdots <a_l\leq k}\left |\bigcap _{i=1}^lA_{a_i}\right |$$ By the inclusion-exclusion principle. Notice that the $2^j$ comes from either $x$ or $x+1$ by the comment above. Notice also that $$\left |\bigcap _{i=1}^lA_{a_i}\right |=\frac{n}{\prod _{i=1}^lp_{a_i}}$$ and so we have that $$\Psi(n)=\sum _{l=0}^k(-1)^{l}2^l\sum _{1\leq a_1<a_2<\cdots <a_l\leq k}\frac{n}{\prod _{i=1}^lp_{a_i}}=n\prod _{l=1}^k\left (1-\frac{2}{p}\right ).$$ Edited: Notice that when you have an expression of the form $(1-a_1x)(1-a_2x)\cdots (1-a_nx)$ and you unfold it, what you are doing is choosing either the $1$ or the $a_jx.$ So, to be able to understand the coefficient corresponding to $x^k$ you have to choose a set of $k$ indices in which you have chosen the $a_j$ in other words you will be adding over the following $$(-1)^kx^k\sum _{\substack{X\subseteq \{a_1,\cdots ,a_n\}\\|X|=k}}\prod _{y\in X}y.$$ This is exactly what is happening with the $a_i$ they are the elements of the set $X$ of size $k.$

Notice that this process is a similar one to the inclusion exclusion process of combinatorics.

Notice that because the negation of the proposition is $(x,n)>1$ or $(x+1,n)>1$ what we are doing is choosing a prime, call it $p_{a_j}$ that is in the prime decomposition of $n,$ and making $x$ or $x+1$ be divisible by it. So we have all the time $2$ options(notice that $p_{a_j}$ can not divide both at the same time!), because in the sum we are assuming $l$ primes of that form then $\underbrace{2\times 2\times \cdots \times 2}_{\text{l times}}=2^l$ is there by the multiplication principle.

Answer 2

Take natural numbers $n,m$ with $\gcd(n,m)=1$.

List the "good" residues for each as $\{m_1, \cdots, m_{\psi(m)}\}$ and $\{n_1, \cdots, n_{\psi(n)}\}$.

For each pair $(i,j)$ with $1≤i≤\psi(m)$, $1≤j≤\psi(n)$ use the Chinese Remainder Theorem to define $$(mn)_{i,j} \equiv \begin{cases} m_i\pmod m \\[2ex] n_j \pmod n \end{cases}$$

Then $(mn)_{i,j}$ is a good residue $\pmod {mn}$.

(Pf: clearly it is relatively prime to $mn$. And $(mn)_{i,j}+1\equiv m_i+1\pmod m$ so it is prime to $m$ since $m_i$ is good. Similarly it is prime to $n$ so we are done.)

It is easy to see that every good residue $\pmod {mn}$ arises in this way, so we are done.

Example: take $m=3$, $n=5$. Then the only good reside $\pmod 3$ is $m_1=1$ and the good residues $\pmod 5$ are $\{1,2,3\}$. The good residues $\pmod {15}$ are then $\{1,7,13\}$...each of these are $\equiv 1 \pmod 3$ and we get $\{1,2,3\}\pmod 5$, respectively.