mersenneforum.org Is there any such theorem that states this?
 Register FAQ Search Today's Posts Mark Forums Read

 2013-03-25, 19:54 #1 soumya   Mar 2013 22 Posts 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
 2013-03-25, 20:16 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts 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.
 2013-03-25, 20:31 #3 NBtarheel_33     "Nathan" Jul 2008 Maryland, USA 5·223 Posts 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
2013-03-25, 20:40   #4
jyb

Aug 2005
Seattle, WA

32458 Posts

Quote:
 Originally Posted by NBtarheel_33 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 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.

2013-03-25, 21:09   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by jyb 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

2013-03-25, 22:35   #6
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by science_man_88 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.

2013-03-25, 23:10   #7
Mr. P-1

Jun 2003

116910 Posts

Quote:
 Originally Posted by Mini-Geek 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}$.

2013-03-25, 23:22   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Mr. P-1 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.

2013-03-26, 05:29   #9
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by NBtarheel_33 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.

 2013-03-26, 15:56 #10 ATH Einyen     Dec 2003 Denmark 17·181 Posts $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
 2013-03-27, 19:07 #11 soumya   Mar 2013 22 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post bgbeuning Computer Science & Computational Number Theory 7 2015-10-13 13:55 Joshua2 Homework Help 15 2009-10-30 05:14 jasong Soap Box 8 2007-01-25 15:33 herege Math 25 2006-11-18 09:54 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