Fungsi Legendre

Jika $p$ merupakan bilangan prima. Untuk sebarang bilangan bulat positif $n$ didefinisikan $e_p(n)$ sebagai pangkat dari $p$ dalam faktorisasi prima dari $n!$ . Sebagai contoh kita ambil $n=4$ dan $p=2$ . Karena $4!=4 \cdot 3\cdot 2\cdot 1=2^3\cdot 3$ maka nilai $e_2(4)=3$ .
Fungsi aritmatika dari $e_p$ disebut Fungsi Legendre yang berkaitan dengan bilangan prima $p$ .
Kita memiliki teorema berikut, ( bukti sengaja tidak ditulis sebagai latihan bagi pembaca. Pembuktiannya bisa menggunakan teori bilangan atau kombinatorik ).

Teorema. Untuk sebarang bilangan prima $p$ dan sebarang bilangan bulat positif $n$ berlaku,
$e_p(n)=\sum_{i\geq 1}\left\lfloor \frac{n}{p^i}\right\rfloor=\left\lfloor \frac{n}{p}\right\rfloor+\left\lfloor \frac{n}{p^2}\right\rfloor+\left\lfloor \frac{n}{p^3}\right\rfloor+\cdots$ .

Contoh Soal :
1. Jika $s$ dan $t$ bilangan bulat positif sehingga $7^s\mid 400!$ dan $3^t\mid ((3!)!)!$ . Hitung nilai $s+t$ .
Solusi :
Perhatikan bahwa $((3!)!)!=(6!)!=720!$ . Dengan menggunakan Fungsi Legendre didapat,
$e_7(400)=\left\lfloor \frac{400}{7}\right\rfloor+\left\lfloor \frac{400}{7^2}\right\rfloor+\left\lfloor \frac{400}{7^3}\right\rfloo=57+8+1=66$
dan
$e_3(720)=\left\lfloor \frac{720}{3}\right\rfloor+\left\lfloor \frac{720}{3^2}\right\rfloor+\left\lfloor \frac{720}{3^3}\right\rfloor+\left\lfloor \frac{720}{3^4}\right\rfloor+\left\lfloor \frac{720}{3^5}\right\rfloor=240+80+26+8+2=356$
Jadi, $s+t=66+356=422 \square$
2. Berapa banyaknya angka $0$ tak terputus di bagian belakang $1000!$
Solusi :
Angka $0$ di bagian belakang $1000!$ didapat dari perkalian $2\cdot 5$ . Dengan Fungsi Legendre, mudah dilihat bahwa $e_2(1000)> e_5(1000)$ . Jadi, banyaknya angka $0$ di bagian belakang $1000!$ adalah $e_5(1000)=\left\lfloor \frac{1000}{5}\right\rfloor+\left\lfloor \frac{1000}{5^2}\right\rfloor+\left\lfloor \frac{1000}{5^3}\right\rfloor+\left\lfloor \frac{1000}{5^4}\right\rfloor=200+40+8+1=249 \square$

Latihan.
1. Tentukan $n$ sehingga $n!=(2^{15})(3^6)(5^3)(7^2)(11)(13)$
2. Hitunglah banyaknya angka nol dibagian belakang $(5^n-1)!$ dengan $n\geq 2$
3. Hitunglah besarnya pangkat $n$ yang merupakan faktor dari $(n^r-1)!$
4. Jika $p$ prima dan $n$ bilangan bulat positif serta $n=p^ar$ dengan $r$ dan $p$ saling prima. Buktikan :
$a=\left\lfloor \frac{n}{p}\right\rfloor+\left\lfloor \frac{n}{p^2}\right\rfloor+\left\lfloor \frac{n}{p^3}\right\rfloor+\cdots$ .

Oke. Sudah capek nulisnya. Kapan- kapan disambung lagi.