Bài tập về Ước chung lớn nhất & thuật toán Euclid môn Đại số & Số học | Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Trường hè Vinh online 2023 – Bài giảng Đại số & Số học
ƯỚC CHUNG LỚN NHẤT & THUẬT TOÁN EUCLID
Ước chung lớn nhất của a & b: là ước chung của a, b và nó sẽ lớn nhất  phân tích các số ra
thừa số nguyên tố rồi chọn ước SNT chung rồi chọn số mũ nhỏ nhất.
Ngoài ra, ta có thể tìm gcd(a,b) bằng thuật toán Euclid:
gcd(a,b) = gcd(a-b, b) = . . = gcd(d, d).
//các số phát sinh trong quá trình thực hiện sẽ là tổ hợp tuyến tính của a, b.
VD: (28, 40)  (28, 12)  (16, 12)  (4, 12)  (4, 8)  (4, 4).
VD: (10^9, 1)  (10^9 – 1, 1)  (10^9 – 2, 1)  ...
Cải tiến của thuật toán Euclid: với a > b  gcd(a, b) = gcd(a mod b, b) = .. = gcd(d, 0).
Tính chất: với a, b nguyên dương cho trước, luôn tồn tại cặp số nguyên x, y mà d = gcd(a,b) = x.a + y.b.
Ước chung lớn nhất thì chia hết cho các ước chung khác. Một cách tương tự, ta định nghĩa
bội chung nhỏ nhất, lcm. Bài 1.
a) Cho a,b là các số nguyên dương, chứng minh rằng
gcd(a, b)  lcm(a, b)  ab và gcd(a, b)  lcm(a, b)  a  . b
a = p1^(x1).p2^(x2)...pn^(xn),
b = p1^(y1).p2^(y2)...pn^(yn).
Khi đó: gcd(a,b) = tích pi^min{xi, yi} và lcm(a,b) = tích pi^max{xi, yi}. Do đó:
gcd(a, b).lcm(a,b) = tích max{x ,y }min{x ,y }  i i i i p = tích ix iy p = a.b. i i
Cách khác: em nghĩ gọi gcd là d sau đó đặt a=d.k, b=d.q thì nhanh hơn.
Theo cách đặt  gcd(k,q) = 1 nên lcm(a,b) = d.k.q  tích gcd.lcm = d.d.k.q = a.b.
Tiếp tục, thay vào BĐT  d + d.k.q >= d.k + d.q  1 + kq >= k+q  (k-1)(q-1) >= 0. Dấu =
xảy ra khi k=1 hoặc q=1, hay số này là ước của số kia.
b) Tìm tất cả các cặp số (a,b) nguyên dương để 2
gcd(a, b)  lcm(a, b)  a  b  2023  7 17 .
Ta có: gcd(a,b) | 7.17^2, hoặc ta viết
VT = d + d.kq + d.k + d.q = d(k+1)(q+1) = 7.17^2.
Hai số k, q không thể cùng chẵn vì gcd(k,q)=1 nên (k+1)(q+1) chẵn  không thỏa mãn. Như
thế thì cần có số ở VP chẵn (với số ban đầu 20162017 cũng không được).
c) Tìm giá trị lớn nhất của gcd(a, ,
b c) và lcm(a,b, c) với các số nguyên a, b, c đôi một phân
biệt lấy từ tập hợp {1, 2, , }
n trong hai trường hợp n  2022 và n  2023.
Do gcd(a,b,c)<=min{a,b,c} nên ta sẽ chọn bộ ba số a,b,c phân biệt mà a lớn nhất mà b,c chia
hết cho a  gcd max=674. VD: a=674, b=674.2, c=674.3.
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học
Đặt d = gcd(a,b,c) và a=dx, b=dy, c=dz thì x, y, z phải phân biệt nên nếu xếp x < y < z  z >=
3 nên n >= c = dz >= 3d  d <= n/3. Do đó max d = [n/3].
Đáp số cho n=2023 và 2023 đều là 674.
Tiếp theo, tìm max của lcm:
 n=2023 thì là 2023.2022.2021 do lcm(a,b,c) <= abc <= 2023.2022.2021.
 n=2022 thì kq = 2019.2020.2021.
