Các bài toán về thặng dư toàn phương

Tài liệu về thặng dư toàn phương

Định lý

Một số là thặng dư bậc hai của mọi số nguyên tố không là ước của nó là một số chính phương.

Vì mọi lũy thừa lẻ của 2 là một số không thặng dư của 3, chúng ta có thể giả sử rằng một số như vậy chứa một thừa số lẻ. Gọi $N$ là một thặng dư bậc hai của mọi số nguyên tố không là ước của nó, và $N = j^2 n$, trong đó $n$ không chứa các thừa số chính phương. Khi đó $n$ là một thặng dư bậc hai của cùng các số nguyên tố như $N$.

Đặt $n = p_1 p_2 \dots p_r$ và hơn nữa, gọi $a$ là một số không thặng dư bậc hai của $p_1$ ($p_1$ lẻ) và $b_i$ là một thặng dư bậc hai của $p_i$, $(i=2,\dots,r)$. Các đồng dư $x \equiv 1 \pmod{4}$, $x \equiv a \pmod{p_1}$,

$x \equiv b_i \pmod{p_i} \equiv 1 \pmod{8}$ nếu $p_i = 2$, $(i = 2, \dots, r)$,

khi đó luôn có một nghiệm $s$, vì các mô-đun là nguyên tố cùng nhau. Có vô số giá trị số nguyên tố cho nghiệm tổng quát $x = 4kn + s$. Chọn một số không là ước của $j$. Khi đó

$$\left(\frac{x}{p_1}\right) = \left(\frac{p_1}{x}\right) = -1, \quad \left(\frac{x}{p_i}\right) = \left(\frac{p_i}{x}\right) = +1, \quad (i = 2, \dots, r);$$

Do đó $\left(\frac{N}{x}\right) = \left(\frac{n}{x}\right) = -1$, trái với giả thuyết, và $N$ phải là một số chính phương. Chúng ta thực sự đã chứng minh nhiều hơn định lý, cụ thể là, nếu $N$ là một thặng dư bậc hai của tất cả các số nguyên tố ngoại trừ một số hữu hạn, thì $N$ phải là một số chính phương.

Link bài báo của định lý này

Bài toán

Tìm tất cả các cặp $(p,k) \in \mathbb{P} \times \mathbb{N}$ sao cho với mọi $1 \leq a \leq p-1$:

• Nếu $a$ là một thặng dư bậc hai modulo $p$, thì $a+k$ hoặc là một số không thặng dư bậc hai, hoặc chia hết cho $p$.
• Nếu $a$ là một số không thặng dư bậc hai modulo $p$, thì $a+k$ hoặc là một thặng dư bậc hai, hoặc chia hết cho $p$.

Chứng minh

Nếu $p > 3$ và $k$ là một thặng dư bậc hai (QR), thì $4k$ là một số không thặng dư bậc hai (NQR), suy ra $4$ là NQR. Nhưng $4 = 2^2$, mâu thuẫn.

Nếu $k$ là một số không thặng dư bậc hai (NQR), thì $4k$ là một thặng dư bậc hai (QR), do đó $4$ là NQR, cũng mâu thuẫn.

Vậy, nghiệm duy nhất là $(3,m)$ khi $m$ không chia hết cho $3$.

Bài toán

Cho số nguyên tố $p > 2$. Chứng minh rằng tồn tại một số nguyên dương $a < 1 + \sqrt{p}$ sao cho $a$ không là một thặng dư bậc hai modulo $p$.

Chứng minh

Giả sử khẳng định là sai: tất cả các số nguyên dương nhỏ hơn $1+\sqrt{p}$ đều là thặng dư bậc hai. Gọi $r \geq 2$ là số không thặng dư bậc hai nhỏ nhất modulo $p$. Tiếp theo, chọn $k$ là số nguyên dương nhỏ nhất sao cho $kr > p$, tức là $(k-1)r < p < kr$. Khi đó, $p = kr - i$ với $1 \leq i \leq r-1$.

Vì $i \leq r-1$, nên $i$ là một thặng dư bậc hai. Do đó, $kr$ là một thặng dư bậc hai, suy ra $k$ là một số không thặng dư bậc hai. Điều này dẫn đến $k \geq r \geq 1+\sqrt{p}$.

Nhưng khi đó, $p = kr - i \geq r(k-1) \geq \sqrt{p}(1+\sqrt{p}) > p$, mâu thuẫn. Vậy giả thuyết ban đầu sai, và bài toán được chứng minh.

Bài toán

Cho số nguyên dương $a$. Cho số nguyên tố $p$ sao cho $p \equiv 1 \mod 4a$. Chứng minh rằng số nguyên $a$ là một thặng dư bậc hai modulo $p$.

Chứng minh

Viết $p = 1 + 4ak$, khi đó đặc biệt $p \equiv 1 \pmod{4}$.

Với một ước số nguyên tố lẻ của $a$ là $q$, ta có:

$$\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)\left( \frac{1+4ak}{q} \right) = \left( \frac{1}{q} \right) = 1$$

Với $q=2$ thì $p\equiv 1\pmod 8$ nên $\left(\frac{q}{p}\right)=1$

Điều này đúng, do đó tất cả các $q$ đều là thặng dư bậc hai, cũng như $q^e$, nên $a$ cũng là một thặng dư bậc hai modulo $p$.

Bài toán

Cho $p$ là một số nguyên tố lẻ. Tìm số lượng $x \in \mathbb{Z}$ thỏa mãn $1 \leq x \leq p-2$ và cả $x$ và $x+1$ đều là thặng dư bậc hai.

Chứng minh

$$4N=\sum ^{p-2}_{x=1}\left(\left(\frac{x}{p}\right) +1\right)\left(\left(\frac{x+1}{p}\right) +1\right)$$ $$=\sum ^{p-2}_{x=1}\left(\frac{x( x+1)}{p}\right) +\sum ^{p-2}_{x=1}\left(\frac{x}{p}\right) +\sum ^{p-2}_{x=1}\left(\frac{x+1}{p}\right) +\sum ^{p-2}_{x=1} 1$$ $$=-1-\left(\frac{p-1}{p}\right) -\left(\frac{1}{p}\right) +p-2$$ $$=p-4-\left(\frac{-1}{p}\right)$$ $$N=\boxed{\frac{p-4-\left(\frac{-1}{p}\right)}{4}}$$

Chú ý :

$$\sum ^{p-2}_{x=1}\left(\frac{x( x+1)}{p}\right)=\sum ^{p-2}_{x=1}\left(\frac{1+\frac{1}{x}}{p}\right)=\sum ^{p-1}_{y=2}\left(\frac{y}{p}\right)=-\left(\frac{1}{p}\right)=-1.$$

Nói chung, nếu $p$ là một số nguyên tố lẻ, $p\nmid a$, và $p\nmid b^{2} -4ac$ thì: $$\sum ^{p}_{x=1}\left(\frac{ax^{2} +bx+c}{p}\right) =-\left(\frac{a}{p}\right).$$

Bài toán

Cho $p = a^2 + b^2$ là một số nguyên tố với $a, b$ là các số nguyên dương và $a$ là số lẻ. Chứng minh rằng $a$ là một thặng dư bậc hai modulo $p$.

Chứng minh

Lưu ý rằng $p$ có dạng $4k+1$. Giả sử rằng $q$ là một số nguyên tố là ước của $a$. Theo luật tương hỗ bậc hai (QRL), ta có: $$b^2 \equiv p \pmod{q} \rightarrow \left(\frac{p}{q} \right)=\left(\frac{q}{p} \right) =1$$ Do đó, $a$ là một thặng dư bậc hai modulo $p$.

Bài toán

Chứng minh rằng nếu một số nguyên tố lớn hơn 3 thì tổng các thặng dư bậc hai modulo $p$ chia hết cho $p$.

Chứng minh

