A variant version of Euler's phi function

We have that $Psi (n)=|{xin [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={xin [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^lsum _{1leq a_1<a_2<cdots <a_lleq 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^lsum _{1leq a_1<a_2<cdots <a_lleq k}frac{n}{prod _{i=1}^lp_{a_i}}=nprod _{l=1}^kleft (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^ksum _{substack{Xsubseteq {a_1,cdots ,a_n}\|X|=k}}prod _{yin 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{2times 2times cdots times 2}_{text{l times}}=2^l$ is there by the multiplication principle.

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_ipmod 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}+1equiv m_i+1pmod 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.