$\newcommand{\Prb}[1]{\mathcal{P}\_{#1}}$
I have the following number theory problem, related to Odlyzko's improvement on Shor’s factoring algorithm (see [this cstheory.sx question](https://cstheory.stackexchange.com/q/32077/2368) for details).



> 
> Let $N$ be a (large) integer and $1≤B≤N$ a bound. If I chose the integer $1≤t≤N$ uniformly at random, can I lower bound the probability $\Prb B$ that $\gcd(t,N)≤B$ ? How should I chose the least possible $B$ such that $\Prb B$ is bounded away from 0 ? Or asymptotically close to 1 ?
> 
> 
> 


Of course 
$$\begin{align}\Prb 1&=\frac{ϕ(N)}N>\frac{1}{e^γ\ln\ln N+\frac3{\ln\ln N}};& \Prb N&=1 \end{align}$$ 
where $ϕ$ is [Euler’s totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function) and $γ$ is the [Euler-Mascheroni constant](https://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant).
More generally, it is easy to see that 
$$
\Prb B=\frac{\sum\_{d\vert N}^{d≤B}ϕ(\frac{N}{d})}N
 =1-\frac{\sum\_{d'\vert N}^{d'<\frac{N}{B}}ϕ(d')}N,
$$
but I did not manage to go further.


If I interpret the 1995 “private communication” from Odlyzko to Shor (referred to in [arXiv:quant-ph/9508027](http://arxiv.org/abs/quant-ph/9508027) and the [cstheory.sx question](https://cstheory.stackexchange.com/q/32077/2368)) correctly, $∀ε>0$, $\Prb{(\log N)^{1+ε}}$ is bounded away from 0. However, I did not manage to find a proof of this.



Lower bounding the probability that $\gcd(t,N)≤B$, for a random $t$ and fixed (large) $N$
In fact one can prove a stronger result -- namely the probability is bounded away from zero, so long as $B \ge (\log N)^\delta$ for some $\delta >0$. This is best possible, by taking $N$ to be the product of the first few primes. Since $\phi(N/d) \ge \phi(N)/d$, our probability is bounded below by 
$$ 
\frac{\phi(N)}{N} \sum\_{d|N, d\le B} \frac{1}{d}\ge \frac{\phi(N)}{N}\sum\_{d|N, d\le B} \frac{\mu(d)^2}{d}, 
$$ 
where in the last sum we have restricted attention to square-free $d$ for simplicity. 


Now I claim that for large enough $B$ (and any $N$, independent of $B$) one has 
$$ 
\sum\_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \frac{1}{4} \prod\_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big). \tag{1} 
$$ 
Assuming the claim, we get a lower bound for our probability of 
$$ 
\ge \frac 14 \frac{\phi(N)}{N} \prod\_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) 
\ge \frac{1}{4} \prod\_{p} \Big(1-\frac 1{p^2}\Big) \prod\_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big)= \frac{3}{2\pi^2} \prod\_{p|N, p>\sqrt{B}} \Big(1-\frac{1}{p}\Big). 
$$
If now $B\ge (\log N)^{\delta}$ then 
$$ 
\prod\_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big) \ge \prod\_{(\log N)^{\delta/2}<p <(\log N)^2}\Big(1-\frac 1p\Big) \prod\_{p>(\log N)^2, p|N} \Big(1-\frac 1p\Big),
$$ 
and by Mertens's theorem the first factor above is $\gg \delta$, and trivially the second factor is $1+o(1)$. This completes the proof. 


It remains to settle the claim (1). With $\alpha =1/\log B$ note that 
$$ 
\sum\_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \sum\_{\substack{d|N, d\le B \\ p|d \implies p\le \sqrt{B}}} \frac{\mu(d)^2}{d} \ge \prod\_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) - B^{-\alpha} \sum\_{\substack{d|N\\ p|d\implies p\le \sqrt{B} }} \frac{\mu(d)^2 d^{\alpha}}{d}.
$$
The second term above is 
$$ 
e^{-1} \prod\_{p|N, p\le \sqrt{B}} \Big(1 + \frac{p^{\alpha}}{p}\Big) \le e^{-1} \prod\_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \exp\Big(\sum\_{p|N, p\le \sqrt{B}} \frac{p^{\alpha}-1}{p}\Big).
$$
Now for large enough $B$, (since $(e^{t}-1)/t \le (\sqrt{e}-1)/(1/2)$ for $0\le t\le 1/2$)
$$ 
\sum\_{p\le \sqrt{B}} \frac{p^{1/\log B}-1}{p} \le\sum\_{p\le \sqrt{B}} \frac{\log p}{p\log B} \Big(\frac{\sqrt{e}-1}{1/2}\Big) = \sqrt{e}-1 +o(1),
$$
and using this above, we obtain 
$$ 
\sum\_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \prod\_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \Big(1- e^{-1} (e^{\sqrt{e}-1}+o(1)) \Big) \ge \frac 14 \prod\_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big), 
$$
proving the claim (1).


