11. จำนวนเฉพาะ

วันที่โพสต์: 7 ม.ค. 2014, 8:41:46

จำนวนเฉพาะ (prime number) คือเลขจำนวนเต็มที่หารด้วยเลขหนึ่ง และตัวของมันเองเท่านั้นได้ลงตัว ดังนั้น ตามความจำกัดความนี้

เลขเฉพาะจึงได้แก่เลข 2, 3, 5, 7, 11, 13, 17, 19, 29, 31.....เพราะ 2 ก็มีเฉพาะ 1 กับ 2 ที่หารมันได้ลงตัว หรือ 17 ก็มีแต่ 1 กับ 17 ที่หารมันลงตัวเช่นกัน แต่เลข 15 ไม่เป็นเลขเฉพาะเพราะ 15 = 5x3 ดังนั้น 15 จึงมีทั้ง 1, 3, 5 และ 15 ที่หารมันได้ลงตัว

นักคณิตศาสตร์ได้ครุ่นคิดมานานแล้วว่า เลขเฉพาะในจักรวาลนี้มีกี่จำนวน และ Euclid ผู้เป็นบิดาของวิชาเรขาคณิต และเป็นนักคณิตศาสตร์ชาวกรีกผู้ยิ่งใหญ่ได้เคยพิสูจน์ให้ทุกคนประจักษ์เมื่อ 2,300 ปีก่อนว่า จักรวาลนี้มีเลขเฉพาะจำนวนมากนับจนมิถ้วน (infinite)

ความสนใจของนักคณิตศาสตร์ในเวลาต่อมาคือ การพยายามหาสูตรสำเร็จที่จะช่วยให้สามารถบอกได้ว่า เลขใดเป็นเลขเฉพาะบ้าง

Pierre Fermat นักคณิตศาสตร์ชาวฝรั่งเศส ผู้มีชื่อเสียงได้เคยเสนอสูตรการหาเลขเฉพาะว่า เลข 22n+1 คือเลขเฉพาะ ไม่ว่า n จะเป็นเลขจำนวนเต็มอะไรเช่น เมื่อ n=1 เราก็จะได้เลข 221+1= 22+1=5 ซึ่งเป็นเลขเฉพาะ (22 คือเลข 2 คูณตัวมันเอง 2 ครั้ง=2x2) และเวลา n=2 เราก็จะได้เลข 222+1= 24+1=17 ซึ่งก็เป็นเลขเฉพาะอีก ดังนั้น โดยการแทนค่า n=1, 2, 3, 4 เราก็จะได้เลข 5, 17, 257 และ 65,537 ซึ่งก็เป็นเลขเฉพาะหมด แต่พอ Leonard Euler นักคณิตศาสตร์ชาวสวิสแทนค่า n ด้วย 5 เขาได้พบว่า 225 +1 = 232+ 1= 4,294,967,297=641x6,700,417 ดังนั้น 225+1 จึงไม่เป็นเลขเฉพาะ เพราะทั้ง 641 และ 6,700,417 ต่างก็สามารถหารมันได้ลงตัว

สูตรการหาเลขเฉพาะสูตรอื่นๆ ได้แก่ n2-n + 41 จะให้ค่าเลขเฉพาะเมื่อ n มีค่าน้อยกว่า 41 และสูตร n2-79n + 1,601 ก็ให้เลขเฉพาะเช่นกัน เมื่อ n มีค่าน้อยกว่า 80

