intTypePromotion=3

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

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

1
434
lượt xem
93
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. 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
  2. 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
  3. 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
  4. 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. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản