1. Phép chia Euclid. Thuật toán Euclid

1.1. Phép chia Euclid

Đây là nền tảng, cơ sở của số học. Từ khi biết tới phép chia hai số nguyên, ta có thể tìm thương và số dư. Nói theo toán học, nếu ta có hai số nguyên dương \(a\) và \(b\) thì tồn tại cặp số \(q\), \(r\) sao cho \(a = qb + r\) với \(0 \leqslant r < b\).

Khi đó, \(a\) gọi là số bị chia, \(b\) gọi là số chia, \(q\) là thương (q trong quotient) và \(r\) là số dư (r trong remainder).

Đặc biệt, sự tồn tại của cặp số \(q\) và \(r\) là duy nhất. Thật vậy, nếu ta giả sử tồn tại hai cặp số \((q_1, r_1)\) và \((q_2, r_2)\) đều thỏa đẳng thức trên, nghĩa là

\[a = q_1 b + r_1, \quad a = q_2 b + r_2.\]

Trừ hai đẳng thức vế theo vế ta có

\[(q_1 - q_2) b + (r_1 - r_2) = 0,\]

tương đương \((r_2 - r_1) = (q_1 - q_2) b\), mà \(0 \leqslant r_1, r_2 < b\) nên \(-b < r_2 - r_1 < b\).

Như vậy chỉ có thể xảy ra trường hợp \(r_2 - r_1 = 0\) (vì giá trị tuyệt đối của vế phải là bội của \(b\) nên sẽ lớn hơn \(b\), còn vế trái lại có giá trị tuyệt đối nhỏ hơn \(b\)) hay \(r_2 = r_1\), kéo theo \(q_1 = q_2\).

Định lý 1.16 (Định lí cơ bản của số học)

Mỗi số nguyên lớn hơn \(1\) đều có thể phân tích thành tích các số nguyên tố theo một cách duy nhất.

1.2. Vành modulo số nguyên (кольца вычётов)

Cố định \(m \in \NN\) với \(m > 1\).

Hai số \(a, b \in \ZZ\) được gọi là đồng dư modulo \(m\) (hay сравнимы по модулю \(m\)) nếu \(a\) và \(b\) có cùng số dư khi chia cho \(m\).

Nói cách khác, \(m \mid (a - b)\). Khi đó ta kí hiệu

\[a \equiv b \pmod{m}.\]

Lớp thương (hay класс вычётов) của số nguyên \(k\) theo modulo \(m\) là tập

\[k \bmod m = \{ l \in \ZZ : l \equiv k \bmod m \} = \{ l = k + m \cdot n : n \in \ZZ \} = k + m \ZZ.\]

Kí hiệu ngắn gọn là \(k \bmod m = \overline{k}\).

Tính chất của lớp thương:

  1. Trong một lớp thương mọi số đều đồng dư với nhau theo modulo \(m\), tức là đều có cùng số dư khi chia cho \(m\).

  2. Các số nguyên từ các lớp thương khác nhau thì không đồng dư theo modulo \(m\).

  3. Các lớp thương khác nhau thì không giao nhau.

  4. Mọi lớp thương modulo \(m\) phân chia tập \(\ZZ\) thành các tập con không giao nhau.

Tập hợp tất cả lớp thương modulo \(m\) được kí hiệu là

\[\ZZ_m = \{ \overline{0}, \overline{1}, \ldots, \overline{m-1} \}.\]

Các toán tử trên \(\ZZ_m\):

  1. Phép cộng: \(\overline{k} + \overline{l} = \overline{k + l}\).

  2. Phép nhân: \(\overline{k} \cdot \overline{l} = \overline{k \cdot l}\).

Lớp \(\overline{a} \in \ZZ_m\) được gọi là khả nghịch (hay обратимый) nếu tồn tại \(\overline{b} \in \ZZ_m\) sao cho \(\overline{a} \cdot \overline{b} = 1\).

Khi đó \(\overline{b}\) được gọi là nghịch đảo (hay обратый) của \(\overline{a}\).

Dễ thấy, nghịch đảo, nếu tồn tại, của \(\overline{a}\) là duy nhất. Ta có thể chứng minh bằng phản chứng.

Lớp khác không \(\overline{a} \in \ZZ_m\) được gọi là делитель нуля nếu tồn tại \(\overline{b} \neq \overline{0} \in \ZZ_m\) sao cho \(\overline{a} \cdot \overline{b} = \overline{0}\).

