# Euler's Totient Function and Residue Classes

I have been working on a formula that seems to be a generalization of Euler's Totient Function and have a number of questions:

1. I have been researching online and can't seem to find this function anywhere. I'm assuming that it is probably just in a different format. Can anyone point me in the right direction?
2. It is pretty easy to prove the equation below when $$m$$ and $$n$$ share the same prime factors since it is equivalent to Euler's Totient Function. Any hints on how to prove when $$m$$ and $$n$$ do not share the same prime factors?

Let $$R_n =\{ a|a \in \mathbb{Z}, 1\leqq a\leqq n,gcd(a,n)=1 \}$$

Let $$T_n =\{a_1,a_2,...,a_k,a_1+n,a_2+n,...,a_k+n\}$$

Let $$g_m(n)$$ represent the number of elements in $$R_n$$ such that $$a_k+m$$ also exists in $$T_n$$.

Let $$n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$$ represent the prime factorization of $$n$$.

We state that $$g_m(n) = \prod_{p|n,p|m} p_k^{e-1}(p_k-1) \prod_{p|n,p|m\notin \mathbb{Z}} p_k^{e-1}(p_k-2)$$ where $$m$$ is even and $$m\leqq n$$

For example, let $$n=20$$ and $$m=6$$. It follows that

$$R_{20} = \{1,3,7,9,11,13,17,19\}$$ $$T_{20}=\{1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39\}$$ $$g_6(20)=2^1*(2-1)*5^0*(5-2)=6$$ The elements of $$g_6(20)$$ are $$1,3,7,11,13,17$$

• Though it's fixable, I'm not a fan of treating $\varphi(20)$ on one hand as a tuple/ordered set and on the other as an integer. – Randall Feb 8 at 16:32
• Thanks, what would be the best way fix? – Rob G Feb 8 at 16:41
• You could define a set $R_{20}$ to be the integers $x$ with $1 \leq x \leq 20$ with $\gcd(x,20)=1$. Then $\varphi(20)$ is just $|R_{20}|$. Of course, there's nothing special about $20$. – Randall Feb 8 at 16:44
• ok. Thank you for your help. – Rob G Feb 8 at 16:46
• Starting with $37$, are the elements in your example of $T$ not too big by $10$? Also, I don't understand the notation $p|n,p|m\notin \mathbb{Z}$ in your second factor; if the second factor is supposed to range over the primes which don't divide $m$, but the third over those where $p$ does divide $m$, isn't that exactly the other way around than in your example computation of $g_6(20)$? – Torsten Schoeneberg Feb 11 at 20:23

Let $$n = \prod_{j=1}^J p_j^{e_j}$$ and $$g_m(n) = \sum_{l=1}^n 1_{gcd(l,n)=gcd(l+m,n)=1}$$
Using the CRT to decompose $$\mathbb{Z}/n\mathbb{Z} = \mathbb{Z}/p_1^{e_1}\mathbb{Z} \times \ldots \times \mathbb{Z}/p_j^{e_j}\mathbb{Z}, b_j \equiv 1 \bmod p_j^{e_j}, b_j \equiv 0 \bmod p_i^{e_i}$$
$$g_m(n)= \prod_{j=1}^J \sum_{l_j=1}^{p_j^{e_j}} 1_{l= \sum_{i=1}^Jl_i b_i, gcd(l,p_j)=gcd(l+m,p_j)=1}= \prod_{j=1}^J \sum_{l_j=1}^{p_j^{e_j}} 1_{l= \sum_{i=1}^Jl_i b_i}\prod_{i=1}^J1_{gcd(l,p_i)=gcd(l+m,p_i)=1}$$ $$= \prod_{j=1}^J \sum_{l_j=1}^{p_j^{e_j}} \prod_{i=1}^J1_{gcd(l_i,p_i)=gcd(l_i+m,p_i)=1}=\prod_{j=1}^J \sum_{l_j=1}^{p_j^{e_j}} 1_{gcd(l_j,p_j)=gcd(l_j+m,p_j)=1}$$ $$=\prod_{j=1}^J p_j^{e_j-1} \sum_{l_j=1}^{p_j} 1_{gcd(l_j,p_j) = gcd(l_j+m,p_j)=1} = \prod_{j=1}^J p_j^{e_j-1} (p_j-1-1_{p_j \, \nmid\, m})$$ $$= \prod_{p^e\| n, p | m} p^{e-1}(p-2)\prod_{p^e\| n, p \,\nmid\, m} p^{e-1}(p-1)$$