Để ý nếu n = 6m  gcd(6m, 6m-2), gcd(6m, 6m-4), gcd(6m, 6m-3) đều > 1. Nếu chọn
6m thì phải bỏ đi 6m-2, 6m-3, 6m-4 nên tích 3 số tối đa <= 6m(6m-1)(6m-5).
Thay vào đó, ta lấy (6m-1)(6m-2)(6m-3) là max có thể có.
Nếu làm tổng quát với mọi n  n lẻ (dễ), n = 6m, n = 6m+2, n = 6m+4 làm tương tự. Bài 2.
a) Chứng minh rằng với a  
, a  1 và m, n   thì m n gcd(m,n)
gcd(a 1, a 1)  a 1 .
Trước hết, ta có x^m – 1 chia hết cho x^d – 1 nếu d|m (do hằng đẳng thưc).
Đặt d = gcd(m,n)  d|m và d|n nên a^d – 1 | a^m-1, a^n-1 nên a^d-1 | gcd(a^m-1, a^n-1).
Theo thuật toán Euclid  tồn tại x, y nguyên để d = xm+yn nên rõ ràng 1 trong 2 số x, y
phải âm (nếu x, y cùng dương thì d = xm+yn > m, vô lý). Giả sử x <= 0 <= y. Khi đó: a^d – 1 = a^(xm+yn) – 1.
Ta có a^(yn) – 1 chia hết cho a^n-1 và a^(-xm) – 1 chia hết cho a^m-1.
Do đó xét t = gcd(a^n-1, a^m-1) là ước chung của a^(yn) – 1 và a^(-xm) – 1  t là ước của
hiệu 2 số, nên t | a^(yn) – a^(-xm) = a^(-xm)[a^(xm+yn) – 1], và t và a nguyên tố cùng nhau
 t | a^(xm+yn) – 1 = a^d – 1.
Vì thế VT|VP và VP|VT  VT = VP.
Chú ý: Nếu m, n cùng lẻ, c/m tương tự có: gcd(a^m+1, a^n+1) = a^gcd(m,n) + 1.
Tổng quát: với a, b nguyên dương và nguyên tố cùng nhau, a > b: gcd( m m  , n n a b
a  b ) = gcd(m,n) gcd(m,n) a  b . 2027 Từ đó tính n 2027
gcd(2023 1,2023 1) //chú ý: 2027 là SNT. n 1 
= tổng 2023^gcd(n,2027) – 1 = 2026.(2023^1 – 1) + 2023^2027 – 1.
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học
b) Tìm tất cả các cặp (a,b) nguyên dương sao cho b b3
gcd((a 1)  a, (a 1)  a) 1.
Giả sử a,b thỏa đề. Đặt: d=gcd((a+1)^b-a, (a+1)^(b+3)-a)>1.
Gọi: p là ước nguyên tố của d.
=>p | (a+1)^(b+3) - (a+1)^b = (a+1)^b . ((a+1)^3 – 1). Mà gcd(p,a+1)=1 nên:
p | (a+1)^3 -1. (1)  (a+1)^3 đồng dư 1 (mod p)  p | a^3+3a^2+3a
Mà tồn tại b để (a+1)^b đồng dư a (mod p) nên viết b=3x+r với r=0,1,2 khi đó:
 ( 1)b  ( 1)r a a a mod p.
 Hoặc: (a+1)^0 đồng dư a (mod p)  1 đồng dư a mod p nên thay vào trên có 2^3
đồng 1 mod p => p = 7 => a=7k-6, b=3l (k, l nguyên dương).
Hoặc: a+1 đồng dư a (mod p) (vô lí)
Hoặc: (a+1)^2 đồng dư a (mod p) => p | a^2+a+1. Mà từ (1) nên: p | a^2 + 3a +3
 p | 2(a+1) => p=2, mà: a^2+a+1 lẻ => vô lí.