Ví dụ, \(\overline{2} \in \ZZ_4\) có \(\overline{2} \cdot \overline{2} = \overline{4}\) nên \(\overline{2}\) là делитель нуля trong của \(\ZZ_4\).

Chú ý rằng, khi \(\overline{a} \cdot \overline{b} = \overline{0}\) trong \(\ZZ_m\) thì ta không thể suy ra \(\overline{a} = \overline{0}\) hay \(\overline{b} = \overline{0}\).

Nếu \(p\) là số nguyên tố thì trong \(\ZZ_p\) không có делитель нуля.

Tập hợp tất cả lớp khả nghịch trong \(\ZZ_m\) được kí hiệu là \(\ZZ_m^{\times}\).

Ta có tính chất trên \(\ZZ_m\):

  1. Với mọi \(a \in \ZZ\), \(a \equiv a \pmod{m}\).

  2. Nếu \(a \equiv b \pmod{m}\) thì \(b \equiv a \pmod{m}\).

  3. Nếu \(a \equiv b \pmod{m}\) và \(b \equiv c \pmod{m}\) thì \(a \equiv c \pmod{m}\).

  4. Nếu \(a \equiv b \pmod{m}\) thì \(a \cdot c \equiv b \cdot c \pmod{m}\).

  5. Nếu \(c \cdot a \equiv c \cdot b \pmod{m}\) và \(\gcd(c, m) = 1\) thì \(a \equiv b \pmod{m}\).

  6. Nếu \(a \equiv b \pmod{m}\) thì \(c \cdot a \equiv c \cdot b \pmod{cm}\).

  7. Nếu \(a \equiv b \pmod{m}\) và \(c \equiv d \pmod{m}\) thì \(a \pm c \equiv b \pm d \pmod{m}\) và \(a \cdot c \equiv b \cdot d \pmod{m}\).

  8. Nếu \(a \equiv b \pmod{m}\) thì \(a^n \equiv b^n \pmod{m}\).

  9. Nếu \(a \equiv b \pmod{m}\) và \(f(x)\) là đa thức với hệ số nguyên thì \(f(a) \equiv f(b) \pmod{m}\).

1.3. Thuật toán Euclid

Dựa trên phép chia Euclid, ta có một thuật toán hiệu quả để tìm ước chung lớn nhất giữa hai số \(a\) và \(b\).

Kí hiệu \(\gcd(a, b)\) là ước chung lớn nhất của \(a\) và \(b\). Chúng ta thực hiện đệ quy như sau:

\[\begin{split}\gcd(a, b) = \begin{cases} a, \ & \text{nếu} \, b = 0 \\ \gcd(b, a \bmod b), \ & \text{nếu} \, b \neq 0. \end{cases}\end{split}\]

Điểm quan trọng ở thuật toán Euclid là thuật toán chắc chắn sẽ dừng sau một số hữu hạn bước, và kết quả sẽ là ước chung lớn nhất của hai số \(a\) và \(b\).

Chứng minh

Đặt \(r_0 = a\) và \(r_1 = b\). Theo phép chia Euclid tồn tại các số \(q_0\) và \(r_2\) sao cho \(r_0 = r_1 q_0 + r_2\) với \(0 \leqslant r_2 < r_1\).

Trong thuật toán Euclid, ở bước thứ \(i\) (\(i = 1, 2, \ldots\)) vì đã biết \(r_i\) và \(r_{i+1}\) nên ta tìm được thương \(q_i\) và số dư \(r_{i+2}\) trong phép chia \(r_i\) cho \(r_{i+1}\).

\[\begin{split}r_0 & = r_1 q_0 + r_2 \\ r_1 & = r_2 q_1 + r_3 \\ r_2 & = r_3 q_2 + r_4 \\ \ldots & = \ldots \\ r_i & = r_{i+1} q_i + r_{i+2} \\ \ldots & = \ldots \\ r_k & = r_{k+1} q_k + 0 \\\end{split}\]

Ở mỗi bước, \(r_{i+2}\) luôn nhỏ hơn \(r_{i+1}\). Do đó cuối cùng sẽ bằng \(0\), và khi đó ta có ước chung lớn nhất là \(r_{k+1}\) như trên.

Hệ quả 1.2

