Divisibility Probability

• 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...

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

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \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...

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

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \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: $\displaystyle 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 $\displaystyle p_i$, ie the divisors are:

$\displaystyle 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 $\displaystyle 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 $\displaystyle 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

$\displaystyle 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 $\displaystyle 2x_i \leq k_i$ . Using the same arguments as before the total number of square divisors is $\displaystyle 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).

$\displaystyle =\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.
• Jul 5th 2011, 09:30 AM
SpringFan25
Re: Divisibility Probability
please can we see the solution now? :)
• Jul 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.
• Jul 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 ^^