¦P¾l¤p°ÝÃD

¦P¾l (Congruence) ¬O¬ã²ß¾ã¼Æ©Ê½è¤¤¤@¤£¥i¤Öªº¤u¨ã¡C¦p§PÂ_¾ã°£©Ê (Divisibility) ¡G

­Y a = 0 (mod m)¡A§Ú­Ì«K¥i»¡ a ¬O m ªº­¿¼Æ©Î m ¾ã°£ a¡C

²{¦bÅý§Ú­Ì¬Ý¬Ý¤@¨Ç¦P¾l¤p°ÝÃD¡A·í¤¤¦³¤£¤Ö¬O¨ú§÷¦Û¼Æ¾ÇÄvÁÉ (Mathematical Competition) ©Î ¼Æ¾Ç¶øªL¤Ç§J (Mathematical Olympiad) ªº¡C

¨D 20052005 °£¥H 7 ªº¾l¼Æ¡C

µª¡G§Y¦Ò¼{ 20052005 ¦b¼Ò (Modulo) 7 ªº³Ñ¾l¡C¦]¬° 2005 = 3 (mod 7)¡A©Ò¥H 20052005 = 32005 (mod 7)¡A¦ý¯d·N¡A³o¤£µ¥©ó 33 ¡C©Ò¥H§Ú­Ì²{¦b±o­pºâ 32005 (mod 7) ¬O¦h¤Ö¡C 32 = 9 = 2 (mod 7)¡A 33 = 2*3 = 6 = -1 (mod 7)¡C¦]¦¹ 32005 = 33*668+1 = (33)668*3 = (-1)668 *3 = 1*3 = 3 (mod7)¡C©Ò¥H 20052005 °£¥H 7 ªº¾l¼Æ¬O 3 ¡C

¤èªk¬O¨D¨ú 3n = ± 1 (mod 7) ¤¤ªº n ­È¡A¦A¥H ± 1 §â«ü¼Æ´î¤Ö¡A¦A¦æ­pºâ¡A¥H¨Dµª®×¡C

 

¨D 460 °£¥H 23 ªº¾l¼Æ¡C

µª¡G§Y¦Ò¼{ 460 ¦b¼Ò 23 ªº³Ñ¾l¡C¦ý§Ú¸Õ¥H¥t¤@¤èªk­pºâ¦¹ÃD¡C 43 = 64 = -5 (mod 23)¡A¬G 46 = (-5)2 = 25 = 2 (mod 23) ¡A ¦Ó 412 = 22 = 4 (mod 23)¡C¨º»ò 460 = 412*5 = 45 = 43*42 = -5*16 = -80 = -11 (mod 23) ¡A©Ò¥H 460 °£¥H 23 ªº¾l¼Æ¬O 12¡C

¤èªk¬O´M§ä«ü¼Æ (60) ªº¦]¤l (¦p¡G12)¡A­pºâ 412 ªº­È¡A¦A¥N¤J­ì¦¡¡A§â¸Ó«ü¼Æ´î¤Ö¡A¦A¦æ­pºâ¡A¥H¨Dµª®×¡C

 

ÃÒ©ú 237 - 1 ¬O 223 ªº­¿¼Æ¡C

µª¡G§Y¦Ò¼{ 237 - 1 = 0 (mod 223)¡C¦ý¥Ñ©ó 223 ¤ñ¸û¤j¡A¬G´M§ä ± 1 ¬O¦æ¤£³qªº¡A¦ý«ü¼Æ 37 ¤S¬O¯À¼Æ¡A¬G§Ú­Ì¥u±o§â 37 ¤À¬l¦¨ 32 + 5¡A¦A¦æ­pºâ¡C¦] 27 = 128¡A28 = 256 = 223+33¡A©Ò¥H 28 = 33 (mod 223)¡C¨ä¹ê³o 28 ¬O2 ªº²Ä¤@­Ó¦¸¤è¼Æ¤j©ó 223¡A¨º»ò§Ú­Ì¤~¥i§â¼Æ­È¦b¼Ò 223 ¤UÁY¤Ö¡A«K§Q­pºâ¡C 216 = 33*33 = -26 (mod 223)¡A232 = (-26)*(-26) = 7 (mod 223)¡A¦Ó 25 = 32¡C©Ò¥H 237 = 232 * 25 = 7*32 = 1 (mod 223)¡CÃÒ²¦¡C

 

¨D 31997 ªº³Ì«á¨â¦ì¼Æ¡C

µª¡G§Y¦Ò¼{ 31997 °£¥H 100 ªº¾l¼Æ¡A©Î 31997 ¦b¼Ò 100 ¤Uªº³Ñ¾l¡A¦ý 100 ³o­Ó¼Ò¼Æ¼g¤Ó¤j¡A­Y¥H 3 ªº¦¸¤è¼Æ¤@¤@¥h¼Æªº¸Ü¡A­pºâ¶q®£©È¤]¤£¤Ö¡C¬G§Ú­Ì¦Ò¼{ 31997 = a (mod 100) ®É¯d·N¨ì 100 = 4 * 25 ¥B (4,25) = 1 ©ó¬O¥Ñ ¨D n ¨Ï 3n = 1 (mod 100) Âର¨D n ¨Ï 3n = 1 (mod 4) ¤Î 3n = 1 (mod 25) ¡C ¤£Ãø¨D¥X 32 = 1 (mod 4)¡A¦ý¼Ò 25 ªº¥i­nªáÂI®É¶¡¡A³Ì«á±o 310 = -1 (mod 25) ¡A§Y 320 = 1 (mod 25)¡C¦]¬° 20 = 2*10 ©Ò¥H 20 «K¬O§Ú­Ì¥Ø¼Ðªº n ¤F¡C 320 = 1 (mod 100)¡A©Ò¥H 31997 = 320*99 + 17 = 1 * 317 = 317 (mod 100)¡C¦ý 36 = 729 = 29 (mod 100)¡A 317 = 36*2+5 = 292 * 243 (mod 100) ¡A29*29 = 841¡A©Ò¥H 31997 = 317 = 41*43 = 63 (mod 100)¡C©Ò¥H¡A31997 ªº³Ì«á¨â¦ì¼Æ¬O 63¡C

 

ÃÒ©ú·í p ¤£¤Ö©ó 5 ªº¯À¼Æ®É¡Ap2 + 2 ¬°¤@¦X¼Æ¡C

µª¡GÆ[¹î 52 + 2 = 27¡A 72 + 2 = 51 µ¥³£¬O 3 ªº­¿¼Æ¡A§Ú­Ì¬Û«H p2 + 2 ·|¥þ¬O 3 ªº­¿¼Æ¡A¬G¦Ò¼{ p2 + 2 (mod 3)¡C¥Ñ©ó p ¬°¤£¤Ö©ó 5 ªº¯À¼Æ¡A©Ò¥H p = ± 1 (mod 3) ¡A¦Ó p2 + 2 = 0 (mod 3)¡A©Ò¥H p2 + 2 ùÚ¬°¤@¦X¼Æ¡CÃÒ²¦¡C

 

¥H pi ªí¥Ü²Ä i ­Ó¯À¼Æ¡AÃÒ©ú p1 * p2 * p3 * ...... * pn + 1 ¤£·|¬O¤@¥­¤è¼Æ¡C

µª¡G¨ä¤¤ p1 = 2¡A¦Ó pi ¬°©_¼Æ¡A·í i ¤£¤Ö©ó 2 ®É¡C¬G N = p1 * p2 * p3 * ...... * pn ¬°¤@°¸¼Æ¡A¦ý¤£·|¬O 4 ªº­¿¼Æ¡A§Y N = 2 (mod 4)¡A©Ò¥H N + 1 = 3 (mod 4)¡A³o¤£·|¬O¤@¥­¤è¼Æ¡A¦]¦b¼Ò 4 ¤U¡A¥­¤è¼Æ¥u·|µ¥©ó 0 ©Î 1¡CÃÒ²¦¡C

 

ÃÒ©ú¥ô¦ó¤T­Ó³sÄò¾ã¼Æ (Consecutive Integer) ªº¥ß¤è©M§¡¬° 9 ªº­¿¼Æ¡C

µª¡G³] N = (n-1)3 + n3 + (n+1)3 = 3n(n2 + 2)¡A­Y n = 0 (mod 3)¡A«h N ¤w§t¦³ 3 ³o­Ó¦]¤l¨â¦¸¡A§Y N ¬O 9 ªº­¿¼Æ¡C­Y n = ± 1 (mod 3) ¡A«h n2 + 2 = 0 (mod 3)¡A¦Ó³o¥ç¦P¼Ë¨Ï N §t¦³3 ³o­Ó¦]¤l¨â¦¸ ¡A§Y N ¬O 9 ªº­¿¼Æ¡CÃÒ²¦¡C

 