Lưu ý rằng $a^2\equiv b^2 \pmod p$ khi và chỉ khi $a \equiv \pm b \pmod p$ (theo hiệu của hai bình phương). Do đó, tổng các thặng dư bậc hai tương đương với: $$1^2 + 2^2 + \cdots + \left(\frac{p-1}{2}\right)^2 = \frac{(p-1)(p+1)p}{24}$$ Vì đã biết rằng $p > 3$, ta dễ dàng thấy rằng: $$p \mid \frac{p(p-1)(p+1)}{24}$$ (Lưu ý rằng điều này cũng cung cấp công thức tổng quát cho tổng các thặng dư bậc hai của một số nguyên tố.)

Bài toán

Cho $p = 8k+1$ là một số nguyên tố, và $h = \operatorname{ord}_p(2)$. Chứng minh rằng $h$ là ước của $\frac{p-1}{2}$.

Chứng minh

Chỉ cần chứng minh rằng $2^{\frac{p-1}{2}} - 1$ chia hết cho $p$. Điều này suy ra từ thực tế rằng $2$ là một thặng dư bậc hai modulo $p$ (vì $8 \mid p - 1$).

Bài toán

Với những số nguyên dương $k$ nào, luôn tồn tại một số nguyên tố $p$ sao cho tất cả các số $1,2,\dots,k$ đều là thặng dư bậc hai modulo $p$?

Chứng minh

Đúng với mọi $k$. Sau đây là lý do.

Trường hợp $k=1$ là hiển nhiên. Giả sử $k>1$. Khi đó, xét tập $S=\{q \text{ nguyên tố}: q\leqslant k\}$ gồm các số nguyên tố nhỏ hơn hoặc bằng $k$. Nếu ta có thể đảm bảo rằng tồn tại một số nguyên tố $p$ sao cho với mọi $q\in S$, ta có $\left(\frac{q}{p}\right)=1$, thì suy ra tất cả các số $1,2,\dots,k$ đều là thặng dư bậc hai.

Để xây dựng một số nguyên tố như vậy, chọn $p \equiv 1 \pmod{8}$. Khi đó, với mỗi $q\in S$ và $q>2$, gọi $a_q$ là một thặng dư bậc hai modulo $q$. Nếu $p\equiv a_q\pmod{q}$, thì theo luật tương hỗ bậc hai: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(\frac{a_q}{q}\right)\left(\frac{q}{p}\right)=1,$$ điều này có nghĩa là $q$ là một thặng dư bậc hai modulo $p$.

Do đó, ta chỉ cần chứng minh rằng tồn tại một số nguyên tố $p$ sao cho $p\equiv 1\pmod{8}$ và $p\equiv a_q\pmod{q}$ với mọi $q\in S$, $q>3$. Một số nguyên tố như vậy rõ ràng tồn tại, theo định lý số dư Trung Hoa và định lý Dirichlet về cấp số cộng số nguyên tố, hoàn tất chứng minh.

Bài toán

Xác định tất cả các số nguyên $n \geq 3$ có dạng thập phân ít hơn 20 chữ số, sao cho mọi số không phải thặng dư bậc hai modulo $n$ đều là một căn nguyên nguyên thủy modulo $n$.

Chứng minh

Giả sử rằng $n$ có một căn nguyên thủy, nếu không bài toán không có ý nghĩa. Giả sử rằng $g$ là một căn nguyên thủy modulo $n$, khi đó tất cả các số $g, g^3, \dots, g^{\varphi(n) -1}$ đều không là thặng dư bậc hai. Do đó, bất kỳ số lẻ nào trong khoảng từ $1$ đến $\varphi(n)$ phải nguyên tố cùng nhau với $\varphi(n)$, điều này có nghĩa là $\varphi(n)$ không có thừa số nguyên tố nào ngoài các số nguyên tố Fermat hoặc $2$. Vì $2^{2^6} + 1$ có hơn 20 chữ số và trong 5 số Fermat đầu tiên, chỉ có số Fermat thứ năm không phải là số nguyên tố, nên các nghiệm là:

$$2,4,F_1,F_2,F_3,F_4,2F_1,2F_2,2F_3,2F_4$$

Trong đó $F_i$ là số Fermat thứ $i$. Riêng nghiệm $4$ thử lại không thỏa mãn do $2$ không là thặng dư bậc hai mod $4$ nhưng $2$ không là căn nguyên thủy mod $4$.

Bài toán

Chứng minh rằng tập hợp các thặng dư bậc hai modulo $2^n$ là một tập con của tập hợp các thặng dư bậc hai modulo $2^{n+1}$ với mọi số tự nhiên $n$.

Chứng minh

Giả sử tồn tại $x^2 \equiv k \pmod{2^n}$ với $x$ là một số lẻ. Ta sẽ chứng minh rằng tồn tại một số nguyên lẻ $y$ sao cho $y^2 \equiv k \pmod{2^{n+1}}$, từ đó suy ra điều cần chứng minh. Để tìm $y$ khi $x$ là số chẵn, ta chỉ cần nhân $x$ với một bội số đủ lớn của 2 từ số lẻ tương ứng $x'$ và giá trị của nó $y'$. Xét phần dư khi $x^2$ chia cho $2^{n+1}$ và gọi nó là $z$. Xuất hiện hai trường hợp:

• (a) $z = k$ Trong trường hợp này, ta đã hoàn thành chứng minh. Chỉ cần đặt $y = x$.
• (b) $z = 2^n + k$ Chọn $y = x + 2^{n-1}$. Dùng khai triển nhị thức, ta có thể kiểm tra rằng $y^2 \equiv k \pmod{2^{n+1}}$.

Vì cả hai trường hợp đều đã được xét, ta kết luận rằng tập hợp các thặng dư bậc hai modulo $2^n$ là một tập con của tập các thặng dư bậc hai modulo $2^{n+1}$.

Bài toán

Tìm giá trị của $$\sum_{a=1}^{p-1}{\left(\frac{a^2+a}{p}\right )}$$ trong đó $p$ là số nguyên tố và $\left(\frac{x}{p}\right)$ là ký hiệu Legendre.

Chứng minh

Ta có: $$\sum_{a=1}^{p-1}{\left(\frac{a^2+a}{p}\right )}=\sum_{a=1}^{p-1}{\left(\frac{1+a^{-1}}{p}\right )}$$ bởi vì $$\left(\frac{a}{p}\right)\left(\frac{a^{-1}}{p}\right)=\left(\frac{1}{p}\right)=1.$$

Và tổng này bằng: $$\sum_{a=2}^{p}{\left(\frac{a}{p}\right )}=-1$$ bởi vì có $\frac{p-3}{2}$ thặng dư bậc hai và $\frac{p-1}{2}$ không phải thặng dư bậc hai trong tập $\{2, \dots, p\}$ không bao gồm $p$.

Bài toán

Chứng minh rằng với mọi số nguyên $x, y$, biểu thức $$\frac{x^2-2}{2y^2+3}$$ không thể là một số nguyên.

Chứng minh

$2y^{2}+3$ có giá trị là $5,3$ theo modulo $8$ và $x^{2}-2$ chỉ có các thừa số nguyên tố lẻ đồng dư với $1,-1$ theo modulo $8$. Điều này có nghĩa là mọi ước số lẻ của nó cũng đồng dư với $1,-1$ theo modulo $8$, do đó, tỉ số không thể là một số nguyên.

Bài toán

Tìm tất cả các bộ ba số nguyên dương $(a, b, c)$ thỏa mãn tính chất sau: Với mọi số nguyên tố $p$, nếu $n$ là một thặng dư bậc hai modulo $p$, thì $an^2+bn+c$ cũng là một thặng dư bậc hai modulo $p$.

Chứng minh

Chọn $n = m^2$, khi đó $am^4 + bm^2 + c$ là một thặng dư bậc hai modulo $p$ với mọi số nguyên tố, và do đó là một số chính phương theo một kết quả quen thuộc rằng $k$ là một thặng dư bậc hai modulo mọi số nguyên tố $\Longleftrightarrow k$ là một số chính phương.

