Bài Tập Trắc Nghiệm Chuyên Đề: Đồng dư và số nguyên tố (Toán học Lớp 10, 11, 12)

(AI giải đề cho tôi)
Câu 5. a) Tập A = {1976,...,2053} có 78 phần tử. Vì 1976 = 79·25 + 1 nên các phần tử của A lần lượt dư 1, 2, ..., 78 khi chia cho 79, tức {x_1,...,x_78} là hoán vị của các số dư 1, 2, ..., 78 modulo 79. Do đó a = x_1x_2...x_78 ≡ 1·2·...·78 = 78! (mod 79). Theo định lý Wilson, vì 79 là số nguyên tố: 78! ≡ -1 ≡ 78 (mod 79). Vậy dư khi chia a cho 79 là 78.

b) Giả sử phản chứng: với mọi m ≠ n thì mx_m ≢ nx_n (mod 79). Khi đó 78 số mx_1, mx_2, ..., mx_78 đôi một khác nhau modulo 79 và đều khác 0 (vì m, x_m đều không chia hết cho 79). Mỗi số dư khác 0 thuộc tập {1, 2, ..., 78}, nên 78 số này chính là một hoán vị của 1, 2, ..., 78 modulo 79. Suy ra tích của chúng: ∏_{k=1}^{78} (k·x_k) ≡ 1·2·...·78 = 78! ≡ -1 (mod 79).

Mặt khác, tính trực tiếp: ∏_{k=1}^{78} (k·x_k) = (1·2·...·78)·(x_1x_2...x_78) ≡ 78!·78! ≡ (-1)·(-1) = 1 (mod 79).

Hai kết quả mâu thuẫn (1 ≢ -1 mod 79). Vậy giả sử phản chứng sai, tức tồn tại m ≠ n ∈ {1,...,78} sao cho mx_m - nx_n chia hết cho 79. Đpcm.

(AI giải đề cho tôi)
Câu 3.

a) Giả sử $p\mid m$. Khi đó $f_p(m)=m^{p-1}+\dots +m+1\equiv 1(\mathrm{mod}m)$ (mọi số hạng chứa $m$ đều chia hết cho $m$), nên $\gcd (f_p(m),m)=1$.

Mặt khác, vì $m\equiv 1(\mathrm{mod}m-1)$ nên $f_p(m)\equiv \underset{p}{\underbrace{1+\dots +1}}\equiv p(\mathrm{mod}m-1)$. Gọi $q$ là ước nguyên tố bất kỳ của $f_p(m)$. Nếu $q\mid m-1$ thì $q\mid p$, tức $q=p$; nhưng khi đó $p\mid m$ và $p\mid m-1$, vô lý. Vậy $q\nmid m-1$. Kết hợp $q\nmid m$ (do $f_p(m)\equiv 1(\mathrm{mod}m)$), ta được $\gcd (q,m(m-1))=1$ với mọi ước nguyên tố $q$ của $f_p(m)$. Đpcm.

b) Giả sử phản chứng chỉ có hữu hạn số nguyên tố dạng $pn+1$, liệt kê $q_1,q_2,\dots ,q_k$ (khác $p$). Đặt $m=p{q}_1{q}_2\cdots q_k$, khi đó $p\mid m$. Theo câu a), mọi ước nguyên tố $q$ của $f_p(m)$ đều nguyên tố cùng nhau với $m(m-1)$; nói riêng $q\nmid m$ và $q\nmid m-1$.

Từ $f_p(m)=\frac{m^p-1}{m-1}$ và $q\mid f_p(m)$, $q\nmid m-1$, suy ra $m^p\equiv 1(\mathrm{mod}q)$. Vì $q\nmid m-1$ nên $m\not\equiv 1(\mathrm{mod}q)$, do đó cấp của $m$ modulo $q$ đúng bằng $p$. Theo định lý Fermat nhỏ, $m^{q-1}\equiv 1(\mathrm{mod}q)$, nên $p\mid q-1$, tức $q=pn+1$ với $n\in {\mathbb{Z}}^{+}$.