ÃÒ©ú 70! = 61! (mod 71)¡C

µª ¡G 70! = 61! * 62 * 63 * 64 * ..... * 70¡A­Y 70! = 61! (mod 71) ¡A«h¥²¶·ÃÒ©ú N = 62 * 63 * 64 * ...... * 70 = 1 (mod 71)¡C¦ý 70 = -1 (mod 71)¡B69 = -2 (mod 71)¡B68 = -3 (mod 71)¡B......¡B62 = -9 (mod 71)¡G©Ò¥H N = (-1) * (-2) * (-3) * ...... * (-9) = - 9! (mod 71)¡A1*2*3*4*5 = 120 = -22 (mod 71)¡A-22*6 = -132 = 10 (mod 71) ¡A10*7 = 70 = -1 (mod 71)¡A-1*8*9 = -72 = -1 (mod 71)¡A©Ò¥H -9! = 1 (mod 71)¡A§Y N = 62 * 63 * 64 * ...... * 70 = 1 (mod 71)¡C©Ò¥HÃÒ²¦¡C

 

ÃÒ©ú¹ï¥ô¦ó¥¿¾ã¼Æ n¡A¤U­±¤­­Ó¦P¾l¦¡ (Congruence Expression) ¤¤¦Ü¤Ö¦³¤@­Ó¦¨¥ß¡G

