We are given an arbitrary number $n$ and a sequence of primes $p_1=2$, $p_2=3$, ..., $p_k$. I am interested in the following question: Are the events "Prime $p_i$ is a factor of $n$" independent for distinct primes $p_i$?

It seems that the answer is no but I think this depends on the size of $n$. If $n$ is slightly greater than $p_k$ or lower than $p_k$, the answer is no. But what about the case where $n \geq \prod_{i=1}^k p_i$?

This is an intuition but I am not able to give a argument.

Thank you

  • $\begingroup$ Isn't probability of $p_i|n$ for given $p_i$ and $n$ equal 0 or 1? $\endgroup$ – Jaroslaw Matlak Sep 22 '17 at 7:41
  • 1
    $\begingroup$ If $n$ follows a uniform random distribution on any set of $N$ consecutive integers, where $N$ is a multiple of $\prod p_i$, then the answer is yes. $\endgroup$ – Hagen von Eitzen Sep 22 '17 at 7:46
  • $\begingroup$ @HagenvonEitzen No. The event $p_i | n$ and $p_j | n$ are not independent. That's why prime numbers are complicated. $\endgroup$ – reuns Sep 22 '17 at 8:55
  • $\begingroup$ @Adam54 When you say "an arbitrary number $n$" you meant $n$ an arbitrary integer $ \le N$. The events are not independent : if $p_i | n$ and $p_i > N/2$ then $p_j \nmid n$. This is enough to prove the dependence in every other cases. Now you can create a random integer variables whose event $X_{i} = p_i| n$ are independent, simply choose $k$ primes and set $n = \prod_{i=1}^k p_i^{E_{i}}$ where each $E_i $ are independent random variables. $\endgroup$ – reuns Sep 22 '17 at 9:02
  • $\begingroup$ Thanks for your comments. What about the case where the number $n$ is chosen in the interval $\left[\prod_{i=1}^k p_i , (\prod_{i=1}^k p_i)^2 \right]$? Are there results which stipulate independence under certain conditions (for instance, for $n$ an arbitrary large number that tends to $\infty$)? $\endgroup$ – Adam54 Sep 22 '17 at 10:30

The "probability" that a natural number N is divided by any prime p is $\frac{1}{p}$ as long as $p≤\sqrt{N}$. These "probabilities" are independent of each other and thus the "probabilty" that a natural number N is divided through the primes p1 and p2 is $$\frac{1}{p1}*\frac{1}{p2}$$

  • $\begingroup$ Are you sure? For infinitely large $N$, maybe it's true, but when a small number can be divided by $p1$, I think that the probability that it can be divided by $p2$ decreases. $\endgroup$ – Adam54 Sep 29 '17 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.