Tóm lại: b = 3l và a = 7k – 6 thỏa mãn.
Bài 3. a) Chứng minh rằng nếu a,b nguyên dương phân biệt thì a  b gcd(a,b)  . 3
đặt gcd(a, b)=d  a=dk và b=dq --> (a+b)/3=d(k+q)/3
do a, b phân biệt k, q cũng phân biệt nên k+q >=3 --> đpcm.
b) Chứng minh rằng nếu a, , b c   thì
gcd(a, b 1)  gcd( , b c 1)  gcd( ,
c a 1)  ab  bc  c . a
Ta có: VT | a.b.c và VT | (a-1)(b-1)(c-1) nên
VT | abc – (a-1)(b-1)(c-1) = ab+bc+ca – (a+b+c) + 1 < ab+bc+ca.
* Định lý 4 số: cho 4 số a, b, c, d mà ab = cd, cần c/m tồn tại x, y, z, t nguyên dương để có:
a=xy, b = zt, c = xz và d = yt.
Đặt k = gcd(a,c)  a = k.a1 và c = k.c1 với gcd(a1, c1) = 1, thay vào đề:
k.a1.b = k.c1.d  a1.b = c1.d.
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học
Do gcd(a1, c1) = 1 nên a1 | d  đặt d = h.a1 thì b = h.c1, từ đó có 4 số h, k, a1, c1 dùng để
chọn giá trị cho x, y, z, t.
Từ đó, ta có thể c/m: a+b+c+d là hợp số. Bài 4.
a) Với các số nguyên dương m, n mà 2  m  n  2022, xét f (m, n) là số cặp số (a,b) nguyên
dương mà m  gcd(a,b) và n  lcm(a,b) . Tìm giá trị lớn nhất của f (m, n).
Ta có m,a,b,n có tối đa là 4 ước nguyên tố vì 2.3.5.7.11>2022.
Mặt khác ta chứng minh được f(m,n)=f(1,n/m) nên ta chỉ cần đếm f(1,n). Vì n có nhiều nhất
4 ước nguyên tố nên f(1,n) max = 2^4=16 hay f(m,n) max=16.
gcd(a,b) = m  đặt a = m.a1 và b = m.b1  gcd(a1, b1) = 1 và lcm(a1,b1) = a1.b1 = lcm(a,b)
/ m = n/m. Có song ánh từ (a,b)  (a1, b1) nên f(m,n) = f(1, n/m).
Số n/m có <= 4 ước nguyên tố p, q, r, s; rõ ràng mỗi SNT này sẽ xuất hiện ở đúng 1 trong 2
số a1 và b1  số cặp = 2^k với k = số ước nguyên tố, mà k <= 4  số cặp <= 2^4 = 6.
Chọn m = 1, n = 2.3.5.7 = 210 là được.
b) Đếm số cặp số nguyên dương m, n thỏa mãn 3 2 2 3
gcd(m , n )  36, lcm(m , n )  16 81 25 . (HS tự giải) Bài 5.
a) Chứng minh rằng với n, a,b nguyên và a  b thì n n  a b  n 1 gcd 
, a  b   gcd(n gcd(a,b)  , a  b).  a  b 
//đặc biệt: nếu gcd(a,b) = 1 thì VP = gcd(n, a-b).
Ta có: (a^n-b^n) / (a-b) = n 1 n2 n 1 a a b b    
, chú ý a  b(mod d) với d = a-b. Thay VP = 1 . n n b  mod d.
Theo thuật toán Euclid dạng phép chia lấy dư, ta có
VT = gcd((a^n-b^n) / (a-b), d) = gcd(n.b^(n-1), d) = gcd(n.a^(n-1), d)
= gcd(gcd(n.b^(n-1), n.a^(n-1)), d)
= gcd(n.gcd(a,b)^(n-1), d) = VP.
C/m tương tự nếu n lẻ  có thể thay dấu – bởi +.
Từ đó giải bài toán sau: chứng minh rằng không tồn tại x, y  mà 5 2 x  y  4.
//viết lại đề: x^5 + 32 = y^2 + 36.
Bổ đề: p = 4k+3 là SNT thì p|a^2+b^2  p | a, b.
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học
Nếu x, y cùng chẵn  x=2x’, y=2y’  32x’^5 = 4y’^2 + 4  8|y’^2 + 1, dễ thấy vô lý. Do đó x, y cùng lẻ. 5 5  Xét d = x 2 gcd(x  2,
) = gcd(5, x+2) | 5  d = 1 hoặc 5. x  2
nếu x lẻ thì một trong 2 số x+2 hoặc x^4-2x^3+4x^2-8x+16 sẽ đồng dư với 3 mod 4 nên
tồn tại ước nguyên tố dạng 4k+3 do đó vô lý, cụ thể:
 Nếu x=1 mod 4  x+2 = 3 mod 4.
 Nếu x=-1 mod 4  x^4-2x^3+4x^2-8x+16 = 1+2+4+8+16 = 3 mod 4.