n = 0 (mod 2)¡An = 0 (mod 3)¡An = 1 (mod 4)¡An = 5 (mod 6)¡An = 7 (mod 12)

µª¡G§Ú­Ì¯d¥H¨ì¤­­Ó¼Ò¼Æªº³Ì¤p¤½­¿¼Æ (Least Common Multiple, L.C.M.) ¬° 12¡C¬G§Ú­Ì¦Ò¼{©Ò¦³¼Ò 12 ªº¥i¯à©Ê¡G¦¡ 1 ¥]¬A¤F©Ò¦³ªº n = 0, 2, 4, 6, 8, 10 (mod 12)¡A¦Ó¦¡ 2 ¥]¬A¤F©Ò¦³ªº n = 0, 3, 6, 9 (mod 12) ¡A¦Ó¦¡ 3 ¥]¬A¤F©Ò¦³ªº n = 1, 5, 9 (mod 12) ¡A¦Ó¦¡ 4 ¥]¬A¤F©Ò¦³ªº n = 5, 11 (mod 12)¡A³Ì«áªº¦¡ 5 ¥]¬A¤F n = 7 (mod 12)¡C§Y 0 ¦Ü 11©Ò¦³¥i¯à©Ê§¡¬°¨ä¤¤¤@¦¡©Î¥H¤W©Ò¥]¬A¡A¬GÃÒ²¦¡C

 

Hosted by www.Geocities.ws

1