Phan Đình Trung: Cấp số nguyên

Bài toán 1 : Cho $a,n,k$ là các số nguyên dương. Chứng minh rằng mọi ước nguyên tố của $a^{2.6^{n}}-a^{6^{n}}+1$ đều có dạng $6^{n+1}.k+1$ .

Lời giải :

Gọi $p$ là ước nguyên tố của $a^{2.6^{n}}-a^{6^{n}}+1$ . Ta có :

$a^{2.6^{n}}-a^{6^{n}}+1\equiv 0\;(mod\;p)\Rightarrow a^{6^n}-a^{2.6^n}\equiv 1\;(mod\;p)\Rightarrow a^{6^n}(1-a^{6^n})\equiv 1\;(mod\;p)\Rightarrow -a^{2.6^n}.a^{6^n}\equiv 1(mod\;p)\Rightarrow a^{6^{n+1}}\equiv 1\;(mod\;p)\Rightarrow ord_p(a)\mid 6^{n+1}$

Từ đây suy ra chỉ có thể là :

$ord_p(a)\in \left \{ 2^k,3^k,6^k \right \},\;\forall k=\overline{1,n+1}$

Nếu mà $ord_p(a)\in \left \{ 2^k,3^k,6^t \right \},\;\forall k=\overline{1,n+1},\forall t=\overline{1,n}$ thì :

$a^{2.6^{n}}-a^{6^{n}}+1\equiv 1\;(mod\;p)$

Mâu thuẫn. Do vậy $ord_p(a)=6^{n+1}$

Bằng định lí Fermat nhỏ ta có ngay :

$6^{n+1}=ord_p(a)\mid p-1$

Điều phải chứng minh.

Bài toán 2 : Tìm số nguyên dương $n$ sao cho $n\mid 3^n-2^n$ .

Lời giải :

Hiển nhiên $n=1$ thỏa mãn. Xét $n\geq 2$ , khi đó $n$ có ước nguyên tố nhỏ nhất, gọi ước nguyên tố nhỏ nhất đó là $p$ .

Gọi $t\in \mathbb{N}$ là nghịch đảo của $2$ modulo $p$ , tức là $2t\equiv 1\;(mod\;p),1\leq t\leq p-1$ .

Ta có $3^{n}\equiv 2^{n}\;(mod\;p)\Rightarrow (3t)^{n}\equiv (2t)^{n}\equiv 1\;(mod\;p)\Rightarrow ord_p(3t)\mid n\;\;(1)$

Nếu $p=3$ thì $3\mid 3\Rightarrow 3\mid 3^{n}-2^{n}\Rightarrow 3\mid 2^n$ (vô lí). Vậy $p\neq 3$ và vì $1\leq t\leq p-1$ nên $gcd(t,p)=1\Rightarrow gcd(3t,p)=1$ .

Theo định lí $Fermat$ nhỏ, ta có $\left ( 3t \right )^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(3t)\mid p-1\;\;(2)$

Từ $(1)(2)$ suy ra $ord_p(3t)$ có một ước nguyên tố $r$ mà $r\mid n$ và $r\leq p-1<p$ . Điều này mâu thuẫn với tính nhỏ nhất của $p$ . Suy ra $ord_p(3t)=1\Rightarrow 3t\equiv 1\equiv 2t\;(mod\;p)\Rightarrow t\equiv 0\;(mod\;p)$

Ta gặp điều mâu thuẫn.

Kết luận : Có duy nhất một số nguyên dương $n$ thỏa đề là $n=1$ .

Bài toán 3 : Cho $n$ là số nguyên dương thỏa mãn $n\mid 2^{n}+5^{n}$ . Chứng minh rằng $n$ chia hết cho $7$ .

Lời giải :

Dễ thấy $n$ là số nguyên dương lẻ. Gọi $p$ là ước nguyên tố bé nhất của $n$ .

Gọi $a$ là nghịch đảo của $2$ modulo $p$ . Khi đó thì $2a\equiv 1\;(mod\;p),gcd(2,a)=gcd(a,p)=1$ .

Ta có $p\mid 2^{n}+5^{n}\Rightarrow p\mid (2a)^n+(5a)^n\Rightarrow (2a)^n+(5a)^{n}\equiv (5a)^n+1\;(mod\;p)\Rightarrow -(5a)^n=(-5a)^n\equiv 1\;(mod\;p)\Rightarrow ord_p(-5a)\mid n\;\;\;\;(1)$

Dễ dàng thấy $gcd(5a,p)=1$ nên theo định lí $Fermat$ nhỏ ta có $(-5a)^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(-5a)\mid p-1\;\;\;\;(2)$

Từ $(1)(2)$ suy ra tồn tại một ước nguyên tố $r$ của $ord_p(-5a)$ mà $r<p-1<p,r\mid n$ . Điều này mâu thuẫn với tính nhỏ nhất của $p$ . Như vậy phải có $ord_p(-5a)=1$ . Suy ra $-5a\equiv 1\equiv 2a\;(mod\;p)\Rightarrow 7a\equiv 0\;(mod\;p)$

