Chào các em học sinh lớp 8 thân mến!

Hôm nay, chúng ta sẽ cùng nhau khám phá một trong những định lý rất quan trọng trong số học, giúp chúng ta hiểu rõ hơn về mối quan hệ giữa các phép toán đồng dư. Định lý này được gọi là Tiêu chuẩn Euler (Euler’s Criterion), một công cụ mạnh mẽ để xác định xem một số có phải là số chính phương modulo \(p\) hay không.

Bài toán chúng ta cần chứng minh có nội dung như sau:

Chứng minh rằng với mọi số nguyên \(a\) thỏa mãn \((a,p)=1\) (tức là \(a\) không chia hết cho \(p\), với \(p\) là một số nguyên tố lẻ), thì:

\(a^{((p-1)/2)} \equiv 1 \pmod p\) khi và chỉ khi tồn tại \(x\) nguyên sao cho \(x^2 \equiv a \pmod p\).

Trước khi đi vào chứng minh chi tiết, chúng ta cần nhớ lại một số kiến thức nền tảng quan trọng:

1. Định lý Fermat nhỏ (Fermat’s Little Theorem): Nếu \(p\) là số nguyên tố và \(a\) là số nguyên không chia hết cho \(p\), thì \(a^{p-1} \equiv 1 \pmod p\).
2. Khái niệm Căn nguyên thủy (Primitive Root): Modulo một số nguyên tố \(p\), tồn tại ít nhất một số nguyên \(g\) (gọi là căn nguyên thủy) sao cho các lũy thừa của nó \(g^1, g^2, \ldots, g^{p-1}\) tạo thành một hệ thặng dư đầy đủ modulo \(p\) (trừ 0). Tức là, mọi số nguyên \(a\) không chia hết cho \(p\) đều có thể viết dưới dạng \(a \equiv g^k \pmod p\) với một số nguyên \(k\) duy nhất trong khoảng \(1 \le k \le p-1\).
3. Tính chất đồng dư: Nếu \(A \equiv B \pmod n\) và \(C \equiv D \pmod n\), thì \(AC \equiv BD \pmod n\). Ngoài ra, nếu \(A \equiv B \pmod n\), thì \(A^k \equiv B^k \pmod n\) với mọi số nguyên dương \(k\).

Chúng ta sẽ chứng minh định lý này theo hai chiều:

—

Chiều thuận (\(\Leftarrow\)): Nếu tồn tại \(x\) nguyên sao cho \(x^2 \equiv a \pmod p\), thì \(a^{((p-1)/2)} \equiv 1 \pmod p\).

Giả sử rằng tồn tại một số nguyên \(x\) sao cho \(x^2 \equiv a \pmod p\).

Vì \((a,p)=1\), tức là \(a\) không chia hết cho \(p\), điều này có nghĩa là \(x^2\) cũng không chia hết cho \(p\). Từ đó suy ra \(x\) cũng không chia hết cho \(p\), hay nói cách khác \((x,p)=1\).

Vì \((x,p)=1\), chúng ta có thể áp dụng Định lý Fermat nhỏ cho \(x\):

\(x^{p-1} \equiv 1 \pmod p\)

Mặt khác, chúng ta có thể viết \(x^{p-1}\) dưới dạng:

\(x^{p-1} = x^{2 \cdot ((p-1)/2)} = (x^2)^{((p-1)/2)}\)

Thay thế \(x^2 \equiv a \pmod p\) vào biểu thức trên, ta được:

\((x^2)^{((p-1)/2)} \equiv a^{((p-1)/2)} \pmod p\)

Kết hợp hai điều này, chúng ta có:

\(a^{((p-1)/2)} \equiv x^{p-1} \equiv 1 \pmod p\)

Vậy là chúng ta đã chứng minh được chiều thuận: Nếu \(x^2 \equiv a \pmod p\) có nghiệm, thì \(a^{((p-1)/2)} \equiv 1 \pmod p\).

—

