Tag Archives: somudung

Bổ đề về số mũ đúng

BỔ ĐỀ VỀ SỐ MŨ ĐÚNG

(Thầy Nguyễn Ngọc Duy giáo viên trường PTNK TP Hồ Chí Minh)

Bổ đề số mũ đúng của một số nguyên là một hướng tiếp cận khá mới đối với các bài toán sơ cấp. Nó cung cấp một công cụ khá hữu hiệu để giải các phương trình Diophante hoặc các bài toán chia hết liên quan đến số mũ. Trong bài viết này tôi sẽ cố gắng mang đến một cái nhìn thật sơ cấp và tự nhiên đến vấn đề, trang bị thêm kiến thức và kĩ năng cho các các em học sinh để giải quyết các bài toán số học. Đặc biệt, ta sẽ dùng bổ đề số mũ đúng để giải quyết một số trường hợp đặc biệt của định lí lớn Fermat.

1. Kiến thức cần nhớ

Định nghĩa 1.1: Cho $\left( a,n \right)=1$. Kí hiệu cấp của a theo modulo n là $or{{d}_{n}}\left( a \right)$, là số nguyên dương d nhỏ nhất thỏa $a^d\equiv 1\, \left( \bmod n \right)$.

Tính chất 1.1: Nếu $x$ là số nguyên dương thỏa mãn $a^x \equiv 1\, \left( \bmod n \right)$ thì $or{{d}_{n}}\left( a \right)|x$.

Định nghĩa 1.2: Cho $p$ là số nguyên tố, $x$ là số nguyên bất kì, kí hiệu $v_p \left( x \right)=n$ nếu $x$ chia hết cho $p^n$ nhưng không chia hết cho $p^{n+1}$ .

Tính chất 1.2: Với $a,b$ là các số nguyên và $n$ là số nguyên dương thì:

  • $v_p \left( ab \right)=v_p \left( a \right)+v_p \left( b \right)$.
  • Nếu $p|a$ thì $v_p(a) >0.$
  • $v_p \left( a^n \right)=n v_p \left( a \right)$.
  • $v_p \left( a+b \right) \ge \min \left\{ v_p \left( a \right), v_p \left( b \right) \right\}$. Đẳng thức xảy ra chẳng hạn khi $v_p(a) \neq v_p(b).$
  • $v_p(\text{gcd}(a,b)) = \min(v_p(a), v_p(b))$ và $v_p(\text{lcm}(a,b)) = \max(v_p(a), v_p(b)).$

Định lý 1.1: Bổ đề số mũ đúng. Cho $p$ là số nguyên tố lẻ; $a,b$ không chia hết cho $p$

$i)$  Nếu $a-b$ chia hết cho p thì $v_p \left( a^n – b^n \right)=v_p \left( a-b \right)+v_p \left( n \right)$.

$ii)$  Nếu $a+b$ chia hết cho $p, n$ lẻ thì $v_p\left( a^n+b^n \right)=v_p\left( a+b \right)+v_p \left( n \right)$.

$iii)$  Nếu $a, b$ lẻ thì $v_2 \left( a^n – b^n \right)=v_2 \left( \dfrac{x^2 – y^2}{2} \right) + v_2 \left( n \right)$.

Chứng minh
  • Trước tiên, ta chứng minh: ${{v}_{p}}\left( {{a}^{p}}-{{b}^{p}} \right)={{v}_{p}}\left( a-b \right)+1$ $(*)$. Ta có:

$${{a}^{p}}-{{b}^{p}}=\left( a-b \right)\left( {{a}^{p-1}}+{{a}^{p-2}}b+…+a{{b}^{p-2}}+{{b}^{p-1}} \right).$$

Do $a\equiv b\left( \bmod p \right)$ nên ${{a}^{p-1}}+{{a}^{p-2}}b+…+a{{b}^{p-2}}+{{b}^{p-1}}\equiv p.{{a}^{p-1}}\equiv 0\left( \bmod p \right)$.

Suy ra : ${{a}^{p-1}}+{{a}^{p-2}}b+…+a{{b}^{p-2}}+{{b}^{p-1}}$ chia hết cho $p$  $(1)$.

Ta chứng minh tiếp $${{a}^{p-1}}+{{a}^{p-2}}b+…+a{{b}^{p-2}}+{{b}^{p-1}} \text{không chia hết cho } {{p}^{2}}. $$

Thật vậy, do $a\equiv b\left( \bmod p \right)$ nên $a=b+kp$ . Sử dụng khai triển nhị thức Newton ta có

$ {{a}^{p-1}}+{{a}^{p-2}}b+\cdots+{{b}^{p-1}}$

$\equiv \left[ \left( p-1 \right)kp{{b}^{p-2}}+{{b}^{p-1}} \right]+\left[ \left( p-2 \right)kp{{b}^{p-2}}+{{b}^{p-1}} \right]+  \cdots+\left[ kp{{b}^{p-2}}+{{b}^{p-1}} \right]+{{b}^{p-1}}\left( \bmod {{p}^{2}} \right) $