ณ วินาทีโลกยังไม่มีสูตรที่ใช้สำหรับหาเลขเฉพาะทุกตัวที่มีในจักรวาลเลย นักคณิตศาสตร์ปัจจุบันกำลังสนใจค้นหาเลขเฉพาะว่ามีเลข ใดบ้าง และก็ได้พบว่า เมื่อ n มีค่ามากเช่น n=7 เลข 225+1 จะมีค่า=2128+1 ซึ่งเป็นตัวเลขที่มี 39 หลัก ซึ่งเลขที่มีมากเช่นนี้ หากเราใช้ คอมพิวเตอร์ธรรมดา ที่สามารถคูณหารเลขได้พันล้านครั้งใน 1 วินาที คอมพิวเตอร์ก็จะต้องใช้เวลานานถึงหมื่นปี จึงจะทดสอบได้ว่ามันเป็นเลขเฉพาะหรือไม่ เมื่อความยาวนานในการพิสูจน์เป็นเช่นนี้ นักคณิตศาสตร์และนักคอมพิวเตอร์จึงต้อง พัฒนาโปรแกรมคอมพิวเตอร์ให้สามารถใช้ทดสอบดูว่า เลขแต่ละจำนวนเป็นเลขเฉพาะหรือไม่ โดยใช้เวลาน้อยที่สุดเท่าที่จะน้อยได้ เช่นเมื่อปี พ.ศ. 2526 G. Simmons และ Sandia National Laboratories ในสหรัฐอเมริกา ใช้เวลานาน 38.3 นาที ในการพิสูจน์ว่าเลข 2193-1 มิได้เป็นเลขเฉพาะเพราะ 2193-1=13821503 x 61654440233248340616559 x 1473265321145317331353282383 หรือเลข 2251-1=178230287214063289511 x 61676882198695257501367 x 120703961782498933039969681 ก็มิได้เป็นเลขเฉพาะเช่นกัน

ดังนั้น เราจะเห็นได้ว่ากระบวนการทดสอบว่าเลขจำนวนใด (ที่มีตัวเลขล้านล้านล้าน...หลัก) เป็นเลขเฉพาะ เป็นเรื่องที่ต้องใช้เวลาและ ความสามารถในการคิดรูปแบบของ algorithm มาพิสูจน์มาก

ในปี พ.ศ. 2539 P.Gage และ D. Slowinski แห่ง Cray Research ได้ใช้ซูเปอร์คอมพิวเตอร์ Cray พบว่าเลข 2859433-1 ซึ่งมี 258,716 หลักเป็นเลขเฉพาะ

H. Dubner ก็นักคณิตศาสตร์อีกท่านหนึ่งที่สนใจเรื่องเลขเฉพาะมาก เขาคือผู้ที่ได้พบเลขเฉพาะที่มีค่ามากที่สุด 2 ตัว ซึ่งแตกต่างกัน เท่ากับ 2 (3 กับ 5 เป็นเลขเฉพาะ 2 ตัว ที่แตกต่างกับ 2 หรือ 7,9 ก็เป็นเลขเฉพาะ 2 ตัว ที่แตกต่างกับ 2) ตัวเลข 2 ตัวที่ Dubner พบคือ 1,692,923,232x104,020+1 และ 1,692,923,232x104,020-1

การกระจัดกระจายของเลขเฉพาะก็เป็นปัญหาวิจัยทางคณิตศาสตร์ปัญหาหนึ่ง ที่นักคณิตศาสตร์สนใจ เมื่อประมาณ 200 ปีมาแล้ว Peter Gustav Lejeune Dirichlet ได้เคยพิสูจน์ว่า ในอนุกรมเลขคณิตทุกอนุกรม เราสามารถจะหาเลขเฉพาะได้จำนวนนับไม่ถ้วน (อนุกรมเลขคณิตได้แก่ 1, 3, 5, 7, 9... ซึ่งตัวเลขหลังได้จากการนำ 2 มาบวกเข้ากับเลขหน้าหรือ 4, 8, 13, 18...ก็เป็นอนุกรมเลขคณิตเพราะ 8=3+5, และ 13=8+5...)

ส่วน Christian Goldbach นักคณิตศาสตร์ชาวเยอรมันก็เป็นอีกผู้หนึ่งที่สนใจเรื่องคุณสมบัติของเลขเฉพาะ ในปี พ.ศ. 2284 เขาได้เขียนจดหมายถึง Leonard Euler ว่า เขาคิดว่า เลขคู่ทุกตัวสามารถแยกออกเป็นผลบวกของเลขเฉพาะได้หมด (เช่น

2=1+1 ซึ่ง 1 เป็นเลขเฉพาะหรือ 4=1+3 ซึ่งต่างก็เป็นเลขเฉพาะ และ 12=5+7 ซึ่งต่างก็เป็นเลขเฉพาะอีก) Goldbach ได้เรียนถาม Euler ว่า Euler สามารถพิสูจน์ทฤษฎีของเขาได้ไหมว่า ถูกหรือผิดอย่างไร และถ้าผิด Euler มีตัวอย่างแสดงให้ดูด้วยได้ไหม จนกระทั่งถึงวันนี้ปัญหา Goldbach ก็ยังไม่มีใครสามารถพิสูจน์ได้ว่าจริงหรือไม่จริง

