Chuyên đề Áp dụng Lí thuyết đồng dư trong một số dạng toán về phép chia hết và phép chia còn dư

Chuyªn ®Ò: ¸p dông LÝ thuyÕt ®ång d­ trong mét sè d¹ng to¸n vÒ phÐp chia hÕt vµ phÐp chia cßn d­. I) LÝ thuyÕt vÒ ®ång d­ : 1) §Þnh nghÜa: NÕu hai sè nguyªn a vµ b khi chia cho c (c ¹ 0) mµ cã cïng sè d­ th× ta nãi a ®ång d­ víi b theo m«®un c; kÝ hiÖu lµ a º b (mod c). Nh­ vËy: a º b (mod c) a – b chia hÕt cho c. HÖ thøc cã d¹ng: a º b (mod c) gäi lµ mét ®ång d­ thøc, a gäi lµ vÕ tr¸i cña ®ång d­ thøc, b gäi lµ vÕ ph¶i cßn c gäi lµ m«®un. 2) Mét sè tÝnh chÊt: KÝ hiÖu a; b; c; d; m; lµ c¸c sè nguyªn d­¬ng (Z+), ta lu«n cã: a) TÝnh chÊt 1: * a º a (mod m); * a º b (mod m) Û b º a (mod m); * a º b (mod m) vµ b º c (mod m) th× a º c(mod m); b) TÝnh chÊt 2: NÕu a º b (mod m) vµ c º d (mod m) th×: * a ± c º b ± d (mod m); * ac º bd (mod m); * NÕu d lµ mét ­íc chung cña a; b; m th×: º (mod ); c) TÝnh chÊt 3: NÕu a º b (mod m) vµ c Î Z+ th× ac º bc (mod mc). 3) Mét sè kiÕn thøc liªn quan: Trong khi lµm bµi tËp sö dông ®ång d­ thøc, ta nªn chó ý tíi c¸c tÝnh chÊt hay dïng sau ®©y: * Víi mäi a, b Î Z+ (a ¹ b) vµ n lµ sè tù nhiªn: an – bn a – b; * Trong n sè nguyªn liªn tiÕp (n ³ 1) cã mét vµ chØ mét sè chia hÕt cho n; * LÊy n + 1 sè nguyªn bÊt k× (n ³ 1) ®em chia cho n th× ph¶i cã hai sè khi chia cho n cã cïng sè d­; (Theo nguyªn lÝ §irichlet); * T×m m ch÷ sè tËn cïng cña sè A lµ t×m sè d­ khi chia A cho 10m; II) Mét sè vÝ dô minh ho¹ sö dông ®ång d­ : D¹ng 1: T×m sè d­ trong mét phÐp chia Ph­¬ng ph¸p: Muèn t×m sè d­ trong phÐp chia sè A cho m, ta ph¶i t×m ®­îc sè x (0 x < m) sao cho A º x (mod m). VÝ dô: T×m sè d­ trong phÐp chia sè 19932000 cho sè 3 ? Gi¶i Ta cã: 1993 º 1 (mod 3) Þ 19932000 º 12000 (mod 3) º 1 (mod 3) VËy: sè 19932000 khi chia cho 3 th× d­ 1. D¹ng 2: T×m dÊu hiÖu chia hÕt cho c¸c sè nhá Ph­¬ng ph¸p: §Ó t×m dÊu hiÖu cña sè A chia hÕt cho m th× ta t¸ch sè A hîp lý ®Ó ®­îc mét biÓu thøc ®¬n gi¶n nhÊt cña c¸c ch÷ sè cña A lµ f(A) sao cho A º f(A) (mod m). VÝ dô: T×m dÊu hiÖu chia hÕt cho 3 ? Gi¶i XÐt sè tù nhiªn cã n + 1 ch÷ sè: A = Ta cã: A = º r (mod 3) (1) Û an.10n + an-1.10n-1 + + a1.101 + a0 º r (mod 3) Û (an. + an) + (an-1. + an-1) + + (a1.9 + a1)+ a0 º r (mod 3) Û (an. + an-1. + + a1.9) + (an + an-1 + + a1+ a0) º r (mod 3) NhËn xÐt: an. + an-1. + + a1.9 º 0 (mod 3) Nªn: (an + an-1 + + a1+ a0) º r (mod 3) (2) VËy: A = º an + an-1 + + a1+ a0 (mod 3) Hay: A = khi chia cho 3 cã cïng sè d­ khi chia tæng c¸c ch÷ sè cña A cho 3. Tõ ®ã: A chia hÕt cho 3 Û tæng c¸c ch÷ sè cña A chia hÕt cho 3. D¹ng 3: chøng minh sù chia hÕt Ph­¬ng ph¸p: §Ó chøng minh sè A chia hÕt cho m, ta ®i chøng minh A º 0 (mod m). VÝ dô 1: Chøng minh r»ng sè A = 22225555 + 55552222 chia hÕt cho 7 ? Gi¶i NhËn xÐt: 2222 º 3 (mod 7) (1) Tõ ®ã: 22224 º 34 (mod 7) hay 22224 º 81 (mod 7) Mµ 81 º 4 (mod 7) Þ 22224 º 4 (mod 7) (2) Nh©n vÕ víi vÕ (1) vµ (2) ta ®­îc 22225 º 3.4 (mod 7) Hay lµ: 22225 º 5 (mod 7) Þ 22225555 º 51111 (mod 7) (3) T­¬ng tù ta cã: 55552222 º 21111 (mod 7) (4) Céng vÕ víi vÕ (3) vµ (4) ta cã: A º 21111 + 51111 (mod 7) (5) MÆt kh¸c: 21111 + 51111 = (2 + 5).M = 7.M º 0 (mod 7) (6) Tõ (5) vµ (6) ta ®­îc: A º 0 (mod 7) VËy: A = 22225555 + 55552222 chia hÕt cho 7. VÝ dô 2: Chøng minh r»ng víi mäi sè tù nhiªn n th× sè B = 42n+1 + 3n+2 lu«n chia hÕt cho 13 ? Gi¶i NhËn xÐt 1: 42 = 16 º 3 (mod 13) Þ (42)n º 3n (mod 13) Þ 42n º 3n (mod 13) Mµ 4 º 4 (mod 13) Þ 42n+1 º 4.3n (mod 13) Hay 42n+1 º 4.3n (mod 13) (1) NhËn xÐt 2: 32 = 9 º - 4 (mod 13) mµ 3n º 3n (mod 13) Tõ ®ã Þ 32.3n º - 4.3n (mod 13), hay lµ: 3n+2 º - 4.3n (mod 13) (2) Tõ (1) vµ (2), céng vÕ víi vÕ, ta ®­îc B º 0 (mod 13). NghÜa lµ B = 42n+1 + 3n+2 lu«n chia hÕt cho 13 víi mäi n Î N. VÝ dô 3: Chøng minh r»ng víi mäi sè nguyªn n > 1: §a thøc A = nn – n2 + n – 1 lu«n chia hÕt cho ®a thøc B = (n – 1)2 ? Gi¶i NhËn xÐt 1: Víi n = 2 th× A = 1, B = 1, râ rµng A chia hÕt cho B. Víi n > 2, ta biÕn ®æi A nh­ sau: A = nn – n2 + n – 1 = n2(nn-2 - 1) + (n - 1) = n2(n - 1)(nn-3 + nn-4 + + 1) + (n - 1) = (n – 1)(nn-1 + nn – 2 + + n2 + 1) NhËn xÐt 2: n º 1 (mod n – 1) Þ nk º 1 (mod n – 1), " kÎN Tõ ®ã: nn-1 + nn-2 + + n2 º n – 2 (mod n – 1) Nªn: nn-1 + nn – 2 + + n2 + 1 º n – 1 (mod n – 1) Hay: nn-1 + nn – 2 + + n2 + 1 º 0 (mod n – 1) (1) Nªn: (n – 1)(nn-1 + nn – 2 + + n2 + 1) º 0 (mod (n – 1)2) Hay: A = (n – 1)(nn-1 + nn – 2 + + n2 + 1) chia hÕt cho (n – 1)2. VËy: A = nn – n2 + n – 1 lu«n chia hÕt cho ®a thøc B = (n – 1)2. D¹ng 4: t×m c¸c ch÷ sè tËn cïng cña mét sè lín Ph­¬ng ph¸p: T×m m ch÷ sè tËn cïng cña sè A lµ t×m sè d­ khi chia A cho 10m. VÝ dô 1: T×m ch÷ sè tËn cïng cña sè A = ? Gi¶i Ta cã: A = = 281 = 24.20 + 1 = 2.(24)20 = 2.1620 NhËn xÐt: 16 º 6 (mod 10) Þ 1620 º 620 (mod 10) Tõ ®ã: 1620 º 6 (mod 10), mµ 2 º 2 (mod 10) Nªn: 2.1620 º 6.2 (mod 10) Þ 2.1620 º 2 (mod 10) VËy A chia cho 10 d­ 2 hay lµ A cã ch÷ sè tËn cïng lµ 2. VÝ dô 2: T×m s¸u ch÷ sè tËn cïng cña sè B = 521 ? Gi¶i NhËn xÐt: B = 515 = 53.5 = 1255 º (-3)5 (mod 26) Hay 515 º 13 (mod 26) Þ 515.56 º 13.56 (mod 26.56) Hay lµ: B = 521 º 13.15625 (mod 106) Û B º 203125 (mod 106) VËy B chia cho 106 d­ 203125, nªn B cã 6 ch÷ sè tËn cïng lµ 203125. III) Bµi tËp rÌn kÜ n¨ng vËn dông: D¹ng 1: T×m sè d­ trong mét phÐp chia Bµi 1: T×m sè d­ trong phÐp chia sè A = 15325 – 1 khi chia cho 9 ? (§S: 4) Bµi 2: Cho sè nguyªn n > 1. T×m d­ trong phÐp chia: A = 19nn + 5n2 + 1890n + 2006 cho B = n2 – 2n + 1 ? D¹ng 2: T×m dÊu hiÖu chia hÕt cho c¸c sè nhá Bµi 3: T×m dÊu hiÖu chia hÕt cho c¸c sè tù nhiªn 3; 4; 5; 6; 7; 8; 9; 10; 11 ? Bµi 4: T×m dÊu hiÖu chia hÕt cho 21 cña mét sè tù nhiªn cã 3 ch÷ sè ? §S: a – 2b + 4c chia hÕt cho 21. D¹ng 3: chøng minh sù chia hÕt Bµi 5: Cho n lµ mét sè tù nhiªn. Chøng minh r»ng: 3n + 1 chia hÕt cho 10 Û 3n+4 + 1 chia hÕt cho 10 ? Bµi 6: Cho n lµ mét sè nguyªn d­¬ng. Chøng minh r»ng: A = 24n – 1 chia hÕt cho 15; B = 25n – 1 chia hÕt cho 31; C = + 1 chia hÕt cho 641; D = 62n + 19n – 2n+1 chia hÕt cho 17; E = 7.52n + 12.6n chia hÕt cho 19; F = 5n+2 + 26.5n + 82n+1 chia hÕt cho 59. Bµi 7: Chøng minh r»ng: Víi mäi sè tù nhiªn n > 0, ta lu«n cã: 52n-1.2n+1 + 3n+1.22n-1 chia hÕt cho 38 ? Bµi 8: Chøng minh r»ng: a) A = + + chia hÕt cho 102 ? b) B = chia hÕt cho 7 ? Bµi 9: Cho n lµ sè tù nhiªn. Chøng minh r»ng: Sè M = 212n+1 + 172n+1 + 15 kh«ng chia hÕt cho 19 ? Bµi 10: Chøng minh r»ng víi mäi sè nguyªn n > 1 ta lu«n cã: A = nn + 5n2 – 11n + 5 chia hÕt cho (n – 1)2 ? Bµi 11: Cho a; b lµ c¸c sè nguyªn. Chøng minh r»ng: 2a + 11b chia hÕt cho 19 Û 5a + 18b chia hÕt cho 19 ? D¹ng 4: t×m ch÷ sè tËn cïng cña mét sè lín Bµi 12: T×m ch÷ sè tËn cïng cña sè: A = ? (§S: 1) Bµi 13: T×m ch÷ sè tËn cïng cña sè: B = ? (§S: 6) Bµi 14: T×m 4 ch÷ sè cuèi cïng cña sè C = ? (§S: 0000)