$\equiv \dfrac{p\left( p-1 \right)}{2}kp{{b}^{n-2}}+p.{{b}^{p-1}}$

$\equiv p{{b}^{p-1}}\left( \bmod {{p}^{2}} \right) $

Theo giả thiết thì $b$ không chia hết cho $p$ nên $p{{b}^{p-1}}$ không chia hết cho ${{p}^{2}}$. Do đó ${{a}^{p-1}}+{{a}^{p-2}}b+\cdots+a{{b}^{p-2}}+{{b}^{p-1}}$ cũng không chia hết cho ${{p}^{2}}$  $(2)$.

Từ $(1), (2)$ ta có: ${{v}_{p}}\left( {{a}^{p-1}}+{{a}^{p-2}}b+\cdots+a{{b}^{p-2}}+{{b}^{p-1}} \right)=1$.

Vậy ${{v}_{p}}\left( {{a}^{p}}-{{b}^{p}} \right)={{v}_{p}}\left( a-b \right)+1$.

  • Tương tự, ta cũng có: nếu m không chia hết cho p thì ${{v}_{p}}\left( {{a}^{m}}-{{b}^{m}} \right)={{v}_{p}}\left( a-b \right)$ $(**)$.

Ta quay lại định lí. Đặt ${{v}_{p}}\left( n \right)=k\Rightarrow n={{p}^{k}}.m$, với $\left( m,p \right)=1$.

Áp dụng $(*)$ và $(**)$ ta có:

${{v}_{p}}\left( {{a}^{n}}-{{b}^{n}} \right)  ={{v}_{p}}\left( {{\left( {{a}^{{{p}^{k-1}}.m}} \right)}^{p}}-{{\left( {{b}^{{{p}^{k-1}}.m}} \right)}^{p}} \right) $

$={{v}_{p}}\left( {{a}^{{{p}^{k-1}}.m}}-{{b}^{{{p}^{k-1}}.m}} \right)+1=\ldots={{v}_{p}}\left( {{a}^{m}}-{{b}^{m}} \right)+k $

$={{v}_{p}}\left( a-b \right)+{{v}_{p}}\left( n \right).$

Vậy ta đã chứng minh xong phần $i)$ của định lí.

Vì $n$ lẻ nên thay $b$ bởi $-b$ trong i. ta được ${{v}_{p}}\left( {{a}^{n}}+{{b}^{n}} \right)={{v}_{p}}\left( {{a}^{n}}-{{\left( -b \right)}^{n}} \right)={{v}_{p}}\left( a+b \right)+{{v}_{p}}\left( n \right)$

Vậy ta đã chứng minh xong phần $ii)$ của định lí. Tương tự cách làm trong $i)$ ta cũng có kết quả $iii)$.

Như vậy ta đã chứng minh xong bổ đề số mũ đúng. Sau đây ta sẽ sử dụng bổ đề để giải quyết một bài toán thú vị.

2. Các bài toán áp dụng

Bài toán Fermat lớn: Cho $n$ là số tự nhiên lớn hơn $2.$ Chứng minh rằng phương trình ${{a}^{n}}+{{b}^{n}}={{c}^{n}}$ không có nghiệm nguyên dương.

Bài Toán Fermat lớn là bài toán cực kì thú vị. Nó tồn tại gần bốn thế kỉ, kích thích biết bao nhà toán học thế giới. Bài toán cuối cùng được chứng minh bởi nhà toán học Andrew Wiles vào năm 1993. Và người ta nói rằng sẽ không có phương pháp sơ cấp nào có thể chứng minh bài toán trên. Bài báo sẽ đề cập một trường hợp đặc biệt của bài toán: số $c$ là số nguyên tố. Và chúng ta sẽ giải quyết thông qua bổ đề số mũ đúng.

Bài toán 1: Cho số nguyên lẻ $n>2$, $p$ là số nguyên tố. Chứng minh rằng phương trình $a^n + b^n = p^n$ không có nghiệm nguyên dương.

Giải

Không mất tính tổng quát, giả sử phương trình có nghiệm $a\ge b$ .

$1.$ Nếu $a=1\Rightarrow b=1$, thế vào phương trình suy ra vô lí.

$2.$ Nếu $a=2\Rightarrow b=1;2$.

  • Trường hợp $\left( a,b \right)=\left( 2,2 \right)\Rightarrow p=2$ (vô lí).
  • Trường hợp $\left( a,b \right)=\left( 2,1 \right)\Rightarrow p=3$ , thế vào phương trình ta được ${{3}^{n}}-{{2}^{n}}=1$ , cũng suy ra vô lí.

Vậy bắt buộc $a\ge 3$, mà ${{p}^{n}}>{{a}^{n}}\Rightarrow p>3$ , nên p là số nguyên tố lẻ. Do n lẻ, ta có : $${{p}^{n}}={{a}^{n}}+{{b}^{n}}=\left( a+b \right)\left( {{a}^{n-1}}-{{a}^{n-2}}b+\cdots-a{{b}^{n-2}}+{{b}^{n-1}} \right) $$

