Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

FoolForMath

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 \) ?

  • one year ago
  • one year ago

  • This Question is Closed
  1. siddhantsharan
    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.

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

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

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

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

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

    N divides N^2

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

    and n∤N ??

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

    "does not divide"

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

    Isnt N a number? How is it a set?

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

    In this context, Set = let

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

    Oh. Okay. Thanks!

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

    wild guess 1??

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

    Nothing is wild about this problem.

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

    no ... i just find my logic too wild

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

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

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

    @experimentx At least 15, man.

    • one year ago
  15. Limitless
    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\)...

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

    Is it 84? Am I even close?

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

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

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

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

    • one year ago
  19. Limitless
    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..

    • one year ago
  20. siddhantsharan
    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.

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

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

    • one year ago
  22. Limitless
    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\).

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

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

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

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

    • one year ago
  25. Limitless
    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\).

    • one year ago
  26. Limitless
    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\). :)

    • one year ago
  27. Limitless
    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!

    • one year ago
  28. Mr.Math
    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.\)

    • one year ago
  29. Limitless
    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\).

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

    Im getting 90 as an answer <.<

    • one year ago
  31. joemath314159
    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.

    • one year ago
  32. joemath314159
    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.

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

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

    • one year ago
  34. joemath314159
    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.

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

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

    • one year ago
  36. joemath314159
    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 >.<

    • one year ago
  37. KingGeorge
    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.

    • one year ago
  38. joemath314159
    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.

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

    90 is the right answer.

    • one year ago
  40. FoolForMath
    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.

    • one year ago
  41. siddhantsharan
    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.

    • one year ago
  42. eliassaab
    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} \]

    • one year ago
  43. Limitless
    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.

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

    What is the elegant solution? :/

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.