Giới thiệu về chức năng Phi của Euler

Question

Đây là từ cuốn sách Lý thuyết số của Joseph Silverman.

Đây là phần giới thiệu trước khi anh ấy tiếp tục với Phi Chức năng của Euler.

---

Trong chương trước, chúng ta đã chứng minh Định lý nhỏ của Fermat: Nếu p là số nguyên tố và p không chia a, thì $a^{p-l} \equiv 1 \pmod p$. Công thức này chắc chắn không đúng nếu chúng ta thay thế p bằng một số tổng hợp. Ví dụ,$5^5 \equiv 5 \pmod 6$ và $2^8 \equiv 4 \pmod 9$. Vì vậy, chúng tôi hỏi liệu có một số sức mạnh, tùy thuộc vào mô-đun m, sao cho$a^{???} \equiv 1 \pmod m$. Quan sát đầu tiên của chúng tôi là điều này là không thể nếu gcd (a, m)> 1. Để xem tại sao, hãy giả sử rằng$a^{k} \equiv 1 \pmod m$. Sau đó$a^{k} = 1 + my$ cho một số nguyên y, vì vậy gcd (a, m) chia $a^{k} -my = 1$. Nói cách khác, nếu một số lũy thừa của a đồng dư với 1 modulo m, thì chúng ta phải có gcd (a, m) = 1.

---

Tôi không thể hiểu được 2 dòng cuối cùng ở đây

• Sau đó $a^{k} = 1 + my$ cho một số nguyên y, vì vậy gcd (a, m) chia $a^{k} - my = 1$.

Dòng trên có nghĩa là gì? $a^{k} - my = 1$là một phương trình. Làm thế nào gcd (a, m) có thể chia một phương trình?

Sau đó, tôi không hiểu làm thế nào dòng tiếp theo cũng nói về

• Nói cách khác, nếu một số lũy thừa của a đồng dư với 1 modulo m, thì chúng ta phải có gcd (a, m) = 1.

Ai đó có thể vui lòng giúp đỡ?

Answer 1

Nếu $c \equiv 1 \pmod{b}$, thì điều này có nghĩa là gì $c-1 \equiv 0 \pmod{b}$ hoặc là $c-1$ là bội số của $b$.

Chúng ta có $a^k \equiv 1 \pmod{m}$, vì thế $a^k-1$ là bội số của $m$, do đó chúng ta có thể tìm thấy một số nguyên $y$ như vậy mà $a^k-1 = my$.

Sắp xếp lại phương trình, $$a^k - my =1$$

Đối với $k \ge 1$, theo định nghĩa của ước số chung, $\gcd(a, m)$ phải chia $a$ và nó cũng phải chia $m$, do đó nó phải chia $a^k-my$ bằng $1$.

$\gcd(a,m)$ phân chia $1$. Số nguyên dương duy nhất chia$1$ Là $1$.

Vì thế $\gcd(a,m)$ cần phải $1$.