Consecutive integers that are coprime to a given number Let $n \in \mathbb{N}$. Is there a general formula for $|\{1 \leq k \leq n \mid (k(k+1),n）= 1\}|$?
Or even more generally, for $1 \leq r < n$, is there a formula for $|\{1 \leq k \leq n \mid (k(k+r),n）= 1\}|$? And for $|\{1 \leq k \leq n \mid (k(k+1)\dots(k+r),n）= 1\}|$?
 A: Unless I'm overlooking something (which is very very possible...) I think you can just use the Moebius function in the form
\[ \sum _{d|n}\mu (d)=\left \{ \begin {array}{ll}1&\text { if }n=1\\ 0&\text { if }n\not =1\end {array}\right .\]
so that, recalling the Chinese Residue Theorem also in the case of non-coprime moduli,
\[ \sum _{k=1\atop {(k,n)=(k+r,n)=1}}^n1=\sum _{k=1}^n\sum _{d|k,n\atop {d'|k+r,n}}1=\sum _{d,d'|n}\mu (d)\mu (d')\sum _{k=1\atop {k\equiv 0(d)\atop {k\equiv -r(d')}}}^n1=n\sum _{d,d'|n\atop {(d,d')|r}}\frac {\mu (d)\mu (d')}{[d,d']}\]
and this sum looks nice and multiplicativey - call it $f(n)$.  If $n$ is a power of a prime $p$ we have
\[ f(n)=\left (\sum _{d,d'|n\atop {(d,d')|r\atop {[d,d']=1}}}+\sum _{d,d'|n\atop {(d,d')|r\atop {[d,d']=p}}}\right )\frac {\mu (d)\mu (d')}{[d,d']}=1+\frac {1}{p}\sum _{d,d'|n\atop {(d,d')|r\atop {[d,d']=p}}}\mu (d)\mu (d')=1+\frac {1}{p}\left (\sum _{d,d'|n\atop {(d,d')|r}}-\sum _{d,d'|n\atop {(d,d')|r\atop {[d,d']=1}}}\right )\mu (d)\mu (d')=1+\frac {1}{p}\sum _{d,d'|n\atop {(d,d')|r}}\mu (d)\mu (d')-1/p=:1+S(n)/p-1/p.\]
We have
\[ S(n)=\sum _{h|r}\sum _{d,d'|n\atop {(d,d')=h}}\mu (d)\mu (d')=\sum _{h|r}\sum _{d,d'|n/h\atop {(d,d')=1}}\mu (dh)\mu (d'h)=\sum _{h|r}\mu (h)^2\sum _{d,d'|n\atop {(d,d')=1\atop {(dd',h)=1}}}\mu (d)\mu (d').\]
The $d,d'$ sum is
\[ \left \{ \begin {array}{ll}-1&\text { if }h=1\\ 1&\text { if }h\not =1\end {array}\right .\]
so
\[ S(n)=\left \{ \begin {array}{ll}0&\text { if }p|r\\ -1&\text { if }p\not |r\end {array}\right .\]
so
\[ f(n)=\left \{ \begin {array}{ll}1-1/p&\text { if }p|r\\ 1-2/p&\text { if }p\not |r\end {array}\right \} =1-\nu (p)/p\]
where $\nu (p)$ is the number of residues represented by $0,r$ modulo $p$, and we conclude
\[ \sum _{k=1\atop {(k(k+r),n)=1}}^n1=n\prod _{p|n}\left (1-\nu (p)/p\right ).\]
