Bentuk kanonik dari bilangan asli

Setiap bilangan asli ${\displaystyle n>1}$ dapat dinyatakan secara tunggal sebagai darab dari perpangkatan bilangan prima $${\displaystyle n=(p_{1})^{e_{1}}\cdot (p_{2})^{e_{2}}\cdot (p_{3})^{e_{3}}\cdot \ldots \cdot (p_{k})^{e_{k}}=\prod _{i\,=\,1}^{k}(p_{i})^{e_{i}}}$$ dengan ${\displaystyle p_{1}<p_{2}<p_{3}<\ldots <p_{k}}$ merupakan bilangan-bilangan prima dan setiap ${\displaystyle e_{i}}$ merupakan bilangan asli nonnegatif. Representasi ini umumnya diperluas menjadi seluruh bilangan asli (termasuk 1) dengan konvensi bahwa nilai dari darab kosong ialah 1 (darab kosong berpadanan dengan nilai ${\displaystyle k=0}$).

Representasi ini disebut representasi kanonik^[8] dari ${\displaystyle n}$, bentuk kanonik^[9] dari ${\displaystyle n}$, atau bentuk standar^[10][11] dari ${\displaystyle n}$. Sebagai contoh,

$${\displaystyle {\begin{aligned}999&=3^{3}\cdot 37\\1000&=2^{3}\cdot 5^{3}\\1001&=7\cdot 11\cdot 13\end{aligned}}}$$

Faktor ${\displaystyle p_{0}=1}$ dapat dimasukkan tanpa mengubah nilai dari ${\displaystyle n}$. Misalnya, ${\displaystyle 1000=2^{3}\cdot 3^{0}\cdot 5^{3}}$. Secara umum, setiap bilangan asli dapat secara tunggal dinyatakan sebagai darab takhingga dari semua bilangan prima positif, yaitu $${\displaystyle n=2^{e_{1}}\cdot 3^{e_{2}}\cdot 5^{e_{3}}\cdot 7^{e_{4}}\cdot \ldots =\prod _{i\,=\,1}^{\infty }(p_{i})^{e_{i}}}$$ dengan banyaknya ${\displaystyle e_{i}}$ yang bernilai positif ialah berhingga, dan sisanya bernilai nol.

Memperbolehkan pangkat negatif akan memberikan bentuk kanonik dari bilangan rasional positif.

Operasi aritmetika

Bentuk kanonik dari darab, faktor persekutuan terbesar (FPB), dan kelipatan persekutuan terkecil (KPK) dari dua bilangan asli ${\displaystyle a}$ dan ${\displaystyle b}$ dapat dinyatakan dalam bentuk kanonik dari ${\displaystyle a}$ dan ${\displaystyle b}$ itu sendiri, yaitu:

$${\displaystyle {\begin{aligned}a\cdot b&=2^{a_{1}+b_{1}}\cdot 3^{a_{2}+b_{2}}\cdot 5^{a_{3}+b_{3}}\cdot 7^{a_{4}+b_{4}}\cdot \ldots \\a\cdot b&=\prod _{i\,=\,1}^{\infty }(p_{i})^{a_{i}+b_{i}}\\\\\operatorname {FPB} \!\left(a,\,b\right)&=2^{\min \left(a_{1},\,b_{1}\right)}\cdot 3^{\min \left(a_{2},\,b_{2}\right)}\cdot 5^{\min \left(a_{3},\,b_{3}\right)}\cdot 7^{\min \left(a_{4},\,b_{4}\right)}\cdot \ldots \\\operatorname {FPB} \!\left(a,\,b\right)&=\prod _{i\,=\,1}^{\infty }(p_{i})^{\min \left(a_{i},\,b_{i}\right)}\\\\\operatorname {KPK} \!\left(a,\,b\right)&=2^{\max \left(a_{1},\,b_{1}\right)}\cdot 3^{\max \left(a_{2},\,b_{2}\right)}\cdot 5^{\max \left(a_{3},\,b_{3}\right)}\cdot 7^{\max \left(a_{4},\,b_{4}\right)}\cdot \ldots \\\operatorname {KPK} \!\left(a,\,b\right)&=\prod _{i\,=\,1}^{\infty }(p_{i})^{\max \left(a_{i},\,b_{i}\right)}\end{aligned}}}$$

Akan tetapi, proses memfaktorkan bilangan bulat—terutama bilangan-bilangan yang besar—jauh lebih sulit dibandingkan menghitung darab, FPB, maupun KPK, sehingga pada penerapannya, rumus-rumus di atas memiliki penggunaan yang cukup terbatas.

Fungsi aritmetika

Banyak fungsi aritmetika yang didefinisikan menggunakan bentuk kanonik. Lebih spesifiknya, nilai fungsi aditif dan fungsi perkalian dari bilangan asli ${\displaystyle n}$ ditentukan oleh nilai pangkat dari bilangan prima yang muncul dari bentuk kanonik dari ${\displaystyle n}$.

Kewujudan

