Mixing
The number of divisors being less than or equal to twice the square root of a natural number
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Ok I have been working through my new book that arrived in the mail this week, "Problems in Analytic Number Theory" Second Edition, by M.Ram Murty.
Exercise 1.3.1 asks the reader to show that:
$$d(n) leq 2 sqrtn$$
and the solution simply states that because every divisor $alpha$ of $n$ corresponds to a factorization $alpha beta=n$, and of course one of $alpha$ or $beta$ must be less than or equal to $sqrtn$, the number of divisors must be less than or equal to $2 sqrtn$.
In as much as yes I can see this to be the most simple and straight forward proof one can arrive at for this problem, there is still something that makes me feel uneasy, almost as if there is a intermediate lemma that is too obvious to the author to warrant inclusion, unfortunately, not so much is as obvious to me, so I was hoping someone could see what this is.
I just don't see how we get from knowing the elementary fact that one of the two factors of a particular factorization (ie, the product of a particular divisor and the rest ) being required to be less than or equal to $sqrtn$,allows for us to make a similar conclusion concerning the total number of such factorizations.
elementary-number-theory
asked 1 hour ago
Adam
36412
 |Â
show 1 more comment
up vote
2
down vote
favorite
Ok I have been working through my new book that arrived in the mail this week, "Problems in Analytic Number Theory" Second Edition, by M.Ram Murty.
Exercise 1.3.1 asks the reader to show that:
$$d(n) leq 2 sqrtn$$
and the solution simply states that because every divisor $alpha$ of $n$ corresponds to a factorization $alpha beta=n$, and of course one of $alpha$ or $beta$ must be less than or equal to $sqrtn$, the number of divisors must be less than or equal to $2 sqrtn$.
In as much as yes I can see this to be the most simple and straight forward proof one can arrive at for this problem, there is still something that makes me feel uneasy, almost as if there is a intermediate lemma that is too obvious to the author to warrant inclusion, unfortunately, not so much is as obvious to me, so I was hoping someone could see what this is.
I just don't see how we get from knowing the elementary fact that one of the two factors of a particular factorization (ie, the product of a particular divisor and the rest ) being required to be less than or equal to $sqrtn$,allows for us to make a similar conclusion concerning the total number of such factorizations.
elementary-number-theory
asked 1 hour ago
Adam
36412
2
Possible duplicate of Prove that $d(n)leq 2sqrtn$
– Martin R
1 hour ago
Try to see what happens if a number greater than √n is taken as a factor of n. Does it work?
– Shatabdi Sinha
1 hour ago
Ok thanks Martin I will take a look.
– Adam
1 hour ago
It's unique factorization (the fundamental theorem of algebra) that you might be missing.
– Michael Burr
1 hour ago
true you might be right there Michael I don't know I think I might be being a sore loser here because it looked easy and I was forced to look at the back of the book and still had some form of confusion, unfortunately with me if I don't hash out these little things they rear their head in embarrassing ways later on
– Adam
58 mins ago
 |Â
