Divisibility Probability

Printable View

May 24th 2011, 10:20 AM
Chris11

Divisibility Probability

let n be an integer greater than 1. Pick 2 distinct divisors of n. What is the probability that EXACTLY one of the divisors is a perfect square? This has been approved by Captain Black.
May 24th 2011, 08:07 PM
chisigma

Quote:

Originally Posted by Chris11

let n be an integer greater than 1. Pick 2 distinct divisors of n. What is the probability that EXACTLY one of the divisors is a perfect square? This has been approved by Captain Black.

In order to undestand correctly: what does it mean 'exactly one of the divisor is a perfect square?'...

May be...

$6=3*2$ has no square factors...

$12=3*2^{2}$ has exactly one square factor...

$36=3^{2}*2^{2}$ has more than one square factor...

... so that 12 is a 'candidate', 6 and 36 aren't?...

Kind regards

$\chi$ $\sigma$
May 24th 2011, 10:18 PM
Chris11

Hey. By example. Consider 36.

Pick 36, 3. 3 isn't a perfect square, but 36 is. That's what I mean by 'exactly one of the divisors is a perfect square.'
May 25th 2011, 02:51 AM
tonio

Quote:

Originally Posted by chisigma

In order to undestand correctly: what does it mean 'exactly one of the divisor is a perfect square?'...

May be...

$6=3*2$ has no square factors...

$12=3*2^{2}$ has exactly one square factor...

$36=3^{2}*2^{2}$ has more than one square factor...

... so that 12 is a 'candidate', 6 and 36 aren't?...

Kind regards

$\chi$ $\sigma$

Hmmm...I think 1 is always a perfect square divisor of any natural...

But even then there are some doubts:

1) Is the integer number n chosen randomly or it is given and THEN we begin choosing randomly from its divisors?

2) Are we supposed to assume that when we choose randomly (I guess) two divisors then

these divisors are different or is it possible that both are one and the same?

Tonio
May 25th 2011, 10:49 AM
Chris11

Quote:

Originally Posted by tonio

Hmmm...I think 1 is always a perfect square divisor of any natural...

But even then there are some doubts:

1) Is the integer number n chosen randomly or it is given and THEN we begin choosing randomly from its divisors?

2) Are we supposed to assume that when we choose randomly (I guess) two divisors then

these divisors are different or is it possible that both are one and the same?

Tonio

1. You're suppose to find an expression for all n.

2. You pick any 2 distinct divisors at random. You pick one, then your universe becomes the set of divisors that you haven't picked. Then you pick one from this set.

3. 1 is something that you 'pick' in this case. Please don't think that you pick 1 automaticly when you pick 57.
May 26th 2011, 10:56 PM
Chris11

Warning There Is a hint below
a
a
a
a
a
a
a
a

a
a
a
a

Consider the prime power factorization of n.
May 30th 2011, 06:07 AM
SpringFan25

is there a closed form solution in terms of n or is an answer in terms of the prime factorisation acceptable?

just on the off chance, my answer in terms of the prime factorisaion is below :)

Spoiler:

start from the prime power factorisation: $n = 1 \times p_2 ^ {k_2} \times p_3 ^ {k_3} ... p_j^{k_j} = 1 \times \prod_{i=2}^{j} p_i^{k_i}$

The above product expression only includes primes above 1 to avoid double counting on the next step.

By definition any part of the above product is a divisor of n. The full set of divisors are formed by varying the powers of each prime factor (other than 1) between 0 and $p_i$ , ie the divisors are:

$p_2^{x_2}p_3^{x_3}....p_j^{x_j} ~~~~ 0 \leq x_i \leq k_i$

The total number of divisors that can be constructed by varying those powers is $D = \prod_{i=2}^{j} (k_i + 1)$ . The construction includes all possible divisors since the prime factorisation of n is unique. No divisor is constructed twice since the prime factorisation of each divisor is unique. So D is the correct total of unique divisors. NB: the total (D) counts both n and 1 as divisors of n. If you dont consider those "real" divisors then you can subtract 1 or 2 from the total.

Getting the number of square divisors is a simple extension. Define $m_i = \lfloor \frac{k_i}{2} \rfloor$

A number is square iff its prime factorsation has even powers, so the possible square divisors are

$p_2^{2x_2}p_3^{2x_3}....p_j^{2x_j} ~~~~ 0 \leq x_i \leq m_i$

Anything constructed in this way is a divisor of n since $2x_i \leq k_i$ . Using the same arguments as before the total number of square divisors is $S = \prod_{i=2}^{j} (m_i + 1)$

Now it's just a probability problem. We want P(square then non-square) + P(non-square then square).

$=\frac{S}{D} \cdot \left(1-\frac{S-1}{D-1} \right) + \left(1-\frac{S}{D}\right) \cdot \frac{S}{D-1}$

apologies if that was really obvious to the rest of you and you wanted a function in terms of n.
July 5th 2011, 09:30 AM
SpringFan25

Re: Divisibility Probability

please can we see the solution now? :)
July 5th 2011, 01:38 PM
Chris11

Re: Divisibility Probability

Sorry for not replying earlier. My solution is actually the same as yours, I hope you enjoyed it. I thought it might have been a bit too easy.
July 6th 2011, 11:19 AM
SpringFan25

Re: Divisibility Probability

Quote:

I thought it might have been a bit too easy.

I had fun and i didn't think it was easy!

PS: I have never done number theory though, i guess it might have been simpler if youve studied that properly ^^