Diambil sembarang bilangan asli ${\displaystyle k>1}$. Akan diasumsikan secara induktif bahwa setiap bilangan asli yang nilainya kurang dari ${\displaystyle k}$ antara berupa bilangan prima, atau merupakan darab dari bilangan-bilangan prima. Jika ${\displaystyle k}$ merupakan bilangan prima, maka pernyataan terbukti.

Jika ${\displaystyle k}$ bukan merupakan bilangan prima, maka terdapat bilangan asli ${\displaystyle a}$ dan ${\displaystyle b}$ sedemikian sehingga ${\displaystyle n=a\cdot b}$, dengan ${\displaystyle 1<a\leq b<k}$. Berdasarkan hipotesis induktif, maka ${\displaystyle a}$ dan ${\displaystyle b}$ dapat berupa bilangan prima, atau dapat dinyatakan sebagai darab dari bilangan-bilangan prima. $${\displaystyle {\begin{aligned}a&=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{n}\\b&=q_{1}\cdot q_{2}\cdot \ldots \cdot q_{N}\end{aligned}}}$$ Akibatnya, diperoleh $${\displaystyle k=a\cdot b=(p_{1}\cdot p_{2}\cdot \ldots \cdot p_{n})\cdot (q_{1}\cdot q_{2}\cdot \ldots \cdot q_{N})}$$ yang menunjukkan bahwa ${\displaystyle k}$ merupakan darab dari bilangan-bilangan prima.

Ketunggalan

Diambil sembarang ${\displaystyle k\in \mathbb {N} }$ beserta dua faktorisasi primanya, yaitu $${\displaystyle k=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}=q_{1}\cdot q_{2}\cdot q_{3}\cdot \ldots \cdot q_{N}}$$ dengan ${\displaystyle n\leq N}$ dan setiap ${\displaystyle p_{m}}$ serta ${\displaystyle q_{m}}$ merupakan bilangan prima. Oleh karena ${\displaystyle p_{1}}$ habis membagi ${\displaystyle p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}}$, maka ${\displaystyle p_{1}}$ habis membagi ${\displaystyle q_{1}\cdot q_{2}\cdot q_{3}\cdot \ldots \cdot q_{N}}$. Berdasarkan lema Euclid, maka terdapat suatu ${\displaystyle j\in \left\{1,\,2,\,3,\,\ldots ,\,N\right\}}$ sedemikian sehingga ${\displaystyle p_{1}}$ habis membagi ${\displaystyle q_{j}}$. Tanpa mengurangi keumuman, diasumsikan bahwa ${\displaystyle p_{1}}$ habis membagi ${\displaystyle q_{1}}$. Oleh karena ${\displaystyle p_{1}}$ dan ${\displaystyle q_{1}}$ merupakan bilangan prima, maka ${\displaystyle p_{1}=q_{1}}$. Akibatnya, diperoleh $${\displaystyle p_{2}\cdot p_{3}\cdot p_{4}\cdot \ldots \cdot p_{n}=q_{2}\cdot q_{3}\cdot q_{4}\cdot \ldots \cdot q_{N}}$$

Dengan proses serupa, perhatikan bahwa ${\displaystyle p_{2}}$ habis membagi ${\displaystyle p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}}$. Akibatnya, ${\displaystyle p_{2}}$ habis membagi ${\displaystyle q_{2}\cdot q_{3}\cdot \ldots \cdot q_{N}}$. Berdasarkan lema Euclid, maka terdapat suatu ${\displaystyle j\in \left\{2,\,3,\,\ldots ,\,N\right\}}$ sedemikian sehingga ${\displaystyle p_{2}}$ habis membagi ${\displaystyle q_{j}}$. Dengan argumen serupa seperti sebelumnya, diasumsikan bahwa ${\displaystyle p_{2}}$ habis membagi ${\displaystyle q_{2}}$. Oleh karena ${\displaystyle p_{2}}$ dan ${\displaystyle q_{2}}$ merupakan bilangan prima, maka ${\displaystyle p_{2}=q_{2}}$. Akibatnya, didapatkan $${\displaystyle p_{3}\cdot p_{4}\cdot \ldots \cdot p_{n}=q_{3}\cdot q_{4}\cdot \ldots \cdot q_{N}}$$

Jika ${\displaystyle n<N}$, maka proses ini akan berakhir pada persamaan $${\displaystyle 1=p_{n+1}\cdot p_{n+2}\cdot \ldots \cdot p_{N}}$$ yang jelas mustahil terjadi, sebab setiap bilangan prima akan memenuhi pertidaksamaan ${\displaystyle p\geq 2}$, sehingga ruas kanan tidak mungkin sama dengan satu. Akibatnya, ${\displaystyle n=N}$.

Oleh karena ${\displaystyle n=N}$, maka berlaku $${\displaystyle {\begin{aligned}p_{1}&=q_{1}\\p_{2}&=q_{2}\\p_{3}&=q_{3}\\&\vdots \\p_{n}&=q_{N}\end{aligned}}}$$ yang berarti bahwa ${\displaystyle k}$ memiliki faktorisasi prima yang bersifat tunggal.

Ketunggalan tanpa lema Euclid