Tuy nhiên, theo một kết quả quen thuộc khác (và không quá khó để chứng minh) rằng một đa thức là số chính phương tại mọi số nguyên khi và chỉ khi nó là số chính phương trong $\mathbb{Z}[x]$, ta có: $$am^4 + bm^2 + c = P(m)^2$$ với một đa thức nguyên $P$.

Lưu ý rằng khi đó $P$ phải có dạng $P(x) = dx^2 + e$, do đó: $$(a,b,c) = (d^2, 2de, e^2)$$ với một số chọn lựa $d, e$. Rõ ràng bài toán đúng trong trường hợp này, và do đó ta đã chứng minh xong.

Bài toán

(Stars of Mathematics 2020) Xác định các số nguyên tố $p$ sao cho các số $$2\lfloor p/k\rfloor - 1, \quad k = 1,2,\ldots, p,$$ đều là thặng dư bậc hai modulo $p$.

Chứng minh

Lưu ý rằng $p=2$ là hợp lệ, và giả sử rằng $p$ là số lẻ. Chọn $k=1$ để suy ra rằng $-1$ là một thặng dư bậc hai. Tiếp theo, chọn $k=2$ và sử dụng kết quả trước để suy ra rằng $2$ cũng là một thặng dư bậc hai.

Lưu ý rằng $\lfloor p/m\rfloor=n \iff p/(n+1) < m\leq p/n$. Do đó, nếu $n\leq\sqrt{p}-1$, ta có $p/n - p/(n+1) \geq 1$, nên chắc chắn tồn tại một số nguyên $m$ sao cho $\lfloor p/m\rfloor=n$. Từ đó suy ra rằng $2i-1$ là một thặng dư bậc hai với mọi $1\leq i\leq\sqrt{p}-1$.

Nói cách khác, tất cả các số nguyên tố $q\leq 2\sqrt{p}-1$ là các thặng dư bậc hai modulo $p$. Bây giờ, sử dụng tính chất bắc cầu của ký hiệu Legendre, ta có: $$\Bigg(\frac{\prod p_i^{a_i}}{p}\Bigg) = \prod\bigg(\frac{p_i}{p}\bigg)^{a_i}$$ Do đó, có thể kết luận rằng tất cả các số nguyên $1\leq n\leq 2\sqrt{p}-1$ là các thặng dư bậc hai modulo $p$.

Bổ đề:

Với mọi số nguyên tố lẻ $p$, thặng dư bậc hai nhỏ nhất không phải là thặng dư bậc hai nhỏ hơn $\sqrt{p}+1$.

Chứng minh bổ đề:

Gọi $n$ là số nhỏ nhất không phải là thặng dư bậc hai. Định nghĩa $m=n\big(\lfloor p/n\rfloor+1\big)-p$, khi đó ta có $n>m>0$. Hơn nữa, ta có: $$\bigg(\frac{m}{p}\bigg) = \bigg(\frac{n\big(\lfloor p/n\rfloor+1\big)}{p}\bigg) = \bigg(\frac{n}{p}\bigg)\bigg(\frac{\lfloor p/n\rfloor+1}{p}\bigg) = -\bigg(\frac{\lfloor p/n\rfloor+1}{p}\bigg).$$ Do $n>m>0$, nên $m$ là một thặng dư bậc hai, theo tính chất tối thiểu của $n$. Vì vậy, $\lfloor p/n\rfloor+1$ không phải là thặng dư bậc hai. Sử dụng tính chất tối thiểu của $n$ một lần nữa, ta có $\lfloor p/n\rfloor+1 \geq n$, dẫn đến $n<\sqrt{p}+1$, hoàn thành chứng minh.

Kết luận: $p=3$ không thỏa mãn vì $-1$ không phải là thặng dư bậc hai modulo $3$, và với các số nguyên tố lẻ $p\geq 5$, ta cũng có kết quả tương tự do bổ đề trên.

Bài toán

Cho hai số nguyên dương $n$ và $k$. Chứng minh rằng nếu $n$ nguyên tố cùng nhau với $30$, thì tồn tại hai số nguyên $a$ và $b$, mỗi số đều nguyên tố cùng nhau với $n$, sao cho biểu thức

$$\frac{a^2 - b^2 + k}{n}$$

là một số nguyên.

Chứng minh

Bổ đề. Với mọi số nguyên tố $p > 5$, $k \in \mathbb{N}$ và $e \in \mathbb{N}$, tồn tại $a, b$ với $(a, p) = (b, p) = 1$ sao cho $p^e \mid a^2 - b^2 + k$.

Tôi sẽ đầu tiên chỉ ra cách Bổ đề dẫn đến kết quả. Đặt $n = \prod_{1 \le i \le N} p_i^{e_i}$ trong đó $p_1 < \cdots < p_N$ là các số nguyên tố. Chọn $a_i, b_i$ sao cho $a_i^2 - b_i^2 + k \equiv 0 \pmod{p_i^{e_i}}$. Bây giờ chỉ cần chọn $a \equiv a_i \pmod{p_i^{e_i}}$ và $b \equiv b_i \pmod{p_i^{e_i}}$, $1 \le i \le N$: các số $a, b$ như vậy thực sự tồn tại nhờ Định lý Số Dư Trung Hoa (CRT).

Bây giờ, phần khó là chứng minh Bổ đề.

Chứng minh Bổ đề. Cố định một số nguyên tố $p > 5$ và $k \in \mathbb{N}$. Chúng ta chứng minh bổ đề bằng quy nạp theo số mũ $e$.

Trường hợp cơ bản, $e = 1$. Bắt đầu với trường hợp cơ bản: đặt $e = 1$. Lưu ý rằng nếu $p \mid k$, không có gì cần chứng minh: đơn giản đặt $a \equiv b \equiv 1 \pmod{p}$. Tiếp theo, giả sử $k$ là một thặng dư bậc hai modulo $p$, tức là $u^2 \equiv k \pmod{p}$ với một số $u$. Nếu $\left(\frac{3}{p}\right) = 1$ thì đặt $b \equiv 2u \pmod{p}$ và $a$ sao cho $a^2 \equiv 3u^2 \equiv 3k \pmod{p}$. Nếu không, thì $\left(\frac{3}{p}\right) = -1$. Bây giờ nếu $\left(\frac{15}{p}\right) = 1$ thì đặt $b \equiv 4u \pmod{p}$ (và chỉ định $a$). Nếu không thì $\left(\frac{15}{p}\right) = -1$, do đó $\left(\frac{5}{p}\right) = 1$. Trong trường hợp này, chúng ta đặt $b \equiv 9u \pmod{p}$ và đặt $a$ tương ứng. Bây giờ chúng ta giả sử $\left(\frac{k}{p}\right) = -1$. Xét $i^2 - k$, $1 \le i \le \frac{p-1}{2}$. Không có số nào trong các số này bằng không modulo $p$ vì $\left(\frac{k}{p}\right) = -1$. Chúng ta khẳng định rằng tồn tại một thặng dư bậc hai khác không trong số chúng. Giả sử ngược lại. Khi đó, $$\left\{i^2 - k : 1 \le i \le \frac{p-1}{2}\right\} \equiv \{1, 2, \dots, p-1\} \setminus \left\{i^2 : 1 \le i \le \frac{p-1}{2}\right\} \pmod{p}$$ Nhưng chúng ta có $$\sum_{1 \le i \le \frac{p-1}{2}} \bigl(i^2 - k\bigr) \equiv \frac{p(p-1)}{2} - \sum_{1 \le i \le \frac{p-1}{2}} i^2 \pmod{p},$$ điều này dễ dàng thấy là không thể vì $p > 3$ và $p \nmid k$ bằng cách xét modulo $p$ của cả hai vế. Điều này hoàn thành trường hợp cơ bản, tức là $e = 1$.

