Timeline for Given an odd integer N find the smalletst prime p > N such that (p-1,N)=1
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2011 at 15:32 | comment | added | GH from MO | @Hugo: Actually I have not verified my claim. I am sure the product of first primes is the worst case, but this requires a rigorous proof! | |
| Mar 29, 2011 at 20:16 | comment | added | Matt Young | I admit I was pretty lazy about the constant! | |
| Mar 29, 2011 at 19:48 | comment | added | Hugo Chapdelaine | Very good point GH, this is the worst case namely when $N\sim\prod\limits_{p\leq\log(N)}p$. Then one uses the fact that $\prod_{p\leq x}(1-1/p)\sim\frac{1}{\log(x)}$. So we don't quite get a constant but $c>>\frac{1}{\log\log(x)}$ is good enough! | |
| Mar 28, 2011 at 19:02 | comment | added | GH from MO | Perhaps it is worth noting that $c\gg\frac{1}{\log\log x}$ which is sufficient. | |
| Mar 28, 2011 at 17:03 | vote | accept | Hugo Chapdelaine | ||
| Mar 28, 2011 at 15:54 | history | answered | Matt Young | CC BY-SA 2.5 |