Teorema 6.3.1.
Misalkan \(U(n)\) grup unit dalam \({\mathbb Z}_n\text{.}\) Maka \(|U(n)| = \phi(n)\text{.}\)
Bagian 6.3 Teorema Fermat dan Euler
Fungsi \(\phi\) Euler adalah pemetaan \(\phi : {\mathbb N } \rightarrow {\mathbb N}\) yang didefinisikan oleh \(\phi(n) = 1\) untuk \(n=1\text{,}\) dan untuk \(n \gt 1\text{,}\) \(\phi(n)\) merupakan banyaknya bilangan bulat positif \(m\) dengan \(1 \leq m \lt n\) dan \(\gcd(m,n) = 1\text{.}\)
Berdasarkan Proposisi 3.1.4, kita mengetahui bahwa orde \(U(n)\text{,}\) yaitu grup unit dalam \({\mathbb Z}_n\text{,}\) adalah \(\phi(n)\text{.}\) Sebagai contoh, \(|U(12)| = \phi(12) = 4\) karena bilangan yang relatif prima terhadap \(12\) adalah \(1\text{,}\) \(5\text{,}\) \(7\text{,}\) dan \(11\text{.}\) Untuk sebarang bilangan prima \(p\text{,}\) berlaku \(\phi(p) = p-1\text{.}\) Hasil-hasil ini dinyatakan dalam teorema berikut.
Teorema berikut merupakan hasil penting dalam teori bilangan yang ditemukan oleh Leonhard Euler.
Teorema 6.3.2. Teorema Euler.
Misalkan \(a\) dan \(n\) bilangan bulat sedemikian sehingga \(n \gt 0\) dan \(\gcd(a, n) = 1\text{.}\) Maka \(a^{\phi(n)} \equiv 1 \pmod{n}\text{.}\)
Bukti.
Berdasarkan Teorema 6.3.1, orde \(U(n)\) adalah \(\phi(n)\text{.}\) Akibatnya, \(a^{\phi(n)} = 1\) untuk setiap \(a \in U(n)\text{;}\) atau \(a^{\phi(n)} - 1\) habis dibagi \(n\text{.}\) Oleh karena itu, \(a^{\phi(n)} \equiv 1 \pmod{n}\text{.}\)
Jika kita mempertimbangkan kasus khusus Teorema Euler ketika \(n = p\) prima dan mengingat bahwa \(\phi(p) = p - 1\text{,}\) kita memperoleh hasil berikut, yang ditemukan oleh Pierre de Fermat.
Teorema 6.3.3. Teorema Kecil Fermat.
Misalkan \(p\) sebarang bilangan prima dan misalkan \(p \notdivide a\) (\(p\) tidak membagi \(a\)). Maka
\begin{equation*}
a^{p-1} \equiv 1 \pmod{ p }\text{.}
\end{equation*}
Lebih lanjut, untuk sebarang bilangan bulat \(b\text{,}\) \(b^p \equiv b \pmod{ p}\text{.}\)
Subbagian 6.3.1 Catatan Sejarah
Joseph-Louis Lagrange (1736–1813), yang lahir di Turin, Italia, merupakan keturunan Prancis dan Italia. Bakat matematikanya tampak sejak usia dini. Leonhard Euler mengenali kemampuan Lagrange ketika Lagrange, yang saat itu baru berusia 19 tahun, menyampaikan kepada Euler beberapa karya yang telah dikerjakannya dalam kalkulus variasi. Pada tahun itu ia juga diangkat menjadi profesor di Sekolah Artileri Kerajaan di Turin. Pada usia 23 tahun ia bergabung dengan Akademi Berlin. Frederick Agung menulis kepada Lagrange dengan menyatakan bahwa “raja terbesar di Eropa” seharusnya mempunyai “matematikawan terbesar di Eropa” di istananya. Selama 20 tahun Lagrange menduduki jabatan yang ditinggalkan mentornya, Euler. Karyanya mencakup sumbangsih pada teori bilangan, teori grup, fisika dan mekanika, kalkulus variasi, teori persamaan, serta persamaan diferensial. Bersama Laplace dan Lavoisier, Lagrange merupakan salah satu tokoh yang bertanggung jawab merancang sistem metrik. Sepanjang hidupnya Lagrange sangat memengaruhi perkembangan matematika, dan mewariskan banyak hal kepada generasi matematikawan berikutnya dalam bentuk contoh serta masalah baru untuk dipecahkan.