Tồn tại các số \(u\) và \(v\) sao cho

\[u \cdot a + v \cdot b = \gcd(a, b).\]

Bổ đề 1.1

Giả sử \(p\) là số nguyên tố. Khi đó nếu \(a \cdot b\) chia hết cho \(p\) thì \(a\) chia hết cho \(p\) hoặc \(b\) chia hết cho \(p\).

Chứng minh

Nếu \(a\) không chia hết cho \(p\) thì \(\gcd(a, p) = 1\), hay tồn tại \(u\) và \(v \in \ZZ\) sao cho \(u \cdot a + v \cdot p = 1\). Khi đó nhân hai vế cho \(b\) ta có

\[u \cdot ab + v \cdot bp = b,\]

mà \(p \mid ab\) và \(p \mid p\) nên \(p \mid b\).

Hai số \(a\) và \(b\) được gọi là nguyên tố cùng nhau (hay coprime, взаимо простые) nếu \(\gcd(a, b) = 1\).

Số tự nhiên \(p\) được gọi là số nguyên tố (hay prime, простой) nếu nó chỉ có hai ước là \(1\) và chính nó.

Ví dụ 1.29

Tìm ước chung lớn nhất của \(784\) và \(74\).

\[\begin{split}\begin{array}{ccccc} r_i & = & r_{i+1} \cdot q_i & + & r_{i+2} \\ 784 & = & {\color{red}{74}} \cdot 10 & + & {\color{blue}{44}} \\ {\color{red}74} & = & {\color{blue}{44}} \cdot 1 & + & {\color{green}{30}} \\ {\color{blue}{44}} & = & {\color{green}{30}} \cdot 1 & + & {\color{magenta}{14}} \\ {\color{green}{30}} & = & {\color{magenta}{14}} \cdot 2 & + & {\color{orange}{2}} \\ {\color{magenta}{14}} & = & {\color{orange}{2}} \cdot 7 & + & {\boxed{\color{purple}{0}}} \end{array}\end{split}\]

Vậy \(\gcd(784, 74) = 2\).

1.4. Thuật toán Euclid mở rộng

Định nghĩa 1.56 (Phương trình Diophantus)

Cho trước các số nguyên \(a\), \(b\) và \(c\). Phương trình Diophantus là phương trình có dạng

\[ax + by = c\]

với \(x\), \(y\) là các số nguyên.

Ví dụ 1.30

Giải phương trình \(5x+3y = 1\).

Ta có

\[y = \dfrac{1-5x}{3} = \dfrac{1-2x-3x}{3} = \dfrac{1-2x}{3} - x.\]

Như vậy nếu \(y \in \mathbb{Z}\) thì \(\dfrac{1-2x}{3} \in \mathbb{Z}\), nghĩa là \(1-2x\) chia hết cho \(3\). Vậy \(1-2x = 3k\) với \(k \in \mathbb{Z}\).

Tiếp tục, \(1-2x = 3k\), suy ra

\[x = \dfrac{1-3k}{2} = \dfrac{1-k-2k}{2} = \dfrac{1-k}{2} - k.\]

Do \(x\) nguyên nên tương tự \(\dfrac{1-k}{2}\) cũng nguyên, hay \(1-k = 2t\), tương đương với \(k = 1-2t\).

Thay ngược lại ta có

\[x = \dfrac{1-3k}{2} = \dfrac{1-3(1-2t)}{2} = {-1+3t}.\]

Tiếp tục thay vào để tìm \(y\) thì

\[y = \dfrac{1-5x}{3} = \dfrac{1-5(-1+3t)}{3} = 2 - 5t.\]

Như vậy nghiệm của phương trình là tất cả các nghiệm \((x, y)\) mà \(x = -1+3t\), \(y = 2-5t\) với \(t \in \mathbb{Z}\).

Ở đây chúng ta đã thực hiện phép chia có dư liên tiếp để tìm nghiệm. Nói cách khác ta đã thực hiện thuật toán Euclid ở bên trên để làm giảm độ phức tạp ở mỗi bước giải.

Tổng quát ta có thuật toán Euclid mở rộng để tìm ước chung lớn nhất \(\gcd(a, b)\) của hai số \(a\), \(b\), và một nghiệm của phương trình \(ax + by = \gcd(a, b)\).

