Số nguyên và thuật toán

S Ố N GU Y ÊN V À TH U Ậ T TOÁN

T h u ật toán E u c l i d e

Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên đó ra thừa số nguyên tố là không hiệu quả. Lý do là ở chỗ thời gian phải tiêu tốn cho sự phân tích đó. Dưới đây là phương pháp hiệu quả hơn để tìm ước số chung lớn nhất, gọi là thuậttoánEuclide. Thuật toán này đã biết từ thời cổ đại. Nó mang tên nhà toán học cổ Hy lạp Euclide, người đã mô tả thuật toán này trong cuốn sách “Nhữngyếu tố” nổi tiếng của ông. Thuật toán Euclide dựa vào 2 mệnh đề sau đây.

Mệnhđề1(Thuậttoánchia):Cho a và b là hai số nguyên và b≠0. Khi đó tồn tại

duy nhất hai số nguyên q và r sao cho a = bq+r, 0 ≤ r < |b|.

Trong đẳng thức trên, b được gọi là số chia, a được gọi là số bị chia, q được

gọi là thương số và r được gọi là số dư.

Khi b là nguyên dương, ta ký hiệu số dư r trong phép chia a cho b là a mod b.

Mệnhđề2:Cho a = bq + r, trong đó a, b, q, r là các số nguyên. Khi đó

UCLN(a,b) = UCLN(b,r).

(Ở đây UCLN(a,b) để chỉ ước chung lớn nhất của a và b.)

Giả sử a và b là hai số nguyên dương với a ≥ b. Đặt r0 = a và r1 = b. Bằng

cách áp dụng liên tiếp thuật toán chia, ta tìm được:

r0 = r1q1 + r2 0 ≤ r2 < r1

r1 = r2q2 + r3 0 ≤ r3 < r2

..................

rn-2 = rn-1qn-1 + rn 0 ≤ rn < rn-1

rn-1 = rnqn .

Cuối cùng, số dư 0 sẽ xuất hiện trong dãy các phép chia liên tiếp, vì dãy các số dư

a = r0 > r1 > r2 >... ≥ 0

không thể chứa quá a số hạng được. Hơn nữa, từ Mệnh đề 2 ở trên ta suy ra: UCLN(a,b) = UCLN(r0,r1) = UCLN(r1,r2) = ... = UCLN(rn-2, rn-1) = UCLN(rn-1,rn) = rn.

Do đó, ước chung lớn nhất là số dư khác không cuối cùng trong dãy các phép chia.

Thídụ6:Dùng thuật toán Euclide tìm UCLN(414, 662).

662 = 441.1 + 248

414 = 248.1 + 166

248 = 166.1+ 82

166 = 82.2 + 2

82 = 2.41.

Do đó, UCLN(414, 662) = 2.

Thuật toán Euclide được viết dưới dạng giả mã như sau:

procedureƯCLN (a,b: positive integers)

x := a y := b

whiley ≠ 0

b egin

e n d

r := x mody x := y

y := r

{UCLN (a,b) là x}

Trong thuật toán trên, các giá trị ban đầu của x và y tương ứng là a và b. Ở mỗi giai đoạn của thủ tục, x được thay bằng y và y được thay bằng x mod y. Quá trình này được lặp lại chừng nào y ≠ 0. Thuật toán sẽ ngừng khi y = 0 và giá trị của x ở điểm này, đó là số dư khác không cuối cùng trong thủ tục, cũng chính là ước chung lớn nhất của a và b.

B i ểu d i ễ n các s ố n gu y ê n

Mệnhđề3:Cho b là một số nguyên dương lớn hơn 1. Khi đó nếu n là một số nguyên dương, nó có thể được biểu diễn một cách duy nhất dưới dạng:

n = akbk + ak-1bk-1 + ... + a1b + a0.

Ở đây k là một số tự nhiên, a0, a1,..., ak là các số tự nhiên nhỏ hơn b và ak ≠ 0.

Biểu diễn của n được cho trong Mệnh đề 3 được gọi là khai triển của n theo cơ số b, ký hiệu là (akak-1... a1a0)b. Bây giờ ta sẽ mô tả thuật toán xây dựng khai triển cơ số b của số nguyên n bất kỳ. Trước hết ta chia n cho b để được thương và số dư, tức là

n = bq0 + a0, 0 ≤ a0 < b.

