Xem mẫu
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
CẤP CỦA MỘT SỐ NGUYÊN VÀ ỨNG DỤNG
GIẢI MỘT SỐ BÀI TOÁN SỐ HỌC
Đặng Thị Mến
THPT Chuyên Hưng Yên
1 Cơ sở lý thuyết
Định nghĩa 1. Số nguyên dương k bé nhất thỏa mãn ak ≡ 1 (mod n) được gọi là cấp của a theo
mod n, ký hiệu ordn ( a) = k.
Nhận xét 1. Cho n ∈ N∗ . Nếu a ∈ Z và ( a, n) > 1 thì không tồn tại số k ∈ N∗ để ak ≡ 1
(mod n), vì nếu ak ≡ 1 (mod n) thì ( ak , n) = (1, n) = 1, mà ( a, n) > 1 nên ( ak , n) > 1 (vô
lý).
Nếu a ∈ Z và ( a, n) = 1 thì luôn tồn tại số k ∈ N∗ để ak ≡ 1 (mod n), chẳng hạn
k = ϕ ( n ).
Từ định nghĩa trên ta có các kết quả sau
• ordn ( a) = 1 ⇔ a ≡ 1 (mod n)
• 1, a, a2 , . . . , aordn (a)−1 là đôi một phân biệt theo mod n. (Chúng lập thành các số đôi một
phân biệt chia cho n có ordn ( a) số dư khác nhau)
Định lý 1. a) Giả sử cấp của a theo mod n là k, khi đó ah ≡ 1 (mod n) ⇔ k |h.
b) Nếu ordn ( a) = k; ordn (b) = h mà (h, k ) = 1 thì ordn ( ab) = hk.
c) Cho các số n1 , n2 , . . . , nk đôi một nguyên tố cùng nhau và n = n1 n2 . . . nk và ordni ( a) = hi . Khi
đó ordn ( a) = [h1 , h2 , . . . , hk ].
h
d) Nếu ordn ( a) = h và u ∈ N∗ thì ordn ( au ) = .
(h, u)
.
Chứng minh. a) Nếu h..k thì h = kq (q ∈ N∗ ) vì ordn ( a) = k ⇔ ak ≡ 1 (mod n) nên akq ≡ 1
(mod n).
Nếu ah ≡ 1 (mod n) và h = kq + r với 1 ≤ r < k thì ah = ( ak )q ar ≡ ar (mod n)
nên ar ≡ 1 (mod n) mà 1 ≤ r < k, mâu thuẫn với định nghĩa số k.
.
Vậy r = 0 hay h..k.
b) ordn ( a) = k ⇔ ak ≡ 1 (mod n) nên ahk ≡ 1 (mod n)
ordn (b) = h ⇔ bh ≡ 1 (mod n) nên bhk ≡ 1 (mod n) suy ra ( ab)hk ≡ 1 (mod n).
.
Gọi t = ordn ( ab) thì hk..t (1)
Lại có ( ab)t ≡ 1 (mod n) nên ( ab)th ≡ 1 (mod n) và ath .(bh )t ≡ 1 (mod n).
184
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
. .
Mặt khác (bh )t ≡ 1 (mod n) nên ath ≡ 1 (mod n) suy ra th..k do (h, k) = 1 nên t..k (*)
.
Tương tự có ( ab)tk ≡ 1 (mod n) nên btk ≡ 1 (mod n) do ( ak )t ≡ 1 (mod n) nên tk..h mà
.
(k, h) = 1 nên t..h (**).
.
Từ (*) và (**) suy ra t..hk (2)
Từ (1) và (2) suy ra hk = t (đpcm).
.
c) Tương tự có h = ordn ( a) ⇔ ah ≡ 1 (mod n) nên ah ≡ 1 (mod n ) suy ra h..h , ∀i = 1, ..., k
i i
Suy ra h là một bội chung của hi , ∀i = 1, . . . , k.
.
Gọi k là một bội chung của hi thì ak ≡ 1 (mod ni ) nên ak ≡ 1 (mod n) suy ra k..h.
Vậy h = [n1 , n2 , . . . , nk ].
d) Gọi k = ordn ( au ), d = (h, u) thì h = dx, u = dy với ( x, y) = 1, x, y ∈ N∗ .
+) ( au )k = aku ≡ 1 (mod n) nên h|ku nên h|dky suy ra dky = m.h = mdx, m ∈ N∗ .
Suy ra ky = mx hay x |ky mà ( x, y) = 1 nên x |k (1).
+) aux = adxy = ( adx )y = ( ah )y ≡ 1 (mod n) nên ( au ) x ≡ 1 (mod n) do đó k| x. (2)
h h
Từ (1) và (2) suy ra k = x = = .
d (h, u)
Nhận xét 2.
• Nếu n = p1α1 p2α2 . . . pαk k là phân tích tiêu chuẩn của n. Để tìm ordn ( a) thì ta tìm ord pαi ( a),
i
với i ∈ {1, . . . , k }.
• a ϕ(n) ≡ 1 (mod n); ∀( a, n) = 1 nên ordn ( a)| ϕ(n) (rộng ra, ordn ( a) ≤ ϕ(n)), hay ordn ( a) ≤
( n − 1).
• Nếu p nguyên tố thì ord p ( a)| p − 1; ∀( a, p) = 1
• a x ≡ ay (mod n) ⇔ ordn ( a)|( x − y).
• m|n thì ordm ( a)| ordn ( a), ordn ( a) = h nên ah ≡ 1 (mod n)
.
m|n thì ah ≡ 1 (mod m) nên h.. ordm ( a)
Định nghĩa 2. Số nguyên g được gọi là căn nguyên thủy của n, nếu cấp của nó theo mod n bằng
ϕ ( n ).
Ví dụ 1. Hãy xác định ord101 (2) và ord125 (12).
Lời giải.
· Gọi d = ord101 (2), có 101 là số nguyên tố nên ϕ(101) = 100.
2d ≡ 1 (mod 101) suy ra d|100, ta chứng minh d 6= 50, d 6= 20.
210 = 1024 ≡ 14 (mod 101) nên 250 ≡ 145 ≡ 1962 .14 ≡ (−6)2 .14 ≡ −1 (mod 101) suy ra
d 6= 50
220 = 10242 ≡ 142 ≡ −6 (mod 101) nên d6= 20 và d = 100 nên ord101 (2) = 100.
1
· Gọi d = ord125 (12); ϕ(125) = 53 . 1 − = 100 nên d|100
5
ord5 (12)|d, mà 12 ≡ 2 (mod 5), 122 ≡ 4 (mod 5) nên 123 ≡ 3 (mod 5); 124 ≡ 1 (mod 5)
do đó ord5 (12) = 4 nên 4|d.
Mà d|100 nên d ∈ {4; 20; 100}.
124 ≡ 1442 ≡ 192 ≡ 361 ≡ −14 (mod 125)
1220 = (124 )5 ≡ (−14)5 ≡ 71.71.(−14) ≡ 41.14 ≡ 74 (mod 125)
suy ra d = 100, vậy ord125 (12) = 100.
185
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Định lý 2. Cho a là số lẻ và n = 2s , ( a, n) = 1.
( 2 .c với u, v ∈ N ; b, c lẻ.
Giả sử a − 1 = 2u .b; a2 − 1 = v ∗
1, u ≥ s
Khi đó h = ordn ( a) thì h =
2max{1;s+1;v} , u < s
Chứng minh.
Nhận xét rằng a2 − 1 = ( a − 1)( a + 1) = 2u .b( a + 1) = 2u .b.(2u .b + 2) = 2u+1 .b(2u−1 .b + 1)
nên v > u
s s (1− 1 ) s −1
· ( a, n) = 1 nên a ϕ(n) ≡ 1 (mod n) mà a ϕ(n) = a ϕ(2 ) = a2 2 = a2 suy ra h|2s−1 nên
h = 2t với t ≤ s − 1 (1)
.
· Nếu u ≥ s thì a − 1 = 2u .b .. 2s nên n| a − 1 suy ra a ≡ 1 (mod n) nên h = 1.
· Nếu u < s thì h ≥ 2 nên t ≥ 1
t t −1 t −2
( ah − 1) = ( a2 − 1) = ( a2 + 1)( a2 + 1) . . . ( a2 + 1)( a2 − 1) (*)
i
a ≡ 1 (mod 2) (a lẻ) nên a2 ≡ 1 (mod 2)
.
Nếu v ≥ s thì a2 − 1 .. n nên a2 ≡ 1 (mod n) suy ra h = 2
Nếu v < s thì s ≥ 2.
i i
Vì a là số lẻ thì a2 ≡ 1 (mod 4) nên a2 ≡ 1 (mod 4) và a2 + 1 ≡ 2 (mod 4)
(*) nên ah − 1 = 2t−1 .a.2v .c với a, c là số lẻ, nên
.
ah − 1..2s ⇔ t − 1 + v ≥ s ⇔ t ≥ s − v + 1 ≥ 2
s − v +1 .
t nhỏ nhất (do h nhỏ nhất) nên t = s − v + 1 hay h = 2
1; u ≥ s
Vậy h = 2; u < s ≤ v
1+ s − v
2 ; u
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Nếu k > 1
t t t t
a ≡ 1 (mod p); ah − 1 = ( a p − 1)( a p .(k−1) + a p .(k−2) + · · · + a p + 1) ≡ k (mod p)
t
thì ah − 1 = ( a p − 1).b; b ≡ k (mod p) ⇒ (b, p) = 1.
. .
Mà ah − 1..p nên a p − 1..p và a p ≡ 1 (mod p).
t t
Suy ra pt |h nên pt < h, vô lý với cách chọn h, nên k = 1, do đó h = pt k; t > 0. Áp dụng bổ
đề nâng lũy thừa, ta có p lẻ, p > 1
v p ( a h − 1) = v p ( a − 1) + v p ( h ) = u + t
hay ah − 1 = pu+t .A; ( p, A) = 1
.
Mà ah − 1..ps nên u + t ≥ s suy ra t ≥ s − u ≥ 1.
Vậy t bé nhất là t = s − u nên h = ps−u .
Trường hợp 2: r > 1
.
ah ≡ 1 (mod n) nên ah ≡ 1 (mod p) suy ra h..n.
Giả sử h = r.k; ah = ( ar )k = bk (với b = ar ) nên b − 1 = pu q; b ≡ 1 (mod p); (b, n) = 1.
Có bk ≡ ah ≡ 1 (mod n), suy ra k là cấp của b theo mod n.
Áp dụng trường hợp 1 cho b (r = 1) ta có
( (
1; u≥s r; u≥s
k= s − u
⇒ h = rk = s − u
p ; u 1)
2 p − 1 ≡ 0 (mod q) nên 2 p ≡ 1 (mod q) suy ra ordq (2)| p.
187
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
(
ordq (2) = 1
Mà p nguyên tố nên (*)
ordq (2) = p
.
Nếu ordq (2) = 1 thì 2 ≡ 1 (mod q) nên 1 .. q và q = 1, vô lý.
Nếu ordq (2) = p thì ordq (2)| ϕ(q) nên p|q − 1 vậy nên q = kp + 1 (k ≥ 1).
Bài toán 2. Nếu p là ước nguyên tố lẻ của n2 + 1 thì p ≡ 1 (mod 4); ∀n ∈ N∗ .
Lời giải. Ta có p|n2 + 1 nên p|(n4 − 1) vậy nên ord p (n)|4.
Nếu ord p (n) = 1 thì n ≡ 1 (mod p) nên p|n − 1. Suy ra p|n2 − 1 mà p|n2 + 1 nên p|2, vô lý
vì p nguyên tố lẻ.
Nếu ord p (n) = 2 thì n2 ≡ 1 (mod p) nên p|n2 − 1 mà p|n2 + 1 do đó p|2, vô lý.
nên ord p (n) = 4 mà ord p (n)| ϕ( p) = p − 1 nên 4| p − 1 do đó p = 4k + 1 hay p ≡ 1 (mod 4).
Bài toán 3. Chứng minh rằng
a) Nếu p là ước nguyên tố lẻ của n4 + 1 thì p ≡ 1 (mod 8)
n
b) Nếu p là ước nguyên tố lẻ của a2 + 1 ( a ∈ Z, n ∈ N∗ ) thì p ≡ 1 (mod 2n ), hay p có dạng
p = 2n+1 .k + 1, k ∈ N∗ .
Lời giải. a) p là ước nguyên tố lẻ của n4 + 1 nên p|n4 + 1 suy ra p|n8 − 1
và ord p (n)|8 nên ord p (n) = 2t ; t ∈ N; t ≤ 3.
Nếu(t < 3 thi t ≤ 2 nên 2t |22 = 4 do đó ord p (n)|4 nên n4 ≡ 1 (mod p).
p | n4 − 1
Mà suy ra p|2 mâu thuẫn với p nguyên tố lẻ.
p | n4 + 1
nên t = 3 suy ra ord p (n) = 8| ϕ( p) = p − 1 và p ≡ 1 (mod 8) hay p = 8k + 1 (k ∈ N∗ ).
b) Chứng minh tương tự có ord p (n) = h ah ≡ 1 (mod p)
n +1 n +1
p| a2n + 1 và p|( a2n + 1)( a2n − 1) = a2 − 1 do đó a2 ≡ 1 (mod p)
nên h|2n+1 suy ra h = 2t (t ≤ n + 1).
n
Nếu(t ≤ n thì 2t |2n nên a2 ≡ 1 (mod p).
n
p | a2 − 1
Mà n nên p|2, mâu thuẫn với p nguyên tố lẻ nên t = n + 1.
p | a2 + 1
nên h = 2n+1 | ϕ( p) = p − 1 do đó p ≡ 1 (mod 2n+1 ) hay p = 2n+1 .k + 1.
n
Nhận xét 4. Mọi ước lẻ của a2 + 1 đều có dạng 2n+1 .k + 1; k ∈ N.
n
Khi a = 2, số Fecma thứ n là Fn = 22 + 1 có tính chất: p là ước nguyên tố lẻ của Fn (n > 1)
thì p ≡ 1 (mod 2n+2 ).
Bài toán 4. Cho p nguyên tố, n ∈ N∗ và q là ước nguyên tố lẻ của n p + 1 thì q|n2 − 1 hoặc
2p|(q − 1).
Lời giải. Giả sử q|n p + 1 thì n p ≡ −1 (mod q) nên n2p ≡ 1 (mod q)
h = ordq (n) nên h|2p, mà h không là ước của p và p nguyên tố nên h = 2 hoặc h = 2p.
Nếu h = 2 thì n2 ≡ 1 (mod q) nên q|n2 − 1 (đpcm).
Nếu h = 2p thì h| ϕ(q) = q − 1 nên 2p|(q − 1) (đpcm).
Bài toán 5. Chứng minh rằng: ∀n > 2 đều không là ước của 2n − 1.
188
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Lời giải. Giả sử có n ≥ 2 và n|2n − 1 mà 2n − 1 là số lẻ, suy ra n lẻ. Gọi p là ước nguyên tố
nhỏ nhất của n thì p lẻ, p ≥ 3.
2n − 1 ≡ 0 (mod p) ord p (2)|n và ord p (2)| p − 1 = ϕ( p).
1 < ord p (2)|( p − 1, n), vô lý vì p là ước nguyên tố nhỏ nhất của n.
Suy ra ( p − 1, n) = 1. Vậy n không thể là ước của 2n − 1.
Bài toán 6. Tìm các số nguyên dương a 6= b với a + b nhỏ nhất sao cho 2012a và 2012b có ba
chữ số tận cùng giống nhau.
Lời giải. Giả sử a > b.
2012a ≡ 2012b (mod 1000) ⇔ 12a ≡ 12b (mod 1000) nên 12b (12a−b − 1) ≡ 0 (mod 1000)
Mà 1000 = 23 .53 , mà 12b là số chẵn, 12a−b − 1 là số lẻ nên 23 |12b do đó b ≥ 2.
Mà (5; 12) = 1 nên 53 |(12a−b − 1)
.
Tìm ord 3 (12), theo ví dụ 1 ta có ord 3 (12) = 100 nên a − b .. 100
5 5
vậy a − b ≥ 100 mà b ≥ 2 nên 2b ≥ 4 suy ra a − b + 2b ≥ 104; a + b ≥ 104.
Dấu "=" khi b = 2, a = 102.
Mà a 6= b; a + b nhỏ nhất suy ra a = 102, b = 2.
Kết luận: a = 102, b = 2 hoặc a = 2, b = 102.
(
n | 2m −1 + 1
Bài toán 7. Tìm tất cả các số nguyên dương (m, n) thỏa mãn .
m | 2n −1 + 1
(
n | 20 + 1 ⇒ n | 2
n=1
Lời giải. · Nếu m = 1 thì n − 1
nên
m |2 +1 n=2
(
n | 2m −1 + 1
m=1
· Nếu n = 1 thì 0
nên
m |2 + 1 m=2
(
n | 2m −1 + 1
· Nếu m > 1, n > 1 có suy ra m, n lẻ.
m | 2n −1 + 1
Giả sử m − 1 = 2a .x ( a ∈ N∗ , x lẻ ) và n − 1 = 2b .y (b ∈ N∗ , y lẻ )
a
Gọi p là ước nguyên tố bất kỳ của n thì p|2m−1 + 1 nên p|(2x )2 + 1 theo bài tập 3.
nên p ≡ 1 (mod 2a+1 ) do đó p = α a+1 k + 1.
Như vậy mọi ước của n đều có dạng 2a+1 k + 1. Do tích của các số có dạng 2a+1 k + 1 cũng là
số có dạng 2a+1 k + 1 nên n ≡ 1 (mod 2a+1 ).
n − 1 = 2a+1 .y1 (y1 ∈ N∗ ) mà n − 1 = 2b .y (y lẻ) nên b ≥ a + 1 (1)
Gọi q là ước nguyên tố bất kỳ của m.
b
q|m thì a|2n−1 + 1 nên q|(2x )2 + 1 theo bài tập 3 nên q ≡ 1 (mod 2b+1 )
⇒ q = 2b+1 .t + 1 nên m = 2b+1 .x1 + 1 ( x1 ∈ N∗ )
⇒ m − 1 = 2b+1 .x1 ( x1 ∈ N∗ ), mà m − 1 = 2a .x (x lẻ) nên a ≥ b + 1 (2)
Từ (1) và (2) vô lý. Vậy không có m > 1, n > 1 thỏa mãn đề bài.
Kết luận: m = 1, n = 1; m = 1, n = 2; m = 2, n = 1.
n
Bài toán 8. Cho số Fecma Fn = 22 + 1 (có thể là hợp số, cũng có thể là số nguyên tố).
a) Chứng minh rằng, nếu Fn là hợp số thì Fn có ít nhất 2 ước nguyên tố phân biệt.
189
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
b) Chứng minh rằng, nếu p| Fn , q| Fn (p, q là số nguyên tố, p 6= q) thì
( (
p | 2q −1 − 1 2q−1 ≡ 1 (mod p)
hay
q | 2 p −1 − 1 2 p−1 ≡ 1 (mod q)
Lời giải. a) Giả sử Fn là hợp số và Fn có đúng một ước nguyên tố phân biệt.
nên Fn = pk (k ≥ 2) vì nếu k = 1 thì Fn = p là số nguyên tố, vô lý.
Nếu k chẵn: k = 2t (t ≥ 1).
n n n −1 n −1
Fn = pk thì 22 + 1 = p2t ⇔ 1 = p2t − 22 = ( pt − 22 )( pt + 22 ), vô lý (vì n ≥ 5, Fn mới
là hợp số).
Nếu k lẻ: k = 2t + 1 (t ≥ 1)
n n
22 + 1 = p2t+1 nên 22 = p2t+1 − 1 = ( p − 1)( p2t + p2t−1 + · · · + p + 1)
n
suy ra 22 có ước lẻ lớn hơn 1, vô lý.
Vậy Fn là hợp số thì phải có 2 ước nguyên tố phân biệt trở lên.
b) Gọi p, q là hai ước nguyên tố phân biệt của Fn thì p, q lẻ vì Fn lẻ.
Ta chứng minh: ord p (2)|q − 1 và ordq (2)| p − 1.
n
Giả sử ord p (2) = h thì 2h ≡ 1 (mod p), có p| Fn nên 22 ≡ −1 (mod p)
n +1
⇒ 22 ≡ 1 (mod p) nên h|2n+1 suy ra h = 2t với t ≤ n + 1.
n n n
Nếu t ≤ n thì 2t |2n thì 22 ≡ 1 (mod p); p|22 − 1; p|22 + 1 nên p|2 mâu thuẫn p nguyên tố
lẻ.
nên t = n + 1 hay h = 2n+1 , chứng minh tương tự có ordq (2) = 2n+1 .
Mà ord p (2)| ϕ( p) = p − 1 nên 2n+1 | p − 1; 2n+1 = ordq (2) do đó 2 p−1 ≡ 1 (mod q).
Mà ordq (2)| ϕ(q) = q − 1 nên 2n+1 |q − 1 mà 2n+1 = ord p (2) suy ra 2q−1 ≡ 1 (mod p)
(đpcm).
Bài toán 9. Cho n > 1, a ∈ N∗ ; n| an + 1. Chứng minh rằng ( a + 1, n) = 1.
Lời giải. Do n > 1 nên n có ước nguyên tố. Gọi p là ước nguyên tố nhỏ nhất của n nên
( p − 1, n) = 1.
.
ord p ( a) = h nên ah ≡ 1 (mod p) suy ra ah − 1 .. p
p|n mà n| an + 1 nên p| an + 1
an ≡ −1 (mod p) do đó p| a2n − 1 nên a2n ≡ 1 (mod p) suy ra h|2n.
Mà h| ϕ( p) = p − 1 nên h|(2n, p − 1); (2n, p − 1) = (2, p − 1) suy ra h|(2, p − 1).
Do (n, p − 1) = 1 nên h|(2, p − 1); (2, p) = 2
.
Nếu h = 1 thì a − 1 .. p nên an ≡ 1 (mod p) nên an + 1 ≡ 2 (mod p).
. . .
Mà an + 1 .. p thì 2 .. p mà p nguyên tố nên p = 2, có ( a − 1) .. 2 nên a lẻ, p| a nên ( a + 1; n) ≥
2 > 1.
.
Nếu h = 2 thì a2 − 1 .. p; 2|( p − 1) nên p lẻ mà a − 1 không chia hết cho p
nên p| a + 1; p|n suy ra p|( a + 1, n) do đó ( a + 1, n) > 1 (đpcm)
Bài toán 10. Giả sử a, b là các số nguyên dương, sao cho 2a − 1; 2b − 1; 2c − 1 đều là các số
nguyên tố. Chứng minh rằng a a + bb và ab + b a đều không chia hết cho a + b.
Lời giải. Có 2a − 1; 2b − 1 là số nguyên tố nên a > 1, b > 1 và a + b > 2 mà a + b nguyên
tố, do đó a + b là số lẻ, ϕ( a + b) = a + b − 1.
190
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
.
Giả sử a chẵn, b lẻ. Vì b lẻ nên ab + bb ..( a + b) (1)
.
· Nếu a a + bb ..( a + b) (2)
. .
Từ (1), (2) suy ra ( ab − a a )..( a + b) và a a ( ab−a − 1)..( a + b), nếu a < b (*)
.
hoặc ab (1 − a a−b )..( a + b) nếu a > b.
. .
Nếu a a ..( a + b) thì a..( a + b) do ( a + b) nguyên tố, vô lý vì a < a + b.
. .
Nếu ab ..( a + b) thì a..( a + b) do ( a + b) nguyên tố, vô lý vì a < a + b.
Từ (*) có a|b−a| ≡ 1 (mod ( a + b)). Gọi( h = orda+b ( a) thì h|(|b − a|)
h|2a − 1
Mà h| ϕ( a + b) nên h| a + b − 1 suy ra
h|2b − 1
.
Do (2a − 1), (2b − 1) là số nguyên tố nên h = 1 do đó a ≡ 1 (mod ( a + b)) nên ( a − 1)..( a +
b), vô lý vì 0 < a − 1 < a + b.
. . .
· Tương tự, nếu ab + b a ..( a + b) mà ( ab + bb )..( a + b) nên (b a − bb )..( a + b)
. .
b a (1 − bb−a )..( a + b) nếu a < b hoặc bb (b a−b − 1)..( a + b) nếu a > b (**)
. .
Nếu b a ..( a + b) thì b..( a + b) do ( a + b) nguyên tố, vô lý vì b < a + b
. .
Nếu bb ..( a + b) thì b..( a + b) do ( a + b) nguyên tố, vô lý vì b < a + b
.
Từ (**) có (b|a−b| − 1)..( a + b) nên b|a−b| ≡ 1 (mod ( a + b))
Gọi k = orda+b (b) thì k|(| a − b|)(.
k |2a − 1
Mà k | a + b − 1 = ϕ( a + b) nên
k |2b − 1
Do 2a − 1; 2b − 1 là số nguyên tố nên k = 1 do đó b ≡ 1 (mod ( a + b))
.
suy ra b − 1..( a + b), vô lý vì 0 < b − 1 < a + b.
Vậy a a + bb ; ab + b a đều không chia hết cho 2a − 1; 2b − 1.
Bài toán 11. Cho p, q là hai số nguyên tố lẻ thỏa mãn p = 2q + 1. Chứng minh − a2 luôn là
căn nguyên thủy mod p với mọi số nguyên a thỏa mãn 1 < a ≤ q.
Lời giải. Giả sử q = 2k + 1, suy ra p = 4k + 3 nên −1 không là số chính phương mod p.
Gọi g là một căn nguyên thủy mod p, khi đó tồn tại các số nguyên dương s, t thỏa mãn
1 ≤ s, t ≤ p − 1 sao cho −1 ≡ gs (mod p), a ≡ gt (mod p).
Do −1 không là số chính phương mod p nên s lẻ, suy ra (s + 2t)q là số lẻ và không chia hết
cho p − 1.
Ta có: (− a2 )q ≡ ( gs .g2t )q ≡ g(s+2t)q 6= 1 (mod p) (1)
Mặt khác, vì 1 < a ≤ q nên a2 6= 1 (mod p)
Do đó (− a2 )2 ≡ a4 6= 1 (mod p) (2)
Gọi ord p (− a2 ) = h thì h| p − 1 nên h chỉ có thể nhận giá trị 2, q, 2q.
Từ (1) và (2) suy ra h = 2q = p − 1.
Vậy − a2 là căn nguyên thủy mod p.
191
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
3 Một số bài tập tương tự
.
Bài 1. Cho số nguyên dương n thỏa mãn 3n − 1..n. Chứng minh rằng n chẵn.
Bài 2. Tìm số nguyên dương n nhỏ nhất sao cho 17n − 1 chia hết cho 22011 .
Bài 3.
a) Có bao nhiêu số nguyên dương n là bội số của 1001 và biểu diễn được dưới dạng n =
10 j − 10i (i, j ∈ N, 0 ≤ i < j ≤ 99).
b) Có bao nhiêu số nguyên dương n là bội số của 2011 và biểu diễn được dưới dạng n =
10 j − 10i (i, j ∈ N, 0 ≤ i < j ≤ 99).
Bài 4. Chứng minh rằng với mỗi số nguyên dương n thì 3n − 2n không chia hết cho n.
Bài 5 (Bulgari OM 1995). Tìm tất cả các số nguyên tố p, q sao cho (5 p − 2 p )(5q − 2q ) chia hết
cho pq.
Đáp số: ( p; q) ∈ {(3; 3); (3; 13); (13; 3)}.
n n
Bài 6. Cho hai số nguyên dương m và n (n > 1), sao cho 1 + m3 + m2.3 chia hết cho n.
Chứng minh rằng n = 3.
Bài 7. Tìm tất cả các số nguyên tố p, q phân biệt sao cho 3 pq ≡ a (mod 3pq), với mọi số
nguyên dương a.
Đáp số: ( p; q) ∈ {(17; 11); (11; 17)}.
Bài 8 (Russia OM 2000). Có tồn tại hay không các số nguyên dương a, b, c thỏa mãn
( a, b) = (b, c) = (c, a) = 1
2a + 1 ... b
.
2b + 1 .. c
2c + 1 ... a
( a + 1) n − a n
Bài 9 (China TST 2006). Tìm tất cả các cặp số nguyên dương ( a, n) sao cho ∈ Z.
n
Bài 10 (Turkey TST 2013). Tìm tất cả các cặp số nguyên dương (m, n) thỏa mãn 2n + (n −
ϕ(n) − 1)! = nm + 1.
Tài liệu
[1] Nguyễn Vũ Thanh, Số học, NXB Tổng hợp Tiền Giang - 1992.
[2] Đặng Hùng Thắng, Nguyễn Văn Ngọc, Vũ Kim Thủy, Bài giảng số học, NXBGD - 1997.
[3] Hà Huy Khoái, Số học, NXBGD - 2004.
[4] Bộ Giáo dục và đào tạo, Tạp chí Toán học và tuổi trẻ, NXBGD
192
nguon tai.lieu . vn