Ở ví dụ trên, ta đã tìm được một nghiệm của phương trình \(5x + 3y = 1\) là \((-1, 2)\) khi \(t = 0\). Khi đó ta có thể suy ra tất cả nghiệm (họ nghiệm) của phương trình có dạng \((-1+3t, 2-5t)\) với \(t \in \mathbb{Z}\).

Thuật toán 1.1 (Thuật toán Euclid mở rộng)

Input: \(a, b \in \mathbb{Z}\)

Output: \(\gcd(a, b)\), \(x\), \(y\)

  1. \(r_0 \gets a\), \(r_1 \gets b\), \(r_2 \gets 0\)

  2. \(x_0 \gets 1\), \(x_1 \gets 0\), \(x_2 \gets 0\)

  3. \(y_0 \gets 0\), \(y_1 \gets 1\), \(y_2 \gets 0\)

  4. While \(r_1 \neq 0\)

    1. \(q \gets r_0 \;\text{div}\; r_1\)

    2. \(r_2 \gets r_0 - q * r_1\), \(r_0 \gets r_1\), \(r_1 \gets r_2\)

    3. \(x_2 \gets x_0 - q * x_1\), \(x_0 \gets x_1\), \(x_1 \gets x_2\)

    4. \(y_2 \gets y_0 - q * y_1\), \(y_0 \gets y_1\), \(y_1 \gets y_2\)

  5. EndWhile

  6. Return \(r_0\), \(x_0\), \(y_0\)

Ở thuật toán trên, \(r_0\), \(r_1\) và \(r_2\) hoạt động như thuật toán Euclid chuẩn.

Ở mỗi bước, \(q\) là thương của phép chia \(r_0\) cho \(r_1\), và ta sử dụng \(q\) đó để tính \(x_0\) và \(y_0\) mới. Kết quả cuối cùng \((r_0, x_0, y_0)\) lần lượt là ước chung lớn nhất \(r_0\), và hai số \(x_0\), \(y_0\) thỏa mãn \(a x_0 + y b_0 = r_0\).

Tại sao chúng ta lại có \((x_0, x_1) = (1, 0)\) và \((y_0, y_1) = (0, 1)\)? Thêm nữa, làm sao biết thuật toán hoạt động đúng?

Mục đích của chúng ta là tìm các số \((x, y)\) sao cho \(ax + by = \gcd(a, b)\). Khi đó, dựa trên thuật toán Euclid cơ bản ở trên, ta xây dựng dãy số \(\{ x_n \}\) và \(\{ y_n \}\) sao cho ở mọi bước thứ \(n\) ta đều có

(1.3)\[a x_n + b y_n = r_n.\]

Từ thuật toán Euclid, với \(r_i\) và \(r_{i+1}\) ở bước thứ \(i\) ta thực hiện phép chia Euclid \(r_i = r_{i+1} q_i + r_{i+2}\) để tìm \(q_i\) và \(r_{i+2}\). Từ \(q_i\) ở mỗi bước ta tính

\[x_{i+2} = x_i - x_{i+1} q_i, \quad y_{i+2} = y_i - y_{i+1} q_i.\]

Chuyển vế hai phương trình trên ta có

\[x_i = x_{i+1} q_i + x_{i+2}, \quad y_i = y_{i+1} q_i + y_{i+2}.\]

Nếu thay hai phương trình vừa rồi vào (1.3) ta được

\[a (x_{i+1} q_i + x_{i+2}) + b (y_{i+1} q_i + y_{i+2}) = r_i,\]

tương đương với

\[(a x_{i+1} + b y_{i+1}) \cdot q_i + (a x_{i+2} + b x_{i+2}) = r_i.\]

Do

\[a x_{i+1} + b y_{i+1} = r_{i+1}, \quad a x_{i+2} + b y_{i+2} = r_{i+2},\]

nên \(r_{i+1} q_i + r_{i+2} = r_i\), đúng với thuật toán Euclid chuẩn ban đầu. Như vậy thuật toán mở rộng hoạt động đúng.

Bây giờ ta cần chọn \((x_0, x_1)\) và \((y_0, y_1)\) vì chúng ta đã đặt \(r_0 = a\) và \(r_1 = b\).

Ở bước thứ \(0\), vì

\[r_0 = a = a x_0 + b y_0,\]

và ở bước thứ \(1\),

\[r_1 = b = a x_1 + b y_1.\]