Teorema dasar aritmetik juga dapat dibuktikan tanpa menggunakan lema Euclid.^[12] Bukti berikut merupakan pembuktian melalui kontradiksi yang terinspirasi dari versi orisinal dari algoritma Euclid.

Andaikan himpunan semua bilangan asli yang faktorisasi primanya tidak tunggal bukan merupakan himpunan kosong, maka berdasarkan prinsip urutan rapi, terdapat suatu bilangan asli terkecil ${\displaystyle k}$ yang memiliki setidaknya dua faktorisasi prima, yaitu $${\displaystyle k=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}=q_{1}\cdot q_{2}\cdot q_{3}\cdot \ldots \cdot q_{N}}$$ dengan ${\displaystyle n\leq N}$ dan setiap ${\displaystyle p_{i}}$ serta ${\displaystyle q_{i}}$ merupakan bilangan prima. Hal ini mengakibatkan bahwa ${\displaystyle k}$ (jika ada) merupakan bilangan komposit yang nilainya lebih dari ${\displaystyle 1}$.

Andaikan terdapat suatu ${\displaystyle i\in \left\{1,\,2,\,3,\,\ldots ,\,n\right\}}$ dan ${\displaystyle j\in \left\{1,\,2,\,3,\,\ldots ,\,N\right\}}$ sedemikian sehingga ${\displaystyle p_{i}=q_{j}}$, maka terdapat suatu bilangan asli ${\displaystyle k'={\tfrac {k}{p_{i}}}={\tfrac {k}{q_{j}}}}$ yang nilainya kurang dari ${\displaystyle k}$, tetapi faktorisasi primanya tidak tunggal. Namun, hal ini mustahil terjadi, sebab ${\displaystyle k}$ adalah bilangan asli terkecil yang memiliki sifat tersebut. Akibatnya, setiap ${\displaystyle p_{i}}$ harus berbeda dengan setiap ${\displaystyle q_{j}}$. Tanpa mengurangi keumuman, diasumsikan bahwa ${\displaystyle p_{1}<q_{1}}$ dengan menukar dua faktorisasinya, jika diperlukan.

Didefinisikan $${\displaystyle {\begin{aligned}P&=p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}\\Q&=q_{2}\cdot q_{3}\cdot \ldots \cdot q_{N}\end{aligned}}}$$ sehingga diperoleh ${\displaystyle k=p_{1}\cdot P=q_{1}\cdot Q}$. Oleh karena ${\displaystyle p_{1}<q_{1}}$, maka ${\displaystyle Q<P}$.^{[note 6]} Tinjau bilangan ${\displaystyle p_{1}\cdot (P-Q)}$, yaitu

$${\displaystyle {\begin{aligned}p_{1}\cdot (P-Q)&=(p_{1}\cdot P)-p_{1}\cdot Q\\&=k-p_{1}\cdot Q\\&=(q_{1}\cdot Q)-p_{1}\cdot Q\\&=(q_{1}-p_{1})\cdot Q\end{aligned}}}$$

Jelas bahwa ${\displaystyle k-p_{1}\cdot Q<k}$. Oleh karena ${\displaystyle k}$ adalah bilangan asli terkecil yang memiliki faktorisasi prima yang tidak tunggal, maka setiap bilangan asli yang kurang dari ${\displaystyle k}$ memiliki faktorisasi prima yang tunggal. Berdasarkan persamaan $${\displaystyle p_{1}\cdot (P-Q)=(q_{1}-p_{1})\cdot Q}$$ maka ${\displaystyle p_{1}}$ harus muncul sebagai faktor dari ${\displaystyle q_{1}-p_{1}}$ atau ${\displaystyle Q}$.

1. andaikan ${\displaystyle p_{1}}$ merupakan faktor dari ${\displaystyle q_{1}-p_{1}}$, maka ${\displaystyle p_{1}}$ juga merupakan faktor dari ${\displaystyle q_{1}}$. Namun, hal ini mustahil terjadi, sebab diketahui bahwa ${\displaystyle p_{1}}$ dan ${\displaystyle q_{1}}$ merupakan bilangan prima yang berbeda.
2. jelas bahwa ${\displaystyle Q<k}$, sehingga ${\displaystyle Q}$ memiliki faktorisasi prima yang tunggal. Oleh karena ${\displaystyle p_{1}}$ haruslah berbeda dengan setiap ${\displaystyle q_{m}}$, maka ${\displaystyle p_{1}}$ mustahil menjadi faktor dari ${\displaystyle Q}$.

Berdasarkan kedua kasus di atas, maka pernyataan "${\displaystyle p_{1}}$ harus muncul sebagai faktor dari ${\displaystyle q_{1}-p_{1}}$ atau ${\displaystyle Q}$" bersifat kontradiktif, sehingga pernyataan "himpunan semua bilangan asli yang faktorisasi primanya tidak tunggal bukan merupakan himpunan kosong" bernilai salah. Dengan kata lain, himpunan semua bilangan asli yang faktorisasi primanya tidak tunggal merupakan himpunan kosong, yang berarti bahwa setiap bilangan asli memiliki faktorisasi prima yang tunggal.