Tìm ước Chung Lớn Nhất - Lập Trình Và Thực Thi Trên Máy Tính Một Số ...

2 Lập trình và thực thi trên máy tính một số thuật toán số

2.4 Tìm ước chung lớn nhất

2.4.1 Tính toán trên máy tính điện tử Vinacal 570ES Plus II Qui tắc tìm ước số chung lớn nhất (GCD) của hai hay nhiều số trình bày ở trên đã được lập trình tính trên Vinacal 570ES Plus II như sau.

Trước tiên bấm phím ON để mở máy. Vào các tính năng vượt trội của Vinacal 570ES Plus II bằng cách bấm phím: SHIFT 6 (VINACAL) 1: Q...r (tìm thương và số dư).

2: LCM (tìm bội số chung nhỏ nhất). 3: GCD (tìm ước số chung lớn nhất).

4: FACT (phân tích một số ra thừa số nguyên tố). 5: lim (tính giới hạn).

6: MinMax (tìm giá trị lớn nhất và nhỏ nhất của hàm bậc hai).

Để tìm ước số chung lớn nhất ta bấm phím 3 . Trên màn hình hiện GCD(. Khai báo các số, đánh dấu phẩy phân cách các số bằng cách bấm phím SHIFT , , bấm phím = để được kết quả trên màn hình.

Ví dụ 2.30 (Đề chọn đội tuyển thi học sinh giỏi giải toán trên máy tính cấp khu vực, Sở Giáo dục và Đào tạo Thái Nguyên, 2004)

Cho a=75125232, b=1754298000. Tìm ƯCLN của a và b. Cách giải 1 (trên Vinacal 570ES Plus II)

Mở máy bằng phím ON và vào tính năng vượt trội của Vinacal 570 ES Plus II bằng cách bấm phím SHIFT 6 . Bấm tiếp phím 3 vào chương trình tính ước số chung lớn nhất. Trên màn hình hiện GCD(. Khai báo các số đã cho (ngăn cách các số bởi phím và SHIFT , . Bấm phím = để được kết quả.

ON SHIFT 6 3 1754298000 SHIFT , 75125232 = (825552) Đáp số ƯCLN của 1754298000 và 75125232 là 825552.

Nhận xét 11 Sau khi bấm phím SHIFT 6 3 , chỉ bằng một thao tác khai báo các số, ta có ngay kết quả. Với các máy tính khác hoặc với chính Vinacal 570 ES Plus II (mà không dùng SHIFT 6 3 ), ta phải sáng tạo thủ công, không cần thiết như sau.

Cách giải 2Khai báo phân số a

b nhờ phím

và bấm phím = để được phân số tối giản 1754298000

75125232 = (2125

91 ).

Chia a = 1754298000 cho 2125 (hoặc chia b = 75125232 cho 91) để được ƯCLN của a và b : 1754298000 ÷ 2125 = (825552) hay 75125232 ÷

91 = (825552).

Đáp số: ƯCLN của a và b bằng 825552.

Giải thích Giả sử d là ước số chung lớn nhất (ƯCLN) của a và b. Khi ấy ta có a

b = da1

db1,trong đó a1

b1 phải là phân số tối giản. Thật vậy, nếu a1 b1 chưa

phải là phân số tối giản, tức là a1 b1 = ka2 kb2 (k > 1).Khi ấy a b = da1 db1 = dka2 dkb2

và dk > d cũng là ước của của a và b. Mâu thuẫn với d là ước số chung lớn nhất của a và b.

Như vậy, để tìm ƯCLN của hai số a và b, trước tiên ta tối giản phân số

a

b, được phân số a1

b1 (tự động thực hiện trên máy sau khi khai báo phân

số và bấm phím = ). Sau đó lấy a chia cho a1 (hoặc lấy b chia cho b1, được thương bằng d, chính là ƯCLN của hai số a và b.

Ví dụ 2.31 Cho a= 1908, b=2756, c=48760. Tìm ƯCLN(a, b, c)

Cách 1 Thực hiện qui trình bấm phím

ON SHIFT 6 3 1908 SHIFT , 2756 SHIFT , 48760 =

Đáp số: ƯCLN(a, b, c)=212. Cách 2 ƯCLN(a, b, c)= (ƯCLN(ƯCLN(a, b), c). Áp dụng cho ba số a= 1908, b=2756, c=48760 ta có a b = 1908 2756 = 9 13. Do đó ƯCLN(a, b) = a 9 = 1908 9 = 212. Ta có 212 48760 = 1 230. Do đó ƯCLN(212, c) = 48760 230 = 212. Vậy ƯCLN(a, b, c)=212.

2.4.2 Lập trình trên chương trình Pascal

Cách 1 Sử dụng thuật toán Euclide. ƯCLN của 2 số x, y cũng là ƯCLN của 2 số y và x mod y, vậy ta sẽ gán xbằng y, ybằng x mod y cho đến khi

y bằng 0. Khi đó ƯCLN là x. PROGRAM Tim ƯCLN cua hai so; VAR a,b,r : integer;

BEGIN

Write (’nhap so a= ’); read (a); Write (’nhap so b= ’); read (b);

Writeln( ’UCLN cua’, a , ’va’, b, ’la ’ ); WHILE b > 0 DO Begin r := a mod b; a := b; b := r; End; Write( a ); END.

Cách 2 Dưới đây là thuật toán tìm ƯCLN bằng cách trừ đi nhau. PROGRAM Chuong trinh tim ƯCLN;

USES crt;

VAR x,y,ƯCLN:integer; BEGIN

Clrscr;

writeln(’ban hay nhap vao 2 so bat ky:’); writeln(’So thu nhat:’); readln(x);

writeln(’So thu hai:’); readln(y); BCNN:=x*y;

WHILE x<>y DO if x>y then x:=x-y else y:=y-x; UCLN:=x;

writeln(’Ket qua la:’); writeln(’UCLN:’);

write(UCLN); Readln;

END.

Cách 3 Tìm ƯCLN bằng cách dùng đệ quy. Đệ quy được hiểu đơn giản là sự gọi nhiều lần chương trình con trong chương trình. Thực sự, đối với bài toán đơn giản, không ai sử dụng đệ quy vì sẽ làm phức tạp vấn đề và làm chương trình trở nên rắc rối, phải thực hiện nhiều phép tính hơn. Tuy nhiên, nếu bắt buộc phải dùng đệ quy có thể tham khảo cách làm dưới đây (xem SGK Tin học 10):

function gcd(a, b); begin

gcd:=gcd(b, a)

else if (b=0) then gcd:=a else gcd:=gcd(b, a mod b); end;

Ví dụ 2.32 Tìm ƯCLN của 1350 và 945.

Chạy chương trình trên Pascal ta thu được như sau Nhap so thu nhat: 1350

Nhap so thu hai: 945

ƯCLN cua 1350 va 945 la: 135. 2.2.3 Tính toán trên Maple

Muốn tìm ƯCLN của A và B ta dùng lệnh igcd(A,B).

Ví dụ 2.33 Tìm ước số chung lớn nhất của 2 số 2121988 và 15091987.

[> igcd(2121988,15091987);

1 Phân tích 2121988 ra thừa số nguyên tố:

[> ifactor(2121988);

(2)2(11) (29) (1663)

Phân tích 15091987 ra thừa số nguyên tố:

[> ifactor(15091987);

(4493)(3359)

Hai số 2121988 và 15091987 không có thừa số nguyên tố chung nào cho nên ƯCLN của chúng phải bằng 1.

Ví dụ 2.34 Tìm ước số chung lớn nhất của 2 số 21988 −1 và 22014−1.

[> igcd(2∧1988-1,2∧2014-1);

3

[> igcd(2∧1988-1,2∧1987-1);

1

Nhận xét 12 Hai ví dụ trên hay ở chỗ: các số 21988 − 1, 22014 − 1 và

21987−1 rất lớn (khoảng 600 chữ số), tuy nhiên với Maple ta vẫn dễ dàng tìm được ước chung lớn nhất của chúng.

Nhận xét 13 Muốn tìm ước chung lớn nhất của nhiều số ta có thể tìm của hai số trước.

Ví dụ 2.36 Tìm ước số chung lớn nhất của 3 số 2000, 1980 và 1910. Trước tiên ta tìm ƯCLN của 2000 và 1980 bằng 20, sau đó tìm ƯCLN của 20 và 1910

[> igcd(2000,1980);

20

[> igcd(1910,20);

10 Phân tích số 1980 ra thừa số nguyên tố:

[> ifactor(1980);

(2)2(3)2(5) (11)

Phân tích số 1910 ra thừa số nguyên tố:

[> ifactor(1910);

(2) (5) (191)

Phân tích số 2000 ra thừa số nguyên tố:

[> ifactor(2000);

(2)4(5)3

Phân tích số 10 ra thừa số nguyên tố:

[> ifactor(10);

Ta thấy rằng ước chung lớn nhất của ba số 1980, 1910, 2000 phải chứa trong phân tích của mình tất cả các thừa số nguyên tố chung của ba số trên với số mũ nhỏ nhất.

Nhận xét 14 Ta có thể tìm ƯCLN của nhiều số bằng lệnh igcd. Ví dụ 2.37 Tìm ước số chung lớn nhất của 3 số 2000, 1980 và 1910.

[> igcd(2000,1980,1910);

10

Nhận xét 15 Ta có thể xác định hai số nguyên m, n thỏa mãn hệ thức gcd(a,b)=an+bm theo thuật toán Euclid mở rộng bằng lệnh

[> igcdex(a,b,’n’,’m’);n;m;

Ví dụ 2.38 Cho a = 3041975 , b = 3042014. Hãy xác định các số nguyên

m, n sao cho an+bm = d, trong đó d là ƯCLN(a,b).

[> igcdex(2121988,1781990,’n’,’m’);n;m 2 -195606

232927

Vậy ta có 1781990.232927−2121988.195606 = 2.

Trong trường hợp a, b là hai số nguyên tố cùng nhau thì n cũng chính là nghịch đảo của a theo modulo b.

Ví dụ 2.39 Cho a = 3041975, b= 3042014.

[> igcdex(3041975,3042014,’n’,’m’);n;m; 1

1092005 -1091991

2.5 Tìm bội chung nhỏ nhất

2.5.1 Tính toán trên máy tính điện tử khoa học Vinacal 570ES Plus II

Qui tắc tìm bội số chung nhỏ nhất của hai hay ba số trình bày ở trên đã được lập trình tính trên Vinacal 570ES Plus II như sau.

Sau khi mở máy (bấm phím ON ), vào các tính năng vượt trội của Vinacal 570ES Plus II bằng cách bấm phím: SHIFT 6 (VINACAL)

1: Q...r (tìm thương và số dư).

2: LCM (tìm bội số chung nhỏ nhất). 3: GCD (tìm ước số chung lớn nhất).

4: FACT (phân tích một số ra thừa số nguyên tố). 5: lim (tính giới hạn).

6: MinMax (tìm giá trị lớn nhất và nhỏ nhất của hàm bậc hai).

Để tìm bội chung nhỏ nhất ta bấm phím 2 . Trên màn hình hiện:LCM( . Khai báo các số, đánh dấu phẩy phân cách các số bằng cách bấm phím

SHIFT , , bấm phím = để được kết quả trên màn hình. Ví dụ 2.40 Cho a= 1908, b=2756, c=48760. Tìm ƯCLN(a, b, c) Cách 1 ƯCLN(a, b, c)= (ƯCLN(ƯCLN(a, b), c). Áp dụng cho ba số a= 1908, b=2756, c=48760 ta có a b = 1908 2756 = 9 13. Do đó ƯCLN(a, b) = a 9 = 1908 9 = 212. Ta có 212 48760 = 1 230. Do đó ƯCLN(212, c) = 48760 230 = 212. Vậy ƯCLN(a, b, c)=212.

Gọi E là BCNN của a và b. Khi đó

Vì ƯCLN(a, b, c)=212 nên ƯCLN(E, c) = 212.

Vậy BCNN(a, b, c)= BCNN(E, c) = E ×c : ƯCLN(E, c) = 24804×48760 : 212 = 5704920.

Cách 2 Mở máy bằng phím ON , vào các tính năng vượt trội của Vinacal 570ES Plus II bằng cách bấm phím: SHIFT 6 . Bấm tiếp phím 2 . Trên màn hình hiện: LCM( .Khai báo các số, đánh dấu phẩy phân cách các số bằng cách bấm phím SHIFT , , bấm phím = để được kết quả. Toàn bộ qui trình bấm phím được viết lại như sau

ON SHIFT 6 2 1908 SHIFT , 2756 SHIFT , 48760

= (5704920)

Đáp số: BCNN(a, b, c)=5704920.

Tìm bội số chung nhỏ nhất vượt quá 10 chữ số của hai hay ba số trên Vinacal 570ES Plus II

Ví dụ 2.41 (Thi học sinh giỏi Giải toán trên máy tính. Sở Giáo dục Đào tạo Thừa Thiên-Huế, lớp 8, 9, 11, 2005)

Cho ba số A=1193984; B=157993; C=38743. Tìm ƯCLN của ba số A, B, C;

Tìm BCNN của ba số A, B, C với kết quả đúng. Cách giải 1 Tối giản phân số AB:

1193984

157993 = (2048 271 ).

Vậy ƯCLN của A và B (kí hiệu là D bằng):

1193984 ÷ 2048 = (583) hay 157993 ÷ 271 = (583). Tối giản phân số DC:

38743

583 = (731

11 ).

Suy ra ƯCLN(A, B, C) = ƯCLN(C, D) = 53. Gọi E là bội chung nhỏ nhất của A và B. Khi đó

E = BCNN(A, B) = A×B

ƯCLN(A, B) = 323569664.

Vì ƯCLN(A, B, C) = 53 nên ƯCLN(E, C) = 53. Vậy bội chung nhỏ nhất của A, B, C là:

BCNN(A, B, C)=BCNN(E, C)=E ×C : ƯCLN(E, C)

= (323569664×38743) : 53 = 2.365294244×1011.

Khi BCNN của các số vượt quá 10 chữ số thì máy cho đáp số dưới dạng lũy thừa. Ta phải tìm các số đuôi bằng cách bỏ các số đầu nhờ bấm phím tiếp như sau

- 2 × 10x 11 = (3.652942438×1011) - 3 × 10x 10 = (6529424384). Vậy BCNN(A, B, C)=236529424384.

Cách giải 2 (trên Vinacal 570 ES Plus)

Mở máy bằng phím ON , vào các tính năng vượt trội của Vinacal 570ES Plus II bằng cách bấm phím: SHIFT 6 . Bấm tiếp phím 2 . Trên màn hình hiện: LCM( .Khai báo các số, đánh dấu phẩy phân cách các số bằng cách bấm phím SHIFT , , bấm phím = để được kết quả.

Toàn bộ qui trình bấm phím được viết lại như sau

ON SHIFT 6 2 1193984 SHIFT , 157993 SHIFT , 38743 = (2.3652942438×1011)

Khi BCNN của các số vượt quá 10 chữ số thì máy cho đáp số chính xác dưới dạng một số thập phân nhân với lũy thừa của 10 mũ trong đó là số tự nhiên. Ta phải dùng thủ tục làm lộ các số đuôi bằng cách bỏ các số đầu

Ví dụ 2.42 Tìm BCNN của ba số 1193984, 157993, 38743

ON SHIFT 6 2 1193984 SHIFT , 157993 SHIFT , 38743 =

2.365294244×1011 - 2 × 10x 11 = (3.652942438×1011) - 3 ×

10x 10 = (6529424384).

Đáp số BCNN(A, B, C)=236529424384. 2.5.2 Lập trình trên chương trình Pascal

Cách 1 Dưới đây là thuật toán tìm ƯCLN bằng cách trừ đi nhau. PROGRAM Chuong trinh tim UCLN va BCNN;

USES crt;

VAR x,y,T,UCLN,BCNN:integer; BEGIN

Clrscr;

writeln(’ban hay nhap vao 2 so bat ky:’); writeln(’So thu nhat:’);

readln(x);

writeln(’So thu hai:’); readln(y);

T:=x*y;

WHILE x<>y DO if x>y then x:=x-y else y:=y-x; UCLN:=x;

BCNN:=T div UCLN;

writeln(’Ket qua la:’); writeln(’BCNN:’);

write(BCNN); readln;

write(UCLN); Readln;

END.

Cách 2 Sử dụng thuật toán Euclide.

program Chuong trinh tim UCLN va BCNN; uses crt;

var a,b,r,T,UCLN,BCNN:longint; begin

clrscr;

writeln(’ban hay nhap vao 2 so bat ky:’); writeln(’So thu nhat:’);

readln(a);

writeln(’So thu hai:’); readln(b); T:=a*b; while b>0 do begin r:=a mod b; a:=b; b:=r; end; UCLN:=a; BCNN:=T div UCLN;

writeln(’Ket qua la:’);

writeln(’BCNN:’);write(BCNN); readln;

writeln(’UCLN:’); write(UCLN); readln;

end.

Ví dụ 2.43 Tìm ƯCLN và BCNN của hai số 39345 và 360 Chạy chương trình trên Pascal ta có

Ban hay nhap vao 2 so bat ky So thu nhat:39345

So thu hai:360 Ket qua la: BCNN: 944280 ƯCLN: 15

2.5.3 Tính toán trên Maple

Bội số chung nhỏ nhất của hai số là số nhỏ nhất chia hết cho cả hai số ấy. Muốn tìm BCNN hai hay nhiều số ta dùng lệnh ilcm.

Ví dụ 2.44 Tìm bội số chung nhỏ nhất của 2 số 2121988 và 15091987.

[> ilcm(2121988,15091987);

32025015310156

Muốn kiểm tra kết quả, ta tính Tích của hai số 2121988 và 15091987

[> 2121988*15091987;

32025015310156

Phân tích 2121988 ra thừa số nguyên tố

[> ifactor(2121988);

Phân tích 15091987 ra thừa số nguyên tố

[> ifactor(15091987);

(4493)(3359)

Hai số 2121988 và 15091987 không có thừa số chung nên BSCNN chính là tích của chúng.

Nhận xét 16 Tất nhiên, ta có thể tìm BCNN của nhiều số.

Ví dụ 2.45 Tìm bội số chung nhỏ nhất của 4 số 1950, 1960, 1985, 1988.

[> ilcm(1950,1960,1985,1988);

10773071400

Phân tích số 1950 ra thừa số nguyên tố

[> ifactor(1950);

(2) (3) (5)2(13)

Phân tích số 1960 ra thừa số nguyên tố

[> ifactor(1960);

(2)3(5) (7)2

Phân tích số 1985 ra thừa số nguyên tố

[> ifactor(1985);

(5)(397)

Phân tích số 1988 ra thừa số nguyên tố

[> ifactor(1988);

(2)2(7) (71)

Phân tích số 1077301400 ra thừa số nguyên tố

[> ifactor(10773071400);

(2)3(3) (5)2(7)2(13) (71) (397)

Ta thấy rằng BSCNN của 1950, 1960, 1985, 1988 phải chứa trong phân tích của mình tất cả các thừa số nguyên tố của bốn số trên với số mũ cao nhất.

Một số ví dụ áp dụng

Bài 1 (Đề thi Giải toán trên máy tính, Trung học Cơ sở, Sở Giáo dục và Đào tạo Sóc Trăng, 2004-2005)

Tìm ƯCLN và BCNN của hai số

1) a=9148, b=16632; 2) a=75125232, b=175429800.

Bài 2 (Thi giải toán trên máy tính cấp huyện, Phòng Giáo dục và Đào tạo Phú Hòa, 2009-2010)

Tìm ƯCLN và BCNN của hai sốA= 2419580247; B= 38021975311234566. Bài 3 (Thi giải toán trên máy tính, Sở Giáo dục và Đào tạo TP Hồ Chí Minh, 2010-2011)

Cho 3 số A = 1193984 ; B = 157993 và C= 38743. Tìm ƯCLN và BCNN của 3 số A; B; C.

Bài 4 (Thi giải toán trên máy tính, Sở Giáo dục và Đào tạo Long An, 2012-2013)

Cho a = 9474372; b = 40096920; c= 51135438. 1)/Tìm ƯCLN(a, b, c).

2) Tìm BCNN(a, b).

Bài 5 (Đề thi Giải toán trên máy tính, Trung học Cơ sở, Sở Giáo dục và Đào tạo Ninh Bình, 2013-2014)

2.6 Tìm số nguyên tố đứng sau hoặc đứng trước một số tự nhiên

Trong nghiên cứu số nguyên tố, nhiều khi ta cần tìm một số nguyên tố trong một khoảng nào đó, hay ta muốn khẳng định một khoảng nào đó không chứa số nguyên tố. Khi ấy ta dùng lệnhnextprime(N)hoặc prevprime(N) để tìm số nguyên tố đứng ngay sau (hoặc trước) số N. Lệnh này cho phép tìm số nguyên tố khá nhanh so với lệnh ifactor(N) (phân tích N ra thừa số nguyên tố).

Ví dụ 2.46Phân tích 122333444455555666666777777788888888999999999 ra thừa số nguyên tố.

[> ifactor(122333444455555666666777777788888888999999999); (3)(12241913785205210313897506033112067347143)(3331)

Chỉ mất vài giây để phân tích số trên ra thừa số nguyên tố. Tuy nhiên phải mất thời gian khá lâu để phân tích số 122333444455555666666777777788888 8889999999991223334444555556666667777777888888889999999991223334 44455555666666777777788888888999999999 ra thừa số nguyên tố. Mặc dầu vậy, chỉ mất vài giây để tìm số nguyên tố đứng trước hoặc sau số trên. Ví dụ 2.47 Tìm số nguyên tố đứng ngay sau số

1223334444555556666667777777888888889999999991223334444555556666 66777777788888888999999999122333444455555666666777777711188888888 999999999 [> nextprime(122333444455555666666777777788888888999999999122 3334444555556666667777777888888889999999991223334444555556666 66777777788888888999999999); 1223334444555556666667777777888888889999999991223334444555556

6666677777778888888899999999912233344445555566666677777778888 88889000000471

Ví dụ 2.48 Tìm số nguyên tố đứng ngay sau 1223334444555556666667777 7778888888899999999912233344445555566666677777778888888899999999 9122333444455555666666777777711188888888999999999 [>prevprime(1223334444555556666667777777888888889999999991223 3344445555566666677777778888888899999999912233344445555566666 6777777788888888999999999); 1223334444555556666667777777888888889999999991223334444555556 6666677777778888888899999999912233344445555566666677777778888 8888999999317

Chỉ sau vài giây, ta được hai số nguyên tố khá lớn (40 chữ số)!

2.7 Một số ứng dụng trong lý thuyết mật mã

Các tính toán trong lý thuyết mật mã thường đòi hỏi lượng tính toán lớn và cũng khá phức tạp. Các thuật toán mật mã thực sự hữu hiệu chỉ có thể triển khai trên Mapple thông qua hàng loạt câu lệnh.

Ví dụ 2.49 Ta cần mã hóa thông báo sau VÊ NHA NGAY

Với p = 3137 và khóa lập mã e = 31, như vậy(e, p−1) = (31,3136) = 1.

Trong trường hợp này,m = 2 ta nhóm văn bản nhận được khi chuyển sang chữ số thành từng nhóm bốn chữ số

2708 1611 0116 1001 2928.

Theo ví dụ 1.16 đã trình bày ở chương 1 ta chuyển khối P trong văn bản thành các khối C trong văn bản mật theo công thức sau

C ≡ P31(mod3137),0≤ C < 3137.

Chẳng hạn, mã hóa khối đầu tiên ta tính:C ≡270831( mod 3137). Để tính được C một cách nhanh chóng ta dùng thuật toán bình phương liên tiếp. Trước tiên ta viết 31 dưới dạng cơ số 2. Tính toán đơn giản cho ta

27082 ≡ 2095,27084 ≡ 362,27088 ≡ 2427,270816 ≡ 2180(mod3137). Từ biểu diễn của 31 dưới dạng cơ số 2, ta được

270831 = (2708.2095.362.2427.2180) ≡ 2450(mod3137).

Với Maple ta thực hiện các công đoạn trên chỉ bằng một câu lệnh irem.