Giải đề mẫu số học và logic 2023 TRẦN QUỐC ANH Ngày 18 tháng 1 năm 2024 1 Câu 1 Câu a)
Định nghĩa: Với số nguyên dương m > 1, gọi ϕ(m) là số các số nguyên dương nhỏ hơn
m và nguyên tố cùng nhau với m. Khi đó, từ một hệ thặng dư đầy đủ mô-đun m, có đúng
ϕ(m) phần tử nguyên tố cùng nhau với m. Ta nói các phần tử này lập thành một hệ thặng
dư thu gọn modulo m. Nói cách khác
(x1, x2, ..., xϕ(m)) là hệ thặng dư thu gọn modulo m ⇐⇒ gcd(xi, m) = 1 và xi − xj
không chia hết cho m với mọi 1 ≤ i < j ≤ ϕ(m).
Tính chất: Nếu (x1, x2, ..., xϕ(m)) là hệ thặng dư thu gọn modulo m và gcd(a, m) = 1 thì
(ax1, ax2, . . . , axϕ(m)) cũng là một hệ thặng dư thu gọn modulo m.
Câu b) Ta có ϕ(15) = 8 và (1, 2, 4, 7, 8, 11, 13, 14) là một hệ thặng dư thu gọc modulo 15, vì
gcd(2, 15) = 1 nên theo tính chất của hệ thặng dư modulo thu gọn thì (x1, x2, x3, x4, x5, x6, x7, x8) =
(2, 4, 8, 14, 16, 22, 26, 28) là một hệ thặng dư thu gọn mod 15 và rõ ràng nó gồm toàn số chẵn. Câu 2
Câu a) Cở sở logic của phép chứng minh phản chứng là
[(P1 ∧ P2 ∧ ... ∧ Pn) −→ Q] ⇐⇒
[(P1 ∧ P2 ∧ ... ∧ Pn ∧ Q) −→ 0]
Câu b) Cách 1: Giả sử chỉ có hữu hạn số nguyên tố là p1, p2, ..., pn, ta lập số A = p1p2...pn + 1
Vì A > 1 nên A có ít nhất một ước nguyên tố p, nếu tồn tại 1 ≤ i ≤ n sao cho p = pi thì
suy ra p|A − (p1p2...pi...pn) = 1, điều này vô lý vì p nguyên tố, do đó p ̸= pi, ∀1 ≤ i ≤ n,
mâu thuẫn, do đó phải có vô hạn số nguyên tố.
Cách 2: Với mọi m > 3 thì m! − 1 > 1, do đó m! − 1 ít nhất có một ước nguyên tố p, suy
ra p ≤ m! − 1 < m!, nếu m ≥ p thì suy ra p|m!, dẫn tới p|1 = m! − (m! − 1), vô lý vì p
nguyên tố, do đó phải có p > m, dẫn tới ta có m < p < m!, cho m → ∞ ta có điều phải chứng minh. 2 Câu 3
1(1 + 1)(2.1 + 1)(3.12 + 3.1 − 1) Với n = 1 ta có 1 = 14 = (đúng). 30
Giả sử đẳng thức đúng tới n, ta sẽ chứng minh nó cũng đúng với n + 1, thật vậy ta có
n(n + 1)(2n + 1)(3n2 + 3n − 1)
12 + 24 + 34 + ... + n4 + (n + 1)4 = + (n + 1)4 30 " #
n(2n + 1)(3n2 + 3n − 1) + 30(n + 1)3 = (n + 1) 30 " # 6n4 + 39n3 + 91n2 + 89n2 + 30 = (n + 1) 30 " # (2n + 3)(n + 2)(3n2 + 9n + 5) = (n + 1) 30
(n + 1)(n + 2)(2n + 3)[3(n + 1)2 + 3(n + 1) − 1] = 30
Do đó đẳng thức cũng đúng với n + 1, do đó theo nguyên lý quy nạp nó đúng với mọi n nguyên dương. Câu 4
Câu a) Thử lần lượt với các số 0, 1, 2, 3, 4, 5, 6 thì chỉ có 3.32 + 4.3 + 3 ≡ 42 ≡ 0 ( mod 7) và
3.52 + 4.5 + 3 ≡ 98 ≡ 0 (mod 7), do đó x ≡ 3 (mod 7) và x ≡ 5 (mod 7) là nghiệm. 800 − 21y 1 − 4y
Câu b) Xét phương trình 17x + 21y = 800, suy ra x = = 47 − y + , 17 17 1 − 17t 1 − t
ta phải có 1 − 4y = 17t, suy ra y = = −4t +
, phải có 1 − t = 4k, suy ra 4 4 1 − 17(1 − 4k) 1 − 4y t = 1 − 4k, suy ra y = = 17k − 4 và x = 47 − y + = 47 − (17k − 4 17 1 − 4(17k − 4) 4) +
= 51 − 17k + 1 − 4k = 52 − 21k, do đó 17 (x = 52 − 21k y = 17k − 4
Với k là một số nguyên. 52 4
Mặt khác vì x, y không âm nên ta có 17k − 4 ≥ 0 và 52 − 21k ≥ 0, suy ra ≥ k ≥ , 21 17
hơn nữa k nguyên nên suy ra k ∈ {1, 2}, suy ra (x, y) = (31, 13) và (x, y) = (10, 30) là hai nghiệm cần tìm. 3 Câu 5
Ta mô hình hóa bài toán như sau: Tìm số nguyên 0 < x ≤ 3000 sao cho  x ≡ 3 ( mod 11)   x ≡ 4 (mod 13)   x ≡ 11 ( mod 19)
Ta có gcd(11, 13) = gcd(13, 19) = gcd(11, 19) = 1, đặt m = 13.11.19 = 2717, xét các đồng dư thức   247b b  1 ≡ 1 ( mod 11)  1 ≡ 9 ( mod 11)   209b2 ≡ 1 (mod 13) =⇒ b2 ≡ 1 (mod 13)     143b3 ≡ 1 ( mod 19) b3 ≡ 2 ( mod 19)
Theo định lý phần dư Trung Hoa ta có
x ≡ 247.3.9 + 209.4.1 + 143.11.2 ≡ 10651 ≡ 2500 (mod 2717)
Suy ra x = 2717t + 2500 với t nguyên, mà 0 < x < 3000, tức là 0 < 2717t + 2500 ≤ 3000, −2500 500 suy ra < t ≤
, vì t nguyên nên suy ra t = 0, dẫn tới x = 2500. 2717 2717 4