Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
FoolForMath
Group Title
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 \) ?
 2 years ago
 2 years ago
FoolForMath Group Title
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 \) ?
 2 years ago
 2 years ago

This Question is Closed

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
I think you messed up the definition of "cute". IT does NOT mean devilishly hard.
 2 years ago

experimentX Group TitleBest ResponseYou've already chosen the best response.0
how do you read nN^2 ?? i seem to have forgotten
 2 years ago

Limitless Group TitleBest ResponseYou've already chosen the best response.2
This is fun. Don't remove it, please. D:
 2 years ago

FoolForMath Group TitleBest ResponseYou've already chosen the best response.1
N divides N^2
 2 years ago

experimentX Group TitleBest ResponseYou've already chosen the best response.0
and n∤N ??
 2 years ago

FoolForMath Group TitleBest ResponseYou've already chosen the best response.1
"does not divide"
 2 years ago

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
Isnt N a number? How is it a set?
 2 years ago

FoolForMath Group TitleBest ResponseYou've already chosen the best response.1
In this context, Set = let
 2 years ago

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
Oh. Okay. Thanks!
 2 years ago

experimentX Group TitleBest ResponseYou've already chosen the best response.0
wild guess 1??
 2 years ago

FoolForMath Group TitleBest ResponseYou've already chosen the best response.1
Nothing is wild about this problem.
 2 years ago

experimentX Group TitleBest ResponseYou've already chosen the best response.0
no ... i just find my logic too wild
 2 years ago

Limitless Group TitleBest ResponseYou've already chosen the best response.2
I agree. There are certain things seeping into my brain.
 2 years ago

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
@experimentx At least 15, man.
 2 years ago

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

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
Is it 84? Am I even close?
 2 years ago

Limitless Group TitleBest ResponseYou've already chosen the best response.2
Argh. There are minor details that I messed up just now.
 2 years ago

FoolForMath Group TitleBest ResponseYou've already chosen the best response.1
Close, very close :) But then I would appreciate a general and formal solution.
 2 years ago

Limitless Group TitleBest 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..
 2 years ago

siddhantsharan Group TitleBest 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.
 2 years ago

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

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

Limitless Group TitleBest ResponseYou've already chosen the best response.2
Actually, oops. \(\frac{k_1}{N}\) is not always an integer.
 2 years ago

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
And similarly I did it for cases of 2 and ..... Obviously missed some.
 2 years ago

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

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

Limitless Group TitleBest 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!
 2 years ago

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

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

joemath314159 Group TitleBest ResponseYou've already chosen the best response.3
Im getting 90 as an answer <.<
 2 years ago

joemath314159 Group TitleBest 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.
 2 years ago

joemath314159 Group TitleBest 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.
 2 years ago

KingGeorge Group TitleBest ResponseYou've already chosen the best response.1
Using the brute force method, @joemath314159 is correct. There are 90 possibilities.
 2 years ago

joemath314159 Group TitleBest 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.
 2 years ago

KingGeorge Group TitleBest ResponseYou've already chosen the best response.1
You could probably place some bounds on the sum of the exponents somehow.
 2 years ago

joemath314159 Group TitleBest 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 >.<
 2 years ago

KingGeorge Group TitleBest 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.
 2 years ago

joemath314159 Group TitleBest 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.
 2 years ago

FoolForMath Group TitleBest ResponseYou've already chosen the best response.1
90 is the right answer.
 2 years ago

FoolForMath Group TitleBest 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.
 2 years ago

siddhantsharan Group TitleBest 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.
 2 years ago

eliassaab Group TitleBest 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} \]
 2 years ago

Limitless Group TitleBest 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.
 2 years ago

siddhantsharan Group TitleBest ResponseYou've already chosen the best response.2
What is the elegant solution? :/
 2 years 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.