Bước quy nạp. Giả sử giả thuyết trên đúng cho $e-1$: tồn tại $a, b \in \mathbb{N}$ với $(a, p) = (b, p) = 1$ và $e \ge 2$ sao cho $$p^{e-1} \mid a_0^2 - b_0^2 + k.$$ Bây giờ nếu $v_p(k) \ge e$ thì chúng ta đơn giản chọn $a \equiv b \equiv 1 \pmod{p^e}$. Tiếp theo, nếu $v_p(k) = e-1$, tức là $k = p^{e-1} k'$ với $p \nmid k'$ thì chúng ta chọn $t > p^{e-1}$ sao cho $t \equiv 1 \pmod{2}$ và $t \equiv p - k' \pmod{p}$ và đặt $a, b$ sao cho $$a + b = t \quad \text{và} \quad a - b = p^{e-1}.$$ Rõ ràng $t \equiv p^{e-1} \pmod{2}$ nên các số $a, b$ như vậy tồn tại và $p \nmid a \cdot b$ vì $p \nmid t$. Với lựa chọn này, chúng ta dễ dàng có $p^e \mid a^2 - b^2 + k$. Cuối cùng, đặt $v_p(k) \le e-2$ và $a_0^2 - b_0^2 + k = p^{e-1} c$ với $p \nmid c$. Khi đó, rõ ràng $v_p(a_0 - b_0) \le e-2$ vì nếu không $v_p(a_0^2 - b_0^2 + k) = v_p(k) < e-1$, một mâu thuẫn. Bây giờ đặt $i = p^{e-1 - v_p(a_0 - b_0)}$ và xét $a = a_0 + \ell p^i$ và $b = b_0 + \ell p^i$, trong đó $\ell$ được điều chỉnh. Lưu ý rằng $$a^2 - b^2 + k = a_0^2 - b_0^2 + k + 2\ell p^i (a_0 - b_0) = p^{e-1}\bigl(c + 2\ell \Delta\bigr), \quad \text{trong đó} \quad a_0 - b_0 = p^{v_p(a_0 - b_0)} \Delta.$$ Rõ ràng $c, \Delta \not\equiv 0 \pmod{p}$ nên chúng ta chọn $\ell$ sao cho $c + 2\ell \Delta \equiv 0 \pmod{p}$, từ đó suy ra $p^e \mid a^2 - b^2 + k$. Điều này hoàn thành bước quy nạp và chứng minh Bổ đề.

Bài toán

Chứng minh rằng:

$$\sum_{n\in\{0,1,2,\ldots,p-1\}}\left(\frac{n^2+a}{p}\right)=-1$$

Với $a \in \mathbb{F}_p \setminus \{0\}$ và $(.)$ là ký hiệu Legendre.

Chứng minh

Ta có:

$$\sum_{n\in\{0,1,2,\ldots,p-1\}}\left(\frac{n^2+a}{p}\right)\equiv\sum_{n=0}^{p-1}(n^2+a)^{\dfrac{p-1}{2}}\pmod{p}$$

và

$$\sum_{n=0}^{p-1}(n^2+a)^{\dfrac{p-1}{2}}\equiv\sum_{i=0}^{\dfrac{p-1}{2}}\binom{i}{\dfrac{p-1}{2}}a^{\dfrac{p-1}{2}-i}\sum_{n=0}^{p-1}n^{2i}\pmod{p}$$

Xét tổng:

$$\sum_{n=0}^{p-1}n^i\equiv0\pmod{p}$$

với $0< i\leq p-2$, nên công thức trên tương đương với:

$$\sum_{n=1}^{p-1}1\equiv-1\pmod{p}$$

Vậy ta thu được kết quả cần chứng minh. Tuy nhiên, cần chú ý đến trường hợp $a\equiv0\pmod{p}$.

Bài toán

Cho $p$ là một số nguyên tố và có dạng $p = a^2 + 5b^2$, trong đó $a$ là số lẻ. Chứng minh rằng:

$$a \text{ là thặng dư bậc hai (mod } p) \iff p \equiv 1 \pmod{5}$$

Chứng minh

Vì $a$ là số lẻ, theo tính chất của ký hiệu Jacobi (một sự tổng quát của ký hiệu Legendre), ta có:

$$\left( \frac{a}{p} \right) \left( \frac{p}{a} \right) = (-1)^{\frac{(a-1)(p-1)}{4}}$$

Nhưng vì $a$ là số lẻ và $p \equiv a^2 \equiv 1 \pmod{4}$ (do $b$ phải là số chẵn), nên:

$$(-1)^{\frac{(a-1)(p-1)}{4}} = 1$$

Do đó, ta suy ra:

$$\left( \frac{a}{p} \right) = \left( \frac{p}{a} \right) = \left( \frac{5b^2}{a} \right) = \left( \frac{5}{a} \right) = \left( \frac{a}{5} \right)$$

Mặt khác, ta có:

$$\left( \frac{a}{5} \right) = 1 \iff a^{\frac{5-1}{2}} \equiv 1 \pmod{5} \iff a^2 \equiv 1 \pmod{5} \iff p \equiv 1 \pmod{5}$$

Vậy điều phải chứng minh được suy ra.

Bài Toán

Chứng minh rằng $4kxy-1$ không là ước của $x^m + y^n$ với mọi số nguyên dương $x, y, k, m, n$.

Chứng Minh

Lưu ý rằng $(x^m, y^n, 4kxy-1) = 1$. Đặt $m' = [m/2]$ và $n' = [n/2]$. Chúng ta cần xét các trường hợp sau.

$1 \quad m = 2m'$ và $n = 2n'$. Khi đó $4kxy-1 \mid (x^{m'})^2 + (y^{n'})^2$ suy ra $\left(\frac{-1}{4kxy-1}\right) = 1$, điều này là sai.

$2 \quad m = 2m'$ và $n = 2n' + 1$ (trường hợp $m = 2m' + 1$, $n = 2n'$ tương tự). Khi đó $4kxy-1 \mid (x^{m'})^2 + y(y^{n'})^2$ và do đó $\left(\frac{-y}{4kxy-1}\right) = 1$. Chúng ta khẳng định điều này là không thể.

Giả sử rằng $y$ là số lẻ. Quy tắc tương hỗ cho chúng ta

$$\left(\frac{-y}{4kxy-1}\right) = \left(\frac{-1}{4kxy-1}\right)\left(\frac{y}{4kxy-1}\right) = (-1) \cdot (-1)^{\frac{y-1}{2}} \left(\frac{-1}{y}\right) = -1.$$

Bây giờ giả sử rằng $y = 2^t y_1$, trong đó $t \geq 1$ là số nguyên và $y_1 \in \mathbb{N}$. Theo Định lý 15, chúng ta có $\left(\frac{2}{4kxy-1}\right) = 1$, trong khi đó, như trong trường hợp $y$ lẻ, $\left(\frac{-y_1}{4kxy-1}\right) = \left(\frac{-y_1}{4^2kxy-1}\right) = -1$. Do đó,

$$\left(\frac{-y}{4kxy-1}\right) = \left(\frac{2}{4kxy-1}\right)^t \left(\frac{-y_1}{4kxy-1}\right) = -1.$$

$3 \quad m = 2m' + 1$ và $n = 2n' + 1$. Khi đó $4kxy-1 \mid x(x^{m'})^2 + y(y^{n'})^2$, và do đó $\left(\frac{-xy}{4kxy-1}\right) = 1$. Mặt khác,

$$\left(\frac{-xy}{4kxy-1}\right) = \left(\frac{-4xy}{4kxy-1}\right) = \left(\frac{-1}{4kxy-1}\right) = -1,$$

một sự mâu thuẫn.

Điều này hoàn thành chứng minh.

Bài Toán

Cho đa thức $P(x) = (x^2 - 2)(x^2 - 3)(x^2 - 6)$. Chứng minh rằng với mọi số nguyên tố $p$, đều tìm được số nguyên dương $n$ sao cho $P(n) \equiv 0 \ (\text{mod}\ p)$.

Lời Giải

Với $p = 2, 3$, tương ứng ta chọn $n = 2, 3$, hiển nhiên thỏa mãn.

Giả sử tồn tại số nguyên tố $p > 3$ sao cho $P(n) \not\equiv 0 \ (\text{mod}\ p)$ với mọi $n \in \mathbb{Z}$.

