Pengantar Fungsi Phi Euler

Question

Ini dari Buku Teori Bilangan oleh Joseph Silverman.

Ini adalah pengantar sebelum dia melanjutkan ke Fungsi Phi Euler.

---

Pada bab sebelumnya kita membuktikan Teorema Kecil Fermat: Jika p adalah bilangan prima dan p tidak membagi a, maka $a^{p-l} \equiv 1 \pmod p$. Rumus ini tentunya tidak benar jika kita mengganti p dengan bilangan komposit. Sebagai contoh,$5^5 \equiv 5 \pmod 6$ dan $2^8 \equiv 4 \pmod 9$. Jadi kita bertanya apakah ada daya, tergantung pada modulus m, sedemikian rupa$a^{???} \equiv 1 \pmod m$. Pengamatan pertama kita adalah bahwa ini tidak mungkin jika gcd (a, m)> 1. Untuk melihat mengapa, anggap saja$a^{k} \equiv 1 \pmod m$. Kemudian$a^{k} = 1 + my$ untuk beberapa bilangan bulat y, jadi gcd (a, m) membagi $a^{k} -my = 1$. Dengan kata lain, jika suatu pangkat a kongruen dengan 1 modulo m, maka kita harus memiliki gcd (a, m) = 1.

---

Saya tidak dapat memahami 2 baris terakhir di sini

• Kemudian $a^{k} = 1 + my$ untuk beberapa bilangan bulat y, jadi gcd (a, m) membagi $a^{k} - my = 1$.

Apa arti baris di atas? $a^{k} - my = 1$adalah persamaan. Bagaimana gcd (a, m) membagi persamaan?

Maka saya tidak mengerti bagaimana baris berikutnya juga muncul

• Dengan kata lain, jika suatu pangkat a kongruen dengan 1 modulo m, maka kita harus memiliki gcd (a, m) = 1.

Dapatkah seseorang tolong bantu?

Answer 1

Jika $c \equiv 1 \pmod{b}$, lalu apa artinya ini $c-1 \equiv 0 \pmod{b}$ atau $c-1$ adalah kelipatan dari $b$.

Kita punya $a^k \equiv 1 \pmod{m}$, karenanya $a^k-1$ adalah kelipatan dari $m$, maka kita dapat menemukan bilangan bulat $y$ seperti yang $a^k-1 = my$.

Menyusun ulang persamaan, $$a^k - my =1$$

Untuk $k \ge 1$, dengan definisi pembagi persekutuan, $\gcd(a, m)$ harus membagi $a$ dan itu juga harus terbagi $m$, karenanya harus membagi $a^k-my$ yang sama dengan $1$.

$\gcd(a,m)$ membagi $1$. Satu-satunya bilangan bulat positif yang membagi$1$ adalah $1$.

Karenanya $\gcd(a,m)$ harus $1$.