Suy ra $p|a+b$ (do $a+b>1$ ). Áp dụng bổ đề số mũ đúng cho $p$, ta có

$${{v}_{p}}\left( {{a}^{n-1}}-{{a}^{n-2}}b+\cdots-a{{b}^{n-2}}+{{b}^{n-1}} \right)={{v}_{p}}\left( {{a}^{n}}+{{b}^{n}} \right)-{{v}_{p}}\left( a+b \right)={{v}_{p}}\left( n \right) $$

Mà ${{a}^{n-1}}-{{a}^{n-2}}b+\cdots-a{{b}^{n-2}}+{{b}^{n-1}}$ là lũy thừa của $p$ nên ta có $$\left( {{a}^{n-1}}-{{a}^{n-2}}b+\cdots-a{{b}^{n-2}}+{{b}^{n-1}} \right)|n.$$

Do ${{a}^{n-1}}-{{a}^{n-2}}b+\cdots-a{{b}^{n-2}}+{{b}^{n-1}}=\frac{1}{2}\left[ {{a}^{n-1}}+{{a}^{n-3}}{{\left( a-b \right)}^{2}}+\cdots+{{b}^{n-3}}{{\left( a-b \right)}^{2}}+{{b}^{n-1}} \right]\ge \dfrac{1}{2}\left( {{a}^{n-1}}+{{b}^{n-1}} \right)$

Vì $a\ge 3$, $n\ge 3$ nên $\frac{1}{2}\left( {{a}^{n-1}}+{{b}^{n-1}} \right)>n$ nên không thể $$\left( {{a}^{n-1}}-{{a}^{n-2}}b+\cdots-a{{b}^{n-2}}+{{b}^{n-1}} \right)|n.$$

Vậy phương trình vô nghiệm khi $p$ là số nguyên tố.

Bài tập 2: Cho số nguyên $n>2$ có ước lẻ khác 1, $p$ là số nguyên tố. Chứng minh rằng phương trình ${{a}^{n}}+{{b}^{n}}={{p}^{n}}$ không có nghiệm nguyên dương.

Giải

Gọi $k>1$ là ước lẻ của $n$, giả sử $n=km$ . Đặt $x={{a}^{m}};y={{b}^{m}}$. Phương trình trên trở thành

$${{x}^{k}}+{{y}^{k}}={{p}^{n}}.$$

Không mất tính tổng quát, giả sử $x\ge y$ . Tương tự bài toán $1$ ta sẽ loại được các trường hợp tầm thường $x=1;x=2$ . Nên ta xét bài toán với trường hợp $x,p\ge 3.$ Do $k$ lẻ, ta có ${{p}^{n}}={{a}^{k}}+{{b}^{k}}=\left( a+b \right)\left( {{a}^{k-1}}-{{a}^{k-2}}b+\cdots-a{{b}^{k-2}}+{{b}^{k-1}} \right)$

Suy ra $p|b+a$. Áp dụng bổ đề số mũ đúng cho $p$ ta có

$${{v}_{p}}\left( {{a}^{k-1}}-{{a}^{k-2}}b+\cdots-a{{b}^{k-2}}+{{b}^{k-1}} \right)={{v}_{p}}\left( {{a}^{k}}+{{b}^{k}} \right)-{{v}_{p}}\left( a+b \right)={{v}_{p}}\left( k \right) $$

Mà ${{a}^{k-1}}-{{a}^{k-2}}b+ \cdots-a{{b}^{k-2}}+{{b}^{k-1}}$ là lũy thừa của $p$ nên ta có $$\left( {{a}^{k-1}}-{{a}^{k-2}}b+\cdots-a{{b}^{k-2}}+{{b}^{k-1}} \right) | k$$

Lập luận tương tự bài toán $1$ ta cũng suy ra vô lí. Vậy phương trình vô nghiệm .

Bài tập 3: Cho số nguyên $n={{2}^{k}},k>1$ , p là số nguyên tố. Chứng minh rằng phương trình ${{a}^{n}}+{{b}^{n}}={{p}^{n}}$ không có nghiệm nguyên dương.

Giải

Tương tự Bài toán $1$, ta loại được các trường hợp tầm thường nên ta chỉ xét đối với trường hợp $a,b$ có ít nhất một số lớn hơn $2$, khi đó $p>3$. Phương trình trở thành dạng

$${{x}^{4}}+{{y}^{4}}={{p}^{{{2}^{k}}}}$$

trong đó $x, y$ có ít nhất một số lớn hơn $2$ và $\left( x,y \right)=1$.

Do $p$ lẻ nên $x, y$ khác tính chẵn lẻ. Không mất tính tổng quát, giả sử $x$ lẻ, $y$ chẵn. Ta có

