Hoang Ngoc Tuit Tgp chi KHOA HQC & CONG NGHE 135(05): 57-60
DONG D l T T H i r c VA I T N G DUNG TRONG VIEC CHtTNG MINH TINH CHIA HET VA TIM SO DLT CUA PHEP CHIA
Hoang Ngoc Tuat' Truang Dai hoc Khoa hoc - DH Thdi \giiyen TOM TAT
Trong bai bao nay chung toi cung cap mgt so iing dung ciia ly thuyet ddng du trong viec chiing minh cac bai toan ve quan he chia het, tim so du cua mgt phep chia va lim cac chtt so tan cung cua mgt s6 ty nhien dang a". Cac vin di nay hoin toan hOu ich cho cac sinh vien dang theo hoc ng^nh toan cung nhu cho cac giao vien day toan trung hoc pho thdng
TJrkh6a: Ddngdu. mddun. chiaheicho. chiacddu, sdnguyen. sdnrnhien, chitsd DAT VAN DE
Ddng du thuc la mgt trong nhirng ndi dung quan trpng ciia hpe phan Ly thuyet sd trong chuong trinh dao tao cir nhan Toan hpc. De sinh vien va giao vien Toan cd them nh&ng ung dyng ve ly thuyet ddng du, trong bai viet nay chiing tdi dua ra mdt vai ung dung ciia ly thuyet ddng du trong viec chung minh cac ti'nh chit chia hit va tim sd du cua cac phep chia.
Khai niem dong dir thiJc [5]
Hai sd nguyen a va b gpi la ddng du theo modun m, m e N , neu a - b chia het cho m hay a va b khi chia cho m cd cimg mgt sd du.
Ki hieu: a = b (mod m) la a ddng du b theo modun m
Mot so tinh chat [3]:
- Neu a s h (mod m) ^:> a = mq + r va b = mqi + r, vdi 0 < r < b.
- Niu a, = b| (mod m), i = 1,2,..., n.
=>ai+a)+.„-i-^=bi+b2+...+b|,(modm).
-Neua, = b, (mod m), i = 1, 2,..., n
=> a|.a2... a„ = b|.b3..,b„ (mod m).
- Neu a s h (mod m)
=> a" = b" (mod m),
- Neu a = b (mod m) va d la udc chung duong ciia a, b. m
- Djnh ly Ole [2]: Neu a e Z, m e N , (a, m)= l.thia'^""^ I (mod m)_.
He qua (Dinh iy Fermat) [2]: Neu p la mgt sd nguyen td, thi mgi so nguyen a khdng chia het cho p ta cd a''"' = I (mod p).
MOT SO U"NG DUNG TRONG VIEC CHLTNG M I N H TiNH CHIA HET VA T I M SO DU" TRONG PHEP CHIA
Chung minh tinh chia het:
Vdi a, b e 2. b Ti 0, ta ndi a chia hit cho b, niu tdn tgi q e Z sao cho a = bq.
Ky hieu a chia het cho b bdi a ! b.
Tir dinh nghTa tren ta cd a i b
<=> a s O (mod b).
Vi du 1: Chiing minh rang vdi mgi sd ty nhien n > 1, thi:
3" + 2 chia het cho 11.
Giai
T a c d ( 3 , l l ) = l z^3''""'= 1 (mod 11) c:>3"'^l (mod II);
Vi (2,5) = I : •)(i>ii) ^ 1 «» 2*" = 1 (mod 5) --
Tel 0974 2S6206
2*" = I (mod 5) => 2''"^' ~ 2 (mod 10) ^ 2^"^'
= lOk + 2
Tacd: 3'^''*-= 3-(mod II) hay 3'*^^ = 9 (mod II)
^ 3 " " - ^ ' + 2 s 0 ( m o d 11), nghTa la 3 ""-^--H 2 : II Vay 3~ + 2 chia het cho 11.
Vi du 2; Chiirng minh rang:
: 2 Q " ' ' ' + 1 1 9 = ' " " ' + 6 9 - - ' - " " " ' chia hit cho 102. [1]
Giai Ta cd:
220 = 0 (mod 2); 220 = I (mod 3);
220 =-I (mod 17);
119^ 1 (mod 2); 119 =-I (mod 3);
119 = 0(mod 17);
69 = 1 (mod 2); 69 = 0 (mod 3);
69 = I (mod 17).
Giai
Vi p nguyen t6, p > 3 => (2, p) = 2"'^ = 1 (mod p).
=^2"-
Ta CO 4C2**"
3
= > n - l
=>2^'-
^ = 1 (mod 3p) hay 2"' 2 = ? - l n 1
3 '-'-1) <2''->-l)(2!'-
3 : 2 p = > 2 " - ' - I ! 2 * - l 1 : n => 2" - 2 :• n
- 1 _
1=
, vi I l 3 p
3
n = — Hoang Ngoc Tuii Tap clii KHOA HOC & CONG NGHE 135(05): 57-60 Tir do 2 2 0 ^ - ' ' = 0 (mod 2): Chiing minli ring: 2 " - 2 In
119°'"'°= I (mod 2 ) : 6 9 - ' ° " " s j (mod 2).
2 2 0 ' " " + 1 1 9 " = " + 6 9 ^ = ' " ' = 0 (mod M^Uhac 2'^^'="i (mod 3) 2 2 0 - - ' ° ' « l (mod 3);
119°'""°=-I (mod 3 ) ; 6 9 - - - ' " " = 0 (mod 3)
2 2 0 " 5 " + 1 1 9 = ' " " ' + 6 9 - : ' ' " = 0 (mod 3) (2)
:::-U--'"»-l (mod 17);
119 '^'•-'s 0 (mod 17) • Cac bai tuffn^ tir:
6 9 " f ' " ' " = l ( m o d l 7 ) Chu-ng minh rang: [1]
2 : o " 5 " + i i 9 « = - + 6 9 : : c - ' ^ 0 (mod 17) " ^ . . . - .
(3) 2 ) 2 - +21 chia het cho 37.
TCr(l),(2),(3)taco ^ _ 3) 7 " " " ' - F 4 ^ - ' ^ ^ ' - 6 5 220 • + 1 1 9 " + 6 9 — - 0 ( m o d l 0 2 ) chiahftcho 100.
Vay 22C'--'" + 1 1 9 ' ' " ° + 65="""' chia 1''™ *° dirtrong phep chia [4]
ll*' ">"' '02. Cho a, b e Z, b * 0, de tim so du trong phep Vi du 3: Chu-ng minh ring 9'°° 9»' chia "^l" f "'"? ''^° '°' ' " "^'^ a = bq + r, voi 0 < r het cho 100. [ 1) < I b [. Bieu nay tuong duong:
Giai f" = '" ' • ' " ° " *>) Tac69«™ = 9 ' = l ( m o d l 0 ) ' i-<r<'b
=> 9' = 1 (mod 10) ^ 9 ' = 9 (mod 10) I ' W^ "^'"^ ^°± ^'°"i P^P ^^'^
=>9'=10k + 9 ^ 9 ' ' = o » . ' 2012-°" + 2013-'°"+ 20I4^»" cho 13 1)2^ '" ' + 19 chia hjt cho 23.
V i 9 ' ° = l (mod 100) = 9 " - ' . Giai
Tacd2012 =-3 (mod 13)
o C r J ' r T 2013=.2(m"odl3)
=> 9'°'*'= 9'(mod 100),
do 9 ' . 89 (mod 100) 2 0 1 4 . - 1 (mod 13) +) (2012,13)=
9(modl00) =3 2 0 l 2 « " l . l ( n , o d l 3 ) hay? a 89 (mod 100) (1). =5 2012"= 1 (mod 13)
^'V^^i'^ = > 2 0 1 2 ™ ' = l ( m o d l 3 ) 9 ' ' = 9 " ' - ' = 9 " (mod 100) =5 2 0 1 2 - " . 2 0 1 2 ' ( m o d 13).
. i 9 " , , ( m o d l 0 0 ) '' Vi 2 0 1 2 . - 3 (mod ,3)
=59" = 9'(mod 100) ^ 2012'.(-3)'(mod 13), vi 9 ' . 89 (mod 100) vi (-3) = l(mod 13)
„,=• = > 2 0 I 2 ^ » " . - I ( m o d l 3 ) (I).
= > ' a 89 (mod 100) (2). +) (2013, 13) = 1 Tir(l)va(2)tac6: => 2013«'"= I (mod 13)
9 ' ' ' - 9 ' ' ; i O C = > 2 0 1 3 ' ' = l ( m o d l 3 ) V i ^ h o p . m o . . 6 n g „ y . „ „ p > 3 . „ Z ^ : ^ V ^ I Z d . ^ ,
3 Vi 2 0 1 3 . - 2 (mod 13)
=3 2013 " = (-2)"'(mod 13), 58
Hoing Nggc Tuit Tap chi KHOA HOC & CONG NGHE 135(05): 57-60 (-2)"'= 10 (mod 13) Ta CO (3,100)= 1 : i 1 (mod 1 0 0 ) 0 O20I3-'' s 10 (mod 13) (2).
+) (2014, 13) = 1
=>2014'i'"'. 1 (mod 13)
^ 2 0 1 4 ' - . 1 (mod 13)
^ 2 0 1 4 - ° ° " . 1 (mod 13)
=5 2 0 1 4 ' ° " . 2 0 1 2 " ( m o d 1 3 ) . Vi 2014=1-1 (mod 13)
=> 2 0 1 4 " . ( - 1 ) " (mod 13), (-1)"=-1 (mod 13)
^ 2 0 1 4 - ° " . - 1 (mod 13) (3).
Tir(1),(2),(3)tac6
2012™'+2013™'+2014"" . 8 (mod 13) Vay so du ciia so
2012'°"+ 2013™*+ 2014'°"
chia cho 13 la 8.
Chirng minh la hop so
De chirng minh mpt so tu nhien la mpt hgp so, ta tim each chung minh s6 d6 chia h€t cho mot so nguyen Ion hon 1 nao do.
Vi du: Chungminhiang 2^ ' +31ahgps6 Giai
Ta thay 2'*"""+ 3 > 11, do vay 2 ' " * ' + 3 CO the la boi ciia 11.
Tathay (2. 11)= 1 ^ 2 " " " = 1 (mod l l ) o 2 ' ° . 1 (mod 11).
Mat khac ta co 3* = 1 (mod 10)
=> 3'" • 1 (mod 10) => 3**' = 3 (mod 10)
^ 3 " ' ' = 10q + 3.
Tir do ta 06:2'°'"= 1 (mod 11) : ^ 2 ' ° ' * ' s 8 ( m o d 1 1 )
=>2'°'*' + 3 = 0(mod 11).
Dieu nay chiing to 2^* + 3 la hgp s6.
Cac bai tiKrng tir [1]
Chiing minh rang cac so sau la hgp so 1) 2 - " ' ' " ' + 19;
2) 2 " ' " ' - 3 - " ' " ' + 5 .
Tim cac chir so tan ciing ciia mot so tu nhien
De tim mpt chir so, hai chir so, ba chir s6 tan cimg ciia mot so tir nhien, ta di tim cac so du ciia so do cho 10, i 00, 1000.
Vi du 1: Tim 2 chir so tan ciing ciia so 3='"°
Giai
D I tim 2 chir so tan ciing vg ben phai cua so 3 ' " " tadi tim soducua 3 " chia cho 100.
3-'°.1 (mod 100)._
Bay gib ta biiu diln so 2""'° qua 40. Gia sir ta CO 2"'° = X (mod 40). Dat x = 4r, ta co 2"-'.8
= 8r (mod 8.5) o 2 " - ' = r(mpd5).
Ta CO 2* = 1 (mod 5) O 2 " ' ° = 1 ( m o d 5 )
=> 2 " " = 2' (mod 5), vi 2' . 3 (mod 5)
=» 2 " " » 3 (mod 5)
=> 2'"° = 24 (mod 40) hay 2™° = 40k+ 24
Ta co: 3 ' . 3 - ' ( m o d 100). Taco 3 " . 61 (mod 100)
=> 3" = 61'(mod 100), v i 6 l ' = 81 (mod 100)
= > 3 " a 8 1 (mod 100) hay 3 = ' " ° _ s i (mod 100).
Vay hai chir so tan ciing cua so dii chp la 81.
Vi du 2: Tim 3 chu so tan ciing ciia so 2 ' " "
Giai
Taco (9, 1000)= 1 o 9 * ° ° ° ' = 9 ™ = l (mod 1000) 3^ g!"" , 9 " (mod 1000).
Do 9 ' = 49 (mod 1000)
= > 9 " . 4 9 ' ( m o d 1000), vi 4 9 ' . 649 (mod 1000)
=> 9"= 649 (mod 1000) hay 9™" = 649 (mod 1000)
=> 9-°"= 1000k+ 649.
Vay bai toan duac dua ve tim 3 chir so tan ciing cua s6 2'°°°'"".
Gia su 2'°°°"-"'. X (mod 1000).
Dat X = 8r o 2'°°°'""' = 8r (mod 8.125) O2'°°°'*"' = r(modl25).
Tac6 2 « ' ' " =2'°°= 1 (mod 125) O 2 ' ° ° ° ' = l ( m o d l 2 5 )
= . 2 ' ° ° ° " " . 2™ (mod 125), v i 2 ' ° ° . 1 (mod 125)
= > 2 ' " ' . l (mod 125)
=>2"'=2'"(mod 125).
Taco 2'° = 2 4 (mod 125)
=> 2 " = 24'(mod 125)
=> 2 " a 2'.24'(mod 125),
Hoang Ngoc Tudt Tap chi KHOA HQC & CONG NGHE 135(05): 57 - 60
vi 2 ^ 2 4 ^ = 39 (mod 125) TAI LIEU T H A M K H A O
= > 2 ' ^ ^ s 3 9 ( m o d 125) 1. Nguyin Duy Hiin, Nguyen Hitu Hoan. Bai tap _ ^ 2 i ' " » k - M 6 ^ 2 9 ( m o d 125) dai s6 va ly thuyet s6, tap 1. Nha xuat ban Su
=> 2 | ™ ^ - 8.39 (mod 1000) pham Ha Noi, 2005.
^ 2 * = 3 1 2 (mod 1000). 2. Nguyin Huu Hoan, Ly thuyit s6. Nha xult ban Vay ba chir s6 tan c u n g cua s6 da cho la 312. Q^^ ^^J. g^^ ^^^^^ 2007.
Cac bai tirong t y : 3 Nguyen Tiin Tai, Nguyin HiJu Hoan, S6 hoc.
1. Tim 2 chil so tan cung ciia so: N h a x u l t ban Giao due. 1998.
2**" 4. Lai Diic Thjnh. Giao trinh S6 hoc. Nha xuat ban 2. Tim 3 c h a s6 tan cimg ciia so: Giao due, 1977.
q j i i i 5. George E. Andrews. Number Theory, 1994.
S U M M A R Y
O N C O N G R U E N C E S A N D A P P L I C A T I O N S IN P R O V I N G
T H E D I V I S I B I L I T Y A N D F I N D I N G T H E R E M A I N D E R S O F D I V I S I O N S Hofing Ng9c T u i t ' College of Science - T\U In this paper we give some applications of the theory of congruence in proving divisibility problems, finding the remainder in the division and finding the digit numbers of the end of a natural number of the a", where a, n are natural numbers. These problems are very useful for students in mathemtics and teachers of maths teaching at high schools.
Keywords: Congruence, modules, divisible, remainder of division, integers, natural number, digit
Ngdy nhdn bdi 20 12 2014. Ngdy phdn biin:27/01/2015: Ngdy duyil ddng: 31/5/2015 Phdn bien khoa hoc: PGS. TS Le Thi Thanh Nhdn - Trudng Dat hoc Khoa hpc - DHTN ' Tel- 0974 286206
60