Do đó có SNT p = 4k+3 là ước của VT và hơn nữa, số mũ của nó phải lẻ (phải tồn tại số như
thế, vì nếu tất cả đều mũ chẵn thì số đó chia 4 dư 1).
Mà gcd(x+2, x^4-2x^3+4x^2-8x+16) = 1 hoặc 5 nên p này là ước của đúng 1 trong 2 số đó  vp(VT) phải lẻ.
Ngoài ra, p | y^2+6^2  p | 6  p = 3 nên 3|y.
Đặt y=3z  y^2+36 = 9(z^2+4)  mà z^2+4 không chia hết cho 3 nên v3(VP) = 2.
Suy ra v3(VT) = 2, mâu thuẫn.
b) Với a,b,c nguyên dương thay đổi và không có ước nguyên tố chung, ký hiệu 2 2 2 f (a, ,
b c)  gcd(a  b  c, a  b  c , n n n
a  b  c ) . n Chứng minh rằng f
(a, b, c) bị chặn trên nhưng f (a, , b c) thì không. 2022 2023
a) Gọi p là ước lẻ của f_2022(a,b,c) và k=v_p(f_2022(a,b,c)).
Khi đó: a+b+c, a^2+b^2+c^2, a^2022 + b^2022 + c^2022 chia hết cho p^k.
Hay: c đồng dư –(a+b) mod p => a^2+b^2 –c^2  –(a+b)^2
=> 2(a^2+ab+b^2) chia hết cho p^k.
Vì p lẻ nên: a^2 + ab + b^2 chia hết cho p^k. (1)
Suy ra a^3  b^3 mod p, tương tự cũng có b^3  c^3 mod p.
Mà 3|2022  a^2022+b^2022+c^2022  3.a^2022 mod p.
Nếu p > 3  p | a, tương tự p|b, c thì mâu thuẫn. Do đó p=3.
Bây giờ giả sử f2022(a,b,c) chia hết cho 9, c/m tương tự trên thì a^3, b^3, c^3 đồng dư với nhau 9, kéo theo:
a^2022+b^2022+c^2022  3.a^2022 mod 9.
Từ đó dẫn đến 3|a và cũng có 3|b, 3|c, mâu thuẫn. Vì thế v3(f2022(a,b,c)) <= 1.
Tiếp theo, xét tính chẵn lẻ của f2022: nếu số này chẵn thì 2|a+b+c nhưng do a, b, c không
cùng chẵn nên có 2 lẻ, 1 chẵn  a^2+b^2+c^2 = 2 mod 4, vì thế f2022 không chia hết cho
4. Và vậy nên f2022 bị chặn trên bởi 2.3 = 6.
b) Tiếp theo, ta xét với f2023: ta có thể chọn trực tiếp bộ (a,b,c) = (1,x,x^2) thì
a+b+c=1+x+x^2 và a^2+b^2+c^2 = 1+x^2+x^4 chia hết cho 1+x+x^2.
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học
Cuối cùng: a^2023+b^2023+c^2023 = 1+x^2023+x^4046 2
 1 x  x mod (x^3 - 1).