Điều này có nghĩa là $(n^2 - 2)(n^2 - 3)(n^2 - 6) \not\equiv 0 \ (\text{mod}\ p)$ với mọi $n \in \mathbb{Z}$.

Suy ra $2, 3, 6$ đều không là số chính phương $(\text{mod}\ p)$, hay

$$2^{\frac{p-1}{2}} \equiv -1 \ (\text{mod}\ p),\ 3^{\frac{p-1}{2}} \equiv -1 \ (\text{mod}\ p),\ 6^{\frac{p-1}{2}} \equiv -1 \ (\text{mod}\ p).$$

Nhưng rõ ràng

$$6^{\frac{p-1}{2}} = 2^{\frac{p-1}{2}} \cdot 3^{\frac{p-1}{2}} \equiv (-1) \cdot (-1) \equiv 1 \ (\text{mod}\ p),$$

mâu thuẫn với giả thiết $6^{\frac{p-1}{2}} \equiv -1 \ (\text{mod}\ p)$.

Vậy giả sử ban đầu là sai, tức là với mọi số nguyên tố $p > 3$, tồn tại số nguyên dương $n$ sao cho $P(n) \equiv 0 \ (\text{mod}\ p)$.

Điều này hoàn thành chứng minh.

Bài toán

Tìm tất cả các số nguyên dương $m$ sao cho tồn tại các số nguyên $x$ và $y$ thỏa mãn:

$$m \mid x^2 + 11y^2 + 2022.$$

Chứng minh

Đáp án là tất cả các số $m \in \mathbb{N}$ sao cho $\nu_2(m) \leq 1, \nu_{337}(m) \leq 1, 11 \nmid m$.

Ý tưởng là chúng ta có thể quy về lũy thừa của số nguyên tố bằng định lý số dư Trung Hoa (CRT), sau đó dùng Hensel để tạo ra các nghiệm cho lũy thừa cao hơn bằng cách cố định $y \in \mathbb{N}$.

Trước tiên, chúng ta sẽ chứng minh rằng không có số $m \in \mathbb{N}$ nào khác thỏa mãn.

Định lý 1: $11 \nmid m$

Chứng minh: Nếu $11 \mid m \mid x^2+11y^2+2022$, điều này dẫn đến mâu thuẫn vì $-2$ là phần dư bậc hai không hợp lệ $\pmod{11}$. $\blacksquare$

Định lý 2: $\nu_2(m) \leq 1$

Chứng minh: Nếu $4 \mid m \mid x^2+11y^2+2022$ thì $4 \mid x^2-y^2+2$, điều này không thể xảy ra vì $x^2 \equiv 0,1 \pmod{4}$ với mọi $x \in \mathbb{N}$. $\blacksquare$

Định lý 3: $\nu_{337}(m) \leq 1$

Chứng minh: Chúng ta chứng minh rằng không tồn tại nghiệm khác ngoài $(x,y) = (0,0)$ cho phương trình $x^2+11y^2+2022 = 0$ trong $\mathbb{F}_p^2$.

Giả sử có nghiệm $x^2 \equiv -11y^2 \pmod{337}$, khi đó ta có $\left( \frac{-11}{337} \right) = 1$. Do $-1$ là phần dư bậc hai $\pmod{337}$, ta có $\left( \frac{11}{337} \right) = 1$. Khi đó,

$$\left( \frac{337}{11} \right) = \left( \frac{11}{337} \right) \cdot \left( \frac{337}{11} \right) = (-1)^{\frac{337-1}{2} \cdot \frac{11-1}{2}} = 1$$

Điều này có nghĩa là $7$ là phần dư bậc hai $\pmod{11}$, nhưng đây là mâu thuẫn.

Do đó, nếu $337 \mid x^2+11y^2+2022$, thì $337 \mid x,y$ vì $337 \mid 2022$, kéo theo $337^2 \mid x^2+11y^2$, dẫn đến $337^2 \nmid x^2+11y^2+2022$. $\blacksquare$

Định lý 4: Nếu $\nu_2(m), \nu_{337}(m) \leq 1$, $11 \nmid m$, thì tồn tại $(x,y) \in \mathbb{N}^2$ sao cho $m \mid x^2+11y^2+2022$.

Chứng minh: Giả sử chúng ta có các cặp $(x_i, y_i) \in \mathbb{N}^2$ sao cho $p_i^{l_i} \mid x_i^2+11y_i^2+2022$ với các số nguyên tố phân biệt $p_1, \dots, p_k$. Khi đó, theo Định lý số dư Trung Hoa, tồn tại $x,y \in \mathbb{N}$ sao cho $\prod_{i=1}^{k} p_i^{l_i} \mid x^2+11y^2+2022$.

Ta cần chứng minh định lý này cho các lũy thừa số nguyên tố $p^k$. Nếu $p \in \{2,337\}$, ta chọn $(x,y) = (0,0)$ để có nghiệm.

Giả sử $p \notin \{2,11,337\}$, ta chứng minh tồn tại $x \not\equiv 0 \pmod{p}$ sao cho $p \mid x^2+11y^2+2022$ với mọi số nguyên tố $p$ ngoài tập này.

Định lý 4.1: Với mọi số nguyên tố $p \not\in \{2,11,337\}$, tồn tại $x, y \in \mathbb{N}$ sao cho $p \mid x^2+11y^2+2022$ và $x \not\equiv 0 \pmod{p}$.

Chứng minh: Nếu $p = 3$, chọn $x \equiv y \equiv 1 \pmod{3}$.

Nếu không có cặp nào thỏa mãn với $p \not\in \{2,3,11,337\}$, ta xét hai trường hợp:

Trường hợp 1: $-11$ là phần dư bậc hai $\pmod{p}$. Khi đó, ta có $a+2022$ luôn là phần dư bậc hai, suy ra tất cả các phần tử của $\mathbb{F}_p$ là phần dư bậc hai, mâu thuẫn. $\blacksquare$

Trường hợp 2: $-11$ là phần dư bậc hai không hợp lệ $\pmod{p}$. Khi đó, dãy số $a+2022k$ cũng quét hết các phần tử của $\mathbb{F}_p$, mâu thuẫn. $\blacksquare$

Nhận xét: Nếu dãy số $2022, 2022+2022, \dots, 2022+2022(p-1)$ bị chặn ở 0, ta có thể đi ngược lại, tìm phần dư bậc hai hợp lệ trước đó, và lại có mâu thuẫn.

Vậy, sử dụng Định lý 4.1, chọn $x$ sao cho $\gcd(p,x) = 1$ và $p \mid x^2+11y^2+2022$. Khi đó, theo Bổ đề Hensel, có thể mở rộng nghiệm lên $p^k$ với mọi $k \in \mathbb{N}$. $\blacksquare$

Kết hợp các định lý 1, 2, 3, 4, ta xác nhận rằng tập nghiệm đúng như đã nêu. $\blacksquare$

Bài toán

Cho số nguyên tố $p > 3$ thỏa mãn $p \equiv 3 \pmod{4}$.

Chứng minh rằng:

$$\left( \frac{p-1}{2} \right)! \equiv (-1)^N \pmod{p}$$

trong đó $N$ là số phần tử không phải là số dư bậc hai modulo $p$ trong khoảng từ $1$ đến $\frac{p}{2}$.

Chứng minh

Với mỗi $1 \leq k \leq \frac{p-1}{2}$, định nghĩa $\epsilon_k \in \{-1,1\}$ sao cho $\epsilon_k \cdot k$ là một số dư bậc hai. Điều này hợp lệ vì $-1$ là một số không phải là dư bậc hai theo điều kiện của $p$. Chú ý rằng $\epsilon_k = -1$ khi và chỉ khi $k$ không phải là dư bậc hai.

Bây giờ, ta có:

$$(-1)^N \cdot \left(\frac{p-1}{2}\right)! = \prod \epsilon_k \cdot k = \prod_{j=1}^{(p-1)/2} j^2 = \left(\frac{p-1}{2}\right)!^2 \pmod{p}$$