$${{y}^{4}}={{p}^{{{2}^{k}}}}-{{x}^{4}}=\left( {{p}^{{{2}^{k-1}}}}+{{x}^{2}} \right)\left( {{p}^{{{2}^{k-1}}}}-{{x}^{2}} \right)$$

Do $\left( {{p}^{{{2}^{k-1}}}}+{{x}^{2}};{{p}^{{{2}^{k-1}}}}-{{x}^{2}} \right)=2$ nên

$$\left\{ \begin{array}{l} {{p}^{{{2}^{k-1}}}}+{{x}^{2}}=2{{m}_{1}}^{2} \\ {{p}^{{{2}^{k-1}}}}-{{x}^{2}}=2{{n}_{1}}^{2} \end{array} \right. $$

Suy ra

$$\left\{ \begin{array}{l} {{p}^{{{2}^{k-1}}}}={{m}_{1}}^{2}+{{n}_{1}}^{2} \\ {{x}^{2}}={{m}_{1}}^{2}-{{n}_{1}}^{2} \end{array} \right. $$

và ${{y}^{2}}=2{{m}_{1}}{{n}_{1}}.$

Ta thấy $\left( {{m}_{1}};{{n}_{1}} \right)=1$ vì nếu ngược lại thì ${{m}_{1}}$ và ${{m}_{2}}$ đều phải chia hết cho $p$ (vô lí) nên có các trường hợp sau

$1)$ Nếu $m_1 = m_2^2, n_1=2n_2^2$ và $(m_2,n_2)=1$ thì thế vào ta được

$${{p}^{{{2}^{k-1}}}}={{m}_{2}}^{4}+4{{n}_{2}}^{4}=\left( {{m}_{2}}^{2}+2{{m}_{2}}{{n}_{2}}+2{{n}_{2}}^{2} \right)\left( {{m}_{2}}^{2}-2{{m}_{2}}{{n}_{2}}+2{{n}_{2}}^{2} \right)$$

mà \[\left( {{m}_{2}}^{2}+2{{m}_{2}}{{n}_{2}}+2{{n}_{2}}^{2},{{m}_{2}}^{2}-2{{m}_{2}}{{n}_{2}}+2{{n}_{2}}^{2} \right)=1\] nên \[{{m}_{2}}^{2}-2{{m}_{2}}{{n}_{2}}+2{{n}_{2}}^{2}=1\Leftrightarrow {{\left( {{m}_{2}}-{{n}_{2}} \right)}^{2}}+{{n}_{2}}^{2}=1\Leftrightarrow {{m}_{2}}={{n}_{2}}=1.\] Trường hợp này không thỏa.

$2)$ Nếu $m_1=2m_2^2,n_1=n_2^2$ và $(m_2,n_2)=1$ thì cũng tương tự.

Vậy phương trình không có nghiệm nguyên dương.

Như vậy sử dụng bổ đề số mũ đúng ta đã chứng minh được một trường hợp đặc biệt của Định lí lớn Fermat.

Sau đây, chúng ta sẽ sử dụng Bổ đề số mũ đúng để giải quyết một số bài toán khác.

Bài tập 4: Tìm bộ số nguyên dương $\left( a,b,p \right)$ trong đó $p$ là số nguyên tố thỏa $${{2}^{a}}+{{p}^{b}}={{15}^{a}}.$$

Giải

Ta có $\forall x,y\in \mathbb{Z};n\in \mathbb{N}$ thì ${{x}^{n}}-{{y}^{n}}\vdots x+y$ nên ${{p}^{b}}={{15}^{a}}-{{2}^{a}}\vdots 13\Rightarrow p=13.$

Áp dụng bổ đề

$$b={{v}_{13}}\left( {{13}^{b}} \right)={{v}_{13}}\left( {{15}^{a}}-{{2}^{a}} \right)={{v}_{13}}\left( 15-2 \right)+{{v}_{13}}\left( a \right)\Rightarrow {{v}_{13}}\left( a \right)=b-1\Rightarrow a \ \vdots \  {{13}^{b-1}}$$

Mà $a>0$ nên $a\ge {{13}^{b-1}}$, suy ra

${{13}^{b}}  ={{15}^{a}}-{{2}^{a}}=\left( 15-2 \right)\left( {{15}^{a-1}}+{{15}^{a-2}}.2+\cdots +{{15.2}^{a-2}}+{{2}^{a-1}} \right) $

$ \ge \left( 15-2 \right)\left( {{15}^{{{13}^{b-1}}-1}}+{{15}^{{{13}^{b-1}}-2}}.2+\cdots+{{15.2}^{{{13}^{b-1}}-2}}+{{2}^{{{13}^{b-1}}-1}} \right) $

$\Rightarrow b=1\Rightarrow a=1.$

Vậy nghiệm bài toán là $\left( a,b,p \right)=\left( 1,1,13 \right)$.

 

Bài tập 5: Chứng minh rằng không tồn tại cặp số $\left( a,n \right)$ nguyên dương, $n>2$ , sao cho ${{\left( a+1 \right)}^{n}}-{{a}^{n}}$ là lũy thừa bậc dương của $5.$

