I suppose that $$P(n)=\frac{\prod_{i=1}^k (2p_i-1)}{n^2}$$ as $n=\prod_{i=1}^kp_i$ ($p_1$ to $p_k$ are different prime numbers).

It works with 1,2 or 3 primes, but I am not able to prove it.

  • $\begingroup$ I guess some of your $n$'s should be denoted by other letters, say $k$ and then $i$ in the index. $\endgroup$
    – Berci
    Mar 13, 2018 at 11:58
  • $\begingroup$ Why is $n$ squarefree? $\endgroup$
    – anomaly
    Mar 13, 2018 at 22:39

2 Answers 2


Assume that the number of distinct prime divisors of $n$ is $k$, so that: $$ n=\prod_{i=1}^k p^{r_i}_i, $$ the overall number of distinct divisors being $\prod_{i=1}^k(r_i+1)$.

Choose some divisor $d$ of $n$ and let $M_d$ be the set of numbers in the range from $1$ to $n$, having $d$ as greatest common divisor with $n$: $m\in M_d: \{1\le m \le n,\ \gcd(m,n)=d\}$. The set will contain $\varphi(n/d)$ numbers, $\varphi(n)$ being the Euler's totient function. Repeating the procedure for all distinct divisors of $n$ one ends up with partition of the set $(1..n)$ into disjoint union of $M_{d_i}$. Observe that for every $m\in M_d$ there are $d$ ways to choose the second number (a multiple of $n/d$) such that the product of both is divisible by $n$.

Thus, the overall number of "good" pairs is: $$ N(n)=\sum_{d|n}\varphi\left(\frac{n}{d}\right)d. $$

$N(n)$ being the Dirichlet convolution of two multiplicative functions $\phi(n)$ and $\text{id}(n)$ is itself a multiplicative function:

$$N\left(\prod_i p_i^{r_i}\right)=\prod_{i}N(p_i^{r_i}),$$ with $$ N(p^{r})=p^r+\sum_{i=1}^{r} p^{i-1}(p-1)p^{r-i} =p^r\left[1+\left(1-\frac{1}{p}\right)r\right]. $$

As the overall number of pairs is $n^2$ the probability in question is: $$P(n)=\frac{N(n)}{n^2}=\frac{\prod_i\left[1+\left(1-\frac{1}{p_i}\right)r_i\right]}{n}. $$ In your case all $r_i=1$, so that the above expression reduces to: $$ P(n)=\frac{\prod_i\left(2-\frac{1}{p_i}\right)}{n}=\frac{\prod_i(2p_i-1)}{n^2}, $$ as claimed.

  • $\begingroup$ Thanks for the answer. But I still wonder why $N(n) $ is a multiplicative function. $\endgroup$ Mar 14, 2018 at 12:41
  • 1
    $\begingroup$ @Mira from Earth: It is the Dirichlet convolution of two multiplicative functions: $\phi(n)$ and $\text{id}(n)$. Don't hesitate to ask further questions if you have doubts. $\endgroup$
    – user
    Mar 14, 2018 at 14:30
  • $\begingroup$ I get the point. Thank you! $\endgroup$ Mar 15, 2018 at 3:25

Assuming $n$ is square-free, it holds. The function $P$ is multiplicative by the Chinese remainder theorem, and the pairs $(n, m)$ in $1, \dots, p$ with $p| nm$ are exactly the $2p - 1$ ones with $p = n$ or $p = m$.


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.