Chiều đảo (\(\Rightarrow\)): Nếu \(a^{((p-1)/2)} \equiv 1 \pmod p\), thì tồn tại \(x\) nguyên sao cho \(x^2 \equiv a \pmod p\).

Để chứng minh chiều này, chúng ta sẽ sử dụng khái niệm căn nguyên thủy modulo \(p\).

Vì \(p\) là số nguyên tố, tồn tại một căn nguyên thủy \(g\) modulo \(p\). Điều này có nghĩa là mọi số nguyên \(a\) không chia hết cho \(p\) đều có thể biểu diễn dưới dạng lũy thừa của \(g\).

Vậy, tồn tại một số nguyên \(k\) (duy nhất trong khoảng \(1 \le k \le p-1\)) sao cho:

\(a \equiv g^k \pmod p\)

Theo giả thiết của chiều đảo, chúng ta có \(a^{((p-1)/2)} \equiv 1 \pmod p\). Hãy thay biểu thức của \(a\) vào:

\((g^k)^{((p-1)/2)} \equiv 1 \pmod p\)

\(g^{k(p-1)/2} \equiv 1 \pmod p\)

Theo định nghĩa của căn nguyên thủy \(g\), lũy thừa nhỏ nhất của \(g\) mà đồng dư với 1 modulo \(p\) là \(p-1\). Nói cách khác, bậc của \(g\) modulo \(p\) là \(p-1\).

Từ \(g^{k(p-1)/2} \equiv 1 \pmod p\), suy ra rằng \(p-1\) phải là ước của \(k(p-1)/2\).

Điều này có nghĩa là:

\(k(p-1)/2 = m(p-1)\) cho một số nguyên \(m\) nào đó.

Chia cả hai vế cho \((p-1)\) (vì \(p-1 \ne 0\)), ta được:

\(k/2 = m\)

Điều này chứng tỏ rằng \(k\) phải là một số chẵn. Chúng ta có thể viết \(k = 2m\) cho một số nguyên \(m\) nào đó (ví dụ: \(m = k/2\)).

Bây giờ, chúng ta thay \(k = 2m\) trở lại biểu thức của \(a\):

\(a \equiv g^k \pmod p\)

\(a \equiv g^{2m} \pmod p\)

\(a \equiv (g^m)^2 \pmod p\)

Nếu chúng ta đặt \(x = g^m\), thì chúng ta có:

\(x^2 \equiv a \pmod p\)

Như vậy, chúng ta đã tìm được một số nguyên \(x\) (cụ thể là \(g^m\)) sao cho \(x^2 \equiv a \pmod p\).

Vậy là chúng ta đã chứng minh được chiều đảo: Nếu \(a^{((p-1)/2)} \equiv 1 \pmod p\), thì tồn tại \(x\) nguyên sao cho \(x^2 \equiv a \pmod p\).

—

Kết luận:

Qua việc chứng minh cả hai chiều của mệnh đề, chúng ta đã hoàn thành việc chứng minh Tiêu chuẩn Euler. Định lý này cho chúng ta một cách hiệu quả để kiểm tra xem một số \(a\) có phải là một số chính phương modulo \(p\) hay không (khi \((a,p)=1\)). Nếu \(a^{((p-1)/2)} \equiv 1 \pmod p\), thì \(a\) là một số chính phương modulo \(p\). Nếu \(a^{((p-1)/2)} \equiv -1 \pmod p\) (điều này cũng xảy ra theo Định lý Fermat nhỏ vì \(a^{p-1} \equiv (a^{((p-1)/2)})^2 \equiv 1 \pmod p\), nên \(a^{((p-1)/2)}\) phải là nghiệm của \(y^2 \equiv 1 \pmod p\), mà hai nghiệm đó là \(1\) và \(-1\)), thì \(a\) không phải là số chính phương modulo \(p\).

Hy vọng các em đã hiểu rõ về định lý quan trọng này và cách chứng minh nó. Đây là một nền tảng vững chắc cho việc học cao hơn về lý thuyết số và mật mã học sau này nhé!