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\}|$?
5
-
$\begingroup$ Yes, working one prime factor of $n$ at a time. For the first question it's $n$ times the product of $(p-2)/p$ over all prime factors of $n$ (regardless of multiplicity, e.g. if $n$ is a multiple of $9$ there's still only one factor of $(3-2)/3$). For the last question, change $p-2$ to $(p-(k+1))$ but replace any negative factor by zero. $\endgroup$– Noam D. ElkiesCommented Dec 19, 2021 at 17:32
-
$\begingroup$ Thanks. That's really helpful. The special cases that I worked out agreed with your answer (prime powers and product of two distinct primes). What about the second question? Is there any place that I can find discussion about it? $\endgroup$– NickCommented Dec 19, 2021 at 18:07
-
1$\begingroup$ The second one is he product of $(p-2)/p$ over all primes $p$ dividing $n$ but not $r$ with $(p-1)/p$ over all primes $p$ dividing $n$ and $r$. These all fall quickly to the Chinese remainder theorem (working with congruences mod the radical of $n$) which reduces you to the case of a single prime $p$. $\endgroup$– Will SawinCommented Dec 19, 2021 at 19:04
-
$\begingroup$ I now see that in all three cases the numbers to be computed as a function of $n$ is multiplicative (at least when $r$ is less than the smallest prime divisor of $n$) so the problem reduces to $n$ being a prime power, which is easy. Perhaps dropping the condition on $r$ makes it slightly more complicated. I also appreciate the elaboration / expansion by Professors Sawin, Gorodetsky and Tomos. $\endgroup$– NickCommented Dec 19, 2021 at 22:14
-
$\begingroup$ multiplicativity: follows just from the definition and working with residue systems. ("for $n,m$ coprime and $N,M$ running over complete residue systems mod $N$ and $M$ then $Nm+Mn$ runs over a complete residue system mod $nm$..." $\endgroup$– tomosCommented Dec 20, 2021 at 6:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 ).\]