ถึงแม้เลขเฉพาะจะมีคุณสมบัติต่างๆ ที่น่าสนใจเพียงใด แต่คุณสมบัติหนึ่งที่อยู่ในหัวใจของนักคณิตศาสตร์ตลอดเวลาคือ ใครจะเป็นผู้พบ เลขเฉพาะที่มีค่ามากสุด คนต่อไปและค่าต่อไป

ในเดือนกันยายน พ.ศ. 2538 H.Dubner และ H.L. Nelson แห่ง Lawrence Liversnore National Laboratory ได้พบเลขเฉพาะเรียงกัน 7 จำนวน ซึ่งแต่ละจำนวนมีค่ามากกว่าจำนวนที่นำหน้ามันเท่ากับ 210 โดยเลขจำนวนแรกที่มี 97 หลักคือ 1 ,089 ,533 ,431 ,247 ,059 ,310 ,875 ,780 ,378 ,922 ,957 ,732 ,908 ,036 ,492 ,993 ,138 ,195 ,385 ,213 ,105 ,561 ,742 ,150 ,447 ,308 ,967 ,213 ,141 ,717 ,486 ,151 และจำนวนต่อไป ได้จากการเอาเลข 97 หลักนี้บวกกับ 210 และจำนวนที่สามก็เท่ากับเลขจำนวนที่ 2 บวกกับ 210 ต่อไปเรื่อยๆ จนครบ 7 จำนวน

ณ วันนี้ งานการหาเลขเฉพาะที่เป็นอนุกรมเลขคณิตเรียงกัน 8, 9, 10, 11...จำนวนก็ยังคงดำเนินอยู่ และเป็นปัญหาที่ยากมาก เพราะเดิมจำนวนดังกล่าวจะต้องมีอย่างน้อย 1,000 หลักขึ้นไป และในเดือนธันวาคมปี พ.ศ. 2540 Gordon Spence กับนักคอมพิวเตอร์อื่นๆ อีก 1,700 คน ได้ระดมกำลังค้นหาเลขเฉพาะที่มีค่ามากที่สุด และก็ได้พบว่าเลข 2 2,976,221-1 เป็นเลขเฉพาะที่มี 895,932 หลัก โดยตัวเลขแปดแสนกว่าหลักนี้ หากถูกนำไปพิมพ์ลงหนังสือหมด หนังสือก็จะหนาประมาณ 450 หน้า และ Spence ก็ต้องใช้เวลาในการคำนวณนานถึง 15 วัน

เมื่อวันที่ 25 ธันวาคม พ.ศ.2544 เด็กหนุ่มวัย 20 ปี ชื่อ Michael Cameron ได้แถลงข่าวการพบเลขเฉพาะที่มีค่ามากที่สุด ซึ่งประกอบด้วยตัวเลขทั้งหมดกว่า 40 ล้านหลัก เลขจำนวนที่ว่านี้คือเลข 213,466,917-1 Cameron ยังได้กล่าวเสริมอีกว่า เขาใช้เวลานานประมาณ 3 สัปดาห์ในการหาเลขจำนวนนี้

หากคุณผู้อ่านต้องการจะค้นหาเลขเฉพาะด้วยตนเองบ้าง ก็ลองแก้โจทย์ต่อไปนี้

จงพิสูจน์ว่า ถ้า x และ x2+2 เป็นเลขเฉพาะ เลข x3+2 ก็เป็นเลขเฉพาะเช่นกัน

จงพิสูจน์ว่า กำลังสองของเลขเฉพาะทุกจำนวนที่มีค่ามากกว่า 3 หากถูกหารด้วย 12 แล้วจะเหลือเศษ 1 ทุกครั้งไป

เลขเฉพาะใดบ้างที่สามารถเขียนให้อยู่ในรูป ผลบวกกำลังสามของเลขจำนวนเต็มสองจำนวน

ถ้า n+1, n+3, n+7, n+9, n+13 และ n+15 เป็นเลขเฉพาะ n มีค่าเท่าไร

ถ้ารู้คำตอบ คุณก็เป็นนักคณิตศาสตร์ผู้ชำนาญเรื่องทฤษฎีเลขเฉพาะที่สามารถมากคนหนึ่งด้วย