Let us fix a natural number $N>1$ and $a_1, \ldots, a_n$ natural numbers satisfying $0 \leq a_i < N$, with the property that $1+ \sum a_i$ is divisible by $N$. Let $\phi$ be the Euler totient function (defined with the convention $\phi(1)=0$). I define the following quantity: $$ \psi(a_1, \ldots, a_n; N):= \sum_{i=1}^n \psi_i := \sum_{i=1}^n \phi(\gcd( a_1, \ldots, a_i +1, \ldots, a_n; N)). $$ I would like to have a closed formula (or an inductive one) for $\psi$ in terms of the initial data (I imagine it should depende on the prime decomposition of $N$).

For example, when $N= p^{\alpha}$ for $p$ a prime number, we have that one of the $a_i$, wlog $a_n$, is coprime with $N$. By defining $p^{\beta}$ to be $\gcd(a_1, \ldots, a_{n-1}, a_n+1, p^{\alpha})$, we have $$ \psi(a_1, \ldots, a_n; p^{\alpha})= \phi(p^{\beta})=p^{\beta}(1-\frac{1}{p}) $$ when $\beta >0$ and $0$ otherwise.

  • $\begingroup$ For me, sum a_i + 1 is ambiguous, while 1 + sum a_i is not : Do you mean the latter? Also, is there anything that keeps your sum from being the sum over n of phi(1)? Gerhard "Ask Me About System Design" Paseman, 2013.02.06 $\endgroup$ Feb 6, 2013 at 16:13
  • $\begingroup$ With your convention $\phi(1)=0$, wouldn't $\psi(a_1,\dots,a_n;p^\alpha) = 0$ when $\beta=0$? $\endgroup$ Feb 6, 2013 at 16:31
  • $\begingroup$ @Gerhard, you are right about the convention for the sum, I was ambiguous. I have now corrected. And yes, most of the time that sum is just the sum over $n$ of $\phi(1)$. $\endgroup$
    – calc
    Feb 6, 2013 at 20:46
  • $\begingroup$ @Greg, yes you are right. I have edited the text to incorporate your remark. $\endgroup$
    – calc
    Feb 6, 2013 at 20:47

1 Answer 1


Below I characterize set of values achievable by $\psi(a_1,\dots,a_n;N)$.

Let $d_i=\gcd(a_1,\dots,a_i+1,\dots,a_n,N)$. First notice that $d_1,\dots,d_n$ are divisors of $N$ and they are pairwise co-prime (as $d_i|(a_i+1)$ while $d_j|a_i$ for every $j\ne i$).

I claim that besides these two conditions the values $d_i$ can be arbitrary. That is, let $d_1,\dots,d_n$ be any pairwise co-prime divisors of $N$; then there exist $a_1, \dots, a_n$ such that $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$ and thus $$\psi(a_1,\dots,a_n;N) = \sum_{i=1}^n \phi(d_i).$$

Let $d_0=1$. Then there exist pairwise co-prime positive integers $D_0, D_1, \dots, D_n$ such that $D_0D_1\cdots D_n=N$ and $d_i|D_i$ for every $i=0,1,\dots,n$. Namely, let $D_i = \gcd(N,d_i^\infty)=\lim_{k\to\infty}\gcd(N,d_i^k)$ for every $i=1,\dots,n$; and $D_0 = \tfrac{N}{D_1D_2\cdots D_n}$.

To enforce equalities $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$ for every $i=1,\dots,n$, it is enough to require the following congruences $$(\star)\qquad a_i \equiv d_j - \delta_{ij} \pmod{D_j}$$ for every $j=0,1,\dots,n$ (where $\delta_{ij}$ is Kronecker's delta). Indeed, if $a_1,\dots,a_n$ satisfy congruences $(\star)$, then $\gcd(a_j,D_j)=1$ and $\gcd(a_j+1,D_j)=d_j$ for $j=1,\dots,n$; and $\gcd(a_i,D_j)=d_j$ for every $i=1,\dots,n$, $j=0,\dots,n$ and $i\ne j$. So we trivially have $\gcd(a_1,\dots,a_i+1,\dots,a_n,D_i)=d_i$ while $\gcd(a_1,\dots,a_i+1,\dots,a_n,D_j)=1$ for every $j\ne i$, which further imply that $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$ for every $i=1,\dots,n$.

For every fixed $i$, the congruences $(\star)$ represent a system of congruences for $a_i$ with pairwise co-prime moduli $D_0, \dots, D_n$. By Chinese Remainder Theorem, this system has a solution (i.e., value of $a_i$) modulo $D_0D_1\cdots D_n=N$. That is, there exist integers $a_1,\dots,a_n$ with $0\leq a_i<N$ that satisfy congruences $(\star)$ and thus $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.