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

  • $\begingroup$ Instead of divisors, you mean $a$ that are not coprime. $\endgroup$ – 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)$.

  • $\begingroup$ Oh very nice. Relieved to see it agrees with my answer for <= 3 primes :-) $\endgroup$ – Kevin Buzzard Jan 22 '17 at 17:11
  • $\begingroup$ @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$? $\endgroup$ – usere5225321 Jan 22 '17 at 17:14
  • $\begingroup$ 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 $\endgroup$ – Fedor Petrov Jan 22 '17 at 17:31
  • $\begingroup$ @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)?$ $\endgroup$ – usere5225321 Jan 22 '17 at 23:56
  • 1
    $\begingroup$ For what it's worth, the function $F(q)$ and its generalisations came up quite recently on MO at mathoverflow.net/q/259768/1384 $\endgroup$ – 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.


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.