Mà $gcd(a,p)=1$ nên $p=7$ . Suy ra $n$ chia hết cho $7$ .

Bài toán 3 (CĐT Olympic 30-4 môn toán 10 năm 2013-2014 THPT Chuyên Trần Hưng Đạo tỉnh Bình Thuận)

Tìm các số nguyên tố $p,q$ thỏa mãn $pq \mid p^p+q^q+1$ .

Lời giải :

Bổ đề : Cho các số nguyên tố $p,q,r$ trong đó $p$ lẻ và thỏa mãn $p \mid q^r+1$ thì khi đó $2r \mid p-1$ hoặc $p\mid q^2-1$ .

Bài toán :

Từ đề bài ta có $p^{p}+1\equiv 0\;(mod\;q)$ và $q^{q}+1\equiv 0\;(mod\;p)$

Xét $p=2$ ta có $4+1\equiv 0\;(mod\;q)\Rightarrow q=5$ , thử lại cặp $(2,5)$ thỏa mãn. Tương tự cặp $(5,2)$ cũng thỏa mãn.

Xét các số nguyên tố $p,q$ đều lẻ.

Vì $q\mid p^p+1$ nên áp dụng bổ đề ta có $2p\mid q-1$ hoặc $q\mid p^2-1$ .

Nếu $2p\mid q-1\Rightarrow q\equiv 1\;(mod\;p)\Rightarrow 0\equiv q^{q}+1\equiv 2\;(mod\;p)\Rightarrow p=2$ (loại)

Nếu $q\mid p^2-1$ thì $q\mid p-1$ hoặc $q\mid p+1$ . Lập luận như trên ta chỉ ra rằng $q\mid p-1$ là vô lí nên phải có $q\mid p+1$ . Tuy nhiên thì $p+1$ chẵn và $gcd(q,2)=1$ nên ta có $2q\mid p+1\Rightarrow p+1\geq 2q$ .

Hoàn toàn tương tự ta có $q+1\geq 2p$ . Suy ra $p+q+2\geq 2(p+q)\Rightarrow p+q\leq 2$ và điều này thì vô lí

Kết luận : $\boxed{(p,q)=(2,5),(5,2)}$

Bài toán 4 : Tìm số nguyên dương $n$ thỏa mãn $n\mid 2^n-1$ .

Lời giải :

Ta thấy $n=1$ thỏa mãn. Xét $n>1$ . Gọi $p$ là ước nguyên tố bé nhất của $n$ .

Theo đề bài ta có $2^{n}\equiv 1\;(mod\;p)\Rightarrow ord_p(2)\mid n$ .

Theo định lí $Fermat$ nhỏ thì $2^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(2)\mid p-1\Rightarrow p>p-1>ord_p(2)$

Ta gọi $q$ là ước nguyên tố của $ord_p(2)$ , ta thấy $q\mid n$ và $p>q$ . Điều này mâu thuẫn vì $p$ là ước nguyên tố bé nhất của $n$ . Trường hợp này không tìm được $n$ thỏa đề.

Kết luận : Có duy nhất số nguyên dương thỏa mãn đề bài là $\boxed{n=1}$

Bài toán 5 (USA TST 2003): Tìm các số nguyên tố $p,q,r$ thỏa mãn đồng thời $p\mid q^r+1\;,\;q\mid r^p+1\;,\;r\mid p^q+1$ .

Lời giải :

Bổ đề : Cho các số nguyên tố $p,q,r$ trong đó $p$ lẻ và thỏa mãn $p\mid q^r+1$ thì khi đó $2r\mid p-1$ hoặc $p\mid q^2-1$

Xem chứng minh bổ đề tại đây

Trở lại bài toán.

Nhận thấy rằng các số nguyên tố $p,q,r$ phải phân biệt.

Trường hợp 1 : Xét các số nguyên tố $p,q,r$ đều lẻ.

Theo bổ đề ta có $2r\mid p-1$ hoặc $p\mid q^2-1$ .

Nếu $2r\mid p-1\Rightarrow p\equiv 1\;(mod\;r)\Rightarrow 0\equiv p^{q}+1\equiv 2\;(mod\;r)\Rightarrow r=2$ (loại)

Do vậy phải có $p\mid q^2-1\Rightarrow p\mid q-1\;\;\vee p\mid q+1$ .

Nếu $p\mid q-1\Rightarrow q\equiv 1\;(mod\;p)\Rightarrow 0\equiv q^{r}+1\equiv 2\;(mod\;p)\Rightarrow p=2$ (loại)

Suy ra $p\mid q+1$ mà $q+1$ chẵn và $gcd(2,p)=1$ nên $2p\mid q+1$ , từ đó $q+1\geq 2p$

Hoàn toàn tương tự ta được $r+1\geq 2q$ và $p+1\geq 2r$ .

Như vậy $p+q+r+3\geq 2(p+q+r)\Leftrightarrow p+q+r\leq 3$ và đây là điều vô lí.

