Timeline for How long iterations of $x \to (p \!\!\! \mod \!\! x)$ can be? [duplicate]
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 22, 2018 at 22:25 | history | closed |
Max Alekseyev Chris Godsil Lucia András Bátkai Mateusz Kwaśnicki |
Duplicate of improving known bounds for Pierce expansions; cash prize | |
| Jul 19, 2018 at 13:18 | comment | added | Kaban-5 | Max Alekseyev: linked post indeed shows that there are upper bounds better than $O(\sqrt p)$, but it does not tell anything even about $O(poly(\log n))$. I am slightly confused about what to do with "This question may already have an answer here:" pop-up window: clearly, the linked post does not fully solve my problem, yet my question is just a special case of linked question. Should I just ignore this pop-up? | |
| Jul 19, 2018 at 10:32 | comment | added | Kaban-5 | Joe Silverman: original motivation was yet another (well known, not invented by me) algorithm that finds $x^{-1} \!\!\! \mod \!\! p$ in $O(\log p)$ arithmetical operations: $x [\frac{p}{x}] + (p \!\!\! \mod \!\! x) = p \equiv 0 \pmod p$, therefore $x^{-1} \equiv -[\frac{p}{x}] (p \!\!\! \mod \!\!x)^{-1} \pmod p$. This formula yields a recursive formula for $x^{-1} \!\!\! \mod \!\! p$, as long both left and right part makes sense, which is not true for composite $p$. I agree that the question I asked makes sense for composite $p$. | |
| Jul 19, 2018 at 2:45 | comment | added | Gerhard Paseman | Gee, I'd forgotten all about that question. Maybe I will see if I can improve the idea I posted. Gerhard "That Will Buy Many Mochas" Paseman, 2018.07.18. | |
| Jul 19, 2018 at 1:08 | review | Close votes | |||
| Jul 22, 2018 at 22:25 | |||||
| Jul 18, 2018 at 20:27 | comment | added | Joe Silverman | I'm curious why you take $p$ to be prime. Why not start with an arbitrary integer $m$? | |
| Jul 18, 2018 at 19:59 | answer | added | Gerhard Paseman | timeline score: 2 | |
| Jul 18, 2018 at 16:30 | answer | added | Neil Strickland | timeline score: 5 | |
| Jul 18, 2018 at 15:32 | comment | added | Gerhard Paseman | Let m be the least common multiple of the first n numbers. Primes which are -1 mod m will need n -1 iterations if the first x is n. However, one can for given p and alpha less than 1 find how many x have p mod x greater than alpha x, and then determine how likely it is to stay away from such x. Gerhard "Thinks Logarithmic Bound Quite Likely" Paseman, 2018.07.18. | |
| Jul 18, 2018 at 15:13 | history | asked | Kaban-5 | CC BY-SA 4.0 |