Timeline for How many pairs of numbers between 0 and n-1 are equal to z mod n? [closed]
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 28, 2017 at 14:19 | vote | accept | Samuel Schlesinger | ||
| Mar 25, 2017 at 15:34 | history | closed |
Gro-Tsen R.P. Stefan Kohl♦ Michael Albanese Emil Jeřábek |
Not suitable for this site | |
| Mar 25, 2017 at 14:27 | answer | added | Seva | timeline score: 4 | |
| Mar 25, 2017 at 6:12 | review | Close votes | |||
| Mar 25, 2017 at 15:39 | |||||
| Mar 25, 2017 at 4:41 | comment | added | GH from MO | Well, this is not of research level, but here is a hint. Put $m=p^2$, and then calculate $f(0)$, then $f(p)$, then $f(1)$. These are the three different values $f(z)$ in this case. If this is still too hard for you, then do this for $p=2$, then $p=3$, and so on. This is one way we do mathematics: we specialize a problem and then make it progressively harder. At any rate, your question would be more suitable at math.stackexchange.com | |
| Mar 25, 2017 at 0:58 | comment | added | Samuel Schlesinger | I can't quite figure out the prime power case either.. any hints there? | |
| Mar 25, 2017 at 0:55 | comment | added | GH from MO | Yes. I meant, for $m=p$ prime, $f(z)=p-1$ when $z$ is coprime with $p$ etc. | |
| Mar 25, 2017 at 0:44 | comment | added | Samuel Schlesinger | Where $m = p$ in the first case? | |
| Mar 25, 2017 at 0:35 | comment | added | GH from MO | No. For $m$ prime, $f(z)=p-1$ when $z$ is coprime with $p$, and $f(z)=2p-1$ when $z$ is divisible by $p$. For $m$ a power of $p$ the answer is similar but slightly more complicated: $f(z)$ depends on the exponent of $p$ in $z$. | |
| Mar 25, 2017 at 0:33 | comment | added | Samuel Schlesinger | So for squarefree $n$, we should have $f(z) = \prod_{i} p_i^{\phi(p_i)}$, $p_i$ being a prime factor of $n$? | |
| Mar 25, 2017 at 0:24 | comment | added | GH from MO | Well, I told you what to do. Find out the (easy) answer when $m$ is a prime power, and then apply the Chinese Remainder Theorem. | |
| Mar 25, 2017 at 0:21 | comment | added | Samuel Schlesinger | Thanks @GHfromMO I realized that when I was writing it up... I now do not think it's not going to yield anything friendly for my recurrence, but am still curious | |
| Mar 25, 2017 at 0:09 | comment | added | Robert Israel | If $z$ is coprime to $m$, you have $f(z) = \varphi(m)$. If not, it's more complicated. | |
| Mar 25, 2017 at 0:06 | comment | added | GH from MO | Your last formula is definitely wrong. For example, when $m=p$ is a prime, we have $f(1)=p-1$ and $f(0)=2p-1$. | |
| Mar 25, 2017 at 0:02 | comment | added | Samuel Schlesinger | I think I have a nicer solution actually: $f (z) = n(n - \phi (n))$ | |
| Mar 25, 2017 at 0:01 | history | edited | GH from MO |
edited tags
|
|
| Mar 25, 2017 at 0:01 | comment | added | GH from MO | By the Chinese Remainder Theorem, it suffices to compute this function when $m$ is a prime power, in which case the task is easy. | |
| Mar 24, 2017 at 23:33 | comment | added | Samuel Schlesinger | If you're curious, the function I really want is $f(m) = \{ (x, y) \in \mathbb{Z}_m^k \times \mathbb{Z}_m^k \mid \langle x, y \rangle = 0 \}$, and this other function in the question ends up being in the recurrence as the base case. | |
| Mar 24, 2017 at 23:31 | history | edited | Samuel Schlesinger | CC BY-SA 3.0 |
Had a mistake
|
| Mar 24, 2017 at 23:30 | comment | added | Samuel Schlesinger | Crap @IgorRivin I have to change that, its for a more general question but I wrote it in that form here... | |
| Mar 24, 2017 at 23:26 | comment | added | Igor Rivin | What is the sum over in the last line? | |
| Mar 24, 2017 at 23:21 | history | asked | Samuel Schlesinger | CC BY-SA 3.0 |