Remember Me?

 Straight Dope Message Board Remember Me?

#### Menu

 Thread Tools Display Modes
#1
04-26-2012, 04:12 PM
 Christopher Robin Davies Guest Join Date: Jan 2012 Posts: 230
Quick question about prime factorization

Take any whole number X. Obviously it is either prime or composite. If it is prime, then by definition it has no factors other than itself and 1. If it is composite then it is the product of a unique series of smaller primes. That is the fundamental theorem of arithmetic. It seems to me that at least those prime factors has to be less than or equal to the square root of Y, where Y is the smallest perfect square that is larger than X. Right? In other words if X was 323, then the next perfect square is 324, which is 18 squared, and so at least one of 323's factors has to be smaller than 18. (And that is correct in this case; 323's factors are 17 and 19.)

That seems intuitively obvious to me and I have a vague memory of seeing the proof way back in junior high. But for the life of me I cannot remember what it is. Anybody know?

Last edited by Christopher Robin Davies; 04-26-2012 at 04:14 PM.
#2
04-26-2012, 04:17 PM
 Trinopus Member Join Date: Dec 2002 Location: San Diego, CA Posts: 22,708
Simple proof by contradiction: assume that all of X's components are larger than the square root of X. Multiply any two of them, and the result is larger than X. This contradicts the assumption, and so must be false.

(This strategy, assume what you want to disprove, is key in the proof that the square root of two is irrational. Simply assume it *is* rational -- x/y -- and show how this leads to a contradiction.)
#3
04-26-2012, 04:43 PM
 Christopher Robin Davies Guest Join Date: Jan 2012 Posts: 230
Quote:
 Originally Posted by Trinopus Simple proof by contradiction: assume that all of X's components are larger than the square root of X. Multiply any two of them, and the result is larger than X. This contradicts the assumption, and so must be false. (This strategy, assume what you want to disprove, is key in the proof that the square root of two is irrational. Simply assume it *is* rational -- x/y -- and show how this leads to a contradiction.)
Thank you. I knew it was something simple but my brain was not working.
#4
04-26-2012, 05:17 PM
 Thudlow Boink Charter Member Join Date: May 2000 Location: Lincoln, IL Posts: 24,015
Quote:
 Originally Posted by Christopher Robin Davies Take any whole number X.
X isn't a whole number; n is!
#5
04-26-2012, 09:36 PM
 TonySinclair Guest Join Date: Feb 2012 Posts: 5,380
Quote:
 Originally Posted by Trinopus assume what you want to disprove
That's absurd!
#6
04-26-2012, 11:04 PM
 Trinopus Member Join Date: Dec 2002 Location: San Diego, CA Posts: 22,708
Quote:
 Originally Posted by TonySinclair That's absurd!
I've been reduced!

(I knew I shouldn't have taken that Trigonometry class from A. Square!)
#7
04-27-2012, 07:51 AM
 Hari Seldon Member Join Date: Mar 2002 Location: Trantor Posts: 11,181
If d divides n, then d and n/d cannot both be larger than the square root of n, else their product would be > n.

To illustrate, I am currently reading a book of 443 pages and I got curious whether that was prime. Well, obviously not divisible by 2,3, or 5. 7 is out since 450 is not divisible by 7. 11 is out by a simple test. 13 is out because 430 (443 - 13) is not divisible by 13. 17 is out because 460 is not divisible by 17 and for 19, I added 57 and saw that 500 is not divisible by 19. The next prime square is too large (529) so in under a minute I saw that 443 is indeed prime.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     General Questions     Great Debates     Elections     Cafe Society     The Game Room     Thread Games     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit

All times are GMT -5. The time now is 10:42 AM.

 -- Straight Dope v3.7.3 -- Sultantheme's Responsive vB3-blue Contact Us - Straight Dope Homepage - Archive - Top
Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright © 2017 Sun-Times Media, LLC.

 -- Straight Dope v3.7.3 -- Sultantheme's Responsive vB3-blue
Copyright © 2017