# Sum of $\sum_{\substack{1<a<q \\(a,q)>1 \\ (a+1,q)>1}}1$

Let $a,q$ be a positive integers. I am trying to evaluate the following sum: $\sum_{\substack{1<a<q \\(a,q)>1 \\ (a+1,q)>1}}1$. Is there a formula that exists to calculate such sums?

Here is an example:

Let $q=15$. We have the following multiple of divisors: 1,2,3,5,6,9,10,12,15.

But since the two pairs (5,6) and (9,10) are consecutives numbers bigger than one but less than q, we get :

$\sum_{\substack{1<a<15 \\(a,15)>1 \\ (a+1,15)>1}}1=2$.

• Instead of divisors, you mean $a$ that are not coprime. – Anthony Quas Jan 22 '17 at 17:01

At first, we count the number of residues $a$ for which both $a$ and $a+1$ are coprime with $n$. Let $q=\prod p_i^{k_i}$ be a factorization of $q$. For any $p_i$, there exist $p_i-2$ admissible remainders modulo $p_i$ (forgotten remainders are 0 and $-1$), thus $(p_i-2)p_i^{k_i-1}$ admissible remainders modulo $p_i^{k_i}$, thus by Chinese Remainders Theorem the answer equals $$F(q):=\prod (p_i-2)p_i^{k_i-1}=q\prod(1-2/p_i).$$ Now your question. There exist $\varphi(q)$ residues $a$ for which $(a,q)=1$, as many residues for which $(a+1,q)=1$, $F(q)$ residues for which both $(a,q)=1$, $(a+1,q)=1$. Thus there exist $\varphi(q)-F(q)$ residues $a$ for which $(a,q)=1$ and $(a+1,q)>1$. But the total number of $a$ for which $(a+1,q)>1$ equals $q-\varphi(q)$. Therefore the answer to your initial question is $q-2\varphi(q)+F(q)$.

• Oh very nice. Relieved to see it agrees with my answer for <= 3 primes :-) – Kevin Buzzard Jan 22 '17 at 17:11
• @FedorPetrov, thanks for your help. Could you give me more details on how you know $F(q)$ is the number of residues for which $a$ and $a+1$ are coprime with $n$? – usere5225321 Jan 22 '17 at 17:14
• when we require that both $a$ and $a+1$ are coprime with $q$, the remainders modulo different prime powers are independent by CRT, this is the main feature – Fedor Petrov Jan 22 '17 at 17:31
• @FedorPetrov Suppose I wanted to calculatee the number of residues $a$ for which $a$,$a+1$ and $a+2$ are coprime with $n$. Does that mean that you would have $q \prod (1-3/p_i)?$ – usere5225321 Jan 22 '17 at 23:56
• For what it's worth, the function $F(q)$ and its generalisations came up quite recently on MO at mathoverflow.net/q/259768/1384 – Kevin Buzzard Jan 23 '17 at 9:49

What you have written down is already a formula for calculating the sum, so really you need to be more precise about what the question is.

But here are some comments which give a simpler formula in the case where $q$ is only divisible by a few primes.

If $q$ is a prime power $p^e$, then the sum is zero, because $(a,q)>1$ if and only if $p$ divides $a$, and that can't happen twice in a row.

If, as in your example, $q$ has two prime divisors $p_1$ and $p_2$, then $q=p_1^{e_1}p_2^{e_2}$ and what must be going on is that one of the two terms $a,a+1$ is a multiple of $p_1$ and the other a multiple of $p_2$. Hence $a$ either satisfies $a=0$ mod $p_1$ and $a=-1$ mod $p_2$ or $a=-1$ mod $p_1$ and $a=0$ mod $p_2$. In each case there is one solution mod $p_1p_2$ by the Chinese Remainder Theorem, and hence $q/p_1p_2=p_1^{e_1-1}p_2^{e_2-1}$ solutions between $1$ and $q$, giving us $2q/p_1p_2$ solutions in this case.

In the general case there is a problem though. Say three primes $p_1,p_2,p_3$ divide $q$. Then we are interested in solving $a=-1$ mod $p_1$ and $a=0$ mod $p_2$ ($q/p_1p_2$ solutions) OR $a=-1$ mod $p_1$ and $a=0$ mod $p_3$ ($q/p_1p_3$ solutions) OR... etc etc, so $3\times2=6$ possibilities giving what looks like $2q(1/p_1p_2+1/p_2p_3+1/p_3p_1)=2q(p_1+p_2+p_3)/(p_1p_2p_3)$ solutions. However unfortunately we have counted some solutions twice here -- there is one number mod $p_1p_2p_3$ which is $-1$ mod $p_1$ and $0$ mod $p_2$ and $p_3$ and we counted it too often. For three or more primes dividing $q$ it's hence messier and I'm not sure there's a simple formula.

Here's the explicit answer when 3 primes divide $q$. We may as well assume $q$ is squarefree (just multiply the answer by $q/p_1p_2p_3$ otherwise). The number of numbers between 1 and $q$ which are $0$ mod $p_1$ and $-1$ mod $p_2$ and congruent to $*$, neither $0$ nor $-1$, mod $p_3$ is $p_3-2$. Similarly for $(-1,0,*)$, $(-1,*,0)$ etc etc giving us $2(p_1+p_2+p_3)-12$. But now you need to count the number of times we are $(a,b,c)$ with $a,b,c$ all either $0$ or $-1$, but not all the same; this gives a further 6. So in this case we get $2(p_1+p_2+p_3)-6$.

The general case will be messier and I don't know if one can do better than this method.