MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 – Gerhard Paseman Feb 6 '13 at 16:13
With your convention $\phi(1)=0$, wouldn't $\psi(a_1,\dots,a_n;p^\alpha) = 0$ when $\beta=0$? – Greg Martin Feb 6 '13 at 16:31
@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)$. – calc Feb 6 '13 at 20:46
@Greg, yes you are right. I have edited the text to incorporate your remark. – calc Feb 6 '13 at 20:47

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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