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\]p=:1+S(n)/p-1/p.\] and the sum here isWe have \[ \sumS(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 the $h$ sum is \[ \leftS(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 ).\]
