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 Group Title

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

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. siddhantsharan Group Title
    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 years ago
  2. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

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

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

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

    N divides N^2

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

    and n∤N ??

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

    "does not divide"

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

    Isnt N a number? How is it a set?

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

    In this context, Set = let

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

    Oh. Okay. Thanks!

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

    wild guess 1??

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

    Nothing is wild about this problem.

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

    no ... i just find my logic too wild

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

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

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

    @experimentx At least 15, man.

    • 2 years ago
  15. Limitless Group Title
    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\)...

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

    Is it 84? Am I even close?

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

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

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

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

    • 2 years ago
  19. Limitless Group Title
    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..

    • 2 years ago
  20. siddhantsharan Group Title
    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.

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

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

    • 2 years ago
  22. Limitless Group Title
    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\).

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

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

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

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

    • 2 years ago
  25. Limitless Group Title
    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\).

    • 2 years ago
  26. Limitless Group Title
    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\). :)

    • 2 years ago
  27. Limitless Group Title
    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!

    • 2 years ago
  28. Mr.Math Group Title
    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.\)

    • 2 years ago
  29. Limitless Group Title
    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\).

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

    Im getting 90 as an answer <.<

    • 2 years ago
  31. joemath314159 Group Title
    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.

    • 2 years ago
  32. joemath314159 Group Title
    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.

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

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

    • 2 years ago
  34. joemath314159 Group Title
    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.

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

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

    • 2 years ago
  36. joemath314159 Group Title
    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 >.<

    • 2 years ago
  37. KingGeorge Group Title
    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.

    • 2 years ago
  38. joemath314159 Group Title
    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.

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

    90 is the right answer.

    • 2 years ago
  40. FoolForMath Group Title
    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.

    • 2 years ago
  41. siddhantsharan Group Title
    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.

    • 2 years ago
  42. eliassaab Group Title
    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} \]

    • 2 years ago
  43. Limitless Group Title
    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.

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

    What is the elegant solution? :/

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