tailieunhanh - Ứng dụng định lý Lucas trong một số bài tập số học

Tài liệu tham khảo về Ứng dụng định lý Lucas trong một số bài tập số học. | ứNgdỤnG định lý LUCAS TRONG MỘT SỐ BÀI TẬP SỐ HỌC ĐÀO MẠNH thắng -Chuyên Hùng Vương Định lý Lucas 1842-1891 là một trong những định lý đẹp của Lý thuyết đồng dư theo mô đun nguyên tố. Bài viết này giới thiệu và trao đổi với các bạn về nội dung định lý và ứng dụng vào một số bài tập số học hên quan đến đồng dư theo mô đun nguyên tố. Nội dung định lý. Cho m n là các số tự nhiên và p là một số nguyên tố. Giả sử biểu diễn cơ sở p của m n là k . k 1 . m mk-L-P mỵ .p mo n nk-pk . no vớio mị ni p 1 i 0 1 . k k Khi đó Cm n c . mod p Quy ước c 0 khi a b . i 0 Chứng minh. Nếu m n thì Định lý hiển nhiên đúng. Không mất tính tổng quát giả sử m n. Ta có nhận xét x 1 xP3 mod p V j E N . k _ 52 k i Do đó 1 xỴ1 1 xỴ v n 1 p 7 0 Suy ra 1 x m n 12 cịnixhví mod p . 7 0 j 0 Đồng nhất hệ số của xn ở 2 vế của đồng dư thức trên suy ra điều phải chứng minh. Sau đây chúng ta xem xét ứng dụng của Định lý Lucas vào giải quyết một số Bài tập số học liên quan đến đồng dư theo mô đun nguyên tố. Ví dụ . Cho số nguyên dương n và số nguyên tố p. Chứng mình rằng n mod p . Lời giải. Giả sứ biểu diễn cơ sỏ p của n là L L_1 n ni-jo n-0 Theo định lý Lucas ta có mod p . Ví dụ . Tìm tất cả các số nguyên dương n sao cho C là số lẻ vói mọi m 0 1 . n. Lời giải. Vì cần xét tính chẵn lẻ của nên ta xét biểu diễn của n m theo hệ cơ số p 2. Giả sử n m biểu diễn theo hệ cơ số 2 là k k n nịSý m ni mị E 0 1 . 7 0 7 0 Khi đó theo định lý Lucas ta có k Cĩ n cy mod 2 2 0 Do đó c m 0 1 . n là số lẻ khi và chỉ khi mị Uị Uị 1 V i 0 1 . k. Vậy C V m 0 1 . n là số lẻ khi và chỉ khi trong biểu diễn theo cơ số 2 của n chỉ có các chữ số 1 tức là n 2s 1. Ví dụ . Xác định tất cả các số nguyên dương n 2 sao cho c _k là số chẵn với mọi k 0 1 . ữ. Lởi giải. Theo ví dụ trên ta có CĨỊỊ-I 1 mod 2 V 0 m 2s 1. Từ đó suy ra n 1 là lũy thừa của 2 vì nếu không ta đặt s log2 s và xét . 08 1. _ . 2s 1 - 2 n _ n k n 2 - 1 n--------- n - I I Khi đó ck k Cks Ả là một số lẻ trái điều kiện của bài .