Chương5 Phương trình đồng dư

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

830
lượt xem 96
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phương trình đồng dư dạng ax=b (mod m) được gọi là phương trình đồng dư tuyến tính với a, b, m là các số đã biết, xo là nghiệm của phương trình khi và chỉ khi ax0=m

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương5 Phương trình đồng dư

Chương 5 Phương trình đ ng dư 5.1 Phương trình đ ng dư tuy n tính 89 5.2 Phương trình đ ng dư b c cao 90 5.3 H phương trình đ ng dư b c nh t n m t n 90 5.4 B c c a phương trình đ ng dư 95 .v 5.5 Bài t p 95 5.6 ng d ng đ nh lý Euler đ gi i h phương trình đ ng dư 96 5.7 Bài t p 101 2 4 Tr n Trung Kiên (Ispectorgadget) o c Nguy n Đình Tùng (tungc3sp) 5.1 i h Phương trình đ ng dư tuy n tính u Đ nh nghĩa 5.1 Phương trình đ ng dư d ng ax ≡ b (mod m) đư c g i V là phương trình đ ng dư tuy n tính v i a, b, m là các s đã bi t. x0 là m t nghi m c a phương trình khi và ch khi ax0 ≡ b (mod m). N u x0 là m t nghi m c a phương trình thì các ph n t thu c l p x0 cũng là nghi m. Ví d 5.1. Gi i phương trình đ ng dư sau: 12x ≡ 7 (mod 23) L i gi i. Do (12; 23) = 1 nên phương trình luôn có nghi m duy nh t. Ta tìm m t s nguyên sao cho 7 + 23k chia h t cho 12. Ch n k = 7 suy ra 12x ≡ 7.24 (mod 23) ⇒ x ≡ 14 (mod 23) 89
90 5.2. Phương trình đ ng dư b c cao Ví d 5.2. Gi i phương trình 5x ≡ 2 (mod 7) L i gi i. Vì (5; 2) = 1 nên t n t i s k = 4 sao cho 2 + 7k chia h t cho 30 5. Khi y 5x ≡ 2 + 6.7 (mod 7) ta đư c nghi m x ≡ ≡ 6 (mod 7) 5 hay x = 6 + 7k Ví d 5.3. Gi i phương trình: 5x ≡ 4 (mod 11) L i gi i. Ta có: 5x ≡ 4 (mod 11) n 4 ≡ 4 (mod 11) .v Áp d ng tính ch t b c c u ta có: 5x ≡ 4 (mod 11) ⇒ 5x = 11t + 4 Ta có th l y t = 1; x = 3. T đó phương trình có nghi m duy nh t là x ≡ 3 (mod 11) trong trư ng h p a là m t s nh ho c d th y ngay s k. 4 h Nh n xét. Cách xác đ nh nghi m này là đơn gi n nhưng ch dùng đư c 5.2 Phương trình đ ng dư b c cao c 2 o Ví d 5.4. Gi i phương trình 2x3 + 4 ≡ 0 (mod 5) L i gi i. Ta th y x = 2 suy ra 2x3 ≡ −4 (mod 5). h Nên x = 2 là nghi m duy nh t c a phương trình đã cho. i 5.3 V u H phương trình đ ng dư b c nh t m t n Đ nh nghĩa 5.2 H phương trình trình đ ng dư b c nh t m t n   x ≡ b1  có d ng sau đư c g i là h phương (mod m1 ) x ≡ b2 (mod m2 )   ....  x ≡ bk (mod mk )  V i m1 ; m2 ; ...mk là nh ng s nguyên l n hơn 1 và b1 ; b2 ; ...; bk là nh ng s nguyên tùy ý. Di n đàn Toán h c Chuyên đ S h c
5.3. H phương trình đ ng dư b c nh t m t n 91 Nh n xét. • Trong trư ng h p t ng quát, chúng ta có th ch ng minh đư c r ng: Đi u ki n c n và đ đ h phương trình (5.2) có nghi m là U CLN (mi ; mj ) chia h t bi − bj v i i = j(1 ≤ i, j ≤ k). • Gi s m = pα1 pαa2 ...pαk là phân tích tiêu chu n c a m. Khi 1 2 k y phương trình đ ng dư f (x) ≡ 0 (mod m) tương đương v i h phương trình đ ng dư f (x) ≡ 0 (mod pα1 ), i = 1, 2, ..., k. T đó i suy ra r ng n u x ≡ b1 (mod pα1 ) là m t nghi m c a phương 1 trình f (x) ≡ 0 (mod pi ), i = 1, 2, ..., k thì nghi m c a h phương trình c a h phương trình đ ng dư   x ≡ b1 (modp1 1 )   x ≡ b2 (modpα2 ) ... α 2 .v n h  x ≡ bk modpαk   k 2 4 cho ta nghi m c a phương trình f (x) ≡ 0(modm). V y trong • Trư ng h p t ng quát gi i m t phương trình đ ng c dư d n đ n gi i h trên. V i các module m1 , m2 , ..., mk đôi m t nguyên t cùng nhau. Phương pháp chung đ gi i: h o i • Trư ng h p 1: h 2 phương trình u x ≡ b1 x ≡ b2 (mod m1 ) (mod m2 ) V V i gi thi t d = (m1 , m2 ) chia h t cho b1 −b2 . Trư c tiên ta nh n xét r ng, m i s x = b1 + m1 t, t ∈ Z là nghi m c a phương trình th nh t. Sau đó ta tìm cách xác đ nh t sao cho x nghi m đúng phương trình th hai, nghĩa là h hai phương trình trên tương đương v i h phương trình x = b1 + m1 t b1 + m1 t ≡ b2 (mod m2 ) Chuyên đ S h c Di n đàn Toán h c
92 5.3. H phương trình đ ng dư b c nh t m t n Vì gi thi t d = (m1 , m2 ) là ư c b1 − b2 nên phương trình: b1 + m1 t ≡ b2 (mod m2 ) tương đương v i phương trình: m1 b2 − b1 m2 t≡ (mod ) d d d m1 m2 Nhưng ( , ) = 1 nên phương trình đ ng dư này cho ta d d m2 nghi m t ≡ t0 (mod ), là t p h p t t c các s nguyên d m2 n t = t0 + u, u ∈ Z d .v Thay bi u th c c a t vào bi u th c tính x ta đư c t p h p các giá tr c a x nghi m đúng c hai phương trình đ ng dư đang xét là: m2 x = b1 + m1 (t0 + d v i x0 = b1 + m1 t0 , m = BCN N (m1 , m2 ). 4 h u) = b1 + m1 t0 + m1dm2 u, hay x = x0 + mu đang xét. c 2 V y x ≡ x0 (mod m) là nghi m c a h hai phương trình đ ng dư o • Trư ng h p 2: H g m n phương trình. Đ u tiên gi i h hai phương trình nào đó c a h đã cho, r i thay trong h hai phương h trình đã gi i b ng nghi m tìm th y, ta s đư c m t h g m n − 1 i phương trình tương đương v i v i h đã cho. Ti p t c như v y sau n − 1 bư c ta s đư c nghi m c n tìm. V u Ví d 5.5. Gi i h phương trình: L i gi i. H hai phương trình:   x ≡ 26 (mod 36)   x ≡ 62 (mod 60) x ≡ 92 (mod 150)   x ≡ 11 (mod 231) x ≡ 26 (mod 36) x = 26 + 36t ⇔ , t ∈ Z. x ≡ 62 (mod 60) 26 + 36t ≡ 62 26 + 36t ≡ 62 (mod 60) ⇔ 36t ≡ 36 (mod 60) ⇔ t ≡ 1 (mod 5) Di n đàn Toán h c Chuyên đ S h c
5.3. H phương trình đ ng dư b c nh t m t n 93 V y nghi m c a h là: x ≡ 26 + 36.1 (mod 180) hay x ≡ 62 (mod 180) Do đó h phương trình đã cho tương đương v i h :  x ≡ 62 (mod 180) x ≡ 92 (mod 150) x ≡ 11 (mod 231)  Ví d 5.6. Gi i h phương trình n x ≡ 62 (mod 180) x = 62 + 180t ⇔ , t ∈ Z. x ≡ 92 (mod 150) 62 + 180t ≡ 92 (mod 150) L i gi i. Ta có: 62 + 180t ≡ 92 (mod 1)50) h .v 4 ⇔180t ≡ 30 (mod 150) ⇔6t ≡ 1 (mod 5) ⇔ t≡1 (mod 5) V y nghi m c a h là: x ≡ 62 + 180.(1+) c 2 (mod 900) ⇔ x ≡ 242 (mod 900) H đã cho tương đương v i: h o u i x ≡ 242 (mod900) x ≡ 11 (mod231) H này có nghi m x ≡ 242 (mod 69300) , và đây cũng là nghi m c a V h đã cho c n tìm. Ví d 5.7. Tìm s nguyên dương nh nh t th a tính ch t: chia 7 dư 5, chia 11 dư 7 và chia 13 dư 3. L i gi i. Ta có: n1 = 7; N1 = 11.13 = 143; n2 = 11; N2 = 7.13 = 91; n3 = 13; N3 = 7.11 = 77. Ta có N1 b1 ≡ 3b1 ≡ 1 (mod 7) → b1 = −2. Tương t b2 = 4; b3 = −1 V y a = 143(−2)5 + (91)(4)(7) + (77)(−1)(3) = −1430 + 2548 − 231 = 887 v y các s c n tìm có d ng b = 877 + 1001k. V y 877 là s c n tìm. Chuyên đ S h c Di n đàn Toán h c
94 5.3. H phương trình đ ng dư b c nh t m t n Ví d 5.8 (Ch n đ i tuy n KHTN). Xét h đ ng dư g m 3 phương trình: xy ≡ −1 (mod z) (5.1) yz ≡ 1 (mod x) (5.2) xz ≡ 1 (mod y) (5.3) Hãy tìm s b (x, y, z)nguyên dương phân bi t v i1 trong 3 s là 19. L i gi i. T ba phương trình, theo tính ch t đ ng dư ta l n lư t có . . . xy + 1. và yz − 1. và zx − 1. Suy ra .z .x .y .v n h . (xy + 1)(yz − 1)(zx − 1). .xyz 4 . ⇒x2 y 2 z 2 − x2 yz − xy 2 z + xyz 2 + xy − yz − zx + 1. .xyz 2 . ⇒xy − yz − zx + 1. .xyz zx + 1 ≤ 2xyz o c Nh n th y do x, y, z nguyên dương cho nên xyz ≥ 1. Suy ra xy − yz − h M t khác yz + zx − xy − 1 ≤ 2xyz ⇒ −(yz + zx − xy − 1) ≥ −2xyz i Do đó ta có b t phương trình kép −2xyz ≤ xy − yz − zx + 1 ≤ 2xyz . Mà xy−yz−zx+1. .xyz ⇒ xy−yz−zx+1 = 2xyz, 1xyz, 0, −1xyz, −2xyz V u • Trư ng h p 1: xy − yz − zx + 1 = 2xyz ⇒ xy ≡ −1 (mod z), yz ≡ 1 (mod x), zx ≡ 1 (mod y) Cho nên ta ch c n tìm nghi m c a xy − yz − zx + 1 = 2xyz là xong. Vì x, y, z có m t s b ng 19 nên ta thay l n lư t vào. N u x = 19 ⇒ 19y − yz − 19z + 1 = 38yz ⇒ 39yz − 19y + 19z = 1 ⇒ (39y + 19)(39z − 19) = −322 V i y = 19 ho c z = 19 thì tương t . • Trư ng h p 2,3,4,5: xy−yz−zx+1 = 1xyz, 0, −1xyz, −2xyz làm hoàn toàn tương t , ta đ y đư c v phương trình có d ng au+bv = ab+uv+x v i x là h ng s . Đưa v (a − v)(b − u) = x và gi i ki u phương trình ư c s . Bài toán hoàn t t. Di n đàn Toán h c Chuyên đ S h c
5.4. B c c a phương trình đ ng dư 95 Nh n xét. Bài toán này mà không cho đi u ki n m t s b ng 19 thì không đưa đư c d ng au + bv = ab + uv + x ↔ (a − v)(b − u) = x lúc đó suy ra vô h n nghi m. 5.4 B c c a phương trình đ ng dư Đ nh nghĩa 5.3 Xét phương trình đ ng dư f (x) = 0 (mod m) v i f (x) = a0 xn + a1 xn−1 + ... + an , ai ∈ N, i = 0, 1, ..., n đ ng dư. .v n N u a0 không đ ng dư 0 (mod m) thì ta nói n là b c c a phương trình Ví d 5.9. Xác đ nh b c c a phương trình 15x6 − 8x4 + x2 + 6x + 8 ≡ 0 h (mod 3) 4 L i gi i. Ta th y 15 ≡ 0 (mod 3) nên b c c a phương trình không ph i là b c 6. Phương trình trên tương đương v i −8x4 + x2 + 2 ≡ 0 (mod 3) 2 Vì −8 ≡ 0 (mod 3) nên b c phương trình là n = 4. c 5.5 Bài t p h o i Bài 1. Gi i các phương trình sau: a) 7x ≡ 6 (mod 13) b) (a + b)x ≡ a2 + b2 (mod ab) v i (a, b) = 1 c) 17x ≡ 13 (mod 11) d) x2 + u x − 2 ≡ 1 (mod 3) V   x≡1  (mod 3) x≡4 (mod 4)  Bài 2. Gi i các h phương trình: a)  x≡2  (mod 7) x≡9 (mod 11)    5x ≡ 1 (mod 12) b) 5x ≡ 2 (mod 8) 7x ≡ 3 (mod 11)  Bài 3. Tìm a nguyên đ h phương trình sau có nghi m Chuyên đ S h c Di n đàn Toán h c
96 5.6. ng d ng đ nh lý Euler đ gi i phương trình đ ng dư   x ≡ 3 (mod 3)  x ≡ 1 (mod 4)  a)  x ≡ 11 (mod 7)  x ≡ a (mod 11)  2x ≡ a (mod 3) b) 3x ≡ 4 (mod 10) Bài 4. M t l p g m 40 h c sinh đ ng thành vòng tròn và quay m t n và trong vòng tròn đ chơi bóng. M i h c sinh nh n đư c bóng ph i ném qua m t 6 b n bên tay trái mình. Ch ng minh r ng .v t t c h c sinh trong l p đ u nh n đư c bóng ném t i mình sau 40 l n ném bóng liên ti p. 5.6 h ng d ng đ nh lý Euler đ gi i phương trình đ ng dư 4 c 2 Qua bài vi t này tôi xin gi i thi u m t phương pháp đ gi i phương trình đ ng dư b ng cách khai thác đ nh lý Euler o Trư c h t, xin nh c l i vài ki n th c quen thu c. h u i Đ nh nghĩa 5.4 Hàm Euler ϕ(m) v i s nguyên dương m là các s t nhiên nh hơn m là các s nguyên t v i m. 5.6.1 V Đ nh lý Euler. Đ nh lý 5.1 (Euler)– Cho m là s nguyên dương và (a, m) = 1 thì aϕ(m) ≡ 1 (mod m) Hàm ϕ có tính ch t sau: • ϕ(mn) = ϕ(m)ϕ(n) v i (m; n) = 1 • N u p nguyên t ϕ(p) = p − 1; ϕ(pn ) = pn − pn−1 (n > 1) Di n đàn Toán h c Chuyên đ S h c
5.6. ng d ng đ nh lý Euler đ gi i phương trình đ ng dư 97 k • N u m = pα1 pα2 ...pα , pi là các s nguyên t thì 1 2 k 1 1 1 φ(m) = m 1 − 1− ... 1 − p1 p2 pk Bây gi ta xét m = a.b trong đó (a; b) = 1 thì có các k t qu sau Đ nh lý 5.2– aϕ(b) + bϕ(a) ≡ 1 (mod ab) (5.4) Ch ng minh. Theo đ nh lý Euler ta có: aϕ(b) ≡ 1 (mod b) mà bϕ(a) ≡ 0 (mod b) Nên aϕ(b) + bϕ(a) ≡ 1 (mod b). Tương t ta có:aϕ(b) + bϕ(a) ≡ 1 (mod a) .v n Theo tính ch t đ ng dư thì : aϕ(b) + bϕ(a) ≡ 1 (mod ab) Đ nh lý 5.3– Gi s có k(k ≥ 2) s nguyên dương m1 ; m2 ; . . . mk và 4 h 2 chúng nguyên t v i nhau t ng đôi m t. Đ t M = m1 .m2 . . . mk = mi ti v i i = 1, 2, 3. . . , k ta có t1 ϕ(m1 ) ϕ(m2 ) + t2 o + ... + tk c ϕ(mk ) ≡1 (mod M ) Ch ng minh. T gi thi t ta có (mi , ti ) = 1 v i m i i = 1, 2, . . . , k nên (5.5) i theo đ nh lý Euler thì h u ϕ(m1 ) t1 ≡1 (mod mi ) (5.6) M t khác v i i; j thu c t p 1;2;. . . ;k và i = j thì tj chia h t cho mj V nên (tj ; mi ) = mi hay ϕ(m ) ϕ(m ) Đ t S = t1 1 + t2 2 + ... + tk k ϕm ϕ(mi ) tj ≡0 ϕ(m ) (mod mi ) (5.7) T (5.6) và (5.7) có S ≡ ti i ≡ 1 (mod mi ) Vì m1 ; m2 ; . . . mk nguyên t v i nhau t ng đôi m t, nên theo tính ch t đ ng dư th c có S − 1 ≡ 0 (mod m1 .m2 ...mk ) ⇔ S ≡ 1 (mod M ), t c là có (5.5). Chuyên đ S h c Di n đàn Toán h c
98 5.6. ng d ng đ nh lý Euler đ gi i phương trình đ ng dư Khi m r ng (5.4) theo hư ng nâng lên lũy th a các s h ng ta có k t qu sau. Đ nh lý 5.4– V i (a, b) = 1 và n, v là hai s nguyên dương nào đó thì anϕ(b) + bvϕ(a) ≡ 1 (mod ab) (5.8) Ch ng minh. Đ ti n l p lu n đ t x = aϕ(b) . Theo đ nh lý Euler thì x = aϕ(b) ≡ 1 (mod b) ⇔ x − 1 ≡ 0 (mod b) Đ ng th i x = aϕ(b) ≡ 0 (mod a). T đó có x(x−1) ≡ 0 (mod a) và x(x−1) ≡ 0 (mod b) nên x(x−1) ≡ 0 (mod ab) T đó x3 ≡ x2 .x ≡ x.x ≡ x2 ≡ x (mod ab) và c l p lu n như th có xn ≡ x (mod ab) hay anϕ(b) ≡ aϕ(b) (mod ab) .v n h Tương t ta có: bvϕ(a) ≡ bϕ(a) (mod ab) nên theo (5.4) có anϕ(b) + bvϕ(a) ≡ bϕ(a) + aϕ(b) ≡ 1 (mod ab). (5.8) đư c ch ng minh. 2 H qu 5.1– V i (a; b) = 1 thì anϕ(b) + bnϕ(a) ≡ 1 (mod ab) 4 c H qu này có th ch ng minh tr c ti p khi nâng hai v c a h th c (5.4) lên lũy th a b c n (s d ng khi tri n nh th c Newton) và chú ý (mod ab)! h o r ng ab ≡ 0 (mod ab). Nên lưu ý r ng trong đ ng dư th c thì a ≡ 0 u i V i kí hi u như đ nh lý 5.3 ta có ti .tj ≡ 0 (mod M ) v i i khác j và m i i; j thu c t p 1,2,...,k (nhưng t ≡ 0 (mod M ) v i m i i = 1, 2, 3, ...k) T đó khi nâng hai v c a (5.5) lên lũy th a b c n ta có k t qu sau. V Đ nh lý 5.5– V i các gi thi t như đ nh lý 5.3 ta có: nϕ(m1 ) t1 + t2 nϕ(m2 ) + ... + tk nϕ(mk ) ≡1 (mod M ) V i các kí hi u như trên ta đ t a = mi và b = ti thì theo (5.4) có (5.9) nϕ(ti ) nϕ(mi ) mi + ti ≡1 (mod M ) (5.10) C ng t ng v c a k đ ng th c d ng (5.10) và s d ng (5.5) ta đư c k t qu sau: Di n đàn Toán h c Chuyên đ S h c
5.6. ng d ng đ nh lý Euler đ gi i phương trình đ ng dư 99 Đ nh lý 5.6– V i các gi thi t đ nh lý 5.3 ta có: ϕ(t1 ) ϕ(t2 ) nϕ(tk ) m1 + m2 + ... + mk ≡k−1 (mod M ) (5.11) Khi nhân 2 v c a (??) v i mi ta đư c 1+ϕ(ti ) ϕ(mi ) m1 + mi .ti + ≡ mi (mod M ) (5.12) ϕ(mi ) ϕ(mi )−1 (mi )−1 Do mi .ti = mi .ti .ti = M.ti nên mi 1+ϕ(t1 ) ≡ mi C ng t ng v k đ ng th c d ng (5.13) ta đư c k t qu sau: (mod M ), i = 1, k .v n (5.13) Đ nh lý 5.7– V i các gi thi t như đ nh lý 5.3 ta có: m1 1+ϕ(t1 ) + m2 2+ϕ(t2 ) + ... + mk 1+ϕ(tk ) 4 h ≡ m1 + m2 + ... + mk (mod M ) Khi nhân 2 v c a (5.10) v i ti ta đư c c 2 (5.14) 1+ϕ(t1 ) m1 + 2+ϕ(t2 ) m2 + ... + h o 1+ϕ(tk ) mk ≡ m1 + m2 + ... + mk (mod M ) (5.15) u i ⇒ ti 1+ϕ(mi ) ≡ ti C ng t ng v c a k đ ng dư d ng (5.16) ta đư c k t qu sau Đ nh lý 5.8– V i các gi thi t như đ nh lý 5.3 ta có: (mod M ), i = 1, k (5.16) t1 V 1+ϕ(m1 ) +t2 1+ϕ(m2 ) +...+tk 1+ϕ(mk ) ≡ t1 +t2 +...+tk Chú ý r ng ti .tj ≡ 0 (mod M ) nên khi nâng lên lũy th a b c n c a t ng t1 + t2 + ... + tk ta có k t qu sau. (mod M ) (5.17) Đ nh lý 5.9– V i các gi thi t như đ nh lý 5.3 ta có: tn + tn + ... + tn ≡ (t1 + t2 + ... + tk )n 1 2 k (mod M ) (5.18) Chuyên đ S h c Di n đàn Toán h c
100 5.6. ng d ng đ nh lý Euler đ gi i phương trình đ ng dư Kh năng tìm ra các h th c đ ng dư m i chưa ph i đã h t m i b n đ c nghiên c u thêm. Đ n m rõ đư c nh ng ph n trên ta tìm hi u qua m t s ví d sau đây. Ví d 5.10. Tìm ít nh t b n nghi m c a phương trình đ ng dư: x3 + y 7 ≡ 1 (mod 30) (5.19) L i gi i. Do 30 = 5.6 và (6; 5) = 1 nên theo (5.4) có 5ϕ(6) + 6ϕ(5) ≡ 1 (mod 30) vì ϕ(6) = ϕ(2).ϕ(3) = 2 và ϕ(5) = 4; 62 ≡ 6 (mod 30). .v Tương t ta có: 257 ≡ 25 (mod 30) và 63 ≡ 6 (mod 30) nên 63 + 257 ≡ 26 + 6 ≡ 1 (mod 30) n h N u phân tích 30 = 3.10 v i (3; 10) = 1 thì theo (5.4) có 3ϕ(10) +10ϕ(3) ≡ 1 (mod 30). Tính toán tương t như trên ta có 34 + 102 ≡ 1 (mod 30). 4 Vì 34 = 81 ≡ 21 (mod 30) và 102 ≡ 10 (mod 30) nên theo (5.8) có (34 )3 + (102 )7 ≡ 1 (mod 30) và (34 )7 + (102 )3 ≡ 1 (mod 30) 2 Suy ra phương trình trên có ít nh t b n nghi m (x; y) là (25; 6); (6; 25); c (21; 10); (10; 21). o Ví d 5.11. Ch ng minh r ng phương trình đ ng dư sau có nghi m (x; y; z; t) khác (0; 0; 0; 0): i h x4 + y 4 + z 4 + t 4 ≡ t 3 (mod 60). u L i gi i. 60 = 3.4.5 và (5; 3) = 1; (5; 4) = 1; (3; 4) = 1 nên đ t m1 = 3; m2 = 4; m3 = 5; t1 = 15; t2 = 1; t3 = 20 theo (5.18) V 15 + 12 + 204 ≡ (15 + 20 + 12)4 ≡ 1 4 4 (mod 60) Ví d 5.12. Tìm ít nh t m t nghi m c a phương trình đ ng dư x17 + y 19 ≡ 1 (mod 35) 7 5 L i gi i. Ta có: 35 = 5.7 mà (5; 7) = 1 nên theo (5.4): 5ϕ + 7ϕ ≡ 1 (mod 35)) Vì ϕ(5) = 4; ϕ(7) = 6 nên 54 + 76 ≡ 1 (mod 35) Theo (5.8): 1417 + 3019 ≡ 14 + 30 ≡ 1 (mod 35) V y phương trình đ ng dư có ít nh t m t nghi m (x; y) = (14; 30) Di n đàn Toán h c Chuyên đ S h c
5.7. Bài t p 101 5.7 Bài t p Bài 1. Ch ng minh r ng phương trình đ ng dư sau có nghi m (x; y; z; t) khác (0; 0; 0; 0): a) x3 + y 3 + z 3 ≡ t3 (mod 210) b) x5 + y 5 + z 5 ≡ t5 (mod 1155) Bài 2. Tìm ít nh t m t nghi m c a phương trình đ ng dư sau: x11 + y 13 ≡ 1 (mod 45) .v n Bài 3. Ch ng t r ng m i phương trình sau có nghi m nguyên dương. a) 2x + 3y + 5z + 7t ≡ 3 (mod 210) b) 3x + 5y + 7z ≡ 2 (mod 105) 4 h c 2 h o u i V Chuyên đ S h c Di n đàn Toán h c