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$

  • 1
    $\begingroup$ 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. $\endgroup$ – Randall Feb 8 '19 at 16:32
  • $\begingroup$ Thanks, what would be the best way fix? $\endgroup$ – Rob G Feb 8 '19 at 16:41
  • $\begingroup$ 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$. $\endgroup$ – Randall Feb 8 '19 at 16:44
  • $\begingroup$ ok. Thank you for your help. $\endgroup$ – Rob G Feb 8 '19 at 16:46
  • $\begingroup$ 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)$? $\endgroup$ – Torsten Schoeneberg Feb 11 '19 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)$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.