Và vì thế f2023(a,b,c) = x^2+x+1, rõ ràng số này không bị chặn trên.
Hướng khác cho việc chặn trên này (của HS gửi): f
(a, b, c) : Nếu tồn tại một số trong a,b chia hết cho p thì số còn lại cũng vậy và từ đó c 2022
cũng chia hết cho p nên vô lí. Suy ra: a,b đều không chia hết cho p. (1)
Hơn nữa a không  -b vì nếu vậy c chia hết cho p => vô lí. (2)
Gọi b’ là nghịch đảo modulo p^k của b.
Nhân b’^2 vào (1) có được: (ab’)^2 + ab’ + 1 chia hết cho p^k => (ab’)^3  1 mod p^k.
Mặt khác: a^2022 + b^2022 –(a+b)^2022 mod p^k
=> a^2022 + (a+b)^2022 + b^2022 chia hết cho p^k.
Nhân vào một lượng b’^2022 thì được:
(ab’)^2022 + 1 + (ab’+1)^2022 chia hết cho p^k. (3)
(1) (2) => ab’ và ab’ + 1 đều không chia hết cho p nên (3) trở thành: 1+1+1 chia hết cho p^k nên p^k=3.
Xét p=2: giả sử a,b lẻ và k=v_2(gcd(f_2022(a,b,c))) thì: -b^2 đồng dư với a^2 đồng dư với -
(-b)^2 => 2b^2 chia hết cho 2^k. => k=1.
Vì thế f_2022 bị chặn trên. f (a, ,
b c) : Bây giờ, với f_2023(a,b,c) gọi p là ước của gcd(a+b+c, a^2+b^2+c^2), 2023
k=v_p(gcd(a+b+c, a^2+b^2+c^2))
Ta sẽ có: (ab’)^3 đồng dư 1 mod p^k  (ab’)^2023 + 1 - (ab’+1)^2023 chia hết cho p^k.
->a^2023 + b^2023 - (a + b)^2023 chia hết cho p^k  a^2023 + b^2023 + c^2023 chia hết cho p^k.
Mà: gcd(a+b+c, a^2+b^2+c^2) không bị chặn trên nên f_2023 không bị chặn trên.
Bài 6. Tìm tất cả các bộ số tự nhiên (a,b, c) không tính thứ tự thỏa mãn:   a) a b c
gcd(a, b)  gcd( , b c)  gcd( , c a)  . 2
//ta có ước lượng: a, b phân biệt thì gcd(a,b) <= (a+b)/3  dùng ý tưởng đã c/m cho đánh giá này vào bài toán.
Ở đây, ta xử lý tương tự: trước hết, tồn tại một gcd(a,b) >= (a+b)/4 (cả ba đều < thì tổng sẽ
< VP). Đặt a=d.a1 và b=d.b1  chặn được cho (a1, b1)  thay vào và xử lý tiếp.
[Phần này không có trình bày trên lớp, HS suy nghĩ trước khi xem]
Không mất tính tổng quát, ta giả sử a b gcd(a, ) b . 4
Đặt d gcd(a,b) và a da ,b db thì gcd(a ,b ) 1 . 1 1 1 1
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học Do đó a b gcd(a, ) b
tương đương với a b 4 , mà a ,b 1 nên ta xét: 4 1 1 1 1 Nếu c c (a ,b ) (1,1) thì đưa về d 2gcd(c,d) d hay gcd(c,d) . Trong trường hợp 1 1 2 4
này, ta có nghiệm (a,b,c) t(2l 1),t(2l
1), 4t ,t 1,l 0 . Nếu c (a ,b )
(1, 3) thì gcd(c,d) gcd(c, 3d) d
. Đặt gcd(c,d) t và c tc ,d td . 1 1 2 1 1 Ta có 2 trường hợp: Nếu tc gcd(3d,c) 3t thì 1 4t td 8 2d c nên d 1,c 6 (do gcd(3,c ) 3 ) 1 1 1 2 1 1 1
dẫn đến một nghiệm của bài toán là (a,b,c)
t, 3t,6t ,t 1 . Nếu c d (a ,b )
(1, 2) thì ta có gcd(c,d) gcd(2d,c)
. Tương tự trên, ta tìm được 1 1 2
nghiệm của bài toán là (a,b,c) (t,2t,3t),t 1 .
Vậy các nghiệm của bài toán là (a,b,c)
(t, 2t, 3t),(t, 3t,6t), ( t 2l 1), (
t 2l 1), 4t với t 1 và l 0 , cùng các hoán vị.   b) a b c
gcd(ab 1, bc 1, ca 1)  . 3 Xét trường hợp:
 Nếu cả 3 bằng nhau thì sao?  a^2+1 = a, vô nghiệm.
 Nếu có 2 trong ba số bằng nhau.
 Nếu cả ba đều phân biệt? d = gcd ở VT thì khi đó:
 d | (ab+1) – (bc+1) = b(a-c) mà dễ thấy gcd(d,b) = 1 nên d|a-c. Tương tự d|b-c, c-a.