Trường hợp 2 : Trong các số $p,q,r$ có ít nhất một số chẵn. Gỉa sử $r=2$ .

Khi đó giả thiết trở thành $q\mid 2^p+1$ và $p\mid q^2+1$ .

Cũng theo bổ đề trên thì ta được $q\mid r^{2}-1$ hoặc $2p\mid q-1$ . Nếu mà $2p\mid q-1$ thì $q\equiv 1\;(mod\;p)\Rightarrow 0\equiv q^{2}+1\equiv 2\;(mod\;p)\Rightarrow p=2$ (loại vì $p,q,r$ phải phân biệt)

Như vậy có $q\mid r^2-1=2^2-1=3\Rightarrow q=3$ . Từ đó $p\mid q^2+1=3^2+1=10\Rightarrow p=5$

Bộ số $(p,q,r)=(5,3,2)$ thoả mãn.

Kết luận : $\boxed{(p,q,r)=(5,3,2),(2,5,3),(3,2,5)}$

Bài toán 6 : Cho số nguyên dương $n$ lớn hơn $1$ và thỏa mãn $n\mid 3^n-1$ . Chứng minh rằng $n$ là số chẵn.

Lời giải :

Gọi $p$ là ước nguyên tố bé nhất của $n$

Theo giả thiết thì $3^{n}\equiv 1\;(mod\;p)\Rightarrow ord_p(3)\mid n\;\;\;(1)$

Hiển nhiên $p\neq 3$ vì nếu vậy thì $3\mid 3^{n}-1$ (vô lí). Khi đó theo định lí $Fermat$ nhỏ ta có $3^{p-1}\equiv 1\;(mod\;p)\Rightarrow ord_p(3)\mid p-1\Rightarrow p>p-1>ord_p(3)\;\;\;(2)$ .

Gọi $q$ là một ước nguyên tố của $ord_p(3)$ thì theo $(1)$ , $q$ là một ước nguyên tố của $n$ nhưng theo $(2)$ thì $p>q$ . Điều này mâu thuẫn với tính nhỏ nhất của $p$ .

Suy ra $ord_p(3)=1$ . Khi đó $3\equiv 1\;(mod\;p)\Rightarrow p=2$ . Suy ra $n$ chẵn. Đây là điều phải chứng minh.

Tổng quát bài toán : Cho số nguyên tố $p$ sao cho tồn tại số nguyên dương $n$ sao cho $n\mid (p+1)^n-1$ . Chứng minh rằng $n$ chia hết cho $p$ .

Bài toán 7 (IMO Shortlist 2006)

Tìm các số nguyên dương $x,y$ thỏa mãn phương trình $\dfrac{x^7-1}{x-1}=y^5-1$ .

Lời giải :

Bổ đề : Cho các số nguyên dương $x,m$ ( $x>1$ ) và số nguyên tố $p$ thỏa mãn $m\mid \dfrac{x^p-1}{x-1}$ . Khi đó thì $m\equiv 0,1\;\;(mod\;p)$

Chứng minh bổ đề :Gọi $r$ là một ước nguyên tố của $m$ .

Từ đề bài ta có

$m\mid x^{p}-1\Rightarrow x^{p}\equiv 1\;(mod\;m)\Rightarrow x^{p}\equiv 1\;(mod\;r)\Rightarrow ord_x(r)\mid p\Rightarrow ord_x(r)\in \left \{ 1,p \right \}$

Nếu $ord_x(r)=1$ thì $x\equiv 1\;(mod\;r)\Rightarrow \dfrac{x^{p}-1}{x-1}=x^{p-1}+x^{p-2}+...+x+1\equiv \underset{p}{\underbrace{1+1+...+1}}=p\;(mod\;r)$

Mà $\dfrac{x^p-1}{x-1}\equiv 0\;(mod\;r)\Rightarrow p\equiv 0\;(mod\;r)\Rightarrow p=r\Rightarrow m\equiv 0\;(mod\;p)$

Nếu $ord_x(r)=p$ , hiển nhiên $r\nmid x$ vì nếu $r\mid x$ thì $\dfrac{x^p-1}{x-1}\equiv 1\;(mod\;r)$ và điều này trái giả thiết.

Do đó áp dụng định lí $Fermat$ nhỏ thì $x^{r-1}\equiv 1\;(mod\;r)$ , suy ra $ord_x(r)\mid r-1\Rightarrow p\mid r-1\Rightarrow r\equiv 1\;(mod\;p)\Rightarrow m\equiv 1\;(mod\;p)$

Như vậy ta có $m\equiv 0,1\;(mod\;p)$ . Bổ đề được chứng minh.

Trở lại bài toán :

Ta viết phương trình dưới dạng : $\dfrac{x^7-1}{x-1}=(y-1)(y^5+y^4+y^3+y^2+y+1)$

Áp dụng bổ đề trên thì ta có $\left\{\begin{matrix} y-1\equiv 0,1\;(mod\;7) & (1) & \\ y^4+y^3+y^2+y+1\equiv 0,1\;(mod\;7) & (2) & \end{matrix}\right.$