I have been working on a formula that seems to be a generalization of Euler's Totient Function and have a number of questions:
- 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?
- 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$
Best Answer
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)$$