Dễ thấy ở bước \(0\) ta chọn \(x_0 = 1\) và \(x_1 = 0\), còn ở bước \(1\) ta chọn \(y_0 = 0\) và \(y_1 = 1\) là được.

Ví dụ 1.31

Tìm một nghiệm nguyên của phương trình \(784 x + 74 y = 2\).

\[\begin{split}\begin{array}{ccccc|ccccc|ccccc} r_i & = & r_{i+1} \cdot q_i & + & r_{i+2} & x_{i+2} & = & x_i & - & x_{i+1} \cdot q_i & y_{i+2} & = & y_i & - & y_{i+1} \cdot q_i \\ 784 & = & {\color{red}{74}} \cdot 10 & + & {\color{blue}{44}} & {\color{blue}1} & = & 1 & - & {\color{red}0} \cdot 10 & {\color{blue}-10} & = & 0 & - & {\color{red}1} \cdot 10 \\ {\color{red}74} & = & {\color{blue}{44}} \cdot 1 & + & {\color{green}{30}} & {\color{green}-1} & = & {\color{red}0} & - & {\color{blue}1} \cdot 1 & {\color{green}11} & = & {\color{red}1} & - & {\color{blue}(-10)} \cdot 1 \\ {\color{blue}{44}} & = & {\color{green}{30}} \cdot 1 & + & {\color{magenta}{14}} & {\color{magenta}2} & = & {\color{blue}1} & - & {\color{green}(-1)} \cdot 1 & {\color{magenta}-21} & = & {\color{blue}-10} & - & {\color{green}11} \cdot 1 \\ {\color{green}{30}} & = & {\color{magenta}{14}} \cdot 2 & + & {\color{orange}{2}} & {\color{orange}-5} & = & {\color{green}(-1)} & - & {\color{magenta}2} \cdot 2 & {\color{orange}53} & = & {\color{green}11} & - & {\color{magenta}(-21)} \cdot 2\\ {\color{magenta}{14}} & = & {\color{orange}{2}} \cdot 7 & + & {\boxed{\color{purple}{0}}} \end{array}\end{split}\]

Các bạn có thể thấy ước chung lớn nhất là số màu cam. Do đó các số \(x_{i+2}\) và \(y_{i+2}\) cũng chính là điểm dừng và mình không cần tính toán thêm.

Như vậy một nghiệm của phương trình \(784 x + 74 y = 2\) là \((-5, 53)\).

Chúng ta cũng có một cách trình bày khác để giải phương trình nghiệm nguyên trên là sử dụng biến đổi tương đương của ma trận.

Ví dụ, để tìm một nghiệm nguyên \((x, y)\) của phương trình \(a x + b y = c\) với \(a\), \(b\), \(c\) là các số cho trước, chúng ta viết ma trận

\[\begin{split}\left(\begin{array}{cc|c} 1 & 0 & a \\ 0 & 1 & b \end{array}\right)\end{split}\]

và biến đổi tương đương về dạng

\[\begin{split} \left(\begin{array}{cc|c} * & * & c \\ * & * & 0 \end{array}\right)\end{split}\]

Khi đó hai số ở hàng trên sẽ là nghiệm cần tìm.

Ví dụ 1.32

Sử dụng bài toán ở trên làm ví dụ: tìm một nghiệm nguyên của phương trình \(784 x + 74 y = 2\).

\[\begin{split}\left(\begin{array}{cc|c} 1 & 0 & 784 \\ 0 & 1 & 74 \end{array}\right) \sim \left(\begin{array}{cc|c} {\color{blue}1} & {\color{blue}-10} & {\color{blue}44} \\ 0 & 1 & 74 \end{array}\right) \sim \left(\begin{array}{cc|c} {\color{blue}1} & {\color{blue}-10} & {\color{blue}44} \\ {\color{green}-1} & {\color{green}11} & {\color{green}30} \end{array}\right) \\ \sim \left(\begin{array}{cc|c} {\color{magenta}2} & {\color{magenta}-21} & {\color{magenta}14} \\ {\color{green}-1} & {\color{green}11} & {\color{green}30} \end{array}\right) \sim \left(\begin{array}{cc|c} {\color{magenta}2} & {\color{magenta}-21} & {\color{magenta}14} \\ {\color{orange}-5} & {\color{orange}53} & {\color{orange}2} \end{array}\right) \sim \left(\begin{array}{cc|c} 37 & -392 & 0 \\ {\color{orange}-5} & {\color{orange}53} & {\color{orange}2} \end{array}\right)\end{split}\]