Số dư a0 chính là chữ số đứng bên phải cùng trong khai triển cơ số b của n. Tiếp

theo chia q0 cho b, ta được:

q0 = bq1 + a1, 0 ≤ a1 < b.

Số dư a1 chính là chữ số thứ hai tính từ bên phải trong khai triển cơ số b của n. Tiếp tục quá trình này, bằng cách liên tiếp chia các thương cho b ta sẽ được các chữ số tiếp theo trong khai triển cơ số b của n là các số dư tương ứng. Quá trình này sẽ kết thúc khi ta nhận được một thương bằng 0.

Thídụ7:Tìm khai triển cơ số 8 của (12345)10.

12345 = 8.1543 + 1

1543 = 8.192 + 7

192 = 8.24 + 0

24 = 8.3 + 0

3 = 8.0 + 3.

Do đó, (12345)10 = (30071)8.

Đoạn giả mã sau biểu diễn thuật toán tìm khai triển cơ số b của số nguyên n.

procedurekhaitriểntheocơsốb(n: positive integer)

q := n k := 0

whileq ≠ 0

b egin

ak := q modb

q

q := [ ]

b

e n d

k := k + 1

T h u ật toán c h o các p h é p tính s ố n g u y ên

Các thuật toán thực hiện các phép tính với những số nguyên khi dùng các khai triển nhị phân của chúng là cực kỳ quan trọng trong số học của máy tính. Ta sẽ mô tả ở đây các thuật toán cộng và nhân hai số nguyên trong biểu diễn nhị phân. Ta cũng sẽ phân tích độ phức tạp tính toán của các thuật toán này thông qua số các phép toán bit thực sự được dùng. Giả sử khai triển nhị phân của hai số nguyên dương a và b là:

a = (an-1an-2 ... a1 a0)2 và b = (bn-1 bn-2 ... b1 b0)2

sao cho a và b đều có n bit (đặt các bit 0 ở đầu mỗi khai triển đó, nếu cần).

Phépcộng:Xét bài toán cộng hai số nguyên viết ở dạng nhị phân. Thủ tục thực hiện phép cộng có thể dựa trên phương pháp thông thường là cộng cặp chữ số nhị phân với nhau (có nhớ) để tính tổng của hai số nguyên.

Để cộng a và b, trước hết cộng hai bit ở phải cùng của chúng, tức là:

a0 + b0 = c0.2 + s0.

Ở đây s0 là bit phải cùng trong khai triển nhị phân của a+b, c0 là số nhớ, nó có thể

bằng 0 hoặc 1. Sau đó ta cộng hai bit tiếp theo và số nhớ

a1 + b1 + c0 = c1.2 + s1.

Ở đây s1 là bit tiếp theo (tính từ bên phải) trong khai triển nhị phân của a+b và c1 là số nhớ. Tiếp tục quá trình này bằng cách cộng các bit tương ứng trong hai khai triển nhị phân và số nhớ để xác định bit tiếp sau tính từ bên phải trong khai triển nhị phân của tổng a+b. Ở giai đoạn cuối cùng, cộng an-1, bn-1 và cn-2 để nhận được cn-1.2+sn-1. Bit đứng đầu của tổng là sn=cn-1. Kết quả, thủ tục này tạo ra được khai triển nhị phân của tổng, cụ thể là a+b = (sn sn-1 sn-2 ... s1 s0)2.

Thídụ8:Tìm tổng của a = (11011)2 và b = (10110)2.

a0 + b0 = 1 + 0 = 0.2 + 1 (c0 = 0, s0 = 1), a1 + b1 + c0 = 1 + 1 + 0 = 1.2 + 0 (c1

= 1, s1 = 0), a2 + b2 +c1 = 0 + 1 + 1 = 1.2 + 0 (c2 = 1, s2 = 0), a3 + b3 + c2 = 1 + 0 + 1

= 1.2 + 0 (c3 = 1, s3 = 0), a4 + b4 +c3 = 1 + 1 + 1 = 1.2 + 1 (s5 = c4 =1, s4 = 1).

Do đó, a + b = (110001)2.

Thuật toán cộng có thể được mô tả bằng cách dùng đoạn giả mã như sau.

procedurecộng (a,b: positive integers)

c := 0

forj := 0 ton-1

b egin

aj  bj  c

d :=  

 2 

e n d

sn := c

sj := aj + bj + c － 2d c := d

