Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
Another cute number theory problem,
Set \( N = 2^{10} \times 3^{9} \). If \( n\in \mathbb{N} \) and \( nN^2 \), how many of \(n\) are there such that \(n<N\) but \( n \nmid N \) ?
 one year ago
 one year ago
Another cute number theory problem, Set \( N = 2^{10} \times 3^{9} \). If \( n\in \mathbb{N} \) and \( nN^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

siddhantsharanBest ResponseYou've already chosen the best response.2
I think you messed up the definition of "cute". IT does NOT mean devilishly hard.
 one year ago

experimentXBest ResponseYou've already chosen the best response.0
how do you read nN^2 ?? i seem to have forgotten
 one year ago

LimitlessBest ResponseYou've already chosen the best response.2
This is fun. Don't remove it, please. D:
 one year ago

siddhantsharanBest ResponseYou've already chosen the best response.2
Isnt N a number? How is it a set?
 one year ago

FoolForMathBest ResponseYou've already chosen the best response.1
In this context, Set = let
 one year ago

siddhantsharanBest ResponseYou've already chosen the best response.2
Oh. Okay. Thanks!
 one year ago

FoolForMathBest ResponseYou've already chosen the best response.1
Nothing is wild about this problem.
 one year ago

experimentXBest ResponseYou've already chosen the best response.0
no ... i just find my logic too wild
 one year ago

LimitlessBest ResponseYou've already chosen the best response.2
I agree. There are certain things seeping into my brain.
 one year ago

siddhantsharanBest ResponseYou've already chosen the best response.2
@experimentx At least 15, man.
 one year ago

LimitlessBest ResponseYou've already chosen the best response.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

siddhantsharanBest ResponseYou've already chosen the best response.2
Is it 84? Am I even close?
 one year ago

LimitlessBest ResponseYou've already chosen the best response.2
Argh. There are minor details that I messed up just now.
 one year ago

FoolForMathBest ResponseYou've already chosen the best response.1
Close, very close :) But then I would appreciate a general and formal solution.
 one year ago

LimitlessBest ResponseYou've already chosen the best response.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

siddhantsharanBest ResponseYou've already chosen the best response.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

siddhantsharanBest ResponseYou've already chosen the best response.2
Now, If it is some, say, \[3^{11} * 2^m\]
 one year ago

LimitlessBest ResponseYou've already chosen the best response.2
OOOH, I may have something. Consider: \(nN^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\), \(nN\). Therefore, there is no \(n\) such that \(nN^2\) and \(n\nmid N\). Thus, \(0\).
 one year ago

LimitlessBest ResponseYou've already chosen the best response.2
Actually, oops. \(\frac{k_1}{N}\) is not always an integer.
 one year ago

siddhantsharanBest ResponseYou've already chosen the best response.2
And similarly I did it for cases of 2 and ..... Obviously missed some.
 one year ago

LimitlessBest ResponseYou've already chosen the best response.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

LimitlessBest ResponseYou've already chosen the best response.2
The set \(\{n:(n<N)\wedge( nN)\wedge (nN^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 (nN^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,N1\}\) has \(N1\) elements, we have that the cardinality of \(\{n:(n<N)\wedge( nN)\wedge (nN^2)\}\) is \(N110\). :)
 one year ago

LimitlessBest ResponseYou've already chosen the best response.2
OOPS. I meant for the set to be: \(\{n:(n<N)\wedge (n \nmid N)\wedge (nN^2)\}\) at the bottom!
 one year ago

Mr.MathBest ResponseYou've already chosen the best response.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

LimitlessBest ResponseYou've already chosen the best response.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

joemath314159Best ResponseYou've already chosen the best response.3
Im getting 90 as an answer <.<
 one year ago

joemath314159Best ResponseYou've already chosen the best response.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

joemath314159Best ResponseYou've already chosen the best response.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

KingGeorgeBest ResponseYou've already chosen the best response.1
Using the brute force method, @joemath314159 is correct. There are 90 possibilities.
 one year ago

joemath314159Best ResponseYou've already chosen the best response.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

KingGeorgeBest ResponseYou've already chosen the best response.1
You could probably place some bounds on the sum of the exponents somehow.
 one year ago

joemath314159Best ResponseYou've already chosen the best response.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

KingGeorgeBest ResponseYou've already chosen the best response.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

joemath314159Best ResponseYou've already chosen the best response.3
Right. I should have used Wolfram >.< I was subtracting the two numbers. Checking if the result was positive or negative.
 one year ago

FoolForMathBest ResponseYou've already chosen the best response.1
90 is the right answer.
 one year ago

FoolForMathBest ResponseYou've already chosen the best response.1
And there exists a very smart/easy solution. It is possible to generalize to any given N.
 one year ago

siddhantsharanBest ResponseYou've already chosen the best response.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

eliassaabBest ResponseYou've already chosen the best response.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

LimitlessBest ResponseYou've already chosen the best response.2
This is fascinating. I did actually screw that upthank you for the correction. I would love to figure out what the elegant argument is, but it eludes me.
 one year ago

siddhantsharanBest ResponseYou've already chosen the best response.2
What is the elegant solution? :/
 one year ago
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
 Engagement 19 Mad Hatter
 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.