từ đó suy ra kết quả.

Bài toán

Chứng minh rằng:

$$\left ( \dfrac{-b}{4bc-1} \right ) = -1$$

với mọi số nguyên dương $b$ và $c$.

Lưu ý: Ở đây ta định nghĩa: $\left ( \dfrac{p}{q} \right ) = -1$ khi và chỉ khi $p$ không phải là dư bậc hai modulo $q$.

Chứng minh

Gọi $A=\left ( \frac{-b}{4bc-1} \right )$. Đặt $b=2^t.k$, trong đó $t\in\mathbb{N}_0$, $k\in\mathbb{N}$ là số lẻ. Theo ký hiệu Jacobi, kết hợp với $k\mid b$ ta có:

$$A=\left ( \frac{-b}{4bc-1} \right )=\left ( \frac{-1}{4bc-1} \right )\left ( \frac{2^t}{4bc-1} \right )\left ( \frac{k}{4bc-1} \right )$$ $$=-\left ( \frac{2}{4bc-1} \right )^t\left ( \frac{4bc-1}{k} \right )(-1)^{\frac{k-1}{2}}=-\left ( \frac{2}{4bc-1} \right )^t\left ( \frac{-1}{k} \right )(-1)^{\frac{k-1}{2}}$$

Xét hai trường hợp:

• Nếu $k\equiv 1,3 \pmod{4}$, ta có:

$$A=-\left ( \frac{2}{4bc-1} \right )^t\left ( \frac{-1}{k} \right )(-1)^{\frac{k-1}{2}}=-\left ( \frac{2}{4bc-1} \right )^t$$

• Nếu $t$ là số chẵn, dễ thấy $A=-1$.
• Nếu $t$ là số lẻ, ta có $4bc-1\equiv 7\pmod{8} \Rightarrow \left ( \frac{2}{4bc-1} \right )=1 \Rightarrow A=-1$.

Vậy ta đã chứng minh được mệnh đề cần chứng minh. $\square$

Bài toán

Chứng minh rằng phương trình:

$$x^3 = y^2 + 80$$

không có nghiệm nguyên.

Chứng minh

Trước tiên, chúng ta chứng minh rằng $x$ là số lẻ:

Chứng minh

Nếu $x = 2x_1$ thì $y = 2y_1$, khi đó:

$$2x_1^3 = y_1^2 + 20$$

Suy ra $y_1 = 2y_2$, khi đó:

$$x_1^3 = 2y_2^2 + 10$$

Tiếp tục, nếu $x_1 = 2x_2$ thì:

$$4x_2^3 = y_2^2 + 5$$

Điều này là vô lý vì $-1$ không phải là số dư bậc hai theo modulo 4.

Giờ ta chứng minh rằng $x \equiv 1 \pmod{4}$:

Chứng minh

$$x^3 - 4^3 = y^2 + 4^2$$ $$(x-4)(x^2+4x+4^2) = y^2+4^2$$

Ta biết rằng nếu $p$ là số nguyên tố và $p$ chia hết cho $y^2 + 4^2$, thì $p \equiv 1 \pmod{4}$.

Do đó, mỗi số nguyên tố chia hết cho $(x - 4)$ đều có dạng $4k+1$, suy ra $x \equiv 1 \pmod{4}$.

Cuối cùng, ta đi đến mâu thuẫn:

Chứng minh

$$x^3 - 2^3 = y^2 + 72$$ $$(x-2)(x^2+2x+2^2) = y^2+72$$

Ta biết rằng nếu $p$ (với $p \neq 3$) là số nguyên tố và $p$ chia hết cho $y^2 + 72$, thì:

$$1 = \left( \frac{-72}{p} \right) = \left( \frac{-2}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{2}{p} \right)$$ $$1 = (-1)^{\frac{p-1}{2} + \left\lfloor \frac{p+1}{4} \right\rfloor}$$

Suy ra số $\left\lfloor \frac{3p-1}{4} \right\rfloor$ là số chẵn, điều này dẫn đến:

$$p \equiv 1 \pmod{8} \quad \text{hoặc} \quad p \equiv 3 \pmod{8}$$

Vì $3 \equiv 3 \pmod{8}$, nên mọi số nguyên tố chia hết cho $(x-2)$ và $(x^2+2x+2^2)$ đều có dạng $8k+1$ hoặc $8k+3$. Do đó:

$$(x-2) \equiv 1 \pmod{8} \quad \text{hoặc} \quad (x-2) \equiv 3 \pmod{8}$$ $$(x^2+2x+2^2) \equiv 1 \pmod{8} \quad \text{hoặc} \quad (x^2+2x+2^2) \equiv 3 \pmod{8}$$

Tuy nhiên, vì $x \equiv 1 \pmod{4}$, ta suy ra:

$$x \equiv 5 \pmod{8}$$

Do đó:

$$(x^2+2x+2^2) \equiv 7 \pmod{8}$$

Điều này dẫn đến mâu thuẫn, do đó phương trình ban đầu không có nghiệm nguyên.

Bài toán

Cho $p$ là một số nguyên tố. Có đúng không rằng nếu:

$$\left(\frac{k}{p}\right) = 1$$

thì với mọi $n \in \mathbb{N}$, ta luôn có:

$$\left(\frac{k}{p^n}\right) = 1?$$

Chứng minh

Giả sử $p$ chia hết cho $x^2 - k y^2$, tức là:

$$p \mid x^2 - k y^2$$

Ta cần chứng minh rằng với mọi $n > 2$, tồn tại các số nguyên $u, v$ sao cho:

$$p^n \mid u^2 - k v^2$$

Điều này có thể được chứng minh bằng cách sử dụng đồng nhất thức:

$$(a^2 - k b^2)(c^2 - k d^2) = (ac + kbd)^2 - k (ad + bc)^2$$

Do đó, ta có thể xây dựng dãy số phù hợp để đảm bảo tính chia hết với lũy thừa cao hơn của $p$.

Bài toán

(IMO Shortlist 2022 N8) Chứng minh rằng $5^n - 3^n$ không chia hết cho $2^n + 65$ với mọi số nguyên dương $n$.

Chứng minh

Chú ý rằng nếu $n$ là số chẵn thì $3 \mid 2^n + 65$ nhưng $3 \not\mid 5^n - 3^n$, điều này là không thể, do đó $n$ phải là số lẻ. Rõ ràng $n = 1$ không thỏa mãn. Bây giờ, ta chứng minh rằng tất cả các giá trị $n > 1$ đều không thỏa mãn.

Để thấy điều này, xét

$$-1 = \left( \frac{2^n+65}{5} \right) = \left( \frac{5}{2^n+65} \right) = \left( \frac{5^n}{2^n+65} \right),$$

và nếu $2^n+65 \mid 5^n-3^n$, thì điều này dẫn đến

$$\left( \frac{3^n}{2^n+65} \right) = \left( \frac{3}{2^n+65} \right) = \left( \frac{2^n+65}{3} \right) = +1,$$

mâu thuẫn.

(Ở đây, ta sử dụng ký hiệu Jacobi.)

Bài Toán

N6. Chứng minh rằng tồn tại vô số số nguyên dương $n$ sao cho $n^{2}+1$ có một ước số nguyên tố lớn hơn $2n+\sqrt{2n}$.

Lời Giải

Giả sử $p \equiv 1 \pmod{8}$ là một số nguyên tố. Phương trình đồng dư $x^{2} \equiv -1 \pmod{p}$ có hai nghiệm trong khoảng $[1, p-1]$ mà tổng của chúng là $p$. Nếu $n$ là nghiệm nhỏ hơn trong hai nghiệm đó thì $p$ chia hết $n^{2}+1$ và $n \leq (p-1)/2$. Ta sẽ chứng minh rằng $p > 2n + \sqrt{10n}$.

Đặt $n = \frac{p-1}{2} - \ell$ với $\ell \geq 0$. Khi đó, từ $n^{2} \equiv -1 \pmod{p}$, ta có:

