Timeline for Consecutive integers that are coprime to a given number
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2021 at 6:33 | comment | added | tomos | 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$..." | |
| Dec 19, 2021 at 22:14 | comment | added | Nick | 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. | |
| Dec 19, 2021 at 19:04 | comment | added | Will Sawin | 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$. | |
| Dec 19, 2021 at 18:53 | answer | added | tomos | timeline score: 4 | |
| Dec 19, 2021 at 18:07 | comment | added | Nick | 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? | |
| Dec 19, 2021 at 17:32 | comment | added | Noam D. Elkies | 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. | |
| Dec 19, 2021 at 17:03 | history | asked | Nick | CC BY-SA 4.0 |