Giải

Giả sử tồn tại số nguyên dương $m$ sao cho $${{\left( a+1 \right)}^{n}}-{{a}^{n}}={{5}^{m}}.$$

Nhận xét: nếu$a$ hoặc $a+1$ chia hết cho $5$ thì số còn lại cũng cũng chia hết cho $5$ (vô lí). Nên cả hai số đều không chia hết cho $5.$ Ta xét các trường hợp:

$1.$  Nếu $a\equiv 1\left( \bmod 5 \right)\Rightarrow 0\equiv {{\left( a+1 \right)}^{n}}-{{a}^{n}}\equiv {{2}^{n}}-1\left( \bmod 5 \right)$ . Suy ra $4|n$.

$2.$  Nếu $a\equiv 2\left( \bmod 5 \right)\Rightarrow 0\equiv {{\left( a+1 \right)}^{n}}-{{a}^{n}}\equiv {{3}^{n}}-{{2}^{n}}\left( \bmod 5 \right)$. Suy ra $2|n$.

$3.$  Nếu $a\equiv 3\left( \bmod 5 \right)\Rightarrow 0\equiv {{\left( a+1 \right)}^{n}}-{{a}^{n}}\equiv {{4}^{n}}-{{3}^{n}}\left( \bmod 5 \right)$. Suy ra $4|n$.

Do đó, $n$ luôn là số chẵn, đặt $n=2{{n}_{1}}$, $\left( {{n}_{1}}\in \mathbb{N},{{n}_{1}}\ge 2 \right)$. Ta có

$ {{5}^{m}} = {{\left( a+1 \right)}^{2{{n}_{1}}}}-{{a}^{2{{n}_{1}}}}=\left( {{\left( a+1 \right)}^{2}}-{{a}^{2}} \right)\left( {{\left( a+1 \right)}^{2\left( {{n}_{1}}-1 \right)}}+ \cdots + {{\left( a+1 \right)}^{2}}{{a}^{2\left( {{n}_{1}}-2 \right)}}+{{a}^{2\left( {{n}_{1}}-1 \right)}} \right) $

$=\left( 2a+1 \right)\left( {{\left( a+1 \right)}^{2\left( {{n}_{1}}-1 \right)}}+{{\left( a+1 \right)}^{2\left( {{n}_{1}}-2 \right)}}{{a}^{2}}+…+{{\left( a+1 \right)}^{2}}{{a}^{2\left( {{n}_{1}}-2 \right)}}+{{a}^{2\left( {{n}_{1}}-1 \right)}} \right). $

Suy ra $5| 2a+15$ , áp dụng bổ đề số mũ đúng ta được

${{v}_{5}}\left( {{\left( a+1 \right)}^{2\left( {{n}_{1}}-1 \right)}}+{{\left( a+1 \right)}^{2\left( {{n}_{1}}-2 \right)}}{{a}^{2}}+…+{{\left( a+1 \right)}^{2}}{{a}^{2\left( {{n}_{1}}-2 \right)}}+{{a}^{2\left( {{n}_{1}}-1 \right)}} \right) $

$= {{v}_{5}}\left( {{\left( a+1 \right)}^{2{{n}_{1}}}}-{{a}^{2{{n}_{1}}}} \right)-{{v}_{5}}\left( 2a+1 \right)={{v}_{5}}\left( {{n}_{1}} \right). $

Do ${{\left( a+1 \right)}^{2\left( {{n}_{1}}-1 \right)}}+{{\left( a+1 \right)}^{2\left( {{n}_{1}}-2 \right)}}{{a}^{2}}+ \cdots +{{\left( a+1 \right)}^{2}}{{a}^{2\left( {{n}_{1}}-2 \right)}}+{{a}^{2\left( {{n}_{1}}-1 \right)}}$ là lũy thừa của $5$ nên $${{n}_{1}}\vdots \left( {{\left( a+1 \right)}^{2\left( {{n}_{1}}-1 \right)}}+{{\left( a+1 \right)}^{2\left( {{n}_{1}}-2 \right)}}{{a}^{2}}+…+{{\left( a+1 \right)}^{2}}{{a}^{2\left( {{n}_{1}}-2 \right)}}+{{a}^{2\left( {{n}_{1}}-1 \right)}} \right)$$ (vô lí vì về phải gồm ${{n}_{1}}$ số nguyên dương, ${{n}_{1}}>1$ và $a+1\ge 2$).

Vậy không tồn tại cặp số $\left( a,n \right)$ nguyên dương, $n>2$ sao cho ${{\left( a+1 \right)}^{n}}-{{a}^{n}}$ là lũy thừa bậc dương của $5.$

 

Bài tập 6: Cho hai số nguyên $a,n\ge 2$ sao cho tồn tại số nguyên dương k thỏa $n|{{\left( a-1 \right)}^{k}}$ . Chứng minh rằng n là ước của $1+a+{{a}^{2}}+…+{{a}^{n-1}}$ .