[Phần này không có trình bày trên lớp, HS suy nghĩ trước khi xem]
a) Đặt d gcd(ab 1,bc 1,ca 1) . Ta xét 3 trường hợp sau:
(1) Nếu cả ba số bằng nhau thì ta phải có 2 a 1
a , không thỏa mãn.
(2.1) Nếu có hai số bằng nhau và lớn hơn số còn lại, giả sử là a b c thì 2 2a c gcd(a 1, ac 1) . 3 Đặt a c t t a c dt,t 0 thì 2 2 2 c d d c 1
d . Từ đây suy ra t 1 vì nếu 3 3 3
không thì vế phải của biểu thức âm. Do đó d d c và 4 a . 3 3
Trường hè Vinh online 2023 – Bài giảng Đại số & Số học 2 2 2 Khi đó 2 16d 9 4d 9 16d 9 d gcd(a 1, ac 1) gcd , gcd , 3 . 9 9 9
Do đó d 1 hoặc d 3 . Thử lại ta thấy cả hai giá trị đều không thỏa mãn đề bài.
(2.2) Nếu có hai số bằng nhau và nhỏ hơn số còn lại, giả sử là a b c thì ta vẫn có 2 2a c gcd(a 1, ac 1) . 3 Đặt a c t t c a dt,t 0 thì 2 a d d a 1
d . Từ đây suy ra t 1, 2, 3 . 3 3 3
Tương tự trên, ta thấy cả ba giá trị này đều không thỏa.
(3) Nếu a,b,c đôi một phân biệt, ta có d | (a-b), (b-c), (c-a).
Không mất tính tổng quát, ta giả sử a b c , đặt a c md,b c nd , m n 0 thì a b c m n 2 1 d c d 0 d d . 3 3 3
Đẳng thức xảy ra khi c 0,m 2,n 1 . Thử lại ta thấy thỏa.
Vậy bộ số tự nhiên cần tìm là (a,b,c) (2,1,0) và các hoán vị.
BT bổ sung: Giải hệ PT nghiệm nguyên dương:
a+b = gcd(a,b)^2, b+c = gcd(b,c)^2 và c+ a = gcd(c,a)^2.
Bài 7. Cho các số nguyên tố p , p , , p phân biệt và các số tự nhiên n , n , , n  1 bất kỳ. 1 2 k 1 2 k
Chứng minh rằng số cặp số nguyên dương (x, y) không tính thứ tự, nguyên tố cùng nhau và 3 3 n n n 1 2 k
x  y  p p p 1 2 k thì không vượt quá 1 2k .
Ta có bổ đề: nếu gcd(x,y)=1 thì gcd(x+y, x^2-xy+y^2) = 1 hoặc 3.
Ta quy về đếm số cách chọn thừa số nguyên tố cho x+y và cho x^2-xy+y^2.
Chú ý, nếu xét hệ PT: x+y=a và x^2-xy+y^2=b  nếu có nghiệm (u,v) thì cũng có nghiệm
(v,u)  với một (a,b) có không quá <= 1 nghiệm (x,y) tương ứng mà không tính thứ tự.
Do đó, thay vì đếm (x,y), ta quy về chặn trên cho số cách chọn bộ (x+y, x^2-xy+y^2).
 Nếu các SNT này đều khác 3  mỗi thừa số ở VP thì chỉ được thuộc 1 trong x+y và x^2-xy+y^2  có 2^k cách.
 Nếu có chứa thừa số 3: ứng với số 3 này sẽ có 4 cách: (3^0, 3^n), (3^n, 3^0), (3^1,
3^(n-1)), (3^(n-1), 3^1)), cùng với 2^(k-1) cách cho các SNT còn lại  có 2^(k-1).4 =2^(k+1) cách.