Về bản chất thì hai cách trình bày là giống nhau.

1.5. Bài tập sưu tầm

Câu 1 (đề kiểm tra, ITMO). Tính

\[\gcd(61^{610} + 1, 61^{671} - 1).\]

Mình thay \(61\) bởi biến \(x\) và thực hiện phép chia đa thức theo thuật toán Euclid.

Đầu tiên, xét phép chia \(x^{671} - 1\) cho \(x^{610} + 1\). Kết quả phép chia là

\[x^{671} - 1 = (x^{610} + 1) \cdot x^{61} - x^{61} - 1.\]

Tiếp theo, xét phép chia \(x^{610} + 1\) cho \(-x^{61} - 1\). Kết quả là

\[x^{610} + 1 = (-x^{61} - 1) \cdot (-x^{549} + x^{488} - \cdots + 1) + 2.\]

Như vậy, ước chung lớn nhất của hai đa thức là \(2\).

Câu 2 (đề kiểm tra, ITMO). Chứng minh rằng với mọi \(a, b, c \in \mathbb{N}\) thì

\[[a, b, c] = \frac{a \cdot b \cdot c \cdot (a, b, c)}{(a, b) \cdot (a, c) \cdot (b, c)},\]

trong đó

  • \([a, b, c]\) là bội chung nhỏ nhất của ba số \(a\), \(b\), \(c\)

  • \((a, b, c)\) là ước chung lớn nhất của ba số \(a\), \(b\), \(c\)

  • \((a, b)\) là ước chung lớn nhất của hai số \(a\), \(b\).

Chưa làm ra.

Câu 3 (đề kiểm tra, ITMO). Tìm ít nhất một nghiệm nguyên của phương trình

\[311 x - 28 y = 2.\]

Sử dụng thuật toán Euclid:

\[\begin{split}& \left(\begin{array}{cc|c} 1 & 0 & 311 \\ 0 & 1 & -28 \end{array}\right) \stackrel{(1) \to (1) + 11 \cdot (2)}{\sim} \left(\begin{array}{cc|c} 1 & 11 & 3 \\ 0 & 1 & -28 \end{array}\right) \stackrel{(2) \to (2) + 10 \cdot (1)}{\sim} \left(\begin{array}{cc|c} 1 & 11 & 3 \\ 10 & 111 & 2 \end{array}\right) \\ \stackrel{(1) \to (1) - (2)}{\sim} & \left(\begin{array}{cc|c} -9 & -100 & 1 \\ 10 & 111 & 2 \end{array}\right) \stackrel{(2) \to (2) - 2 \cdot (1)}{\sim} \left(\begin{array}{cc|c} -9 & -100 & 1 \\ 28 & 311 & 0 \end{array}\right)\end{split}\]

Như vậy mình có \((-9, -100)\) là một nghiệm của phương trình

\[311 x - 28 y = 1.\]

Từ đó suy ra một nghiệm của phương trình

\[311 x - 28 y = 2\]

là \((2 \cdot (-9), 2 \cdot (-100)) = (-18, -200)\).

Cho \(n\) là số tự nhiên lớn hơn \(4\). Chứng minh rằng \(n\) là số nguyên tố khi và chỉ khi \(n \nmid (n - 1)!\).

Cho \(n > 1\), \(p \nmid n\) với \(p\) là số nguyên tố sao cho \(p \leqslant \sqrt{n}\). Chứng minh rằng \(n\) là số nguyên tố.

Cho \(\gcd(a, b) = 1\). Chứng minh rằng \(\gcd(7a + 6b, 8a + 7b) = 1\).

Ta có \(\gcd(a, b) = \gcd(a, ka + b)\) với \(k \in \ZZ\). Khi đó

\[\gcd(7a + 6b, 8a + 7b) = \gcd(7a + 6b, a + b) = \gcd(a + b, a) = \gcd(b, a) = 1.\]

Giải phương trình \(3x^2 - 2 = y^2\) trên \(\ZZ\).

Giải theo modulo 3.

Chứng minh rằng tồn tại vô hạn số nguyên tố dạng \(3k + 2\) với \(k \in \ZZ\).