Giải

Giả sử $p$ là ước nguyên tố bất kì của $n$ . Theo giả thiết $n|{{\left( a-1 \right)}^{k}}$ nên p cũng là ước của $a-1$ .

Do ${{a}^{n}}-1=\left( a-1 \right)\left( 1+a+{{a}^{2}}+\cdots +{{a}^{n-1}} \right)$ nên áp dụng bổ đề số mũ đúng ta có

$${{v}_{p}}\left( 1+a+{{a}^{2}}+\cdots+{{a}^{n-1}} \right)={{v}_{p}}\left( {{a}^{n}}-1 \right)-{{v}_{p}}\left( a-1 \right)={{v}_{p}}\left( n \right).$$

Do mọi ước nguyên tố $p$ của n đều thỏa điều trên nên ta có $$n|1+a+{{a}^{2}}+\cdots+{{a}^{n-1}}.$$

Bài tập 7 (HSG Trung Quốc 2009): Tìm cặp số nguyên tố $\left( p,q \right)$ thỏa $pq|{{5}^{p}}+{{5}^{q}}$ (*).

Giải

Ta xét các trường hợp

$1.$   $p=q=5$ thỏa mãn bài toán.

$2.$   Nếu có một số bằng $5$, một số khác $5$. Không mất tính tổng quát, giả sử $p=5;q\ne 5$. Ta có :

$$5q|{{5}^{5}}+{{5}^{q}}\Leftrightarrow q|{{5}^{4}}+{{5}^{q-1}}\Leftrightarrow q|{{5}^{4}}+1=626$$ do ${{5}^{q-1}}\equiv 1\left( \bmod \,q \right)$ nên suy ra $q=2$ hoặc $q=313$.

$3.$  Nếu cả hai số $p,q\ne 5$ . Do ${{5}^{p}}\equiv 5\left( \bmod p \right),\,\,{{5}^{q}}\equiv 5\,\,\,\,\left( \bmod \,q \right)$ nên

