Probability that 2 distinct integers are divisible by the same number

[nomadreid]

TL;DR

Does p have to be prime so that the probability that two randomly chosen integers are both divisible by p is 1/p^2?

The probability that a randomly chosen integer is divisible by a given integer p is 1/p, regardless of whether p is prime.
The probability that 2 distinct randomly chosen integers are divisible by the same prime p is
1/p².
I am not sure however whether the probability that 2 distinct randomly chosen integers are divisible by the same positive integer n is not simply
1/n².
I feel that if n is not prime there might be some duplication somewhere, but I don't see where.
Any indications would be very much appreciated.

 

[PeroK]

TL;DR Summary: Does p have to be prime so that the probability that two randomly chosen integers are both divisible by p is 1/p^2?

How are you going to choose an integer at random? It can only be done uniformly for a finite set of integers. That said, if the integers are selected uniformly from a set $1$ to $N$, where $N >> p$, then this holds.

The probability that a randomly chosen integer is divisible by a given integer p is 1/p, regardless of whether p is prime.
The probability that 2 distinct randomly chosen integers are divisible by the same prime p is
1/p².
I am not sure however whether the probability that 2 distinct randomly chosen integers are divisible by the same positive integer n is not simply
1/n².
I feel that if n is not prime there might be some duplication somewhere, but I don't see where.
Any indications would be very much appreciated.

Every nth integer is divisible by $n$, so given the above assumption, the probabilityan integer is divisible by $n$ is $1/n$.

 

[fresh_42]

Consider the ring $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$ and its projection $\pi\, : \,\mathbb{Z}\longrightarrow \mathbb{Z}_n.$ Then $n\,|\,a$ if and only if $\pi(a)=0.$

If we have two numbers $a,b$ then we have the situation $\pi'\, : \,\mathbb{Z}\times \mathbb{Z}\longrightarrow \mathbb{Z}_n\times \mathbb{Z}_n$ and $a\,|\,n$ AND $b\,|\,n$ if and only if $\pi'(a,b)=(0,0).$

The ring $\mathbb{Z}_n$ has $n$ elements, so we hit $0$ every $n$ integers and $P(n\,|\,a)=1/n.$

The ring $\mathbb{Z}_n\times \mathbb{Z}_n$ has $n^2$ elements, so we hit $(0,0)$ every $n^2$ integers and $P(n\,|\,a\wedge n\,|\,b)=1/n^2.$

We don't need to consider primes.

 

[nomadreid]

Super, fresh_42. Thanks!

The reason I was in doubt was because, in the usual presentation of the probability of two numbers being coprime, one derives it with
(1-1/2²)(1-1/3²)(1-1/5²)(1-1/7²)(1-1/11²)...
But when does the calculations to figure out whether two arbitrarily chosen integers are both divisible by the same two numbers (not necessarily prime), one ends up discarding repetitions, as in
https://gmatclub.com/forum/two-dist...-random-from-the-list-of-integers-296859.html

Thanks for the answer, PeroK. In answer to your question, see the answer by fresh_42

 

[PeroK]

Thanks for the answer, PeroK. In answer to your question, see the answer by fresh_42

There is no uniform distribution on the integers. It's not mathematically possible to choose an integer at random unless some integers are more likely than others.

 

[fresh_42]

There is no uniform distribution on the integers. It's not mathematically possible to choose an integer at random unless some integers are more likely than others.

Picking a certain integer is of probability zero. Picking an even integer is a probability of $0.5.$ We compare two infinite sets $\mathbb{Z}$ and $n\mathbb{Z},$ and the quotient of them is finite. Picking an integer, in our case $0,$ from a finite set is uniformly distributed.

 

[PeroK]

Picking a certain integer is of probability zero.

That's not a valid probability distribution, as the total probability is zero:
$$\sum_{n = 1}^{\infty} p(X = n) = \sum_{n = 1}^{\infty} 0 = 0$$

Picking an even integer is a probability of $0.5.$

That depends on the distribution you use to choose an integer. A uniform distribution is not possible.

 

[PeroK]

There is no uniform distribution on the integers. It's not mathematically possible to choose an integer at random unless some integers are more likely than others.

See here, for example:

https://math.stackexchange.com/ques...ty-distribution-over-the-positive-real-number

 

[fresh_42]

I think that's not the topic here. We are not choosing one integer from all, we only consider the finite set $\{0,1,\ldots,n\}.$ It is irrelevant how we got the number. The problem statement was/should have been: given two integers, how likely is it that they are both divisible by $n.$ But, yes, the phrase ...

The probability that a randomly chosen integer

... was unfortunate. It should have been given two integers. Of course, any automatism to generate an integer is heavily biased towards shorter numbers because it has to come to a halt in a finite time.

 

[PeroK]

I think that's not the topic here. We are not choosing one integer from all, we only consider the finite set $\{0,1,\ldots,n\}.$ It is irrelevant how we got the number. The problem statement was/should have been: given two integers, how likely is it that they are both divisible by $n.$ But, yes, the phrase ...

... was unfortunate. It should have been given two integers. Of course, any automatism to generate an integer is heavily biased towards shorter numbers because it has to come to a halt.

The best way to patch this up is to assume that the set of integers available is much larger than the possible divisors. For example, if we choose $X$ uniformly from the set $\{1, 2, \dots N\}$, then:
$$\lim_{N \to \infty}p(X \ \text {is even}) = 0.5$$And that straightens everything out.

That's the nearest we can get to a uniform distribution on the natural numbers.

PS likewise, if we pick two naturals:
$$\lim_{N \to \infty}p(X \ \text {is even} \wedge Y \ \text {is even}) = 0.25$$