mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2013-03-25, 19:54   #1
soumya
 
Mar 2013

22 Posts
Default Is there any such theorem that states this?

Is there any such theorem that implies/states that if C is a composite number, so that it is greater than an integer i and less than i^2 (i.e. the square of i), then C must have at least one factor (other than 1) which is less than i?
i.e. if i<C<i^2 (where i is any positive integer and C a composite number) then C must have at least one factor (other than 1) say F, so that F<i.
soumya is offline   Reply With Quote
Old 2013-03-25, 20:16   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

That is true. Even the more strict F \le sqrt{C}, where F is the smallest prime factor of C, is known to be true. It's easy to prove, since if F > sqrt{C}, the product must be larger than C, which is a contradiction.
I don't know if this fact is called a "theorem", but I know it's proven true.
Mini-Geek is offline   Reply With Quote
Old 2013-03-25, 20:31   #3
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5·223 Posts
Default

First of all, a technical nitpick: the symbol i has a special, specific meaning in mathematics: namely the imaginary unit i = sqrt{-1}. So instead of i for integer, let's use n. We can still use C to represent your composite number, also, of course, an integer.

So you're saying that C is composite, and that n < C < n^2 for some integer n. Well, let's take the square root on all sides of this inequality, which would yield sqrt{n} < sqrt{C} < n (*).

Now we know that the maximum possible size of any factor of C is going to be sqrt{C} (think about this for a while until it is clear, if it is not already!).

Therefore, any factor F of C will be such that F \leq sqrt{C}. But then, by the inequality (*) above, we know that sqrt{C} < n, which implies the strict inequality F < n(**) for all factors F of n.

Note that if n is indeed composite, as we have assumed, we are guaranteed the existence of a nontrivial F, and hence, along with inequality (**), we are guaranteed the existence of a nontrivial factor F < n.

Q. E. D.

[Not sure if this has a name, e.g. "Blah's Theorem", but it's easy enough to prove to yourself. More likely it is something like an exercise in an elementary number theory course.]

Last fiddled with by NBtarheel_33 on 2013-03-25 at 20:33
NBtarheel_33 is offline   Reply With Quote
Old 2013-03-25, 20:40   #4
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

32458 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Now we know that the maximum possible size of any factor of C is going to be sqrt{C} (think about this for a while until it is clear, if it is not already!).
Huh?! Isn't 50 a factor of 100? And isn't 50 > 10?

Quote:
Originally Posted by NBtarheel_33 View Post
Therefore, any factor F of C will be such that F \leq sqrt{C}. But then, by the inequality (*) above, we know that sqrt{C} < n, which implies the strict inequality F < n(**) for all factors F of n.

Note that if n is indeed composite, as we have assumed, we are guaranteed the existence of a nontrivial F, and hence, along with inequality (**), we are guaranteed the existence of a nontrivial factor F < n.

Q. E. D.

[Not sure if this has a name, e.g. "Blah's Theorem", but it's easy enough to prove to yourself. More likely it is something like an exercise in an elementary number theory course.]
If you change your uses of "any factor" and "all factors" to "the minimum nontrivial factor" then I agree with your argument.
jyb is offline   Reply With Quote
Old 2013-03-25, 21:09   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by jyb View Post
Huh?! Isn't 50 a factor of 100? And isn't 50 > 10?

I believe strictly speaking only primes are factors, the rest ( like 50) are divisors.

Last fiddled with by science_man_88 on 2013-03-25 at 21:10
science_man_88 is offline   Reply With Quote
Old 2013-03-25, 22:35   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I believe strictly speaking only primes are factors, the rest ( like 50) are divisors.
There's a term for factors that are prime: prime factors. Factors and divisors are basically synonymous in this usage.
Mini-Geek is offline   Reply With Quote
Old 2013-03-25, 23:10   #7
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

116910 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
There's a term for factors that are prime: prime factors. Factors and divisors are basically synonymous in this usage.
Strictly Speaking, Mini-Geek is correct. Of course we often just write "factor" when we mean prime factor.

However interpreting NBtarheel_33's remark as refering to prime factors only isn't enough to save it. For example 5|15 and 5 > \sqrt{16} > \sqrt{15}.
Mr. P-1 is offline   Reply With Quote
Old 2013-03-25, 23:22   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
However interpreting NBtarheel_33's remark as refering to prime factors only isn't enough to save it. For example 5|15 and 5 > \sqrt{16} > \sqrt{15}.
the keyword missing is least.
science_man_88 is offline   Reply With Quote
Old 2013-03-26, 05:29   #9
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Now we know that the maximum possible size of any factor of C is going to be sqrt{C} (think about this for a while until it is clear, if it is not already!).
This is a false statement, as has been pointed out already. Also as has been pointed out, there can even be prime factors greater than \sqrt {C}.

Nitpick the second: i is a perfectly good variable to use; its use is in no way at all limited to that of \sqrt{-1} (which is certainly its "default" meaning wihtout context). In this case he clearly and unambiguously defined what i is.
Dubslow is offline   Reply With Quote
Old 2013-03-26, 15:56   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

17·181 Posts
Default

C < i^2 so sqrt{C} < i.

At least one factor of C is <= sqrt{C} and therefore < i which is what OP asked.

Last fiddled with by ATH on 2013-03-26 at 15:57
ATH is offline   Reply With Quote
Old 2013-03-27, 19:07   #11
soumya
 
Mar 2013

22 Posts
Default

One of my friends suggested a simpler proof which I want to share. Let's presume all factors of C are greater than 'i'. Therefore, all such factors can be written in the form i+k. Let's presume the smallest factor of 'i' is F, which is equal to i+x. So now we can say that C=(i+x) * (i+y) = i^2 +i(x+y)+xy, which is greater than i^2. So our first proposition must be false.
A big "thank you" to all of you. But I would still want to know, if such a theorem already exists?

Last fiddled with by soumya on 2013-03-27 at 19:08
soumya is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pocklington's Theorem bgbeuning Computer Science & Computational Number Theory 7 2015-10-13 13:55
DifEQ theorem ? Joshua2 Homework Help 15 2009-10-30 05:14
The United States of America is not a democracy. jasong Soap Box 8 2007-01-25 15:33
Number Theorem herege Math 25 2006-11-18 09:54
Størmer's theorem grandpascorpion Factoring 0 2006-09-10 04:59

All times are UTC. The time now is 04:12.

Mon Apr 19 04:12:26 UTC 2021 up 10 days, 22:53, 0 users, load averages: 1.81, 1.92, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.