Nhưng $q\nmid m=p{q}_1\cdots q_k$, mâu thuẫn với cách dựng $q_1,\dots ,q_k$ là toàn bộ các số nguyên tố dạng $pn+1$. Vậy tồn tại vô số số nguyên dương $n$ sao cho $pn+1$ là số nguyên tố. Đpcm.

(AI giải đề cho tôi)
Các số nguyên tố nhỏ hơn 10 là 2, 3, 5, 7 (0 và 1 không phải số nguyên tố). Vậy dãy theo thứ tự tăng dần là 2, 3, 5, 7, tương ứng phương án C.

(AI giải đề cho tôi)
Dãy gồm $C_n^4$ với $n=4,\dots ,2024$ (2021 số hạng). Theo định lý Lucas, $C_n^4$ lẻ khi và chỉ khi các bit của $4=100_2$ là tập con các bit của $n$, tức $n\equiv 4,5,6,7(\mathrm{mod}8)$; ngược lại $C_n^4$ chẵn khi $n\equiv 0,1,2,3(\mathrm{mod}8)$.

Xét tổng ba số hạng liên tiếp $C_n^4+C_{n+1}^4+C_{n+2}^4$: tổng lẻ khi trong ba chỉ số $n,n+1,n+2(\mathrm{mod}8)$ có số lượng phần tử thuộc $\{4,5,6,7\}$ là lẻ. Xét theo $n\mathrm{mod}8$:
- $n\equiv 0$: chỉ số $0,1,2$ → 0 số lẻ → tổng chẵn
- $n\equiv 1$: chỉ số $1,2,3$ → 0 số lẻ → tổng chẵn
- $n\equiv 2$: chỉ số $2,3,4$ → 1 số lẻ → tổng lẻ ✓
- $n\equiv 3$: chỉ số $3,4,5$ → 2 số lẻ → tổng chẵn
- $n\equiv 4$: chỉ số $4,5,6$ → 3 số lẻ → tổng lẻ ✓
- $n\equiv 5$: chỉ số $5,6,7$ → 3 số lẻ → tổng lẻ ✓
- $n\equiv 6$: chỉ số $6,7,0$ → 2 số lẻ → tổng chẵn
- $n\equiv 7$: chỉ số $7,0,1$ → 1 số lẻ → tổng lẻ ✓

Vậy mỗi chu kỳ 8 có 4 vị trí cho tổng lẻ: $n\equiv 2,4,5,7(\mathrm{mod}8)$.

Ba số hạng liên tiếp được chọn với $n=4,\dots ,2022$: 2019 giá trị. Vì $2019=252\cdot 8+3$ và dãy chỉ số bắt đầu tại $n\equiv 4(\mathrm{mod}8)$, 252 chu kỳ đầy đủ cho $252\cdot 4=1008$ trường hợp lẻ; 3 giá trị còn lại là $n=2020,2021,2022\equiv 4,5,6(\mathrm{mod}8)$, trong đó $n\equiv 4,5$ cho tổng lẻ (thêm 2). Tổng cộng 1010 trường hợp lẻ.

Xác suất $=\frac{1010}{2019}$; $2019=3\cdot 673$, $1010=2\cdot 5\cdot 101$ nguyên tố cùng nhau nên tối giản. Vậy $a+b=1010+2019=3029$.

Câu 5. (3,0 điểm). Chứng minh rằng với mọi số tự nhiên $n$ thì $2^{2^{4n+1}}+7$ chia hết cho 11.

- (0,5 điểm). Ta có $2^4\equiv 6(\mathrm{mod}10)$ suy ra $2^{4n+1}\equiv 2(\mathrm{mod}10)$.

- (0,5 điểm). Suy ra $2^{4n+1}=10q+2$, $(q\in \mathbb{N})\Rightarrow 2^{2^{4n+1}}=2^{10q+2}$

- (0,5 điểm). Theo định lí Fetmat nhỏ ta có $2^{10}\equiv 1(\mathrm{mod}11)$ suy ra $2^{10q}\equiv 1(\mathrm{mod}11)$.

- (0,5 điểm). Do đó $2^{10q+2}\equiv 4(\mathrm{mod}11)$ hay $2^{2^{4n+1}}\equiv 4(\mathrm{mod}11)$.

- (0,5 điểm). Mặt khác $7\equiv 7(\mathrm{mod}11)$.

- (0,5 điểm). Suy ra $2^{2^{4n+1}}+7\equiv 0(\mathrm{mod}11)$. Vậy $2^{2^{4n+1}}+7$ chia hết cho 11.

Gọi các số dạng $a_i^3-1$ là số đặc biệt. Chú ý rằng nếu $n$ là số lẻ thì $2^3-1=7$ là đặc biệt nên $f(n)\mid 7$, chứng tỏ $f(n)\ne 2$. (0.5 điểm)

Với $n=4;n=6$, thử trực tiếp ta thấy không thỏa mãn.
Xét $n$ là số chẵn $\ge 8$.
Đặt $n=2^{k}m$, với $m$ lẻ và $k\ge 1$. Chú ý rằng khi này mỗi $a_i$ là số lẻ, kéo theo $2\mid f(n)$. (0.5 điểm)

• Xét $m=1$. Khi này $k\ge 3$. Chú ý rằng $3^3-1=26$ và $5^3-1=124$ là các số đặc biệt và $\gcd (26,124)=2$. Từ đó suy ra $f(n)\mid 2$ và do đó $f(n)=2$. (0.5 điểm)

• Xét $m=3$. Khi này $k\ge 2$. Chú ý rằng $5^3-1=124=4\cdot 31$, $7^3-1=342=2\cdot 9\cdot 19$ là các số đặc biệt và $\gcd (124,342)=2$.
Suy ra $f(n)=2$. (0.5 điểm)

• Xét $m\ge 5$. Dễ thấy mỗi số $m-4,m-2,m+2,m+4$ là số lẻ và nguyên tố cùng nhau với $m$ nên chúng nguyên tố với $2^{k}m$. Hơn nữa hiển nhiên chúng nhỏ hơn $2m\le 2^{k}m$.
Do đó $(m-4{)}^3-1$, $(m-2{)}^3-1$, $(m+2{)}^3-1$, $(m+4{)}^3-1$ là các số đặc biệt. Vì $f(n)$ là ước của mỗi số này nên
$f(n)\mid ((m+4{)}^3-1)+((m-4{)}^3-1)-((m+2{)}^3-1)-((m-2{)}^3-1)=72m$.
Để ý một trong hai số $m+2,m+4$ không chia 3 dư 1, nên một trong hai số $(m+2{)}^3-1$, $(m+4{)}^3-1$ không chia hết cho 3, chứng tỏ $3\nmid f(n)$. Tương tự, chú ý rằng $(m+2{)}^2\equiv (m+4{)}^2\equiv 1(\mathrm{mod}4)$, kéo theo $(m+2{)}^3-1\equiv (m+2)-1=m+1$, $(m+4{)}^3-1\equiv m+4-1=m+3(\mathrm{mod}4)$ và một trong hai số $m+1,m+3$ không chia hết cho 4 vì thế $4\nmid f(n)$.
Từ đó suy ra $f(n)\mid 2m$. (1 điểm)

Giả sử $f(n)$ có một ước nguyên tố $p$ lẻ nào đó.
Khi đó $p\mid m$. Khi này từ $p\mid m$ và $p\mid f(n)\mid (m+2{)}^3-1$ ta có $p\mid 7$, kéo theo $p=7$. Tương tự, từ $p\mid m$ và $p\mid (m-2{)}^3-1$ ta có $p\mid 9$, kéo theo $p=3$, mâu thuẫn.
Suy ra: $f(n)$ không thể có ước nguyên tố lẻ. Vì thế $f(n)\mid 2$ và do đó $f(n)=2$.
Vậy, các số $n$ cần tìm là tất cả các số chẵn $\ge 8$. (1 điểm)

Lời giải.

a) Gọi $S$ là tập các số nguyên thu được từ 0.

$P(x)$ là đa thức 3-tốt $⟺S=\mathbb{Z}$.

Quy tắc sinh phần tử của tập $S$:

- (Quy tắc A): $u\in S⟹P(u)\in S$.
- (Quy tắc B): $v\in S$ và $P(u)\equiv v(\mathrm{mod}3)⟹u\in S$.

Nhận xét 1: Nếu $u\in S$ thì mọi số nguyên $x$ thỏa mãn $x\equiv u(\mathrm{mod}3)$ cũng thuộc $S$.

Chứng minh: Với $P(x)\in \mathbb{Z}[x]$, ta có tính chất cơ bản: $x\equiv u(\mathrm{mod}3)⟹P(x)\equiv P(u)(\mathrm{mod}3)$. Vì $u\in S\stackrel{\text{Quy ta˘ˊc A}}{\to }P(u)\in S$. Lại có $P(x)\equiv P(u)(\mathrm{mod}3)\stackrel{\text{Quy ta˘ˊc B}}{\to }x\in S$.

Nhận xét 1 cho thấy để $S=\mathbb{Z}$, tập $S$ chỉ cần chứa đủ 3 đại diện có số dư là $0,1,2$ khi chia cho 3.

Nhận xét 2: Có $3^3=27$ bộ số dư $(P(0),P(1),P(2))$ modulo 3.

Tập $S$ (xuất phát từ 0) không thể sinh ra toàn bộ $\mathbb{Z}⟺$ tập $\{0,1,2\}$ bị phân hoạch thành các tập con $X$ rời nhau thỏa mãn: $x\in X⟺P(x)\in X$.

Các trường hợp thất bại này bao gồm:

- Phân hoạch thành 3 tập $\{0\},\{1\},\{2\}$:

Vì $0\in \{0\}⟹P(0)\in \{0\}⟹P(0)\equiv 0(\mathrm{mod}3)$.

Vì $1\in \{1\}⟹P(1)\in \{1\}⟹P(1)\equiv 1(\mathrm{mod}3)$.

Vì $2\in \{2\}\Rightarrow P(2)\in \{2\}\Rightarrow P(2)\equiv 2(\mathrm{mod}3)$.

Suy ra: $P(x)\equiv x(\mathrm{mod}3),\forall x\in \{0,1,2\}$.

$\Rightarrow$ Có 1 trường hợp.

• Phân hoạch thành 2 tập $\{a\}$ và $\{b,c\}$ (với $\{a,b,c\}=\{0,1,2\}$):

Vì $a\in \{a\}\Rightarrow P(a)\in \{a\}\Rightarrow P(a)\equiv a(\mathrm{mod}3)$.

Vì $b\in \{b,c\}\Rightarrow P(b)\in \{b,c\}\Rightarrow P(b)\equiv b$ hoặc $P(b)\equiv c(\mathrm{mod}3)$.

Vì $c\in \{b,c\}\Rightarrow P(c)\in \{b,c\}\Rightarrow P(c)\equiv b$ hoặc $P(c)\equiv c(\mathrm{mod}3)$.

Có 3 cách chọn $a$. Với mỗi $a$, có $2^2=4$ cách chọn ảnh cho $P(b)$ và $P(c)$. Trừ đi 1 trường hợp $P(b)\equiv b,P(c)\equiv c$ (đã đếm ở trên). $\Rightarrow$ Có $3\times (4-1)=9$ trường hợp.

Suy ra số bộ $(P(0),P(1),P(2))$ thành công (thỏa mãn $S=\mathbb{Z}$) là: $27-1-9=17$.

Mặt khác, với $x\in \{1,2\}$, ta có $x^2\equiv 1(\mathrm{mod}3)\Rightarrow x^{lẻ}\equiv x$ và $x^{ch\widetilde{\stackrel{˘}{a}}n}\equiv 1(\mathrm{mod}3)$. Do đó:

$$P(x)\equiv c_0+\left(\sum _{klẻ}{c}_k\right)x+\left(\sum _{kch\widetilde{\stackrel{˘}{a}}n\ge 2}{c}_k\right)(\mathrm{mod}3)$$

Đặt $A=c_0$, $B={\sum }_{klẻ}{c}_k$ và $C={\sum }_{kch\widetilde{\stackrel{˘}{a}}n\ge 2}{c}_k$. Ta có hệ:

$$\{\begin{array}{l}P(0)\equiv A(\mathrm{mod}3)\\ P(1)\equiv A+B+C(\mathrm{mod}3)\\ P(2)\equiv A+2B+C\equiv A-B+C(\mathrm{mod}3)\end{array}$$

Hệ phương trình này xác định duy nhất bộ dư $(A,B,C)(\mathrm{mod}3)$ từ bộ $(P(0),P(1),P(2))$. Suy ra có đúng 17 bộ $(A,B,C)$ thỏa mãn.

Cuối cùng, ta đếm số cách chọn hệ số $c_k\in \{1,2,\dots ,99\}$. Tập này có 99 số, chia đều mỗi loại số dư 0, 1, 2 có 33 số. Với một bộ $(A,B,C)$ cố định:

• $c_0\equiv A(\mathrm{mod}3)$: Có 33 cách chọn.

• Tổng của 50 hệ số bậc lẻ $\equiv B(\mathrm{mod}3)$: Chọn 49 hệ số đầu tiên tùy ý (có $99^{49}$ cách). Hệ số cuối cùng bị buộc phải nhận một số dư duy nhất để tổng bằng $B$ (có 33 cách chọn giá trị thỏa mãn số dư đó). Nhóm này có $99^{49}\cdot 33$ cách.

• Tổng của 49 hệ số bậc chẵn $\equiv C(\mathrm{mod}3)$: Tương tự, chọn tùy ý 48 số đầu, số cuối bị cố định số dư. Nhóm này có $99^{48}\cdot 33$ cách.

Số lượng đa thức tạo thành cho một bộ $(A,B,C)$ là:

$$33\times (99^{49}\cdot 33)\times (99^{48}\cdot 33)=33^3\cdot 99^{97}$$

Tổng số đa thức 3-tốt là: $\boxed{17\cdot 33^3\cdot 99^{97}}$.

b) Đặt $\phi (r)=P(r)\mathrm{mod}p$. Với $u\in S$ (tập sinh từ 0), dãy lặp $u,\phi (u),{\phi }^2(u),\dots$ luôn tuần hoàn về một chu trình cố định - gọi là chu trình tối hạn của $u$; quy nạp trực tiếp trên hai quy tắc sinh của đề bài cho thấy mọi phần tử của $S$ có cùng chu trình tối hạn với 0. Nếu tồn tại hai chu trình tối hạn phân biệt, các điểm trên chu trình thứ hai không thuộc $S$, do đó $P$ không $p$-tốt.

Ta phát biểu và chứng minh các bổ đề sau:

Bổ đề 1

Nếu hàm số $f\in \mathbb{Z}[x]$ không là hàm hằng, thì có vô hạn số nguyên tố $p$ để phương trình $f(x)\equiv 0(\mathrm{mod}p)$ có nghiệm nguyên.

Chứng minh: Nếu $f(0)=0$ thì hiển nhiên $x=0$ là nghiệm với mọi $p$.

Giả sử $f(0)=c_0\ne 0$ và chỉ có hữu hạn $p_1,\dots ,p_k$ thỏa mãn, đặt $N=c_0{p}_1\cdots p_k$. Do các số hạng có bậc $\ge 1$ trong $f(Nt)$ đều chia hết cho $N$, ta có thể viết $f(Nt)$ dưới dạng $c_0(1+N.M(t))$ (với $t\in \mathbb{Z}$). Thừa số sau nguyên tố cùng nhau với mọi $p_i$, và ta có thể chọn $t$ đủ lớn để nó có giá trị tuyệt đối lớn hơn 1. Khi đó nó có ước nguyên tố mới $q\notin \{p_i\}$ — mâu thuẫn. Ta có điều phải chứng minh.

Bổ đề 2

Cho $f\in \mathbb{Z}[x]$ là hàm số bậc 2 có $\Delta =B^2-4AC\ne 0$. Khi đó có vô hạn số nguyên tố $p$ để phương trình $f(x)\equiv 0(\mathrm{mod}p)$ có hai nghiệm phân biệt.

Chứng minh: Theo Bổ đề 1, có vô hạn $p$ để $f$ có một nghiệm $x_0\mathrm{mod}p$. Ta loại bỏ hữu hạn giá trị $p\mid A\Delta$. Vì $p\nmid A$ và $x_0$ là nghiệm, phép chia đa thức trong ${\mathbb{F}}_p[x]$ cho ta $f(x)\equiv A(x-x_0)(x-x_1)(\mathrm{mod}p)$ với $x_1\in {\mathbb{F}}_p$ nào đó; theo hệ thức Viète ta được $x_0+x_1\equiv -B/A(\mathrm{mod}p)$

Giả sử $x_1\equiv x_0(\mathrm{mod}p)$, khi đó $2x_0\equiv -B/A\Rightarrow 2A{x}_0+B\equiv 0(\mathrm{mod}p)$. Mà $4A\cdot f(x)=(2Ax+B{)}^2-\Delta$, thay $x=x_0$ ta có được $\Delta \equiv 0(\mathrm{mod}p)$ — vô lí. Ta có điều phải chứng minh.

Trở lại bài toán, đặt $Q(x)=P(x)-x=a{x}^2+(b-1)x+c$, $\Delta =(b-1{)}^2-4ac$.

Ta thấy $Q(x)\equiv 0(\mathrm{mod}p)⟺P(x)\equiv x(\mathrm{mod}p)$, do đó các nghiệm của $Q(x)$ chính là các điểm bất động của hàm $\phi$ kể trên. Xét 2 trường hợp:

- $\Delta \ne 0$. Theo Bổ đề 2, có vô hạn số nguyên tố $p$ để $Q$ có 2 nghiệm phân biệt $x_1\ne x_2$ sao cho $Q(x_1)\equiv Q(x_2)\equiv 0(\mathrm{mod}p)$. Đa thức $P(x)$ có 2 điểm bất động, và do đó nó không $p$-tốt.

- $\Delta =0$. Lúc này $Q(x)=a(x-r{)}^2$ với $r=\frac{1-b}{2a}\in \mathbb{Q}$. Với $p\nmid 2a$, đặt $y=x-r$ ta được $\phi (y)=a{y}^2+y\mathrm{mod}p$ với điểm bất động duy nhất là $y=0$.

Ta tính được $\phi (\phi (y))-y=a{y}^2(a^2{y}^2+2ay+2)$. Xét $H(y)=a^2{y}^2+2ay+2\in \mathbb{Z}[y]$ có $\Delta =-4a^2\ne 0$ (vì $a\ne 0$), áp dụng Bổ đề 2 cho thấy có vô hạn số nguyên tố $p$ sao cho $H$ có 2 nghiệm phân biệt $y_1\ne y_2$ và đều khác 0 (theo hệ thức Viète thì $y_1{y}_2=\frac{2}{a^2}\ne 0$).

Với modulo các số nguyên tố $p$ kể trên, ta có $\phi (\phi (y))\equiv y$ nên $\phi (\phi (\phi (y)))\equiv \phi (y)$, nên $\phi (y)$ cũng là một trong các nghiệm $\{0;y_1;y_2\}$ của phương trình $\phi (\phi (y))-y\equiv 0(\mathrm{mod}p)$.

Mà $\phi (y_1)\ne y_1$ (do $y_1$ không bất động) và $\phi (y_1)\ne 0$ (khi đó $\phi (\phi (y_1))\equiv 0\ne y_1$), ta bắt buộc có $\phi (y_1)\equiv y_2$, và chứng minh tương tự ta có $\phi (y_2)\equiv y_1$.

Như vậy, tồn tại chu trình có độ dài 2 là $\{y_1;y_2\}$ khác 0 và phân biệt với điểm bất động $\{0\}$, suy ra $P(x)$ có 2 chu trình tối hạn và do đó $P$ không $p$-tốt.

Bài toán đã được giải quyết.

a) Để ý vì $u_{n+2}\equiv -u_n(\mathrm{mod}3)$ và $3\mid u_1$ nên $3\mid u_n$ với mọi $n$ lẻ.

Xét dãy $(v_n)$ xác định bởi $v_n=\frac{u_{2n+1}}{3}$ với mọi số tự nhiên $n$.

Khi đó $u_{n+4}=3u_{n+3}-u_{n+2}=3(3u_{n+2}-u_{n+1})-u_{n+2}=8u_{n+2}-(u_{n+2}+u_n)=7u_{n+2}-u_n$.

Suy ra $v_0=1$, $v_1=6$ và $v_{n+2}=7v_{n+1}-v_n$ với mọi số tự nhiên $n$.

Để ý $v_n$ chia hết cho 3 khi và chỉ khi $n\equiv 1,4(\mathrm{mod}6)$, hay $n\equiv 1(\mathrm{mod}3)$.

Viết $N=2k+1$ với $k$ nguyên dương thì $2k+1\not\equiv 0(\mathrm{mod}3)$ nên $k\not\equiv 1(\mathrm{mod}3)$ nên $3\nmid v_k$.

Từ đó $u_N=u_{2k+1}=3v_k$ không chia hết cho 9, điều phải chứng minh.

b) Ta cần chứng minh $v_k\equiv 1(\mathrm{mod}4N)$ và $v_k$ là hợp số.

Vì $u_N\equiv 3(\mathrm{mod}N)$ nên $3v_k\equiv 3(\mathrm{mod}N)$ nên $v_k\equiv 1(\mathrm{mod}N)$ do $\gcd (N,3)=1$.

Ta có $v_n\equiv 1(\mathrm{mod}4)⟺n\equiv 0,2(\mathrm{mod}3)$.

Vì $k\not\equiv 1(\mathrm{mod}3)$ nên $v_k\equiv 1(\mathrm{mod}4)$, kết hợp $\gcd (N,4)=1$ để có $v_k\equiv 1(\mathrm{mod}4N)$.

Đặt $\alpha =\frac{3+\sqrt{5}}{2}$ và $\beta =\frac{3-\sqrt{5}}{2}$ thì $u_n={\alpha }^n+{\beta }^n$ với mọi $n$ nguyên dương.

Ta có $N=ab$ với $a,b>1$ là các số lẻ thì dễ dàng thấy được $u_N$ chia hết cho $u_a$.

Vì thế $M=\frac{u_N}{3}=\frac{u_N}{u_b}\cdot \frac{u_b}{3}$ là hợp số do $\frac{u_b}{3}$ là số nguyên lớn hơn 1 và $u_N>u_b$.

Từ đó ta có điều phải chứng minh.

Lời giải.

a) Trước hết ta có bổ đề sau:

Bổ đề. Với số nguyên dương $n$ thỏa mãn $n+1$ chia hết cho 24 thì $\sigma (n)$ chia hết cho 24.

Chứng minh. Để ý nếu $n\equiv -1(\mathrm{mod}24)$ thì $n$ không là số chính phương. Gọi $d_1,d_2,\cdots ,d_k$ là tất cả các ước dương của $n$ bé hơn $\sqrt{n}$. Để ý với $d$ là ước dương của $n$ thì $d+\frac{n}{d}=\frac{d^2+n}{d}$ chia hết cho 24, vì thế $\sigma (n)$ chia hết cho 24. $\square$

Để ý $n\equiv 2(\mathrm{mod}3)$ và $n\equiv 7(\mathrm{mod}8)$ nên $n\equiv -1(\mathrm{mod}24)$, theo bổ đề có điều phải chứng minh.