$$\left( * \right)\Leftrightarrow \left\{ \begin{array}{l}  {{5}^{p-1}}+1\vdots q \\ {{5}^{q-1}}+1\vdots p \end{array} \right. \Rightarrow \left\{ \begin{array}{l} {{5}^{2\left( p-1 \right)}}-1\vdots q \\ {{5}^{2\left( q-1 \right)}}-1\vdots p \end{array} \right.$$

Do ${{5}^{2\left( p-1 \right)}}-1$ chia hết cho $q$ nhưng ${{5}^{p-1}}-1$ không chia hết cho $q$ nên

$${{v}_{2}}\left( \text{ord}_{q}\left( 5 \right) \right)=1+{{v}_{2}}\left( p-1 \right) .$$

Do ${{5}^{q-1}}-1$ chia hết $q$ nên $q-1\vdots or{{d}_{q}}\left( 5 \right)$ nên

$${{v}_{2}}\left( q-1 \right)\ge 1+{{v}_{2}}\left( p-1 \right) .$$

Tương tự khi xét chia hết cho $p$ ta lại có ${{v}_{2}}\left( p-1 \right)\ge 1+{{v}_{2}}\left( q-1 \right)$ (vô lí).

Vậy các cặp số thỏa mãn là $\left( p,q \right)=\left( 2,5 \right);\left( 5,2 \right);\left( 5,5 \right);\left( 5,313 \right);\left( 313,5 \right).$

Bài tập 8 (HSG Brazil 2009): Cho hai số nguyên tố $p, q$ sao cho $q=2p+1$ . Chứng minh rằng tồn tại một số là bội của $q$ có tổng các chữ số của nó trong hệ cơ số $10$ nhỏ hơn $4.$

Giải

Do $p,q$ đều là số nguyên tố nên $q\ge 5$ .

Nếu $q=5$ thì ta chỉ cần chọn số $10$ thì thỏa yêu cầu bài toán.

Nếu $q>5$ , áp dụng Định lí Fermat nhỏ thì $q|{{10}^{q-1}}-1={{10}^{2p}}-1=\left( {{10}^{p}}-1 \right)\left( {{10}^{p}}+1 \right)$

Suy ra $q|{{10}^{p}}+1$ hoặc $q|{{10}^{p}}-1$.

$1.$  Nếu $q|{{10}^{p}}+1$ thì số $a={{10}^{p}}+1$ là số thỏa yêu cầu đề bài.

$2.$  Nếu $q|{{10}^{p}}-1$. Do $p$ là số nguyên tố và $q$ không là ước của $10-1$(do $q>5$ ) nên $p$ cũng chính là $or{{d}_{q}}\left( 10 \right)$. Do đó $10;{{10}^{2}};\ldots ;{{10}^{p}}$ sẽ có số dư khác nhau khi chia cho $q.$

Ta sẽ có các trường hợp

  • Nếu tồn tại $1\le k\le p$ mà ${{10}^{k}}\equiv p\left( \bmod \,q \right)$ thì ${{2.10}^{k}}+1\equiv 2p+1\equiv 0\left( \bmod \,q \right)$. Khi đó số $a={{2.10}^{k}}+1$ là số thỏa yêu cầu đề bài.
  • Nếu tồn tại $1\le k\le p$ mà ${{10}^{k}}\equiv 2p\left( \bmod \,q \right)$ thì ${{10}^{k}}+1\equiv 2p+1\equiv 0\left( \bmod \,q \right)$. Khi đó số $a={{10}^{k}}+1$ là số thỏa yêu cầu đề bài.
  • Nếu không tồn tại $1\le k\le p$ mà ${{10}^{k}}$ có số dư là $p$ hay $2p$ khi chia cho $q.$ Thì ta sẽ chia các số dư còn lại của $q$ thành $p$ bộ $$\left( 1;2p-1 \right),\left( 2;2p-2 \right),\ldots,\left( p-1;p+1 \right)$$ (tổng $2$ phần tử của một bộ bằng $2p$) . Do tập số dư khi chia cho $q$ của tập $\left\{ 10;{{10}^{2}};\ldots ;{{10}^{p}} \right\}$ có $p$ phần tử nên Theo nguyên lí Dirichlet sẽ có ít nhất hai số ${{10}^{k}}$ và ${{10}^{l}}$ thuộc cùng một bộ. Khi đó số $a={{10}^{k}}+{{10}^{l}}+1$ sẽ chia hết cho $q$ là số thỏa yêu cầu đề bài.

Bài tập 9 (IMO Shortlist 1997): Cho $b,m,n$ là các số nguyên dương thỏa$m>1;\,\,m\ne n$. Biết ${{b}^{m}}-1$và ${{b}^{n}}-1$ có cùng tập hợp các ước nguyên tố. Chứng minh $b+1$ là lũy thừa của $2.$

Giải

Theo đề, gọi $p$ là ước nguyên tố bất kì của ${{b}^{m}}-1$và ${{b}^{n}}-1$.

Ta có kết quả quen thuộc: $$\left( {{b}^{m}}-1,{{b}^{n}}-1 \right)={{b}^{\left( m,n \right)}}-1,$$ đặt $\alpha =\left( m,n \right)$ nên $p|{{b}^{\alpha }}-1$. Suy ra tồn tại $k,l\in \mathbb{N}*$ thỏa $m=\alpha k;\,\,n=\alpha l$.

Đặt $a={{b}^{\alpha }}$ , từ giả thiết suy ra mọi ước nguyên tố của ${{a}^{k}}-1$ và ${{a}^{l}}-1$ đều là ước của $a-1$ . Nói cách khác, tập hợp các ước nguyên tố của ${{a}^{k}}-1,{{a}^{l}}-1$ và $a-1$ là trùng nhau.

Do $m\ne n$ suy ra tồn tại một số $k$ hoặc $l$ lớn hơn 1. Giả sử số đó là k.

Ta chứng minh $a+1$ là lũy thừa của 2.

Thật vậy:

$1.$  Nếu $k$ là số chẵn, đặt $k={{2}^{\beta }}.k’$($k’$ là số lẻ).

Ta có: $${{a}^{k}}-1=\left( {{a}^{k’}}-1 \right)\left( {{a}^{k’}}+1 \right)\left( {{a}^{2k’}}+1 \right)…\left( {{a}^{{{2}^{\beta -1}}k’}}+1 \right).$$

Do đó mọi ước nguyên tố $q$ của ${{a}^{k’}}+1$ cũng là ước của $a-1$

Mà ${{a}^{k’}}+1\vdots a+1$, $\left( a+1;a-1 \right)=1$ hoặc $2.$ Suy ra $2\vdots q\Rightarrow q=2$ nên ${{a}^{k’}}+1$ là lũy thừa của $2.$ Suy ra $a+1$ cũng là lũy thừa của $2.$

$2.$  Nếu $k$ là số lẻ, ta có ${{a}^{k}}-1=\left( a-1 \right)\left( {{a}^{k-1}}+{{a}^{k-2}}+…+a+1 \right)$

Gọi $q$ là ước nguyên tố bất kì của ${{a}^{k-1}}+{{a}^{k-2}}+…+1$. Do ${{a}^{k-1}}+{{a}^{k-2}}+…+a+1$ là số lẻ nên, nên $q$ cũng lẻ và là ước của ${{a}^{k}}-1$ . Do đó q cũng là ước của $a-1$ .

Áp dụng bổ đề số mũ đúng của $q$ ta có

${{v}_{q}}\left( {{a}^{k-1}}+{{a}^{k-2}}+…+1 \right)={{v}_{q}}\left( {{a}^{k}}-1 \right)-{{v}_{q}}\left( a-1 \right)={{v}_{q}}\left( k \right)$

Suy ra $k\vdots \left( {{a}^{k-1}}+{{a}^{k-2}}+…+1 \right)$ (vô lí vì vế phải có k số nguyên dương, $a>1$ ).

Vậy $a+1={{b}^{\alpha }}+1$ là lũy thừa của $2$.

Vì ${{b}^{\alpha }}+1$ là lũy thừa của $2$ nên nếu $\alpha $ là số chẵn thì ${{b}^{\alpha }}+1={{\left( {{b}^{\alpha ‘}} \right)}^{2}}+1$ hoặc là số lẻ hoặc chia 4 dư 2 nên chỉ có một trường hợp thỏa là $b=1$ . Còn nếu $\alpha $ là số lẻ thì ${{b}^{\alpha }}+1=\left( b+1 \right)\left( {{b}^{\alpha -1}}+{{b}^{\alpha -2}}+…+b+1 \right)$ nên $b+1$ cũng là lũy thừa của $2$.

Bài tập 10 (IMO Shortlist 1999): Tìm các số nguyên dương $n,p$ trong đó p nguyên tố thỏa ${{n}^{p-1}}|{{\left( p-1 \right)}^{n}}+1$.

Giải

Ta xét các trường hợp sau

$1.$  Nếu $p=2\Rightarrow n|2\Rightarrow n=1;2$ (thỏa).

$2.$  Nếu $p>2$ , suy ra $p$ lẻ nên ${{\left( p-1 \right)}^{n}}+1$ lẻ $\Rightarrow n$ lẻ

Gọi $q$ là ước nguyên tố nhỏ nhất của n $\Rightarrow q|{{n}^{p-1}}|{{\left( p-1 \right)}^{n}}+1$ $\Rightarrow q|{{\left( p-1 \right)}^{2n}}-1$

Mà : $q|{{\left( p-1 \right)}^{q-1}}-1\Rightarrow q|{{\left( p-1 \right)}^{\left( 2n,q-1 \right)}}-1$

Do n lẻ và $q$ là ước nguyên tố nhỏ nhất của n nên $\left( 2n;q-1 \right)=2$ .

Suy ra $q|{{\left( p-1 \right)}^{2}}-1=\left( p-2 \right)p$ $\Rightarrow $ $q|p-2$ hoặc $q=p$. Ta lại có các trường hợp nhỏ

$(a)$  Nếu $q|p-2\Rightarrow 0\equiv {{\left( p-1 \right)}^{n}}+1\equiv 1+1\equiv 2\left( \bmod \,q \right)$ $\Rightarrow q=2$ (vô lí vì q lẻ)

$(b)$  Nếu $q=p$ . Áp dụng bổ đề số mũ đúng cơ số q ta có

$\left( p-1 \right){{v}_{p}}\left( n \right)={{v}_{p}}\left( {{n}^{p-1}} \right)\le {{v}_{p}}\left[ {{\left( p-1 \right)}^{n}}+1 \right]={{v}_{p}}\left( p-1+1 \right)+{{v}_{p}}\left( n \right)=1+{{v}_{p}}\left( n \right)$

Suy ra : $\left( p-2 \right){{v}_{p}}\left( n \right)\le 1\Rightarrow p=3$ và ${{v}_{p}}\left( n \right)=1.$

Đến đây, bài toán trở thành : Tìm n để ${{n}^{2}}|{{2}^{n}}+1$.

Nhận xét $n=1$ thỏa yêu cầu bài toán nên ta xét $n>1$. Suy ra $n$ là số lẻ, gọi $r$ là ước nguyên tố nhỏ nhất của $n$. Suy ra $r|{{2}^{n}}+1\,\,|{{2}^{2n}}-1$, mà $r|{{2}^{r-1}}-1$ nên suy ra $r|{{2}^{\left( 2n;r-1 \right)}}-1$.

Do $n$ là số lẻ và $r$ là ước nguyên tố nhỏ nhất của $n$ nên $\left( 2n;r-1 \right)=2$ nên $r=3$. Ta có đánh giá sau

$$2{{v}_{3}}\left( n \right)\le {{v}_{3}}\left( {{4}^{n}}-1 \right)={{v}_{3}}\left( 4-1 \right)+{{v}_{3}}\left( n \right)\Rightarrow {{v}_{3}}\left( n \right)\le 1\Rightarrow {{v}_{3}}\left( n \right)=1.$$ Suy ra $n=3.m$, $\left( m,n \right)=1$. Thế vào đề bài, ta được $${{m}^{2}}|{{8}^{m}}+1|{{8}^{2m}}-1.$$

Nếu $m>1$ , tương tự ta gọi $s$ là ước nguyên tố nhỏ nhất của $m.$ Suy ra $m$ là ước của ${{8}^{2}}-1=63$. Do đó $s=7$, điều này vô lí vì ${{8}^{m}}+1$ chia $7$ dư $2.$ Suy ra $m=1\Rightarrow n=3$.

Vậy $\left( n,p \right)=\left( 1,2 \right);\left( 2,2 \right);\left( 3;3 \right)$ .