$$\left(\frac{p-1}{2} - \ell\right)^{2} \equiv -1 \pmod{p} \quad \text{hoặc} \quad (2\ell + 1)^{2} + 4 \equiv 0 \pmod{p}.$$

Do đó, $(2\ell + 1)^{2} + 4 = rp$ với $r \geq 0$. Vì $(2\ell + 1)^{2} \equiv 1 \equiv p \pmod{8}$, ta có $r \equiv 5 \pmod{8}$, nên $r \geq 5$. Từ đó, $(2\ell + 1)^{2} + 4 \geq 5p$, suy ra $\ell \geq \frac{\sqrt{5p - 4} - 1}{2}$. Đặt $\sqrt{5p - 4} = u$ để rõ ràng hơn; khi đó $\ell \geq \frac{u - 1}{2}$. Do đó:

$$n = \frac{p - 1}{2} - \ell \leq \frac{1}{2}(p - u).$$

Kết hợp với $p = \frac{u^{2} + 4}{5}$, ta có $u^{2} - 5u - 10n + 4 \geq 0$. Giải bất phương trình bậc hai này với $u \geq 0$, ta được $u \geq \frac{5 + \sqrt{40n + 9}}{2}$. Vì vậy, ước lượng $n \leq \frac{p - u}{2}$ dẫn đến:

$$p \geq 2n + u \geq 2n + \frac{1}{2}(5 + \sqrt{40n + 9}) > 2n + \sqrt{10n}.$$

Vì có vô số số nguyên tố có dạng $8k + 1$, nên dễ dàng suy ra rằng cũng có vô số số $n$ thỏa mãn tính chất đã nêu.

Bài toán

Tìm tất cả các số nguyên $a, b$ sao cho:

$$a^2 + 38 = 3b^2$$

Chứng minh

Số $3$ không phải là dư bậc hai theo modulo $19$, và $a \equiv b \equiv 0 \pmod{19}$ là không thể xảy ra vì:

$$38 \not\equiv 0 \pmod{19^2}$$

Do đó, ta kết luận rằng:

$$\boxed{\text{Không có nghiệm}}$$

Bài toán

Chứng minh rằng nếu $p$ là một số nguyên tố có dạng $4k+3$ và $m$ là số dư bậc hai nhỏ hơn $\frac{p}{2}$, thì:

$$2\cdot4\cdot6\cdots(p-1)\equiv (-1)^{m+k} \pmod{p}$$

Chứng minh

Trước tiên, ta có:

$$\left(2.4.6. \cdots (p-1)\right).\left(1.3.5\cdots (p-2)\right)\equiv -1\pmod p$$ từ định lý Wilson.

Do đó:

$$2.4.6 \cdots (p-1).\left((p-2).(p-4)\cdots 1\right)\equiv -1\pmod p$$ $$\implies (2(p-2))(4(p-4))\cdots (p-1)1\equiv -1\pmod p$$ $$\implies (2p-p^2)(4p-p^2)\cdots \equiv -1\pmod p$$ $$\implies (-1)^{\frac{p-1}{2}}\left(2.4.6. \cdots (p-1)\right)^2 \equiv -1\pmod p$$ $$\implies 2.4.6. \cdots (p-1)\equiv 1 \text{ hoặc } -1\pmod p$$ Gọi $2.4.6. \cdots (p-1)\equiv (-1)^{f(p)}\pmod p$, ta có: $$2^{\frac{p-1}{2}}.\left(1.2.\cdots \frac{p-1}{2}\right)\equiv (-1)^{f(p)}\pmod p$$ Mặt khác, ta biết rằng: $$2^{\frac{p-1}{2}}\equiv (-1)^{\frac{p^2-1}{8}}\pmod p$$ Thay $p=4k+3$, ta thấy rằng $k+1$ và $\frac{p^2-1}{8}$ có cùng tính chẵn lẻ. $$\implies \left(1.2.\cdots \frac{p-1}{2}\right)\equiv (-1)^{f(p)+k+1}\pmod p$$ Bây giờ, ta nâng hai vế lên lũy thừa $\frac{p-1}{2}$: Trong vế trái, theo tiêu chuẩn Euler, có $m$ số bằng $1$ và $\frac{p-1}{2}-m$ số bằng $-1$. Từ đây, ta có: $$(f(p)+k+1)\frac{p-1}{2}-\left(\frac{(p-1)}{2}-m\right) \text{ là số chẵn}$$ Suy ra, $m+k$ và $f(p)$ luôn có cùng tính chẵn lẻ.

Bài toán

Xét dãy số $u_0, u_1, u_2, ...$ được xác định bởi:

$$u_0 = 0, \quad u_1 = 1, \quad u_n = 6u_{n - 1} + 7u_{n - 2}, \quad \text{với } n \geq 2.$$

Chứng minh rằng không tồn tại các số nguyên không âm $a, b, c, n$ sao cho:

$$ab(a + b)(a^2 + ab + b^2) = c^{2022} + 42 = u_n.$$

Chứng minh

Ta tìm phương trình đặc trưng của truy hồi:

$$\lambda^2 - 6\lambda - 7 = 0$$

có nghiệm $\lambda = -7$ và $\lambda = 1$. Kết hợp với điều kiện ban đầu $u_0 = 0$ và $u_1 = 1$, ta có công thức tổng quát:

$$u_n = \frac{7^n - (-1)^n}{8}.$$

Giả sử tồn tại các số nguyên không âm $a, b, c, n$ thỏa mãn bài toán. Nếu $n$ là số lẻ, thì:

$$7^n - (-1)^n \equiv 8 \pmod{16}$$

suy ra $u_n$ là số lẻ. Điều này dẫn đến $a, b, a+b$ đều là số lẻ, mâu thuẫn. Do đó, $n$ phải là số chẵn, tức là $n = 2k$, khi đó:

$$u_{2k} = \frac{7^{2k} - 1}{8} = c^{2022} + 42.$$

Xét đồng dư modulo 7:

$$u_{2k} \equiv -1 \pmod{7}.$$

Điều này dẫn đến:

$$c^{2022} \equiv -1 \pmod{7}.$$

Nhưng $-1$ không phải là một số dư bậc hai modulo 7, mâu thuẫn xảy ra. Vậy không tồn tại các số nguyên không âm $a, b, c, n$ thỏa mãn bài toán.

Bài toán

Tìm tất cả các hàm $f:\mathbb{N} \to \mathbb{N}$ thỏa mãn:

$$|xf(y) - yf(x)|$$

là một số chính phương với mọi $x,y \in \mathbb{N}$.

Chứng minh

Ký hiệu $\square$ là tập hợp các số chính phương.

Gọi $P(x,y)$ là mệnh đề $|xf(y) - yf(x)| \in \square$.

Chọn một số nguyên tố $p$ có dạng $4k+1$.

Từ $P(p,x)$ suy ra $|pf(x) - xf(p)| \in \square$, do đó $\left(\frac{xf(p)}{p}\right) = 0$ hoặc $1$.

(Chú ý rằng $\left(\frac{-1}{p}\right) = 1$ vì $4 | p - 1$, nên dấu cộng trừ không quan trọng).

Nếu $p \nmid f(p)$ thì ta có thể chọn $x$ sao cho $\left(\frac{x}{p}\right) = -\left(\frac{f(p)}{p}\right)$, khi đó:

$$1 = \left(\frac{xf(p)}{p}\right) = \left(\frac{x}{p}\right) \left(\frac{f(p)}{p}\right) = -1$$

Mâu thuẫn! Do đó, phải có $p | f(p)$ với mọi $p \in \mathbb{P}_{4k+1}$.

Ta định nghĩa một hàm khác $g:\mathbb{N} \to \mathbb{Q}^+$ và xét mệnh đề $Q(x,y)$ tương ứng với $xy | g(x) - g(y) \in \square$.

Chọn ba số nguyên tố phân biệt có dạng $4k+1$: $p, x, y$.