b) Đặt $d=(x,y)$, $x=da$, $y=db$ với $(a,b)=1$. Khi đó ta có được
$$\frac{d^{3}a{b}^3}{a+b}=p.$$
Do $(a,b)=1$ nên $(a+b,a{b}^3)=1$. Vì $a+b\mid d^{3}a{b}^3$, nên $a+b\mid d^3$.

Đặt $d^3=c(a+b)$ với $c\in {\mathbb{N}}^{\ast }$ thì $ca{b}^3=p$.

Vì $p$ là số nguyên tố nên $b=1$. Do đó $ca=p$, nên ta có hai trường hợp sau:

- Nếu $a=1$, $c=p$, thì $d^3=2p$, vô lý vì $2p$ không thể là một lập phương.
- Nếu $a=p$, $c=1$, thì $d^3=p+1$ hay $p=d^3-1=(d-1)(d^2+d+1)$. Vì $p$ là số nguyên tố và $d^2+d+1>1$, ta phải có $d-1=1$. Suy ra $d=2$ và $p=7$.

Khi đó $x=14$ và $y=2$.

Thử lại thấy thỏa mãn, vậy nghiệm duy nhất thỏa mãn là $(x,y,p)=(14,2,7)$.

Nhận xét. Bài toán trên là bài toán đã xuất hiện trong đề thi Hy Lạp MO 2015. Ta cũng có thể làm mạnh bài toán như sau: Bài toán: Cho số nguyên dương $k$. Tìm tất cả các số nguyên dương $x,y$ và số nguyên tố $p$ sao cho $\frac{x{y}^3}{x+y}=p^k$.

a) Chú ý $10^{10^n}\equiv 0(\mathrm{mod}10)$; $9^{9^n}\equiv 9(\mathrm{mod}10)$ với mọi số nguyên dương $n$. Vậy ta được $A(n)\equiv 0-9\equiv 1(\mathrm{mod}10)$. Do đó, nếu $A(n)$ có nhiều chữ số tận cùng giống nhau thì các chữ số đó phải là 1.

Với $n=1$, ta chứng minh $A(1)\equiv 11(\mathrm{mod}100)$ hay $9^9\equiv -11(\mathrm{mod}100)$.

Thật vậy, ta có $9^2\equiv -19(\mathrm{mod}100)$; $9^4\equiv -39(\mathrm{mod}100)$; $9^8\equiv 21(\mathrm{mod}100)$; $9^9\equiv -11(\mathrm{mod}100)$.

Vậy $A(1)\equiv 11(\mathrm{mod}100)$ hay $A(1)$ có hai chữ số tận cùng giống nhau.

b) Giả sử tồn tại số nguyên dương $n$ để $A(n)$ có 5 chữ số tận cùng giống nhau. Chú ý rằng $A(n)\equiv 1(\mathrm{mod}10)$ nên 5 chữ số tận cùng của $A(n)$ là 11111. Lúc này ta được $A(n)\equiv 11111(\mathrm{mod}10^5)$.

Do $10^n>5$ nên $10^{10^n}\equiv 0(\mathrm{mod}10^5)$. Vậy $-9^{9^n}\equiv 11111(\mathrm{mod}10^5)\Rightarrow 9^{9^n}\equiv -11111\equiv 25(\mathrm{mod}32)$.

Ta có: $9\equiv 9(\mathrm{mod}32)$; $9^2\equiv 17(\mathrm{mod}32)$; $9^3\equiv 25(\mathrm{mod}32)$; $9^4\equiv 1(\mathrm{mod}32)$. Vậy để $9^{9^n}\equiv 25(\mathrm{mod}32)$ thì $9^n\equiv 3(\mathrm{mod}4)$. Tuy nhiên điều này là vô lý vì $9^n\equiv 1(\mathrm{mod}4)$.

Vậy $A(n)$ không thể có 5 chữ số tận cùng là giống nhau hay nói cách khác, nếu $k$ là số chữ số tận cùng giống nhau của $A(n)$ thì $k\le 4$.