Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

FoolForMath

  • 3 years ago

Another cute number theory problem, Set \( N = 2^{10} \times 3^{9} \). If \( n\in \mathbb{N} \) and \( n|N^2 \), how many of \(n\) are there such that \(n<N\) but \( n \nmid N \) ?

  • This Question is Closed
  1. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I think you messed up the definition of "cute". IT does NOT mean devilishly hard.

  2. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    how do you read n|N^2 ?? i seem to have forgotten

  3. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    This is fun. Don't remove it, please. D:

  4. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    N divides N^2

  5. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and n∤N ??

  6. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    "does not divide"

  7. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Isnt N a number? How is it a set?

  8. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    In this context, Set = let

  9. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Oh. Okay. Thanks!

  10. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    wild guess 1??

  11. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Nothing is wild about this problem.

  12. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    no ... i just find my logic too wild

  13. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I agree. There are certain things seeping into my brain.

  14. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    @experimentx At least 15, man.

  15. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    In the set of naturals, all numbers \(2^{i}\) with \(0\leq i \leq 9\) satisfy \(n < N\) and \(n \mid N\). Similarly, all numbers \(3^{i}\) with \(0\leq i \leq 9\). And likewise all values of \(f(i,j)=2^i3^j\) for all values of \(i\) and \(j\) between \(0\) and \(9\). This implies all \(n\) satisfying both \(n<N\) and \(n \nmid N\) cannot fall into either of those forms. However, I haven't fully understood the importance of the parameter \(n \mid N^2\)...

  16. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Is it 84? Am I even close?

  17. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Argh. There are minor details that I messed up just now.

  18. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Close, very close :) But then I would appreciate a general and formal solution.

  19. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I am getting the feeling that \(\{n: n\mid N^2 \wedge n<N \wedge n\nmid N\}\) is an empty set.. Hmm..

  20. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Well. The given number is \[2^{10} * 3^{9}. \] Now in order for it to divide N but not N^2 it has to be of a form \[2^m * 3^n\] However, Their product must be less than N. So the possible cases Could be Now I assumed that at least One of m or n must be greater than their respective powers in N in order for it to not divide N.

  21. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Now, If it is some, say, \[3^{11} * 2^m\]

  22. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    OOOH, I may have something. Consider: \(n|N^2\) is equivalent to \(N^2=k_1n\) for some integer \(k_1\). Via a little algebra, \(N=\frac{k_1}{N}n\). Since \(N\) is an integer, \(N=k'n\) for some integer \(k'\). Via definition of \(a | b\), \(n|N\). Therefore, there is no \(n\) such that \(n|N^2\) and \(n\nmid N\). Thus, \(0\).

  23. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Actually, oops. \(\frac{k_1}{N}\) is not always an integer.

  24. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    And similarly I did it for cases of 2 and ..... Obviously missed some.

  25. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    My proof ironically illustrates that the original parameters are necessary: If \(n \geq N\), then \(n \mid N\) for many \(n\).

  26. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    The set \(\{n:(n<N)\wedge( n|N)\wedge (n|N^2)\}\) is enumerated by the function \[f(i,j)=2^i3^j \text{ if } 0\leq i \leq 9 \text{ and }0 \leq j \leq 8 .\] I believe \(\{n:(n<N)\wedge( n\nmid N)\wedge (n|N^2)\}\) is large. Consider: If \(n \nmid N\), then \(\frac{N}{n}\neq k\) for some integer \(k\). This implies \(\frac{N}{n}=u\) for \(\{u:u \notin \mathbb{Z}\}\). Multiply both sides by \(N\) and you get \(\frac{N^2}{n}=uN\). Recall that \(n\) must be less than \(N\). This tells you that \(0<u<1\). The product \(uN\) is an integer at \(u=\left\{f(i,j)^{-1}=\frac{1}{2^i3^j}\right\}\) with \(0 \leq i \leq 10\) and \(0 \leq j \leq 9\) and \(2^i3^j\neq 1\). This tells us that \(n \mid N^2\) for \(109\) \(n\). (\((i,j)=(0,0)\) is excluded.) All other cases must not divide \(N^2\). Since the set \(\{1,\dots,N-1\}\) has \(N-1\) elements, we have that the cardinality of \(\{n:(n<N)\wedge( n|N)\wedge (n|N^2)\}\) is \(N-110\). :)

  27. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    OOPS. I meant for the set to be: \(\{n:(n<N)\wedge (n \nmid N)\wedge (n|N^2)\}\) at the bottom!

  28. Mr.Math
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    The choices we have for \(n=2^i3^j\) are At \(i=0,1, \cdots, 9\): \(j=0,1,\cdots 9\). At \(i=10\): \(j=0,1,\cdots 8\). The number of all n's is \(10\cdot 10+9=109.\)

  29. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I think I can clarify my post: If \(n \nmid N\), then \(\frac{N}{n} \neq k\) for some integer \(k\). If \(\frac{N}{n} \neq k\) , then \(\frac{N}{n}=u\) for some \(u\) that is not an integer. If \(n<N\), then \(0 < u < 1\). If \(0<u<1\), then \(u=\frac{1}{b}\) for some integer \(b\). If \(\frac{N}{n}=u\), then \(\frac{N^2}{n}=uN\). Therefore, \(n | N^2\) if and only if \(uN\) is an integer. If \(N=2^{10}\cdot 3^{9}\), then \(uN\) is an integer if and only if \(b=2^i3^j\) for \(0 \leq i \leq 10\), \(0 \leq j \leq 9\), and \((i,j)\neq(0,0)\). There are \(109\) such \(b\). Therefore, there are \(109\) \(n\) such that \(n \nmid N\), \(n<N\), and \( n \mid N^2\).

  30. joemath314159
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Im getting 90 as an answer <.<

  31. joemath314159
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    There is a little flaw in Limitless' argument. If n<N, then\[1<\frac{N}{n}\]so u would have to be greater than 1, not in between 0 and 1.

  32. joemath314159
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    I looked at the problem this way. If:\[n\mid N^2\]then n has to be of the form:\[n=2^a\cdot 3^b\]where:\[0\le a \le 20,0\le b\le 18\]But we dont want n to divide N, so a cant be less than 11 and b cant be less than 10 at the same time. Also, we dont want n to be bigger than N, so a cant be bigger than 9 and b cant be bigger than 8 at the same time. So what conditions on a and b are we looking for? We want all n such that:\[n=2^a3^b\]such that only one of these two conditions are met: either:\[11\le a\le 20, 0\le b\le 8, n<N\]or \[0\le a \le 9, 10\le b\le 18, n<N\]So we nee to count these possibilities.

  33. KingGeorge
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Using the brute force method, @joemath314159 is correct. There are 90 possibilities.

  34. joemath314159
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Yeah, i could only brute force it too. Im not sure if there is a clever way to attempt this problem.

  35. KingGeorge
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    You could probably place some bounds on the sum of the exponents somehow.

  36. joemath314159
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    i just sat there and went:\[2^{11}, 2^{11}\cdot 3, 2^{11} \cdot 3^2, \ldots 2^{11}\cdot 3^8\]"How many of these are less than 2^10*3^9? Not this one, not that one" etc etc. Went from the exponent of 2 being 11 all the way to 20, then did the same thing with 3 being the larger exponent. Took forever >.<

  37. KingGeorge
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I did a similar thing. Used Wolfram to help me though. Put 2^11*3^8 < 2^10*3*9 2^12*3^8 < 2^10*3*9 2^12*3^7 < 2^10*3*9 ... whenever it said "true" I increased the exponent of 2, and if it said "false" I decreased the exponent of 3. Then switched it around so that I was increasing the exponent of 3, and decreasing the exponent of 2.

  38. joemath314159
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Right. I should have used Wolfram >.< I was subtracting the two numbers. Checking if the result was positive or negative.

  39. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    90 is the right answer.

  40. FoolForMath
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    And there exists a very smart/easy solution. It is possible to generalize to any given N.

  41. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I think writing it as \[2^{m - 10} < 3^{9 - n}\] Where either n > 9 Or m > 10, Makes things a lot simpler.

  42. eliassaab
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    There are 90 as many people suggested above. Here they are \[ \begin{array}{cccccccccc} 2^{11} & 2^{12} & 2^{11} 3^1 & 2^{13} & 2^{12} 3^1 & 2^{14} & 2^{11} 3^2 & 2^{13} 3^1 & 2^{15} & 2^{12} 3^2 \\ 2^{14} 3^1 & 2^{11} 3^3 & 3^{10} & 2^{16} & 2^{13} 3^2 & 2^{15} 3^1 & 2^{12} 3^3 & 2^1 3^{10} & 2^{17} & 2^{14} 3^2 \\ 2^{11} 3^4 & 3^{11} & 2^{16} 3^1 & 2^{13} 3^3 & 2^2 3^{10} & 2^{18} & 2^{15} 3^2 & 2^{12} 3^4 & 2^1 3^{11} & 2^{17} 3^1 \\ 2^{14} 3^3 & 2^3 3^{10} & 2^{11} 3^5 & 2^{19} & 3^{12} & 2^{16} 3^2 & 2^{13} 3^4 & 2^2 3^{11} & 2^{18} 3^1 & 2^{15} 3^3 \\ 2^4 3^{10} & 2^{12} 3^5 & 2^{20} & 2^1 3^{12} & 2^{17} 3^2 & 2^{14} 3^4 & 2^3 3^{11} & 2^{11} 3^6 & 2^{19} 3^1 & 3^{13} \\ 2^{16} 3^3 & 2^5 3^{10} & 2^{13} 3^5 & 2^2 3^{12} & 2^{18} 3^2 & 2^{15} 3^4 & 2^4 3^{11} & 2^{12} 3^6 & 2^{20} 3^1 & 2^1 3^{13} \\ 2^{17} 3^3 & 2^6 3^{10} & 2^{14} 3^5 & 2^3 3^{12} & 2^{11} 3^7 & 2^{19} 3^2 & 3^{14} & 2^{16} 3^4 & 2^5 3^{11} & 2^{13} 3^6 \\ 2^2 3^{13} & 2^{18} 3^3 & 2^7 3^{10} & 2^{15} 3^5 & 2^4 3^{12} & 2^{12} 3^7 & 2^{20} 3^2 & 2^1 3^{14} & 2^{17} 3^4 & 2^6 3^{11} \\ 2^{14} 3^6 & 2^3 3^{13} & 2^{11} 3^8 & 2^{19} 3^3 & 3^{15} & 2^8 3^{10} & 2^{16} 3^5 & 2^5 3^{12} & 2^{13} 3^7 & 2^2 3^{14} \\ \end{array} \]

  43. Limitless
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    This is fascinating. I did actually screw that up--thank you for the correction. I would love to figure out what the elegant argument is, but it eludes me.

  44. siddhantsharan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    What is the elegant solution? :/

  45. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy