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, privacy policy and cookie policy

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