## FoolForMath 3 years ago 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$$ ?

1. siddhantsharan

I think you messed up the definition of "cute". IT does NOT mean devilishly hard.

2. experimentX

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

3. Limitless

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

4. FoolForMath

N divides N^2

5. experimentX

and n∤N ??

6. FoolForMath

"does not divide"

7. siddhantsharan

Isnt N a number? How is it a set?

8. FoolForMath

In this context, Set = let

9. siddhantsharan

Oh. Okay. Thanks!

10. experimentX

wild guess 1??

11. FoolForMath

12. experimentX

no ... i just find my logic too wild

13. Limitless

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

14. siddhantsharan

@experimentx At least 15, man.

15. Limitless

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$$...

16. siddhantsharan

Is it 84? Am I even close?

17. Limitless

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

18. FoolForMath

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

19. Limitless

I am getting the feeling that $$\{n: n\mid N^2 \wedge n<N \wedge n\nmid N\}$$ is an empty set.. Hmm..

20. siddhantsharan

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.

21. siddhantsharan

Now, If it is some, say, $3^{11} * 2^m$

22. Limitless

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$$.

23. Limitless

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

24. siddhantsharan

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

25. Limitless

My proof ironically illustrates that the original parameters are necessary: If $$n \geq N$$, then $$n \mid N$$ for many $$n$$.

26. Limitless

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$$. :)

27. Limitless

OOPS. I meant for the set to be: $$\{n:(n<N)\wedge (n \nmid N)\wedge (n|N^2)\}$$ at the bottom!

28. Mr.Math

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.$$

29. Limitless

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$$.

30. joemath314159

Im getting 90 as an answer <.<

31. joemath314159

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.

32. joemath314159

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.

33. KingGeorge

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

34. joemath314159

Yeah, i could only brute force it too. Im not sure if there is a clever way to attempt this problem.

35. KingGeorge

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

36. joemath314159

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 >.<

37. KingGeorge

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.

38. joemath314159

Right. I should have used Wolfram >.< I was subtracting the two numbers. Checking if the result was positive or negative.

39. FoolForMath

90 is the right answer.

40. FoolForMath

And there exists a very smart/easy solution. It is possible to generalize to any given N.

41. siddhantsharan

I think writing it as $2^{m - 10} < 3^{9 - n}$ Where either n > 9 Or m > 10, Makes things a lot simpler.

42. eliassaab

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}$

43. Limitless

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.

44. siddhantsharan

What is the elegant solution? :/