Probability a random number $M$ is not a factor of $N$

Question

Let $N$ be some positive integer and let $S := \lbrace 1, 2, \cdots, \log^2(N) \rbrace$ (pretending at $\log^2(N)$ is an integer). Suppose $M$ is randomly chosen from the set $S$. The goal is to use the Prime Number Theorem show that

\begin{align} \text{Pr}\lbrace N \not\equiv 0 \mod M\rbrace = \Omega(1/\log\log(N)) \end{align}

By the Prime Number Theorem, we know that the number of primes less than some integer $n$ is $\Theta(n/\log(n))$. My thought on how to approach this is to consider the negated event, namely finding an upper bound on the probability that $N \equiv 0 \mod M$. Unless I am totally being clueless, this event is equivalent to when either $M = 1$ or $M>1$ is a factor of $N$. The probability of the first disjoint event, namely when $M = 1$, is readily $1/\log^2(N)$. I am having issues thinking about the latter event when $M > 1$ and is a a factor of $N$.

I know that $N$ can be decomposed into prime factors and within the set $S$, there is at most $c\log^2(N)/\log\log(N)$ prime numbers for some $c > 0$ using the Prime Number Theorem. Thus, at most a proportion of $c/\log\log(N)$ numbers from $S$ are a prime factor of $N$. I feel like this fact should come into play, but I am not seeing how to bring it in.

Any thoughts that could help me work out proving this result?

Answer 1

I ended up working out a solution to this problem that I felt was worth posting. We can first observe that

$$\text{Pr}\lbrace N \equiv 0 \mod M \rbrace = \text{Pr} \lbrace M \text{ is a factor of } N \rbrace = \frac{n_f(N)}{\log^2(N)}$$

where $n_f(N)$ is the number of factors of $N$ in $S$. Using the definition of $n_f$, we can then see that

\begin{align} n_f(N) &= \log^2(N) - |\lbrace m \in S : m \text{ not a factor of } N\rbrace| \\ &\leq \log^2(N) - |\lbrace m \in S: m \text{ is prime and not a factor of } N \rbrace| \end{align}

By the Prime Number Theorem, the number of prime numbers in $S$, denoted as $n_p(S)$, satisfies the inequality

$$c_1 \frac{\log^2(N)}{2 \log\log(N)} \leq n_p(S) \leq c_2 \frac{\log^2(N)}{2 \log\log(N)}$$

for some constants $0 < c_1 \leq c_2$. Now suppose that $N$ has $k$ prime factors in $S$. We observe that $\log(N) \geq k \log(2)$ which implies that $k \leq \log(N) / \log(2)$. Thus, the number of primes in $S$ that are not factors of $N$ satisfy

$$n_p(S) - k \geq c_1 \frac{\log^2(N)}{2 \log\log(N)} - \log(N)/\log(2) \geq \frac{c_1\log^2(N)}{4 \log\log(N)}$$

for sufficiently large $N$. Thus result implies then that

$$n_f(N) \leq \log^2(N) - \frac{c_1\log^2(N)}{4 \log\log(N)}$$

which further implies that our first probability is bounded like so:

$$\text{Pr}\lbrace N \equiv 0 \mod M \rbrace \leq 1 - \frac{c_1}{4} \frac{1}{\log\log(N)} $$

Taking the compliment of this, we see that

$$\text{Pr}\lbrace N \not \equiv 0 \mod M \rbrace \geq \frac{c_1}{4} \frac{1}{\log\log(N)} = \Omega\left(\frac{1}{\log\log(N)}\right)$$

completing the problem.