แฟคทอเรียล!

[Beatmania]

สำหรับจำนวนนับ $n>1$ จงแสดงว่า

$$n!\prod_{d|n}[d^{\frac{n}{d}}(\frac{n}{d})!]^{\mu(d)}$$

เป็นจำนวนนับ

ปล. $\mu(n)$ คือ $Mobius$ $Function$ นะครับ

[Thgx0312555]

สามารถแยกเป็นสองส่วนครับ
(1) $\displaystyle n!\prod_{d|n}[d^{\frac{n}{d}}]^{\mu(d)}$ เป็นจำนวนเต็ม
และ
(2) $\displaystyle \prod_{d|n}[(\frac{n}{d})!]^{\mu(d)}$ เป็นจำนวนเต็ม

ขอเขียนส่วนที่ยาก (2) ก่อนละกันครับ ส่วนง่าย (1) เดี๋ยวมาเฉลยต่อแต่ถ้าคนอื่นอยากทำก็ทำเลยครับ

สมมติ $p_1p_2 \cdots p_m \mid n$ เป็นจำนวนเฉพาะที่หาร $n$ ทั้งหมด

พิจารณากำลังของ $p$ เมื่อ $p$ เป็นจำนวนเฉพาะใดๆ
$$\displaystyle \prod_{d|n}[(\frac{n}{d})!]^{\mu(d)}$$

จะได้ว่าเท่ากับ $\displaystyle \sum_{i=1}^{\infty}(\left\lfloor \frac{n}{p^i} \right\rfloor - \left\lfloor \frac{n}{p^ip_1} \right\rfloor - \left\lfloor \frac{n}{p^ip_2} \right\rfloor - \cdots - \left\lfloor \frac{n}{p^ip_m} \right\rfloor + \left\lfloor \frac{n}{p^ip_1p_2} \right\rfloor + \cdots + (-1)^m \left\lfloor \frac{n}{p^ip_1p_2 \cdots p_m} \right\rfloor)$

$= \displaystyle \sum_{i=1}^{\infty}(\left\lfloor n/p^i \right\rfloor - \left\lfloor \frac{\left\lfloor n/p^i \right\rfloor}{p_1} \right\rfloor - \left\lfloor \frac{\left\lfloor n/p^i \right\rfloor}{p_2} \right\rfloor - \cdots - \left\lfloor \frac{\left\lfloor n/p^i \right\rfloor}{p_m} \right\rfloor + \left\lfloor \frac{\left\lfloor n/p^i \right\rfloor}{p_1p_2} \right\rfloor + \cdots + (-1)^m \left\lfloor \frac{\left\lfloor n/p^i \right\rfloor}{p_1p_2 \cdots p_m} \right\rfloor)$

นั่นคือเราเหลือเพียงแสดงว่า
$f(k) := \displaystyle \left\lfloor k \right\rfloor - \left\lfloor \frac{k}{p_1} \right\rfloor - \left\lfloor \frac{k}{p_2} \right\rfloor - \cdots - \left\lfloor \frac{k}{p_m} \right\rfloor + \left\lfloor \frac{k}{p_1p_2} \right\rfloor + \cdots + (-1)^m \left\lfloor \frac{k}{p_1p_2 \cdots p_m} \right\rfloor \ge 0$

ซึ่งสามารถพิสูจน์ได้ว่า
$f(k)-f(k-1) = \cases{1 & , \gcd (k,n)=1 \cr 0 & , \gcd (k,n)>1} $

นั่นคือ $f(k)$ มีค่าเท่ากับจำนวนของจำนวนเฉพาะสัมพัทธ์กับ $n$ ที่มีค่าตั้งแต่ $1$ ถึง $k$ จึงได้ว่า $f(k) \ge 0$

ปล. รอดูผลผู้แทนปีนี้นะครับ

[Beatmania]

ครับผม ผมคงไม่ได้หรอกครับ

จริงๆแล้ว โจทย์สามารถลดให้เหลือเป็น จงแสดงว่า

$$\prod_{d|n}[d^{\frac{n}{d}}(\frac{n}{d})!]^{\mu(d)}$$

เป็นจำนวนนับได้ครับ (อันนี้ผมสะเพร่าเอง นึกว่า $\mu(1)=0$ = =*)

และจะได้ว่า

$$\prod_{d|n}[d^{\frac{n}{d}}(\frac{n}{d})!]^{\mu(d)}=\prod_{1<d<n,(d,n)=1}d$$

[Beatmania]

เฉลยสำหรับผู้ที่สนใจนะครับ

Solution

พิจารณาจำนวนนับ $m\leq n$ เราจะนับจำนวนครั้งที่ $m$ ปรากฏในผลคูณนี้

ก่อนอื่น สังเกตว่า

$$d^{\frac{n}{d}}(\frac{n}{d})!=d\cdot(2d)\cdot...\cdot n$$

เราจะแยกกรณีดังนี้
1.) $gcd(m,n)=1$

เราจะได้ว่า $m$ ปรากฏใน $1^{\frac{n}{1}}(\frac{n}{1})!=n!$ เพียงครั้งเดียวเท่านั้น

2.) $gcd(m,n)\neq1$

เราให้ $gcd(m,n)=p_1^{a_1}p_2^{a_2}...p_l^{a_l}$

ดังนั้นแล้ว $m$ จะปรากฏในผลคูณทั้งหมด $2^l$ ครั้ง

เนื่องจาก $\mu(r)=1$ เมื่อ $r$ เป็นผลคูณของจำนวนเฉพาะที่แตกต่างกันจำนวนคู่ตัว

ดังนั้นแล้ว $m$ จะปรากฏเป็น $m^1$ ทั้งหมด $\binom{l}{0} +\binom{l}{2}+...$ ครั้ง

และในทำนองเดียวกัน $\mu(r)=-1$ เมื่อ $r$ เป็นผลคูณของจำนวนเฉพาะที่แตกต่างกันจำนวนคี่ตัว

ดังนั้นแล้ว $m$ จะปรากฏเป็น $m^{-1}$ ทั้งหมด $\binom{l}{1} +\binom{l}{3}+...$ ครั้ง

แต่เนื่องจาก $\binom{l}{0} +\binom{l}{2}+...=\binom{l}{1} +\binom{l}{3}+...$

ดังนั้นแล้ว ในที่สุดจะไม่ปรากฎ $m$ ในผลลัพธ์

ดังนั้นแล้ว เราจึงสรุปได้ว่า

$$\prod_{d|n}[d^{\frac{n}{d}}(\frac{n}{d})!]^{\mu(d)}$$

จะมีค่าเท่ากับผลคูณของจำนวนนับที่น้อยกว่า $n$ และเป็นจำนวนเฉพาะสัมพัทธ์กับ $n$