A community for students.
Here's the question you clicked on:
 0 viewing
FoolForMath
 2 years 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 \) ?
FoolForMath
 2 years 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 \) ?

This Question is Closed

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

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

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

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

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

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

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

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

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

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

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2In 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\)...

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

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

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

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2I am getting the feeling that \(\{n: n\mid N^2 \wedge n<N \wedge n\nmid N\}\) is an empty set.. Hmm..

siddhantsharan
 2 years ago
Best ResponseYou've already chosen the best response.2Well. 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.

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

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2OOOH, 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\).

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

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

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2My proof ironically illustrates that the original parameters are necessary: If \(n \geq N\), then \(n \mid N\) for many \(n\).

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2The 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\). :)

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

Mr.Math
 2 years ago
Best ResponseYou've already chosen the best response.1The 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.\)

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2I 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\).

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

joemath314159
 2 years ago
Best ResponseYou've already chosen the best response.3There 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.

joemath314159
 2 years ago
Best ResponseYou've already chosen the best response.3I 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.

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

joemath314159
 2 years ago
Best ResponseYou've already chosen the best response.3Yeah, i could only brute force it too. Im not sure if there is a clever way to attempt this problem.

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

joemath314159
 2 years ago
Best ResponseYou've already chosen the best response.3i 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 >.<

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.1I 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.

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

FoolForMath
 2 years ago
Best ResponseYou've already chosen the best response.190 is the right answer.

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

siddhantsharan
 2 years ago
Best ResponseYou've already chosen the best response.2I think writing it as \[2^{m  10} < 3^{9  n}\] Where either n > 9 Or m > 10, Makes things a lot simpler.

eliassaab
 2 years ago
Best ResponseYou've already chosen the best response.0There 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} \]

Limitless
 2 years ago
Best ResponseYou've already chosen the best response.2This 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.

siddhantsharan
 2 years ago
Best ResponseYou've already chosen the best response.2What is the elegant solution? :/
Ask your own question
Sign UpFind more explanations on OpenStudy
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.