ตัวประกอบเฉพาะ

ตัวประกอบเฉพาะ ในทฤษฎีจำนวน หมายถึงจำนวนเฉพาะใดๆ ที่สามารถหารจำนวนเต็มหนึ่งได้ลงตัวโดยเหลือเศษเป็นศูนย์ กระบวนการของการหาตัวประกอบเฉพาะเรียกว่า การแยกตัวประกอบจำนวนเต็ม หรือการแยกตัวประกอบเป็นจำนวนเฉพาะ

สำหรับตัวประกอบเฉพาะ p ของจำนวน n ภาวะรากซ้ำ (multiplicity) ของ p คือเลขชี้กำลัง a ที่มากที่สุดจาก p^a ที่หาร n ลงตัว การแยกตัวประกอบที่เป็นจำนวนเฉพาะของจำนวนเต็มหนึ่งๆ จะได้ผลลัพธ์เป็นรายการตัวประกอบเฉพาะของจำนวนนั้น ซึ่งจะมีบางจำนวนที่ซ้ำกัน (เกิดภาวะรากซ้ำ) ทฤษฎีบทมูลฐานของเลขคณิตกล่าวว่า จำนวนเต็มทุกจำนวนมีรูปแบบการแยกตัวประกอบที่เป็นจำนวนเฉพาะได้เพียงแบบเดียว

จำนวนเต็มบวกสองจำนวนจะเรียกว่าเป็นจำนวนเฉพาะสัมพัทธ์ (coprime) ซึ่งกันและกัน ก็ต่อเมื่อไม่มีตัวประกอบเฉพาะอื่นใดนอกจากสองจำนวนนี้ แต่จำนวนเต็ม 1 จะเป็นจำนวนเฉพาะสัมพัทธ์ของทุกๆ จำนวนเต็มบวกรวมทั้งตัวมันเอง เนื่องจาก 1 ไม่มีตัวประกอบเฉพาะใดอยู่เลย ซึ่งมันคือผลคูณว่าง (empty product) ด้วยเหตุผลนี้ทำให้สามารถนิยาม a และ b ว่าเป็นจำนวนเฉพาะสัมพัทธ์ต่อกันเมื่อ gcd(a, b) = 1 (gcd คือตัวหารร่วมมาก) ดังนั้น gcd(1, b) = 1 สำหรับ b ≥ 1 ขั้นตอนวิธีของยุคลิด (Euclid's algorithm) สามารถใช้เพื่อพิจารณาว่าจำนวนเต็มสองจำนวนเป็นจำนวนเฉพาะสัมพัทธ์หรือไม่ โดยไม่ต้องมีความรู้ในเรื่องตัวประกอบเฉพาะ เพราะขั้นตอนวิธีดังกล่าวใช้พหุนามในรูปแบบตัวเลขช่วยคำนวณ

สำหรับจำนวนเต็มบวก n จำนวนตัวประกอบเฉพาะทั้งหมดของ n และผลรวมของตัวประกอบเฉพาะทั้งหมดของ n (โดยไม่นับตัวซ้ำ) คือตัวอย่างหนึ่งของฟังก์ชันเชิงคำนวณของ n ที่สามารถบวก (additive) กันได้ แต่เป็นการบวกที่ไม่บริบูรณ์

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

ตัวอย่าง

ตัวประกอบเฉพาะของ 6 คือ 2 กับ 3 (6 = 2 × 3) ทั้งคู่มีภาวะรากซ้ำเท่ากับ 1
5 มีตัวประกอบเฉพาะเพียงตัวเดียวก็คือตัวมันเอง (5 เป็นจำนวนเฉพาะ) มีภาวะรากซ้ำเท่ากับ 1
100 มีตัวประกอบเฉพาะสองตัวคือ 2 กับ 5 (100 = 2² × 5²) ทั้งคู่มีภาวะรากซ้ำเท่ากับ 2
2, 4, 8, 16, ... ล้วนมีตัวประกอบเฉพาะคือ 2 เท่านั้น (2 เป็นจำนวนเฉพาะ และ 4 = 2², 8 = 2³, ...)
1 ไม่มีตัวประกอบเฉพาะ (1 คือหน่วย)

ดูเพิ่ม

แหล่งข้อมูลอื่น