show 1 more comment
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Ok I have been working through my new book that arrived in the mail this week, "Problems in Analytic Number Theory" Second Edition, by M.Ram Murty.
Exercise 1.3.1 asks the reader to show that:
$$d(n) leq 2 sqrtn$$
and the solution simply states that because every divisor $alpha$ of $n$ corresponds to a factorization $alpha beta=n$, and of course one of $alpha$ or $beta$ must be less than or equal to $sqrtn$, the number of divisors must be less than or equal to $2 sqrtn$.
In as much as yes I can see this to be the most simple and straight forward proof one can arrive at for this problem, there is still something that makes me feel uneasy, almost as if there is a intermediate lemma that is too obvious to the author to warrant inclusion, unfortunately, not so much is as obvious to me, so I was hoping someone could see what this is.
I just don't see how we get from knowing the elementary fact that one of the two factors of a particular factorization (ie, the product of a particular divisor and the rest ) being required to be less than or equal to $sqrtn$,allows for us to make a similar conclusion concerning the total number of such factorizations.
elementary-number-theory
asked 1 hour ago
Adam
36412
Ok I have been working through my new book that arrived in the mail this week, "Problems in Analytic Number Theory" Second Edition, by M.Ram Murty.
Exercise 1.3.1 asks the reader to show that:
$$d(n) leq 2 sqrtn$$
and the solution simply states that because every divisor $alpha$ of $n$ corresponds to a factorization $alpha beta=n$, and of course one of $alpha$ or $beta$ must be less than or equal to $sqrtn$, the number of divisors must be less than or equal to $2 sqrtn$.
In as much as yes I can see this to be the most simple and straight forward proof one can arrive at for this problem, there is still something that makes me feel uneasy, almost as if there is a intermediate lemma that is too obvious to the author to warrant inclusion, unfortunately, not so much is as obvious to me, so I was hoping someone could see what this is.
I just don't see how we get from knowing the elementary fact that one of the two factors of a particular factorization (ie, the product of a particular divisor and the rest ) being required to be less than or equal to $sqrtn$,allows for us to make a similar conclusion concerning the total number of such factorizations.
elementary-number-theory
elementary-number-theory
asked 1 hour ago
Adam
36412
asked 1 hour ago
Adam
36412
asked 1 hour ago
Adam
36412
asked 1 hour ago
Adam
36412
asked 1 hour ago
Adam
36412
36412
2
Possible duplicate of Prove that $d(n)leq 2sqrtn$
– Martin R
1 hour ago
Try to see what happens if a number greater than √n is taken as a factor of n. Does it work?
– Shatabdi Sinha
1 hour ago
Ok thanks Martin I will take a look.
– Adam
1 hour ago
It's unique factorization (the fundamental theorem of algebra) that you might be missing.
– Michael Burr
1 hour ago
true you might be right there Michael I don't know I think I might be being a sore loser here because it looked easy and I was forced to look at the back of the book and still had some form of confusion, unfortunately with me if I don't hash out these little things they rear their head in embarrassing ways later on
– Adam
58 mins ago
 |Â
show 1 more comment
2
Possible duplicate of Prove that $d(n)leq 2sqrtn$
– Martin R
1 hour ago
Try to see what happens if a number greater than √n is taken as a factor of n. Does it work?
– Shatabdi Sinha
1 hour ago
Ok thanks Martin I will take a look.
– Adam
1 hour ago
It's unique factorization (the fundamental theorem of algebra) that you might be missing.
– Michael Burr
1 hour ago
true you might be right there Michael I don't know I think I might be being a sore loser here because it looked easy and I was forced to look at the back of the book and still had some form of confusion, unfortunately with me if I don't hash out these little things they rear their head in embarrassing ways later on
– Adam
58 mins ago
2
2
Possible duplicate of Prove that $d(n)leq 2sqrtn$
– Martin R
1 hour ago
Possible duplicate of Prove that $d(n)leq 2sqrtn$
– Martin R
1 hour ago
Try to see what happens if a number greater than √n is taken as a factor of n. Does it work?
– Shatabdi Sinha
1 hour ago
Try to see what happens if a number greater than √n is taken as a factor of n. Does it work?
– Shatabdi Sinha
1 hour ago
Ok thanks Martin I will take a look.
– Adam
1 hour ago
Ok thanks Martin I will take a look.
– Adam
1 hour ago
It's unique factorization (the fundamental theorem of algebra) that you might be missing.
– Michael Burr
1 hour ago
It's unique factorization (the fundamental theorem of algebra) that you might be missing.
– Michael Burr
1 hour ago
true you might be right there Michael I don't know I think I might be being a sore loser here because it looked easy and I was forced to look at the back of the book and still had some form of confusion, unfortunately with me if I don't hash out these little things they rear their head in embarrassing ways later on
– Adam
58 mins ago
true you might be right there Michael I don't know I think I might be being a sore loser here because it looked easy and I was forced to look at the back of the book and still had some form of confusion, unfortunately with me if I don't hash out these little things they rear their head in embarrassing ways later on
– Adam
58 mins ago
 |Â
