Results 1 to 4 of 4

Math Help - How many positive divisors of n^2...

  1. #1
    rcs
    rcs is offline
    Senior Member rcs's Avatar
    Joined
    Jul 2010
    From
    iligan city. Philippines
    Posts
    455
    Thanks
    2

    How many positive divisors of n^2...

    can anybody please

    Let n = 2^31 x 3^19. How many positive divisors of n^2 are less than n but
    do not divide n?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    \displaystyle n^2=(2^{31}*3^{19})^2=2^{62}*3^{38}

    \displaystyle \tau (p^e)=e+1

    p is prime and e\in\mathbb{Z} .

    \displaystyle \tau (n^2)=\tau (2^{62})*\tau (3^{38})=(62+1)(38+1)=63*39=2457

    Then, from here, we subtract 1 because the highest factor is n^2.

    2457-1=2456

    Just read the factors can't divide n.

    Adjusting.

    We know that n|n, \ 1|n, \ 2|n, \ 3|n.

    Therefore, we must subtract n, 1, 31, 19

    31 are the number of multiple of 2s, 19 are the multiple of 3s, and 19 are the multiples of 6.

    However, this includes some overlap. Your job is to figure out how many to add back in.
    Last edited by dwsmith; December 19th 2010 at 10:21 AM. Reason: Took out inclusions-exclusions since that is the number of integers not divisors
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Suppose m\mid n^2. Then there exist some i and j such that m=2^i\cdot 3^j. Moreover, m\nmid n iff i\ge 32 or j\ge 20. Next, \lfloor\log_2n\rfloor=61 and \lfloor\log_3n\rfloor=38. Therefore, if m\nmid n and m < n, then either (1) 32\le i\le61 or (2) 20\le j\le 38. Note that (1) and (2) are mutually exclusive. Conversely, for each 32\le i\le61 and each 0\le j\le\lfloor\log_3(n/2^i)\rfloor, 2^i\cdot 3^j<n and 2^i\cdot 3^j\nmid n. Similarly, for each 20\le j\le38 and each 0\le i\le\lfloor\log_2(n/3^j)\rfloor, 2^i\cdot 3^j<n and 2^i\cdot 3^j\nmid n.

    Therefore, the answer is \displaystyle\sum_{i=32}^{61}(\lfloor\log_3(n/2^i)\rfloor+1)+\sum_{j=20}^{38}(\lfloor\log_2(n/3^j)\rfloor+1). According to my brute-force calculations, this is 589.

    Maybe someone will figure out a more elegant solution.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    rcs
    rcs is offline
    Senior Member rcs's Avatar
    Joined
    Jul 2010
    From
    iligan city. Philippines
    Posts
    455
    Thanks
    2
    thanks a lot sir emakarov, i got that problem from a book but does not have a solution shown, but i has an answer of 589, you so amazing. thank you so much.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of Positive Divisors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 6th 2011, 03:35 AM
  2. Sum of positive divisors function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 17th 2010, 05:42 AM
  3. Running Through Positive Divisors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 4th 2010, 09:28 AM
  4. Positive divisors
    Posted in the Algebra Forum
    Replies: 8
    Last Post: January 26th 2010, 05:36 AM
  5. Sum of Positive Divisors Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 12th 2008, 02:36 PM

Search Tags


/mathhelpforum @mathhelpforum