ถ้า p เป็นจำนวนเฉพาะ, n เป็นจำนวนเต็มบวก แล้ว (p^n)! หารด้วย p ลงตัวกี่ครั้ง ?

วิธีทำ

ลองมองง่ายๆก่อน เช่น สมมุติ p = 5, n = 3 จะได้ว่า (5³)! หารด้วย 5 ลงตัวกี่ครั้ง?

(5³)! = 125*124*123*...*2*1

หารด้วย 5 ลงตัวจะมีเลข 5, 10, 15,..., 115, 120, 125 = 25 ตัว (หารด้วย 5 ลงตัวตอนนี้ 25 ครั้ง)

ผลจากการหาร 25 ตัวนั้นด้วย 5 จะกลายเป็น 1, 2, 3,..., 24, 25

เอา  1, 2, 3,..., 24, 25 มาหารด้วย 5 อีกครั้ง จะได้ว่า 5, 10, 15, 20, 25 = 5 ตัว (หารด้วย 5 ลงตัวตอนนี้ 5 ครั้ง)

ผลจากการหาร 5 ตัวนั้นด้วย 5 จะกลายเป็น 1, 2, 3, 4, 5

เอา  1, 2, 3, 4, 5 มาหารด้วย 5 อีกครั้ง จะได้ว่า 5 = 1 ตัว (หารด้วย 5 ลงตัวตอนนี้ 1 ครั้ง)

สรุป   (5³)! หารด้วย 5 ลงตัว = 25 + 5 + 1 = 31 ครั้ง

กลับมาที่โจทย์ จาก 1 ถึง pⁿ  มีตัวเลข pⁿ  ตัว

1, 2, 3, ...p, p +1, ...2p, ...(p-1)p, ...p², ...pⁿ

ซึ่งถ้าถูกหารด้วย p^k โดยที่ k เป็นจำนวนเต็มบวก (k มากกว่าหรือเท่ากับ 1 แต่น้อยกว่าหรือเท่ากับ n)

จะมีเลขที่ถูกหารลงตัวจำนวน pⁿ/p^k = p^n-k ตัว

นั่นคือ

ถ้ามี pⁿ ตัว  p หารลงตัวมี p^n-1 ตัว

ถ้ามี pⁿ ตัว p² หารลงตัวมี p^n-2 ตัว

ถ้ามี pⁿ ตัว  p³ หารลงตัวมี p^n-3 ตัว

                       .

                       .

                       .

ถ้ามี pⁿ ตัว  p^n-1 หารลงตัวมี p ตัว

ถ้ามี pⁿ ตัว  pⁿ หารลงตัวมี 1 ตัว

สรุปง่ายๆคือ

ถ้า pⁿ ตัว ใช้ p หารลงตัวมี p^n-1  ตัว

ลองหาร p^n-1  ตัว นั้นด้วย p อีกที ปรากฎว่าหารได้ลงตัวมี p^n-2 ตัว

ลองหาร p^n-2  ตัว นั้นด้วย p อีกที ปรากฎว่าหารได้ลงตัวมี p^n-3 ตัว

ไปเรื่อยๆ

ดังนั้น จำนวนครั้งที่ (pⁿ)! หารด้วย p ลงตัว = sum p^(n-k), k = 1 to n

= p^n-1 + p^n-2 +...+ p + 1 = (pⁿ - 1)/(p -1) ครั้ง  จบ

ที่มา: ข้อสอบเข้า Kyoto University ปี2009 ครึ่งแรก ข้อ5 สายศิลป์

Create Date : 19 กันยายน 2553		0 comments
Last Update : 19 กันยายน 2553 13:24:40 น.
Counter : 726 Pageviews.
Share Tweet