show 1 more comment
4 Answers
4
active
oldest
votes
up vote
1
down vote
accepted
For every divisor $d$, make the ordered pair $(d,frac nd)$. The number of such ordered pairs is $d(n)$, clearly. Split them into three types, those with $d<frac nd, d=frac nd,d>frac nd$. The middle group contains at most $1$ element, namely, $(sqrt n,sqrt n)$. The other two groups are in bijection with each other, by reversing the terms. Letting $A(n)$ be the number of elements in group $1$ we then see that:
$$d(n) =
begincases
2A(n), & textif $n$ is not a perfect square \
2A(n)+1 , & textif $n$ is a perfect square
endcases$$
How big is $A(n)$?
Well, the smaller member of any ordered pair other than $(sqrt n,sqrt n)$ must be less than $sqrt n$, clearly (otherwise both members would be $>sqrt n$ hence the product would be greater than $n$). Thus $A(n)<sqrt n$. It follows that
$$d(n) <
begincases
2sqrt n, & textif $n$ is not a perfect square \
2sqrt n+1 , & textif $n$ is a perfect square
endcases$$
This is very close to what you wanted, but not exact. Of course, we can tighten our estimates. We distinguish two cases:
If $n$ is not a perfect square. In that case we already have $d(n)<2sqrt n$ so we are done.
If $n$ is a perfect square then the fact that $2sqrt n+1$ and $d(n)$ are both integers tells us that $$d(n)<2sqrt n+1implies d(n)≤2sqrt n$$
answered 43 mins ago
lulu
36.4k14275
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
add a comment |Â
up vote
1
down vote
List all the divisors of $n$:
$$d_1, d_2, ldots, d_k.$$
Note that $k = tau(n)$. These divisors come in pairs. For each $d_i$ that divides $n$, there is a $d_j$ such that $d_id_j = n.$ By your little fact, one of these hast to be less than or equal to $sqrtn.$ That means half of the divisors are less than or equal to $sqrtn$. There are only $sqrtn$ possible values for $d_i$, then. And hence only $sqrtn$ possible values for $d_j$. In total that's at most $2sqrtn$ divisors.
When you see it, you'll go "Doh!"
answered 50 mins ago
B. Goddard
16.7k21338
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
add a comment |Â
up vote
1
down vote
You've already observed that there is a pairing between divisors greater than $sqrtn$ and those less than $sqrtn$. To get that this pairing, you need the fundamental theorem of algebra, i.e., there's no way to use the same factor twice.
Since every pair has a distinct factor less than or equal to $sqrtn$ and there are $sqrtn$ positive numbers less than or equal to $sqrtn$, this gives the desired count.
answered 48 mins ago
Michael Burr
25.7k13262
add a comment |Â
up vote
1
down vote
Let $n$ be a positive integer. Suppose that we have $ab=n$ for some positive integers $a$ and $b$. If $a>sqrtn$ and $b>sqrtn$, then $n=ab>sqrtnsqrtn=n$, a contradiction. Therefore, one of $a$ and $b$ must be at most $sqrtn$. Set theoretically, this argument says
$$(a,b)inmathbbZ_>0^2:ab=nsubseteq (a,b)inmathbbZ_>0^2: alesqrtn mbox or blesqrtn.$$
Note that the cardinality of the set on the left-hand side is the number of divisors of $n$, and the cardinality of the set on the right-hand side is at most $2sqrtn$. Hence, $d(n)le 2(n)$.
answered 59 mins ago
eloiPrime
1,617519
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
That's not what was asked.
– the_fox
52 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
I updated my answer.
– eloiPrime
33 mins ago
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
For every divisor $d$, make the ordered pair $(d,frac nd)$. The number of such ordered pairs is $d(n)$, clearly. Split them into three types, those with $d<frac nd, d=frac nd,d>frac nd$. The middle group contains at most $1$ element, namely, $(sqrt n,sqrt n)$. The other two groups are in bijection with each other, by reversing the terms. Letting $A(n)$ be the number of elements in group $1$ we then see that:
$$d(n) =
begincases
2A(n), & textif $n$ is not a perfect square \
2A(n)+1 , & textif $n$ is a perfect square
endcases$$
How big is $A(n)$?
Well, the smaller member of any ordered pair other than $(sqrt n,sqrt n)$ must be less than $sqrt n$, clearly (otherwise both members would be $>sqrt n$ hence the product would be greater than $n$). Thus $A(n)<sqrt n$. It follows that
$$d(n) <
begincases
2sqrt n, & textif $n$ is not a perfect square \
2sqrt n+1 , & textif $n$ is a perfect square
endcases$$
This is very close to what you wanted, but not exact. Of course, we can tighten our estimates. We distinguish two cases:
If $n$ is not a perfect square. In that case we already have $d(n)<2sqrt n$ so we are done.
If $n$ is a perfect square then the fact that $2sqrt n+1$ and $d(n)$ are both integers tells us that $$d(n)<2sqrt n+1implies d(n)≤2sqrt n$$
answered 43 mins ago
lulu
36.4k14275
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
add a comment |Â
up vote
1
down vote
accepted
For every divisor $d$, make the ordered pair $(d,frac nd)$. The number of such ordered pairs is $d(n)$, clearly. Split them into three types, those with $d<frac nd, d=frac nd,d>frac nd$. The middle group contains at most $1$ element, namely, $(sqrt n,sqrt n)$. The other two groups are in bijection with each other, by reversing the terms. Letting $A(n)$ be the number of elements in group $1$ we then see that:
$$d(n) =
begincases
2A(n), & textif $n$ is not a perfect square \
2A(n)+1 , & textif $n$ is a perfect square
endcases$$
How big is $A(n)$?
Well, the smaller member of any ordered pair other than $(sqrt n,sqrt n)$ must be less than $sqrt n$, clearly (otherwise both members would be $>sqrt n$ hence the product would be greater than $n$). Thus $A(n)<sqrt n$. It follows that
$$d(n) <
begincases
2sqrt n, & textif $n$ is not a perfect square \
2sqrt n+1 , & textif $n$ is a perfect square
endcases$$
This is very close to what you wanted, but not exact. Of course, we can tighten our estimates. We distinguish two cases:
If $n$ is not a perfect square. In that case we already have $d(n)<2sqrt n$ so we are done.
If $n$ is a perfect square then the fact that $2sqrt n+1$ and $d(n)$ are both integers tells us that $$d(n)<2sqrt n+1implies d(n)≤2sqrt n$$
answered 43 mins ago
lulu
36.4k14275
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
For every divisor $d$, make the ordered pair $(d,frac nd)$. The number of such ordered pairs is $d(n)$, clearly. Split them into three types, those with $d<frac nd, d=frac nd,d>frac nd$. The middle group contains at most $1$ element, namely, $(sqrt n,sqrt n)$. The other two groups are in bijection with each other, by reversing the terms. Letting $A(n)$ be the number of elements in group $1$ we then see that:
$$d(n) =
begincases
2A(n), & textif $n$ is not a perfect square \
2A(n)+1 , & textif $n$ is a perfect square
endcases$$
How big is $A(n)$?
Well, the smaller member of any ordered pair other than $(sqrt n,sqrt n)$ must be less than $sqrt n$, clearly (otherwise both members would be $>sqrt n$ hence the product would be greater than $n$). Thus $A(n)<sqrt n$. It follows that
$$d(n) <
begincases
2sqrt n, & textif $n$ is not a perfect square \
2sqrt n+1 , & textif $n$ is a perfect square
endcases$$
This is very close to what you wanted, but not exact. Of course, we can tighten our estimates. We distinguish two cases:
If $n$ is not a perfect square. In that case we already have $d(n)<2sqrt n$ so we are done.
If $n$ is a perfect square then the fact that $2sqrt n+1$ and $d(n)$ are both integers tells us that $$d(n)<2sqrt n+1implies d(n)≤2sqrt n$$
answered 43 mins ago
lulu
36.4k14275
For every divisor $d$, make the ordered pair $(d,frac nd)$. The number of such ordered pairs is $d(n)$, clearly. Split them into three types, those with $d<frac nd, d=frac nd,d>frac nd$. The middle group contains at most $1$ element, namely, $(sqrt n,sqrt n)$. The other two groups are in bijection with each other, by reversing the terms. Letting $A(n)$ be the number of elements in group $1$ we then see that:
$$d(n) =
begincases
2A(n), & textif $n$ is not a perfect square \
2A(n)+1 , & textif $n$ is a perfect square
endcases$$
How big is $A(n)$?
Well, the smaller member of any ordered pair other than $(sqrt n,sqrt n)$ must be less than $sqrt n$, clearly (otherwise both members would be $>sqrt n$ hence the product would be greater than $n$). Thus $A(n)<sqrt n$. It follows that
$$d(n) <
begincases
2sqrt n, & textif $n$ is not a perfect square \
2sqrt n+1 , & textif $n$ is a perfect square
endcases$$
This is very close to what you wanted, but not exact. Of course, we can tighten our estimates. We distinguish two cases:
If $n$ is not a perfect square. In that case we already have $d(n)<2sqrt n$ so we are done.
If $n$ is a perfect square then the fact that $2sqrt n+1$ and $d(n)$ are both integers tells us that $$d(n)<2sqrt n+1implies d(n)≤2sqrt n$$
answered 43 mins ago
lulu
36.4k14275
edited 38 mins ago
answered 43 mins ago
lulu
36.4k14275
answered 43 mins ago
lulu
36.4k14275
answered 43 mins ago
lulu
36.4k14275
36.4k14275
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
add a comment |Â
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
ok thankyou very much for this @lulu this is perfect
– Adam
38 mins ago
add a comment |Â
up vote
1
down vote
List all the divisors of $n$:
$$d_1, d_2, ldots, d_k.$$
Note that $k = tau(n)$. These divisors come in pairs. For each $d_i$ that divides $n$, there is a $d_j$ such that $d_id_j = n.$ By your little fact, one of these hast to be less than or equal to $sqrtn.$ That means half of the divisors are less than or equal to $sqrtn$. There are only $sqrtn$ possible values for $d_i$, then. And hence only $sqrtn$ possible values for $d_j$. In total that's at most $2sqrtn$ divisors.
When you see it, you'll go "Doh!"
answered 50 mins ago
B. Goddard
16.7k21338
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
add a comment |Â
up vote
1
down vote
List all the divisors of $n$:
$$d_1, d_2, ldots, d_k.$$
Note that $k = tau(n)$. These divisors come in pairs. For each $d_i$ that divides $n$, there is a $d_j$ such that $d_id_j = n.$ By your little fact, one of these hast to be less than or equal to $sqrtn.$ That means half of the divisors are less than or equal to $sqrtn$. There are only $sqrtn$ possible values for $d_i$, then. And hence only $sqrtn$ possible values for $d_j$. In total that's at most $2sqrtn$ divisors.
When you see it, you'll go "Doh!"
answered 50 mins ago
B. Goddard
16.7k21338
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
List all the divisors of $n$:
$$d_1, d_2, ldots, d_k.$$
Note that $k = tau(n)$. These divisors come in pairs. For each $d_i$ that divides $n$, there is a $d_j$ such that $d_id_j = n.$ By your little fact, one of these hast to be less than or equal to $sqrtn.$ That means half of the divisors are less than or equal to $sqrtn$. There are only $sqrtn$ possible values for $d_i$, then. And hence only $sqrtn$ possible values for $d_j$. In total that's at most $2sqrtn$ divisors.
When you see it, you'll go "Doh!"
answered 50 mins ago
B. Goddard
16.7k21338
List all the divisors of $n$:
$$d_1, d_2, ldots, d_k.$$
Note that $k = tau(n)$. These divisors come in pairs. For each $d_i$ that divides $n$, there is a $d_j$ such that $d_id_j = n.$ By your little fact, one of these hast to be less than or equal to $sqrtn.$ That means half of the divisors are less than or equal to $sqrtn$. There are only $sqrtn$ possible values for $d_i$, then. And hence only $sqrtn$ possible values for $d_j$. In total that's at most $2sqrtn$ divisors.
When you see it, you'll go "Doh!"
answered 50 mins ago
B. Goddard
16.7k21338
answered 50 mins ago
B. Goddard
16.7k21338
answered 50 mins ago
B. Goddard
16.7k21338
answered 50 mins ago
B. Goddard
16.7k21338
16.7k21338
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
add a comment |Â
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
I know but i promised myself I would post whenever I was confused over something straight forward to everyone else, it's sort of a means of making sure it has a "memorable" learning process to put it nicely
– Adam
35 mins ago
add a comment |Â
up vote
1
down vote
You've already observed that there is a pairing between divisors greater than $sqrtn$ and those less than $sqrtn$. To get that this pairing, you need the fundamental theorem of algebra, i.e., there's no way to use the same factor twice.
Since every pair has a distinct factor less than or equal to $sqrtn$ and there are $sqrtn$ positive numbers less than or equal to $sqrtn$, this gives the desired count.
answered 48 mins ago
Michael Burr
25.7k13262
add a comment |Â
up vote
1
down vote
You've already observed that there is a pairing between divisors greater than $sqrtn$ and those less than $sqrtn$. To get that this pairing, you need the fundamental theorem of algebra, i.e., there's no way to use the same factor twice.
Since every pair has a distinct factor less than or equal to $sqrtn$ and there are $sqrtn$ positive numbers less than or equal to $sqrtn$, this gives the desired count.
answered 48 mins ago
Michael Burr
25.7k13262
add a comment |Â
up vote
1
down vote
up vote
1
down vote
You've already observed that there is a pairing between divisors greater than $sqrtn$ and those less than $sqrtn$. To get that this pairing, you need the fundamental theorem of algebra, i.e., there's no way to use the same factor twice.
Since every pair has a distinct factor less than or equal to $sqrtn$ and there are $sqrtn$ positive numbers less than or equal to $sqrtn$, this gives the desired count.
answered 48 mins ago
Michael Burr
25.7k13262
You've already observed that there is a pairing between divisors greater than $sqrtn$ and those less than $sqrtn$. To get that this pairing, you need the fundamental theorem of algebra, i.e., there's no way to use the same factor twice.
Since every pair has a distinct factor less than or equal to $sqrtn$ and there are $sqrtn$ positive numbers less than or equal to $sqrtn$, this gives the desired count.
answered 48 mins ago
Michael Burr
25.7k13262
answered 48 mins ago
Michael Burr
25.7k13262
answered 48 mins ago
Michael Burr
25.7k13262
answered 48 mins ago
Michael Burr
25.7k13262
25.7k13262
add a comment |Â
add a comment |Â
up vote
1
down vote
Let $n$ be a positive integer. Suppose that we have $ab=n$ for some positive integers $a$ and $b$. If $a>sqrtn$ and $b>sqrtn$, then $n=ab>sqrtnsqrtn=n$, a contradiction. Therefore, one of $a$ and $b$ must be at most $sqrtn$. Set theoretically, this argument says
$$(a,b)inmathbbZ_>0^2:ab=nsubseteq (a,b)inmathbbZ_>0^2: alesqrtn mbox or blesqrtn.$$
Note that the cardinality of the set on the left-hand side is the number of divisors of $n$, and the cardinality of the set on the right-hand side is at most $2sqrtn$. Hence, $d(n)le 2(n)$.
answered 59 mins ago
eloiPrime
1,617519
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
That's not what was asked.
– the_fox
52 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
I updated my answer.
– eloiPrime
33 mins ago
add a comment |Â
up vote
1
down vote
Let $n$ be a positive integer. Suppose that we have $ab=n$ for some positive integers $a$ and $b$. If $a>sqrtn$ and $b>sqrtn$, then $n=ab>sqrtnsqrtn=n$, a contradiction. Therefore, one of $a$ and $b$ must be at most $sqrtn$. Set theoretically, this argument says
$$(a,b)inmathbbZ_>0^2:ab=nsubseteq (a,b)inmathbbZ_>0^2: alesqrtn mbox or blesqrtn.$$
Note that the cardinality of the set on the left-hand side is the number of divisors of $n$, and the cardinality of the set on the right-hand side is at most $2sqrtn$. Hence, $d(n)le 2(n)$.
answered 59 mins ago
eloiPrime
1,617519
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
That's not what was asked.
– the_fox
52 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
I updated my answer.
– eloiPrime
33 mins ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $n$ be a positive integer. Suppose that we have $ab=n$ for some positive integers $a$ and $b$. If $a>sqrtn$ and $b>sqrtn$, then $n=ab>sqrtnsqrtn=n$, a contradiction. Therefore, one of $a$ and $b$ must be at most $sqrtn$. Set theoretically, this argument says
$$(a,b)inmathbbZ_>0^2:ab=nsubseteq (a,b)inmathbbZ_>0^2: alesqrtn mbox or blesqrtn.$$
Note that the cardinality of the set on the left-hand side is the number of divisors of $n$, and the cardinality of the set on the right-hand side is at most $2sqrtn$. Hence, $d(n)le 2(n)$.
answered 59 mins ago
eloiPrime
1,617519
Let $n$ be a positive integer. Suppose that we have $ab=n$ for some positive integers $a$ and $b$. If $a>sqrtn$ and $b>sqrtn$, then $n=ab>sqrtnsqrtn=n$, a contradiction. Therefore, one of $a$ and $b$ must be at most $sqrtn$. Set theoretically, this argument says
$$(a,b)inmathbbZ_>0^2:ab=nsubseteq (a,b)inmathbbZ_>0^2: alesqrtn mbox or blesqrtn.$$
Note that the cardinality of the set on the left-hand side is the number of divisors of $n$, and the cardinality of the set on the right-hand side is at most $2sqrtn$. Hence, $d(n)le 2(n)$.
answered 59 mins ago
eloiPrime
1,617519
edited 34 mins ago
answered 59 mins ago
eloiPrime
1,617519
answered 59 mins ago
eloiPrime
1,617519
answered 59 mins ago
eloiPrime
1,617519
1,617519
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
That's not what was asked.
– the_fox
52 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
I updated my answer.
– eloiPrime
33 mins ago
add a comment |Â
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
That's not what was asked.
– the_fox
52 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
I updated my answer.
– eloiPrime
33 mins ago
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
Sure I understand this part well, it is how we then use this to make an assertion concerning the number of such factorizations being less than or equal to twice the square root of the number, I just want to state this algebraically somehow
– Adam
56 mins ago
That's not what was asked.
– the_fox
52 mins ago
That's not what was asked.
– the_fox
52 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
$d(n)$ denotes the number of divisors of $n$ yes?
– Adam
40 mins ago
I updated my answer.
– eloiPrime
33 mins ago
I updated my answer.
– eloiPrime
33 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2920119%2fthe-number-of-divisors-being-less-than-or-equal-to-twice-the-square-root-of-a-na%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Possible duplicate of Prove that $d(n)leq 2sqrtn$
– Martin R
1 hour ago
Try to see what happens if a number greater than √n is taken as a factor of n. Does it work?
– Shatabdi Sinha
1 hour ago
Ok thanks Martin I will take a look.
– Adam
1 hour ago
It's unique factorization (the fundamental theorem of algebra) that you might be missing.
– Michael Burr
1 hour ago
true you might be right there Michael I don't know I think I might be being a sore loser here because it looked easy and I was forced to look at the back of the book and still had some form of confusion, unfortunately with me if I don't hash out these little things they rear their head in embarrassing ways later on
– Adam
58 mins ago