Bổ đề số học hay và ứng dụng - Lê Xuân Đại - THTT số 509

Bài viết này đề cập đến một tính chat hay và đẹp đẽ của số học cùng với ứng dung của nó trong việc giải các bài toán chia hết cấp trung học cơ sở. Nội dung của nó được phát biểu dưới dạng bổ đề sau:
Bổ đề: Cho a là số nguyên, p là số nguyên dương và h là số nguyên dương nhỏ nhất thỏa mãn $a^{h}\equiv (\text{ mod }p )$. Khi đó nếu $n$ là số nguyên dương thỏa mãn $a^{n}\equiv  1(\text{ mod }p)$ thì $n$ chia hết cho $h$.
Chứng minh. Ta biểu diễn $n=kh+r,0\le r<h$.
Khi đó: $a^{n}=a^{kh+r}=(a^{h})^{k}.a^{r}\equiv a^{r}(\text{ mod }p)$.
$\implies a^{r}\equiv 1(\text{ mod }p)(*)$.
Nếu $r>0$ thì từ $(*)$ dẫn đến mâu thuẫn với tính nhỏ nhất của $h$. Vậy $r=0$, tức là $n$ chia hết cho $h$.
Nhận xét. Rõ rang chiều ngược lại là hiển nhiên, tức là nếu $n\vdots h$ thì ta có $a^{n}\equiv 1(\text{ mod }p)$. Sau đây là 1 số ví dụ áp dung bổ đề trên.
Thí dụ 1. Cho $n$ là số nguyên dương lớn hơn 1 thỏa mãn $3^{n}-1\vdots n$. Chứng minh rang n chẵn.
Phân tích. Để chứng minh một số n chẵn ta chỉ cần chứng minh ước nguyên p nhỏ nhất của n là 2. Khi đưa them số nguyên tố p vào đây coi chư ta có them một quan hệ động dư $3^{n}\equiv 1 (\text{ mod }p)$, cùng với việc áp dung bổ đề và kết hợp them định lý Fermat nhỏ ta sẽ có them nhiều suy luận cho p và n. Cụ thể lời giải bài toán như sau:
Gọi p là ước nguyên tố nhỏ nhất của n. Ta có: $3^{n}\equiv 1(\text{ mod }p)\implies p\ne 3$. Gọi $h$ là số nguyên dương nhỏ nhất sao cho $3^{h}\equiv 1(\text{ mod p})(1)$.
Theo định lý Fermat nhỏ ta được: $3^{p-1}\equiv 1(\text { mod }p)$. Do đó theo bổ đề ta được $n\vdots h$ và $p-1\vdots h$. Nếu $h>1$ thì gọi q là ước nguyên của $h$, suy ra $h\ge q$ và $h\vdots q$. Mà $p-1\ge h\implies p>h\ge q$, mâu thuẩn với $p$ là ước nguyên tố nhỏ nhất của n. Vậy $h=1$, từ đó theo (1) ta được $p=2$. Do đó $n$ chẵn (đpcm).
Chú ý. Khi áp dung bổ đề, để có sự tồn tại của h nhỏ nhất thỏa mãn $a^{h}\equiv 1(\text{ mod }p)$ thì trước đó ta phải chỉ ra tồn tại $n$ sao cho $a^{n} \equiv 1(\text { mod } p )$. Ngoài ra khi áp dung bổ đề trên ta cũng thường sử dung them định lý Fermat nhỏ để tạo them một quan hệ đồng dư.
Thí dụ 2. Cho $p$ là số nguyên tố. Gọi $q$ là ước nguyên tố bất kỳ của $2^{p}-1$. Chứng minh rang q-1 chia hết cho p.
Lời giải. Gọi h là số nguyên dương nhỏ nhất thỏa mãn $2^{h}\equiv 1(\text{ mod }q)$, theo bổ đề thì $p\vdots h$.
Dễ thấy $h\ne 1$ suy ra $h=p$. Theo định lý Fermat nhỏ ta có: $2^{q-1}\equiv 1(\text{ mod }q)\implies q-1\vdots h$. Vậy $q-1\vdots p$ (đpcm)
Nhận xét. Từ kết quả bài toán ta suy ra mỗi ước nguyên tố của $2^{p}-1$ đều lơn hơn p.
Bài toán tiếp theo là một tổng quát của thí dụ 2.
Thí dụ 3. Cho $p$ là số nguyên tố, a là số nguyên với $1<a\le p-1$. Đặt $A=\sum\limits
_{k=0}^{p-1}a^{k}$. Gọi $q$ là một ước nguyên tố bất kỳ của $A$. Chứng minh rang $q-1$ chia hết cho $p$.
Lời giải. Ta có: $A=\sum\limits_{k=0}^{p-1}a^{k}=\frac{a^{p}-1}{a-1}$, suy ra $a^{p}\equiv 1(\text{ mod }q)$ và $a^{q-1}\equiv 1(\text{ mod }q)$.
Gọi $h$ là số nguyên dương nhỏ nhất thỏa mãn $a^{h}\equiv 1(\text{ mod }q)$, theo bổ đề thì $p\vdots h$ và $q-1\vdots h$. Nếu $h=1$ thì $a\equiv 1 (\text{ mod }q)$, khi đó $A=\sum\limits{k=0}^{p-1}a^{k}\equiv p(\text{ mod }q)$, suy ra $p\vdots q\implies p=q$.
Khi đó $a-1\vdots p$, mâu thuẩn với $1<a\le p-1$. Vậy $h=p$ và ta có đpcm.
Thí dụ 4. Cho a là số tự nhiên, n là số nguyên lớn hơn 1 thỏa mãn $a^{n}+1\vdots n^2$.
a) Chứng minh rang n lẻ.
b) Chứng mình rang a+1 không là lũy thừa của 2.
Lời giải. a) Nếu n chẵn thì $a^{n}$ là số chính phương, suy ra: $a^{n}\equiv 0,1(\text{ mod }4)\implies a^{n}+1\equiv 1,2(\text{ mod } 4)$.
Mặt khác $n^2\equiv 0(\text{ mod }4)$, từ đó dẫn đến mâu thuẫn.
b) Gọi $p$ là ước nguyên tố nhỏ nhất của n, vì n lẻ nên p lẻ. Ta có: $a^{n}\equiv -1(\text{ mod }p)\implies (-a)^{n}\equiv 1(\text{ mod }p)$.
Gọi $h$ là số nguyên dương nhỏ nhất sao cho $(-a)^{h}\equiv 1(\text{ mod }p)$. Ta có ngay $n\vdots h$ và $p-1\vdots h$. Tương tự như trên ta được $h=1$. Suy ra $a+1\vdots p$. Vậy $a+1$ có ước nguyên tố lẻ, tức là a+1  không thể là lũy thừa của 2 (đpcm).
Thí dụ 5. Cho $a,b$ là hai số tự nhiên sao cho $a+b$ không có ước nguyên tố lẻ. Chứng minh rang với mọi số n lẻ lớn hơn 1 thì $a^n+b^n$ không chia hết cho $n$.
Lời giải. Giả sử tồn tại n lẻ, n>1 thỏa mãn $a^n+b^n\vdots n$.
Gọi $p$ là ước nguyên tố nhỏ nhất của n. Khi đó p lẻ và $a^{n}\equiv -b^{n}(\text{ mod }p)$, suy ra $a^{n}\equiv (-b)^{n}(\text{ mod }p)(1)$.
nếu $a\vdots p$ thì $b\vdots p$, suy ra $a+b\vdots p$, trái giả thiết, do đó $(a.p)=(b,p)=1$.
Theo định lý Fermat nhỏ ta được $a^{p-1}\vdots (-b)^{p-1}\equiv 1(\text{ mod }p)$.
Gọi $h$ là số nguyên dương nhỏ nhất sao cho $a^{h}\equiv (-b)^{h}(\text{ mod }p)$. Khi đó dễ thấy $n\vdots h$ và $p-1\vdots h$. Từ đó suy ra $h<p$, kết hợp với p là ước nguyên tố nhỏ nhất của n ta được $h=1$. Do đó $a+b\vdots p$, mâu thuẩn. Vậy ta có điều phải chứng minh.
Thí dụ 6 (AIME 2001). Có bao nhiêu số nguyên dương n là bội của 1001 có thể biểu diễn dưới dạng $10^{j}-10^{i};0\le i<j\le 99$.
Lời giải. Ta có $n=10^{j}-10^{I}=10^{I}(10^{j-i}-1)$ và $1001=7.11.13$ là số nguyên tố cùng nhau với $10^i$. Vậy $(I,j)$ thỏa mãn $10^{j-i}-1\vdots 1001\iff 10^{j-i}\vdots 1(\text{ mod }1001) $.
Ta có: $10^3\vdots -1 (\text{ mod }1001)\implies 10^6\vdots 1(\text{ mod 1001})$.
Cũng dễ thấy $h=6$ là số nguyên dương nhỏ nhất thỏa mãn $10^{h}\equiv 1(\text{ mod }1001)$, từ đó $j-i\vdots 6$.
Vậy số các số n cần tìm thực chat bang số các bộ $(I,j)$ thỏa mãn phương trình $j-i=6m(1)$ với $0\le i <j\le 99;m\in \mathbb{N}^*$. Ta thấy ngay $1\le m\le 16$ và với mỗi $m=1,2,3,...,16$ sẽ có 100-6m giá trị của (I và j). Vậy số nghiệm của phương trình (1) là 94+88+82+...+4=784.
Do đó có 784 số n thỏa mãn đề bài.
Thí dụ 7. Cho $p$ là số nguyên tố lẻ và q,r là những số nguyên tố sao cho $q^r+1\vdots p$. Chứng minh rang hoặc $p-1\vdots 2r$ hoặc $q^2-1\vdots p$.
Lời giải. Từ $q^r+1vdots p$ suy ra $q^{r}\equiv -1\ne 1(\text{ mod }p)$ và $q^{2r}\equiv 1(\text{ mod }p)$. Gọi $h$ là số nguyên dương nhỏ nhất thỏa mãn $q^h\equiv 1(\text{ mod }p)0$. Khi đó $2r\vdots h$ nhưng $r\not \vdots h$.
Do r nguyên tố nên chỉ có thể xảy ra khi h=2 hoặc h=2r.
Nếu $h=2r$ thì từ $q^{p-1}\equiv 1(\text{ mod } p )$ suy ra $p-1\vdots 2r$.
Nếu $h=2$ thì $q^2\equiv 1(\text{ mod } p )$ nên $q^2-1\vdots p$ (đpcm).
Thí dụ 8. Cho $a,n$ là các số nguyên dương, $a>1$ và p là một ước nguyên tố lẻ của $a^{2^{n}}+1$. Chứng minh rang $(p-1)\vdots 2^{n+1}$.
Lời giải. Từ $a^{2^{n}}\equiv -1(\text{ mod }p)$, ta có: $a^{2^{n+1}}\equiv 1(\text{ mod }p)$. Gọi $h$ là số nguyên dương nhỏ nhất thỏa mãn $a^h\equiv 1(\text{ mod }p)$ thì $2^{n+1}\vdots h$. Nhưng $a^{2^{n}}\equiv -1(\text{ mod }p)$ nên suy ra $h=2^{n+1}$.
Rõ rang $(a,p)=1$ nên $^{p-1}\equiv 1(\text{ mod }p)$, suy ra $(p-1)\vdots 2^{n+1}$ (đpcm).
Nhận xét. Trong trường hợp đặc biệt $a=2$ thì $F_{n}=2^{2^{n}}+1$ là số Fermat thứ n. Như vậy nếu p là một ước nguyên tố của số Fermat $F_n$ thì $(p-1)\vdots 2^{n+1}$.
Bài toán trên có thể tổng quát như sau: Cho hai số $a,b$ nguyên, nguyên tố cùng nhau. Gọi $p$ là một ước nguyên tố lẻ của $a^{2^{n}}+b^{2^{n}}$ (n là số nguyên dương nào đó). Chứng minh rang $(p-1)\vdots 2^{n+1}$.
Bài tập:
1. Cho $n$ nguyên với $n\ge 2$. Chứng minh rang $2^{n}-1$ không chia hết cho n.
2. Cho $n$ nguyên, $n>1$ và thỏa mãn $3^{n}-1\vdots n^3$. Chứng minh rang n chẵn và n không chia hết cho 4.
3. (China 2009). Tìm tất cả các số nguyên tố $p,q$ sao cho $5^p+5^q\vdots pq$.
4. Tìm tất cả các số nguyên tố $p,q$ sao cho $(5^p-2^p)(5^q-2^q)\vdots pq$.
5. (USATST 2003). Tìm tất cả các bộ số nguyên tố $(p,q,r)$ sao cho $q^{r}+1\vdots p,r^p+1\vdots q$ và $p^{q}+1\vdots r$.



Nhận xét

Bài đăng phổ biến từ blog này

Sinh Test trong Python va code AC

Học về Segment Tree

Cách tính a*b mod m , a^b mod m , a^(-1) mod m với m không phải là số nguyên tố (inversion có nghĩa khi (a,m)=1)