Máy tính phân tích thừa số nguyên tố

Máy tính phân tích thừa số nguyên tố - Phân rã số

🔢 Phân tích bất kỳ số nào thành các thừa số nguyên tố. Xem kết quả dưới dạng tích, dạng lũy thừa, trực quan hóa cây thừa số và quá trình chia từng bước.

Phân tích thừa số nguyên tố là gì?

Phân tích thừa số nguyên tố (hay phân tích số nguyên) là quá trình tách một hợp số thành tích của các số nguyên tố. Mỗi hợp số có một phân tích thừa số nguyên tố duy nhất.

Định lý cơ bản của số học

Mọi số nguyên lớn hơn 1 đều có thể được biểu diễn duy nhất dưới dạng tích của các số nguyên tố, bỏ qua thứ tự của các thừa số. Đây là một trong những định lý quan trọng nhất của lý thuyết số.

Các dạng biểu diễn

Dạng tích: 2 × 2 × 3 × 5

Dạng lũy thừa: 2² × 3 × 5

Dạng chỉ số: 2² · 3¹ · 5¹

Ví dụ

Ví dụ 1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• Thừa số nguyên tố: 2, 3

Ví dụ 2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• Thừa số nguyên tố: 2, 3, 5

Ví dụ 3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• Thừa số nguyên tố: 2, 5

Phương pháp phân tích

1. Thử chia:

• Chia cho các số nguyên tố nhỏ nhất (2, 3, 5, 7...)
• Tiếp tục cho đến khi thương bằng 1
• Đơn giản nhưng có thể chậm với số lớn

2. Cây thừa số:

• Tách số thành hai thừa số bất kỳ
• Tiếp tục tách cho đến khi tất cả đều là số nguyên tố
• Trực quan và dễ hiểu

3. Chia theo số nguyên tố:

• Chỉ chia cho các số nguyên tố
• Hiệu quả hơn so với thử mọi số
• Thuật toán tiêu chuẩn cho máy tính

Từng bước: phân tích 60

60 ÷ 2 = 30   (2 là số nguyên tố)
30 ÷ 2 = 15   (2 là số nguyên tố)
15 ÷ 3 = 5    (3 là số nguyên tố)
5 ÷ 5 = 1     (5 là số nguyên tố)

Kết quả: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

Tìm tất cả ước số

Khi đã có phân tích thừa số nguyên tố, bạn có thể tìm tất cả các ước:

Ví dụ: 60 = 2² × 3¹ × 5¹

• Với mỗi số nguyên tố, chọn số mũ từ 0 đến tối đa
• 2⁰ hoặc 2¹ hoặc 2² → (1, 2, 4)
• 3⁰ hoặc 3¹ → (1, 3)
• 5⁰ hoặc 5¹ → (1, 5)
• Kết hợp tất cả khả năng
• Ước số: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Công thức số lượng ước

Nếu n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Số lượng ước = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

Ví dụ: 60 = 2² × 3¹ × 5¹

• Số lượng ước = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12 ước

Công thức tổng các ước

Tổng = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

Ví dụ: 60 = 2² × 3 × 5

• Tổng = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

Ứng dụng của phân tích thừa số nguyên tố

• Mật mã học: mã hóa RSA dựa trên độ khó phân tích số lớn
• ƯCLN/BCNN: tìm ước chung lớn nhất và bội chung nhỏ nhất
• Rút gọn phân số: đưa về dạng tối giản
• Lý thuyết số: nghiên cứu tính chất số nguyên
• Khoa học máy tính: hàm băm, thuật toán

Các loại số đặc biệt

Số hoàn hảo:

• Bằng tổng các ước số thực sự
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

Số dư thừa (Abundant):

• Tổng các ước số thực sự > số
• 12: tổng ước = 1+2+3+4+6 = 16 > 12

Số thiếu (Deficient):

• Tổng các ước số thực sự < số
• 8: tổng ước = 1+2+4 = 7 < 8

Lũy thừa của 2

Các số là lũy thừa của 2 có dạng phân tích đơn giản:

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

Số có nhiều ước (Highly Composite)

Các số có nhiều ước hơn bất kỳ số nguyên dương nhỏ hơn:

• 1 (1 ước)
• 2 (2 ước)
• 4 (3 ước)
• 6 (4 ước)
• 12 (6 ước)
• 24 (8 ước)
• 36 (9 ước)
• 60 (12 ước)

Độ khó của phân tích

• Số nhỏ: dễ phân tích bằng tay
• Số nguyên tố lớn: rất khó phân tích
• Semiprime: tích của hai số nguyên tố, nền tảng của RSA
• 200+ chữ số: hiện rất khó với máy tính cổ điển
• Máy tính lượng tử: thuật toán Shor có thể phân tích hiệu quả

Các phân tích phổ biến

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 Mẹo nhanh: Để kiểm tra nhanh tính chia hết cho các số nguyên tố nhỏ: chia hết cho 2 nếu chữ số cuối chẵn; cho 3 nếu tổng chữ số chia hết cho 3; cho 5 nếu chữ số cuối là 0 hoặc 5; cho 9 nếu tổng chữ số chia hết cho 9; cho 11 nếu tổng xen kẽ chia hết cho 11. Ví dụ, 4356: tổng = 4+3+5+6 = 18 (chia hết cho 9), nên 4356 chia hết cho 9! Hãy bắt đầu với các kiểm tra nhanh này trước khi thử các số nguyên tố lớn hơn.