Results 1 to 10 of 10

Math Help - Divisibility Probability

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1

    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.
    Last edited by CaptainBlack; May 24th 2011 at 06:55 PM. Reason: Yes it has
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by Chris11 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    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.'
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chisigma View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    Quote Originally Posted by tonio View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    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.
    Last edited by SpringFan25; May 30th 2011 at 10:22 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28

    Re: Divisibility Probability

    please can we see the solution now?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28

    Re: Divisibility Probability

    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 ^^
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility by 9
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 26th 2010, 05:33 AM
  2. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 11:55 AM
  3. Probability and divisibility
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 22nd 2009, 04:36 PM
  4. Divisibility (gcd) 16
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2008, 09:20 AM
  5. Divisibility (gcd) 15
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 21st 2008, 03:55 AM

Search Tags


/mathhelpforum @mathhelpforum