{khai triển nhị phân của tổng là (sn sn-1 ...s1 s0) 2}

Tổng hai số nguyên được tính bằng cách cộng liên tiếp các cặp bit và khi cần

phải cộng cả số nhớ nữa. Cộng một cặp bit và số nhớ đòi ba hoặc ít hơn phép cộng

các bit. Như vậy, tổng số các phép cộng bit được sử dụng nhỏ hơn ba lần số bit

trong khai triển nhị phân. Do đó, độ phức tạp của thuật toán này là O(n).

Phépnhân:Xét bài toán nhân hai số nguyên viết ở dạng nhị phân. Thuật toán

thông thường tiến hành như sau. Dùng luật phân phối, ta có:

n－1

n－1

ab = a  bj2 j=  a(bj2 j) .

j=0

j=0

Ta có thể tính ab bằng cách dùng phương trình trên. Trước hết, ta thấy rằng abj=a nếu bj=1 và abj=0 nếu bj=0. Mỗi lần ta nhân một số hạng với 2 là ta dịch khai triển nhị phân của nó một chỗ về phía trái bằng cách thêm một số không vào cuối khai triển nhị phân của nó. Do đó, ta có thể nhận được (abj)2j bằng cách dịch khai triển nhị phân của abj đi j chỗ về phía trái, tức là thêm j số không vào cuối khai triển nhị phân của nó. Cuối cùng, ta sẽ nhận được tích ab bằng cách cộng n số nguyên abj.2j với j=0, 1, ..., n-1.

Thídụ9:Tìm tích của a = (110)2 và b = (101)2.

Ta có ab0.20 = (110)2.1.20 = (110)2, ab1.21 = (110)2.0.21 = (0000)2, ab2.22 = (110)2.1.22 = (11000)2. Để tìm tích, hãy cộng (110)2, (0000)2 và (11000)2. Từ đó ta có ab= (11110)2.

Thủ tục trên được mô tả bằng đoạn giả mã sau:

procedurenhân (a,b: positive integers)

forj := 0 ton-1

b egin

e n d

if bj = 1 thencj := a được dịch đi j chỗ

elsecj := 0

{c0, c1,..., cn-1 là các tích riêng phần}

p := 0

forj := 0 ton-1

p := p + cj

{p là giá trị của tích ab}

Thuật toán trên tính tích của hai số nguyên a và b bằng cách cộng các tích riêng phần c0, c1, c2, ..., cn-1. Khi bj=1, ta tính tích riêng phần cj bằng cách dịch khai triển nhị phân của a đi j bit. Khi bj=0 thì không cần có dịch chuyển nào vì cj=0. Do

đó, để tìm tất cả n số nguyên abj.2j với j=0, 1, ..., n-1, đòi hỏi tối đa là

0 + 1 + 2 + ... + n－1 =

n(n－ 1)

2

phép dịch chỗ. Vì vậy, số các dịch chuyển chỗ đòi hỏi là O(n2).

Để cộng các số nguyên abj từ j=0 đến n－1, đòi hỏi phải cộng một số nguyên n bit, một số nguyên n+1 bit, ... và một số nguyên 2n bit. Ta đã biết rằng mỗi phép cộng đó đòi hỏi O(n) phép cộng bit. Do đó, độ phức tạp của thuật toán này là O(n2).

S ố n g u y ê n t ố ( đ ọ c t h ê m )

