Is there any such theorem that states this?

soumya · 2013-03-25, 19:54

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.

Mini-Geek · 2013-03-25, 20:16

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.

NBtarheel_33 · 2013-03-25, 20:31

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

jyb · 2013-03-25, 20:40

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.

science_man_88 · 2013-03-25, 21:09

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.

Mini-Geek · 2013-03-25, 22:35

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.

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

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

science_man_88 · 2013-03-25, 23:22

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.

Dubslow · 2013-03-26, 05:29

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.

ATH · 2013-03-26, 15:56

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

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

soumya · 2013-03-27, 19:07

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?

2013-03-25, 19:54	#1
soumya Mar 2013 2² 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<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.

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-26, 15:56	#10
ATH Einyen Dec 2003 Denmark 5×11×61 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 4₁₆ 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
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

2013-03-25, 20:16	#2
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 2·3·23·31 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.