Từ $Q(p,x)$ suy ra $px | g(p) - g(x) \in \square$, do đó $px | g(p) - g(x)$, suy ra:

$$p | g(p) - g(x) \quad (1)$$

Tương tự, từ $Q(p,y)$ suy ra:

$$p | g(p) - g(y) \quad (2)$$

Trừ (1) và (2) ta có $p | g(y) - g(x)$.

Vì tồn tại vô số số nguyên tố có dạng $4k+1$, ta suy ra $g(y) - g(x)$ có vô hạn ước nguyên tố, dẫn đến $g(y) - g(x) = 0$.

Do đó, $f(x)$ là một hằng số $c$ với mọi $x \in \mathbb{P}_{4k+1}$.

Cuối cùng, chọn $p \in \mathbb{P}_{4k+1}$ và $x \in \mathbb{N}$ (với $p \nmid x$). Từ $Q(x,p)$ suy ra:

$$px | g(x) - c \in \square \Rightarrow p | g(x) - c$$

Một lần nữa, vì có vô hạn số nguyên tố có dạng $4k+1$, ta suy ra $g(x) - c$ có vô hạn ước nguyên tố, tức là $g(x) - c = 0$.

Vậy, ta có $g(x) = c$ với mọi $x \in \mathbb{N}$, tức là:

$$\boxed{f(x) = cx \quad \forall x}$$

trong đó $c$ là một số nguyên dương tùy ý. Kết quả này thỏa mãn bài toán vì:

$$|xf(y) - yf(x)| = |cxy - cxy| = 0 \in \square, \quad \forall x, y.$$

Bài toán

Cho $n$ là một số tự nhiên. Chứng minh rằng không tồn tại số nguyên tố $p$ thỏa mãn đồng thời cả hai điều kiện sau:

• (a) $6^n \equiv -3 \pmod{p}$
• (b) $p \equiv -1 \pmod{24}$

Chứng minh

Giả sử tồn tại số nguyên tố $p$ thỏa mãn cả hai điều kiện.

Ta chứng minh rằng $-3$ là phần dư bậc hai mod $p$ là sai:

• Vì $p \equiv 3 \pmod{4}$, ta có $-1$ không phải là phần dư bậc hai mod $p$.
• Vì $p \equiv 4 \pmod{4}$ và $p \equiv 2 \pmod{3}$, theo luật tương hỗ bậc hai, $3$ là phần dư bậc hai mod $p$.

Tiếp theo, ta chứng minh rằng $6$ là phần dư bậc hai mod $p$:

• Như đã chứng minh, $3$ là phần dư bậc hai mod $p$.
• Vì $p \equiv 7 \pmod{8}$, theo tiêu chuẩn Euler, $2$ cũng là phần dư bậc hai mod $p$.

Do đó, $6^n$ là phần dư bậc hai mod $p$, trong khi $-3$ là không. Điều này mâu thuẫn với điều kiện $6^n \equiv -3 \pmod{p}$.

Vậy không tồn tại số nguyên tố $p$ thỏa mãn cả hai điều kiện đã cho.

Bài toán

Cho số nguyên tố $p$ có dạng $p = 6k+5$. Chứng minh rằng nếu $a+b+c$ và $a^4+b^4+c^4$ đều chia hết cho $p$ thì $p$ chia hết cho $a, b, c$.

Chứng minh

Giả sử trước tiên rằng $p\mid a$. Khi đó, $p\mid b+c$ và $p\mid b^4+c^4$. Vì $c\equiv -b\pmod{p}$, ta có $b^4+c^4\equiv 2b^4\pmod{p}$, suy ra $p\mid b$. Điều này dẫn đến $p\mid a,b,c$, đúng như yêu cầu. Do đó, ta giả sử $p\nmid abc$ và dẫn đến một mâu thuẫn.

Đặt $m=a+b$ và $n=ab$. Ta có $c\equiv -m\pmod{p}$, do đó:

$$a^4+b^4+c^4\equiv a^4+b^4+m^4\pmod{p}.$$

Hơn nữa,

$$a^4+b^4 = (a^2+b^2)^2 -2a^2b^2 = \bigl((a+b)^2 -2ab\bigr)^2 -2a^2b^2\equiv (m^2-2n)^2 -2n^2\equiv m^4-4m^2n+2n^2\pmod{p}.$$

Do đó,

$$p\mid a^4+b^4+c^4\Rightarrow m^4-2m^2n+n^2\equiv 0\pmod{p}\Rightarrow p\mid m^2-n.$$

Điều này dẫn đến $p\mid (a+b)^2 - ab = a^2+ab+b^2$. Vì $p\ne 2$, ta có $p\mid 4a^2+4ab+4b^2=(2a+b)^2+3b^2$. Do giả sử $p\nmid b$, ta thu được $p\mid r^2+3$ với $r\equiv 2ab^{-1} +1\pmod{p}$. Tuy nhiên, vì $p\equiv -1\pmod{6}$, ta có $-3$ không là một số dư bậc hai theo modulo $p$, dẫn đến mâu thuẫn.

Bài toán

Liệu có tồn tại số tự nhiên $n$ sao cho $3^n + 1$ có một ước có dạng $24k + 20$?

Chứng minh

Rõ ràng $n$ là số lẻ theo modulo $4$, do đó $(-3)$ phải là một số dư bậc hai theo modulo một số nguyên tố $\equiv 5 \pmod{6}$, điều này dẫn đến mâu thuẫn.

Bài toán

Cho $p > 5$ là một số nguyên tố thỏa mãn $p \equiv 1 \pmod{4}$, và $a \in \mathbb{Z}$.

Chứng minh rằng tồn tại $b, c \in \mathbb{Z}$ sao cho $a = b + c$, đồng thời $b$ và $c$ đều là phần dư bậc hai modulo $p$.

Chứng minh

Giả sử không tồn tại các phần dư bậc hai không phải là số chính phương $b$ và $c$ sao cho $a = b + c$. Khi đó

$$-1 = \sum_{x = 1}^{p - 1} \left(\frac{x}{p}\right)\left(\frac{a - x}{p}\right) = \sum_{\text{x là QR}} \left(\frac{a - x}{p}\right) - \sum_{\text{x không là QR}} 1$$

Biến đổi lại, ta có

$$\sum_{\text{x là QR}} \left(\frac{a - x}{p}\right) = \frac{p - 3}{2}$$

Chỉnh sửa: Nếu $x$ là phần dư bậc hai, thì $a - x$ phải là số chính phương. Điều này cho thấy có $\frac{p - 1}{2}$ số chính phương. Tổng trên cho thấy có nhiều hơn $\frac{p - 1}{2}$ số chính phương, dẫn đến mâu thuẫn.

Lưu ý: Kết quả sau đây được biết đến rộng rãi:

$$\sum_{x = 1}^{p - 1} \left(\frac{x}{p}\right)\left(\frac{a - x}{p}\right) = -1$$

Để chứng minh điều này, ta nhận thấy

$$\left(\frac{x}{p}\right)\left(\frac{a - x}{p}\right) = \left( \frac{\frac{a - x}{x}}{p} \right),$$

nên tổng này tương đương với

$$\sum_{k} \left(\frac{k}{p}\right)$$

với $k$ nhận các giá trị của $\frac{a - x}{x}$. Lưu ý rằng một giá trị của $x$ sẽ thỏa mãn tất cả $k$ trừ $k = -1$. Do đó,

$$\sum_{k} \left(\frac{k}{p}\right) = \sum_{x = 1}^{p - 1} \left(\frac{x}{p}\right) - \left(\frac{-1}{p}\right) = -1.$$

Bài toán

Với $p$ là một số nguyên tố và $t$ là một nguyên dương, tìm $p$ và $t$ sao cho:

$$p^3 - 2 = 5^t$$

Chứng minh

Nếu t chẵn thì xét mod 3 suy ra p = 3. Còn nếu t lẻ thì xét mod 8 suy ra $p\equiv 3\pmod 8$. Kết hợp với -10 là thặng dư toàn phương mod p sẽ suy ra điều vô lý.