Có thể nói rằng số nguyên tố là số được chú ý từ trước đến nay không những của cộng đồng toán học, mà còn của cộng đồng tin học, không bởi vì tính chất đặc biệt của nó mà còn vì những ứng dụng hết sức thực tế của số nguyên tố (ví dụ ứng dụng điển hình là trong mã hóa RSA http://en.wikipedia.org/wiki/RSA)

Định nghĩa: Sốnguyêntốlà số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chia hết

cho chính nó.

Ví dụ: 2, 3, 5, 7, 11..

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

Phát biểu định lý: "Mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích những thừa số nguyên tố, và sự phân tích này là duy nhất nếu không kể đến thứ tự của các thừa số."

Từ đó có dạng phân tích tiêu chuẩn của một số tự nhiên bất kỳ là:

Trong đó p1,p2,...,pm, là các số nguyên tố đôi một khác nhau. Ta có n chia hết cho

(k1+1)(k2+1)...(km+1) số tự nhiên. Ví dụ:

300 = 22.52.3

300 chia hết cho (2+1)(2+1)(1+1)=18 số tự nhiên.

Tí n h c h ất

Ký hiệu "b a" nghĩa là b là ước của a, ký hiệu a b nghĩa là a chia hết cho b.

1.Ước tự nhiên khác 1 nhỏ nhất của một số tự nhiên là số nguyên tố .

Chứng minh: Giả sử d a; d nhỏ nhất; d 1. Nếu d không nguyên tố d = d1.d2; d1, d2 > 1

d1|a với d1 < d: mâu thuẫn với d nhỏ nhất. Vậy d là nguyên tố.

2.Cho p là số nguyên tố; a N; a 0. Khi đó

(a,p) = p (ap) (a,p) = 1 (ap)

3.Nếu tích chia hết cho một số nguyên tố p thì có ít nhất một thừa số chia hết cho p.

p ai p

4.Ước số dương bé nhất khác 1 của một hợp số a là một số nguyên tố không vượt

quá

5.Tập hợp các số nguyên tố là vô hạn.

Tuy nhiên, vì tập hợp số nguyên tố là tập con của số tự nhiên, mà tập hợp số tự nhiên là đếm được nên tập hợp các số nguyên tố là đếm được.

Một thông tin khác về số nguyên tố:

Nhà khoa học Josh Findley đã dùng máy vi tính để tìm ra số nguyên tố lớn nhất từ trước tới nay với 7.235.733 chữ số - nếu được viết ra. Số này sẽ trải dài đến 25km và thời gian viết là 6 tuần!

S à n g Erato s t h e n e

Sàng Eratosthene là một giải thuật cổ xưa để lập bảng tất cả các số nguyên tố nhỏ hơn một số n cho trước. Giải thuật dựa trên tính chất: mọi hợp số n đều có ước nguyên tố không vượt quá căn của chính nó (sqrt(n)). Giải thuật đầu tiên xóa số 1 ra khỏi tập các số nguyên tố. Số tiếp theo số 1 là số 2, là số nguyên tố. Bắt đầu từ số 2 xoá tất cả các bội của 2 ra khỏi bảng. Số đầu tiên không bị xoá sau số 2 (số 3) là số nguyên tố. Tiếp theo lại xoá các bội của 3... Giải thuật tiếp tục cho đến khi găp số nguyên tố nhỏ hơn sqrt(n) thì dừng lại. Tất cả các số chưa bị xoá là số nguyên tố. Theo ngôn ngữ thuật toán ta có thể diễn đạt giải thuật sàng Eratosthene như sau: Eratosthene(n)

Var ListPrime[1..n]

Inti,j,k

for i:=1 to n Prime[i]:=True

Prime[1]:=false k=0

while k < sqrt(n) {

i=k+1

while Prime[i]=False i:=i+1 k=i

j=2

Prime[k]:= True

while k*j<=n { Prime[k*j]:= False j:=j+1

}

}

Câu chuyện về số nguyên tố:

Giả t h iết Gold b ach - E u ler

Năm 1742, nhà toán học Đức Goldbach viết thư cho Ơ-le biết rằng ông mạo hiểm đưa ra bài toán: Mọi số tự nhiên lớn hơn 5 đều biểu diễn được dưới dạng tổng của 3 số nguyên tố. Ơ-le trả lời rằng theo ông, mọi số chẵn lớn hơn 2 đều biểu diễn được dưới dạng tổng của 2 số nguyên tố. Nếu chứng minh được một trong hai mệnh đề thì sẽ chứng minh được mệnh đề còn lại. 200 năm sau, đến năm 1937, nhà toán học Liên Xô Vi-nô-gra-đốp đã giải quyết gần trọn vẹn bài toán đó bằng cách chứng minh rằng mọi số lẻ đủ lớn đều có thể biểu diễn được dưới dạng tổng của 3 số nguyên tố.

Cho đến nay, bài toán Goldbach-Euler vẫn chưa giải được hoàn toàn. Nếu mệnh đề của Ơ-le là đúng, hãy chứng minh mệnh đề Gôn-bách. Giải: Cho số tự nhiên n>5, ta sẽ chứng minh rằng n viết được dưới dạng tổng của 3 số nguyên tố. Xét:

1. Trường hợp 1: Nếu n chẵn thì n=2+m với m chẵn, m>3.

2. Trường hợp 2: nếu n lẻ thì n=3+m với m chẵn, m>2. Theo mệnh đề Ơ-le, m chẵn, m>2 nên m viết được dưới dạng tổng hai số nguyên tố. Do đó n viết được dưới dạng tổng của 3 số nguyên tố.

S ố n g u y ên t ố l ớ n n h ất v ớ i h ơ n 9 tr i ệu c h ữ số ( đ â y l à b ài v i ết n ăm 2005)

Một nhóm các nhà khoa học thuộc Đại học Missouri, Mỹ, đã sử dụng hơn 700 máy tính để tìm ra số nguyên tố lớn nhất cho đến nay, một con số khổng lồ với

9.152.052 con số.

Phát hiện này được thực hiện vào ngày 15/12 và đã được xác nhận lại vào ngày

24/12 vừa qua, đánh dấu lần thứ hai trong năm nay dự án kết hợp máy tính có tên TìmkiếmsốnguyêntốMersennetrênInternet(GIMPS - Great Internet Mersenne Prime Search) tìm ra một số nguyên tố lớn nhất. Nhưng cũng tương tự như phát hiện hồi tháng 2, con số mới được tìm ra này vẫn chưa đạt được kích thước 10 triệu con số cần thiết để giành được giải thưởng 100.000 USD từ Quỹ điện tử có tên là Electronic Frontier Foundation.

Dự án GIMPS khai thác sức mạnh của hơn 200.000 máy tính được cung cấp một cách tình nguyện với nhiệm vụ tìm kiếm tất cả các số nguyên tố Mersene. Một số nguyên tố là một số chỉ có thể chia hết cho 1 và chính nó, và một số nguyên tố Mersenne (Đây là số nguyên tố Mersenne thứ 43, được đặt tên theo Marin Mersenne, một tu sĩ người Pháp sống vào thế kỷ thứ 17, người đã nghiên cứu số

nguyên tố hiếm cách đây 300 năm). là một dạng đặc biệt có công thức 2p-1 trong

đó p cũng là một số nguyên tố. Thí dụ, 7 cũng là một số nguyên tố Mersenne bởi nó

là một số nguyên tố và bằng 23-1.

Đã vài năm nay, những số nguyên tố lớn lớn nhất được phát hiện đều là các số nguyên tố Mersenne. Chúng được đặt tên theo tên của Marin Mersenne, một tu sĩ người Pháp sinh năm 1588, người đã khám phá ra dạng số này.

Các số nguyên tố Mersenne trong nhiều trường hợp đã được các cá nhân tìm ra, nhưng lần này thì thành quả lại là của một nhóm tình nguyện viên. Nhóm này tới nay đã cống hiến một năng lực xử lý nhiều hơn bất cứ ai: tương đương với khả năng xử lý của của một máy tính Pentium 90MHz chạy liên tục trong 67.000 năm. Hai giáo sư Curtis Cooper và Steven Boone là những người phụ trách dự án này.

Con số nguyên tố được phát hiện lần này là số nguyên tố Mersenne thứ 43 được tìm ra, bằng 230.402.457-1. Những ai muốn thấy con số thực này có thể tải nó về tại http://www.mersenneforum.org/txt/43.txt.

(Theo NhânDân,Cnet)

Tại thời điểm bài này (18/10/2008), số nguyên tố thứ 45 đã được tìm thấy với

11185272 chữ số 237,156,667-1 và chữ số 46 là số 243,112,609-1 với 12978189 chữ số

(nếu số này khai triển ra và đánh máy không để khoảng cách sẽ có chiều dài xấp xỉ

3 km).

D i s cove r y d ate Pr i m e D igits Na m e

6 September 2008 M37156667 11185272 M45 ?

23 August 2008 M43112609 12978189 M46 ?

4 September 2006 M32582657 9808358 M44 ?

15 December 2005 M30402457 9152052 M43 ?

18 February 2005 M25964951 7816230 M42 ?

15 May 2004 M24036583 7235733 M41 ?

17 November 2003 M20996011 6320430 M40 ?

14 November 2001 M13466917 4053946 M39

1 June 1999 M6972593 2098960 M38

27 January 1998 M3021377 909526 M37

24 August 1997 M2976221 895932 M36

13 November 1996 M1398269 420921 M35

Để thấy rõ hơn chúng ta có thể xem tại: http://en.wikipedia.org/wiki/GIMPS