Dùng thặng dư bậc hai để giải phương trình nghiệm nguyên

Các kiến thức cần nhớ:
$$-1 \equiv a^2 (mod p) \Leftrightarrow p \equiv 1 (mod 4)\\
2 \equiv a^2 (mod p) \Leftrightarrow p\equiv 1,7 (mod 8)\\
-2 \equiv a^2 (mod p) \Leftrightarrow p \equiv 1,3 (mod 8)$$

Ta sẽ xét các ví dụ dùng thặng dư bậc hai để chứng minh một số trường hợp vô nghiệm của phương trình Mordell:

Vd 1: Giải phương trình $y^2=x^3+7$ trên tập số tự nhiên.

Giải:

Giả sử tồn tại $(x,y)$ thỏa mãn.
Nếu $x$ chẵn thì $y^2 \equiv 7 (mod 8)$ ( Loại)
Nên $x$ lẻ và $y^2+1=(x+1)(x^2-2x+4)$

Vì $x$ lẻ nên $x^2-2x+4=(x-1)^2+3 \equiv 3 (mod 4)$ vì thế $x^2-2x+4$ phải có một ước nguyên tố $p \equiv 3 (mod 4)$ (nếu không thì $x^2-2x+4 \equiv 1 (mod 4)$)

Ta suy ra $p| y^2+1$ nên $-1 \equiv y^2 (mod p)$ không được do $p \equiv 3 (mod 4)$

Vd 2: Chứng minh phương trình $y^2=x^3-5$ vô nghiệm tự nhiên.

Giải:

Giả sử tồn tại, xét mod 4: $y^2\equiv x^3-1 (mod 4)$
Xét $y \equiv 0,1,2,3 (mod 4), x \equiv 0,1,2,3 (mod 4)$  nhận thấy chỉ có giá trị chung của $y^2 (mod 4)$ và $x^3-1 (mod 4)$ là $0$ vì thế $y$ chẵn và $x \equiv 1 (mod 4)$
vậy:
$y^2+4=x^3-1=(x-1)(x^2+x+1)$, $x^2+x+1 \ge 3 \equiv 3 (mod 4)$ nên $-4$ là số chính phương mod $p$ hay $-1$ là số chính phương mod $p$ suy ra $p \equiv 1 (mod 4)$ mâu thuẫn với $p \equiv 3 (mod 4)$

Vd3: Chứng minh rằng phương trình $y^2=x^3-6$ không có nghiệm tự nhiên.
Giải:

Giả sử ngược lại. Nếu $x$ chẵn thì $y^2 \equiv -6 \equiv 2 (mod 8)$ ( vô lí với số chính phương )
Nên $x$ lẻ, $y$ lẻ và $x^3=y^2+6 \equiv 7 (mod 8)$ Ta cũng có: $x^3 \equiv x (mod 8 ) \forall x$ lẻ, nên $x \equiv 7 (mod 8)$
Viết lại:
$y^2-2=(x-2)(x^2+2x+4)$ với $x^2+2x+4 \equiv 7^2+2.7+4 \equiv 3 (mod 8)$. Vì thế phải có ước $p \equiv \pm 3 (mod 8)$ vì nếu không $x^2+2x+4 \equiv \pm 1 (mod 8)$. Ta có $2 \equiv y^2 (mod p) \Rightarrow p \equiv \pm 1 (mod 8)$ ( Mâu thuẫn)

Tính chất của dãy số Fibonacci

1) $(F_n,F_{n+1})=1$

2) Nếu $n |m $ thì $F_n |F_m$
Ta chỉ cần chứng minh tính chất sau:
$F_{m+n}=F_{m-1}F_{n+1}+F_{m}.F_{n}$
Quy nạp theo $n$, với $n=1$ đúng
Giả sử đúng với $n=k$ khi đó với $n=k+1$ thì:
$F_{m+k+1}=F_{m+k}+F_{m+k-1}=(F_{m-1}F_{k+1}+F_{m}.F_{k})+(F_{m-1}_F{k}+F_{m}.F_{k-1})=F_{m-1}F_{k+2}+F_{m}F_{k+1}$
Vậy theo nguyên lí quy nạp ta có điều phải chứng minh.
Cho $m=kn$ thì ta suy ra thêm được một số tính chất sau
3)Nếu $F_n$ chia hết cho $F_m$ thì $n$ chia hết cho $m$ (m>2)
4) $(F_m,F_n)=F_{(m,n)}$
5) $n \ge 5$ và $F_n$ là số nguyên tố thì n cũng là số nguyên tố.
6) $(F_n)$ chứa vô hạn những số nguyên tố đôi một cùng nhau
7) $F_{5n}=5F_nq_n$ $q_n$ không chia hết cho 5.

Chứng minh:

Cách 1:
$F_{5n}=\frac{q_1^{5n}-q_2^{5n}}{\sqrt 5}=F_n(q_1^{4n}+q_1^{3n}q_2^n+(q_1q_2)^2n+q_1^nq_2^{3n}+q_2^{4n})=F_n(L_{4n}+(-1)^nL_{2n}+1)=F_n(L_{2n}^2+(-1)^nL_{2n}-1).$ Vì thế $v_5(F_{5n})=v_5(F_n)+v_5(L_{2n}^2+(-1)^nL_{2n}-1)$.
$L_n^2-5F_n^2=4(-1)^n$
$F_{2n}=F_nL_n$.
Do $n=1$ $L_2^2-L_2-1=5$.
$L_n,F_n$ chu kì 20 mod 5 ($L{n+10}=-L_n\mod 5, F_{n+10}=-F_n\mod 5$. $5|F_n$ khi và chỉ khi $5|n$
nếu $n>1$ $5|F_5|F_{5k}$. Vì thế $5|n$  $L_{2n}^2=4(-1)^n\mod 25$. Vì $10|n$ $L_{2n}=\pm 2\mod 25$.
$L_{2n}^2+(-1)^nL_{2n}-1=4+2-1=5\mod 25$. Vậy $v_5(F_{5n})=v_5(F_n)+1\to v_5(F_n)=v_5(n).$ (Đpcm)

Cách 2:



Dùng cách tính chất ở trên, nếu $a|b$ thì $F_a|F_b$ và , $(F_a,F_b)=F_{(a,b)}$.

Đặt $n=5^p \cdot q$ Với $(5,q)=1$. thì $v_5(n)=p$. thấy rằng $(F_{5^k \cdot m}, F_{5^k}) = F_{5^k}$ . Hiển nhiên $5^k|F_{5^k}$.và $5^{k+1}$ không là ước của ${F_{5^k \cdot m}}$ vì nó sẽ dẫn đến $5|m$ mâu thuẫn. Vậy $v_5(F_{5^k \cdot m})=k$ . Đpcm $\Box$




8) $F_n \vdots 5^k$ khi và chỉ khi $n \vdots k$
9) $F_n$ có tận cùng là 0 khi và chỉ khi $n \vdots 15$

10) $F_n$ có tận cùng là hai chữ số 0 khi và chỉ khi $n \vdots 150$

Chứng minh tồn tại số tự nhiên thỏa mãn yêu cầu bài toán

Bài toán:

Cho trước $ k\in \mathbb{Z}^+$ và $ m$ lẻ .

Chứng minh rằng tồn tại $ n\in \mathbb{Z}^+$ sao cho $ 2^k| n^n-m$

Lời giải:

Ta sẽ chứng minh quy nạp theo $ k$.

Trường hợp $ k=1$ là hiển nhiên, chọn $ n=1$.

Giả sử rằng tồn tại $ n$ sao cho $ 2^k|n^n-m$,Đặt $ n=n_0$ hay $ 2^k|n_0^{n_0}-m$ hiển nhiên $ n_0$ lẻ

Tiếp theo xét 2 trường hợp

$ 1)$ Nếu $ 2^{k+1} | n_0^{n_0}-m$

Rõ ràng chỉ cần chọn $ n=n_0$.

$ 2)$ Nếu $ 2^{k+1}$ Không là ước của $ n_0^{n_0}-m$.

Đặt $ n_0^{n_0}-m=u\cdot 2^k$ Với $ u$ lẻ và theo định lý Euler,Cho mọi số lẻ $ a$ ta có $ a^{2^{k}}\equiv 1\pmod{2^{k+1}}$,Vì thế

$ (2^k+n_0)^{2^k+n_0}-m=(2^k+n_0)^{2^k}\cdot (2^k+n_0)^{n_0}-m\equiv (2^k+n_0)^{n_0}-m\\\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\cdot 2^k-m=(u+n_0^{n_0})2^k\equiv 0\pmod{2^{k+1}}$ Vì cả $ u$ và $ n_0$ đều lẻ.

Vì thế $ n=2^k+n_0$ thỏa mãn, nên ta có đpcm

TÍNH CHẴN LẺ TRONG BÀI TOÁN TỔ HỢP

Tính chẵn lẻ là một trong các bất biến quan trọng nhất trong một số tình huống tổ hợp. Đó là một ý tưởng đơn giản nhưng vô cùng hiệu quả. Tính chẵn lẻ là việc xét đồng dư theo modulo 2, một cách phức tạp hơn ta có thể nghĩ đến một lớp đồng dư theo modulo là một số tự nhiên tùy ý như một bất biến trong một số bài toán.
 VD1: Có 2015 bánh răng được xếp trên một mặt phẳng kề nhau tạo thành một vòng kín. Hỏi các bánh răng có thể quay cùng lúc hay không?
Lời giải: Câu trả lời là không. Mấu chốt ở bài này là việc phát hiện ra hai bánh răng kề nhau luôn quay ngược nhau. Giả sử bánh răng thứ nhất quay theo chiều dương kéo theo bánh thứ hai quay chiều âm, bánh thứ ba quay chiều dương... Như vậy bánh có số thứ tự lẻ quay chiều dương còn bánh có thứ tự chẵn quay chiều âm. Do đó bánh số 1 và số thứ 2015 cùng quay chiều dương. Vô lý. Ý tưởng chính của bài toán trên là sự xen kẽ chiều quay của các bánh răng. Tìm đối tượng xen kẽ cũng là hướng đi đầu tiên của các bài toán sau.
VD2:Trong một bàn cờ vua , một quân mã bắt đầu đi từ vị trí a1 và trở lại đó sau một số bước đi. Chứng minh số bước đi vừa thực hiện là một số chẵn.
Lời giải: Vị trí ban đầu của con mã là màu đen. Sau bước đi thứ nhất nó đến ô màu trắng, sau bước thứ hai nó đến ô màu đen.... Như vậy sau lẻ bước nó đến ô trắng và sau chẵn bước nó đến ô đen. Suy ra đpcm.
 VD3: Một đường gấp khúc khép kín được tạo bởi 11 đoạn thẳng nằm trên một mặt phẳng. Tồn tại hay không một đường thẳng d không đi qua bất kỳ đầu mút nào của các đoạn thẳng trên và cắt tất cả 11 đoạn thẳng đó.
Lời giải:
Gọi $(P_1), (P_2)$ là hai nửa mặt phẳng có bờ là đt d. Kí hiệu đường gấp khúc trên là $A_1A_2A_3...A_{11}A_1$ . Giả sử $A_1$ thuộc $(P_1)$ thì $A_2$ thuộc $(P_2)$, $A_3$ thuộc $(P_1)$,...,$A_{11}$ thuộc $(P_1)$. Nhưng khi đó $A_1$ và $A_{11}$ cùng thuộc $(P_1)$ nên d không thể cắt đoạn $A_1A_{11 }$điều này trái với giả thiết nên không thể tồn tại đường thẳng d thỏa mãn.
VD4 Ba quả bóng hockey A, B, C nằm trên một sân chơi. Một người đánh một trong ba quả đó sao cho nó đi qua giữa hai quả còn lại. Anh ta làm thể 25 lần. Liệu anh ta có thể đưa ba quả bóng trở về vị trí ban đầu hay không?
Lời giải:

Giả sử ban đầu ba quả bóng được sắp thứ tự theo chiều dương. Sau mỗi lượt chơi thì thứ tự của chúng thay đổi từ dương sang âm và ngược lại. Do vậy sau lượt đánh thứ nhất thứ tự của chúng theo chiều âm, sau lượt thứ hai lại đổi thành chiều dương,...Sau 25 lượt thì thứ tự của 3 quả bóng đó là chiều âm, do đó anh ta không thể đưa chúng về vị trí ban đầu.
VD5: Có hay không một đường gấp khúc khép kín gồm 9 đoạn thẳng sao cho mỗi đoạn cắt duy nhất một trong các đoạn còn lại?
Lời giải:
Nếu tồn tại đường gấp khúc đó thì tập hợp các đoạn thẳng trên có thể chia thành từng cặp các đoạn thẳng giao nhau. Như vậy tổng số đoạn thẳng phải là số chẵn.
Nhận xét: Điểm mấu chốt của ví dụ trên là nếu một nhóm các đối tượng có thể chia thành từng cặp thì số các đối tượng là một số chẵn. Sau đây là một số ví dụ tương tự.
VD6: Có thể chia một đa giác lồi 13 cạnh thành các hình bình hành được không?
Lời giải:
Giả sử thực hiện được công việc trên. Khi đó cạnh A1A2 phải thuộc một hình bình hành A1PNM trong đó A1P thuộc A1A2. Tiếp đó tồn tại hình bình hành RSPQ trong đó P,Q thuộc MN... Quá trình này cứ tiếp tục đến khi tồn tại một hình bình hành có cạnh song song với A1 A2 và thuộc một cạnh AmAm+1 nào đó và cạnh Am Am+1 tương ứng với A1A2 là duy nhất. Như vậy các cạnh của đa giác được chia thành các cặp nên số cạnh phải là số chẵn . Vô lý. Tương tự ta giải quyết các bài toán sau nhờ kỹ thuật “ghép cặp”
VD7: 25 quân cờ được đặt trên bàn cờ 25x25 sao cho mỗi quân cờ đối xứng với một quân cờ khác qua một đường chéo. Chứng minh có ít nhất một quân cờ được đặt trên một đường chéo.
VD8: Cho một bảng 15x15 ta viết các số từ 1 đến 15 sao cho hai ô đối xứng với nhau qua một trong hai đường chéo chính thì chứa hai số bằng nhau và không có số nào trong cùng một hàng hoặc một cột bằng nhau. Chứng tỏ rằng không có hai số nào trên đường chéo chính bằng nhau.
VD9: Hình vuông “kỳ diệu” là một bảng vuông 6x6 với mỗi một con số ở mỗi ô sao cho tổng các số ở mỗi cột, mỗi hàng và hai đường chéo bằng nhau . Có thể lập ra một hình vuông “kỳ diệu” từ 36 số nguyên tố đầu tiên không?
Lời giải:
Không . Vì khi đó tổng các số thuộc hình vuông là một số chẵn trong khi đó tổng của 36 số nguyên tố đầu tiên lại là số lẻ.
VD10: Các số từ 1 đến 10 được viết trên bảng theo một hàng ngang theo một thứ tự bất kỳ. Liệu có thể chèn vào giữa tất cả hai số kề nhau một cách tùy ý dấu “+” hoặc dấu “-” sao cho kết quả cuối cùng nhận được là số 0 hay không?
Lời giải: Giả sử ban đầu các dấu gồm toàn dấu “+” sau đó ta thay một số dấu cộng bằng dấu trừ. Bất biến ở đây là tính chẵn lẻ của tổng 10 số đó không đổi. Nhưng tổng các số từ 1 đến 10 là số lẻ nên sau hữu hạn bước không thể đưa về tình huống đề bài yêu cầu.
VD11: Một con châu chấu nhảy trên một đường thẳng. Bước đầu tiên của nó dài 1 cm, bước thứ hai dài 2cm và cứ thế, mỗi bước nó có thể nhảy về bên trái hoặc bên phải. Hỏi sau 2015 bước nó có thể trở về vị trí ban đầu hay không ?
Câu trả lời là không.
VD 12: Trên bảng có các số 1;2;3;...;2013. Một học sinh xóa hai số bất kỳ và thay bằng giá trị tuyệt đối của hiệu hai số đó. Sau hữu hạn bước chỉ còn một số trên bảng. Số này có thể abừng 0 được không?
Lời giải: Ta có (a + b) - |a - b| là số chẵn với hai số tự nhiên a, b bất kỳ. Như vậy tổng cac số sau mỗi bước luôn cùng tính chẵn lẻ. Do đó số cuối cùng phải là số lẻ vì tổng các số ban đầu là lẻ.
VD 13:
Có 45 điểm cùng nằm trên một đường thẳng AB, tất cả đều nằm ngoài đoạn AB. Chứng minh tổng khoảng cách tổng các khoảng cách từ các điểm này tới A khác tổng các khoảng cách từ các điểm đó tới B.
Lời giải:
Nhận thấy hiệu hai tổng khoảng cách đó luôn bằng số lẻ lần độ dài đoạn thẳng AB nên ta có đpcm.

Bản chất của bất biến xét theo tính chẵn lẻ là xét theo modul 2. Ta có thể tổng quát khi thay 2 bởi một số tự nhiên khác.  
VD14: Cho 1000 số từ 1 đến một 1000 được viết theo một hàng ngang trên bảng. Mỗi lần ta thay một hoặc vài số trên bảng bởi tổng các chữ số của nó. Hỏi dãy số cuối cùng thu được có nhiều số 1 hơn hay nhiều số 2 hơn?

Lời giải:
Trong dãy số trên có 112 số chia 9 dư 1 và 111 số chia 9 dư 2. Vậy dãy số cuối cùng có số 1 nhiều hơn số 2.
Nhận xét:  Đại lượng bất biến ở đây là một số tự nhiên và tổng các chữ số của nó có cùng số dư trong phép chia cho 9
VD15: Mối bước cho phép chọn một số tự nhiên a và phân tích a thành tích hai số tự nhiên m, n sau đó viết lên bảng hai trong số bốn số m ± 2, n ± 2. Ban đầu ta có số a = 20152015...2015 (100 số 2015). Hỏi sau một số bước như vậy có thu được một dãy gồm toàn số 1 hay không?
Lời giải:
Vì a chia 4 dư 3 nên trong hai số m, n phải có một số chia 4 dư 1 và một số chia 4 dư 3.Mà số chia 4 dư 1 thì cộng 2 hay trừ đi 2 đều chia 4 dư 3. Do đó ở mỗi bước luôn có mặt số chia 4 dư 3, như vậy sau hữu hạn bước không thể ra kết quả như đề yêu cầu.
Nhận xét: Bài này ta để ý đến a là một số chia 4 dư 3 cũng như việc tồn tại các số như vậy trong dãy.
VD16:Trên bảng có hai số 1 và 2. Thực hiện việc ghi số theo nguyên tắc sau: Nếu trên bảng có hai số a, b thì được phép ghi thêm số c = a + b + ab. Hỏi bằng cách đó có thể xuất hiện các số 2013, 2014 và 2015 được không?
Lời giải:
Dãy các số được viết là: 1; 2; 5; 11; 17;... Dễ thấy các số viết thêm trong dãy trên đều chia 3 dư 2. Như vậy bất biến trên cho phép ta khẳng định số 2013 và 2014 không thể có mặt. Với số 2015 ta phải dùng bất biến khác.
Đem tăng thêm 1 cho mỗi số hạng ở dãy trên thì ta nhận được dãy: 2; 3; 6; 12; 18;... Ta chứng minh cho các số hạng của dãy đều có dạng 2m.3n nhưng số 2015 + 1 không có tính chất đó.
VD17: Có ba đống sỏi với số lượng tương ứng là 8; 9; 19 viên. Ta được phép chọn hai đống sỏi và chuyển một viên của mỗi đống đã chọn sang đống còn lại. Hỏi sau một số lần làm như vậy ta có thể thu được ba đống sỏi mỗi đống có đúng 12 viên không?
Lời giải:
Bất biến trong bài này là trong tất cả các trạng thái thì số dư của số sỏi trong mối đống trong phép chia cho 3 là một hoán vị của bộ {0;1;2}. Do đó không thể thưch hiện được.

Tương tự ta có bài sau:

VD18: Ngoài biển đông, trên một hòn đảo sinh sống ba giống thằn lằn có ba loại màu: màuxám có 133 con, màu nâu có 155 con và màu đỏ có 177 con. Nếu hai con thằn lằn khác màu gặp nhau thì chúng đồng thời đổi sang màu thứ ba (ví dụ nếu thằn lằn màu xám gặp thằn lằn màu nâu thì cả hai con đều đổi sang màu đỏ). Trong những trường hợp hai con thằn lằn cùng màu gặp nhau thì chúng giữ nguyên không đổi màu. Có xảy ra tình trạng là trên đảo tất cả thằn lằn cùng một màu được không?
VD19: A và B tiến hành trò chơi với 2014 hạt gạo. Một nước đi là lấy khỏi đống gạo đó 1;2 hoặc 3 hạt. A đi trước và thay phiên nhau. Người nào lấy được hạt gạo sau cùng sẽ là người chiến thắng. Ai là người có thể luôn chiến thắng và chiến thuật ra sao?
Lời giải:
A sẽ là người luôn chiến thắng nếu chới theo chiến thuật sau: Bước 1: A lấy 2 hạt gạo. Bước 2: B lấy x hạt (x = 1;2;3) 7 Bước 3: A lấy 4 – x hạt Cứ tiếp tục như vậy....Ta thấy sau mối lần A lấy thì số gạo còn lại luôn là bội của 4. Ở bước áp chót số gạo còn lại là 4 hạt thì dù B có chọn cách chơi nào thì A cũng là người thắng cuộc.  
VD20: Có một tờ giấy được cắt thành 6 mảnh hoặc 11 mảnh. Sau đó mỗi mảnh bất kỳ trong số đó lại được cắt thành 6 hoặc 11 mảnh nhỏ hơn. Hỏi có thể tạo thành 2015 mảnh không?
Lời giải:
Sau mỗi lần cắt một mảnh giấy thành 6 mảnh hoặc 11 mảnh thì số mảnh giấy tăng lên là 5 hoặc 10. Như vậy tính bất biến của bài toán là “số mảnh giấy luôn tăng lên một bội số của 5”. Vậy số mảnh giấy sau các lần cắt có dạng 1 + 5k, mặt khác 2005 có dạng 5k nên với cách cắt như trên, từ một tờ giấy ban đầu, ta không thể cắt được thành 2005 mảnh. Nhận xét. Bất biến của bài toán là số mảnh giấy tăng lên luôn là một bội số của 5.
VD21: Trên bảng, người ta viết các số tự nhiên liên tiếp từ 1 đến 100 sau đó thực hiện trò chơi như sau: mỗi lần xóa hai số bất kỳ và viết một số mới bằng tổng lập phương của hai số đã cho. Việc làm này thực hiện liên tục cho đến khi còn một số trên bảng. Hỏi số cuối cùng còn lại trên bảng có thể là $987654321^n$ (n là số tự nhiên lớn hơn 1) hay không? Tại sao?
Lời giải:
Để ý rằng : $(a^3 + b^3 ) – (a + b) = (a^3 - a) + (b^3 - b )$ luôn chia hết cho 3 với mọi cặp số tự nhiên a, b. Do đó sau mỗi lần chơi tổng các số ban đầu thay đổi một lượng là bội của 3. Vì tổng các số từ 1 đến 100 chia cho 3 dư 1 nên ở trạng thái kết thúc ta cũng phải thu được số chia 3 dư 1, nhưng số đề cho lại là số chia hết cho 3.
Ta cùng luyện tập thêm một số bài cùng chủ đề sau:
Bài 1: Một con ốc sên bò trên một mặt phẳng với vận tốc không đổi. Sau mỗi 15 phút thì nó lại rẽ theo một góc vuông. Chứng minh ốc sên có thể quay lại điểm xuất phát sau một số nguyên lần.
Lời giải:
hi con ốc sên quay trở lại vị trí xuất phát thì nó đã đi được một đường gấp khúc khép kín. Kí hiệu: $\overrightarrow{a},\overrightarrow{-a},\overrightarrow{b},\overrightarrow{-b}$
chỉ các hướng đi lên, đi xuống, sang trái, sang phải của ốc sên. Gọi m, n, p,q là số lần đi lên , xuống, sang trái, sang phải. Ta cần chứng minh (m + n + p + q) là bội của 4.
Từ  $m\overrightarrow{a}+n \overrightarrow{-a}+p \overrightarrow{b}+q\overrightarrow{-b}=0$ mà hai véc to a,b khác phương  nên suy ra m = n và p = q. Do cứ sau 15 phút ốc sên lại rẽ sang góc $90^o$ nên m + n = p + q. Từ đó ta được đpcm
Bài 2: Ba con châu chấu chơi trò nhảy cóc trên một đường thẳng. Cứ mỗi nước đi một con châu chấu nhảy qua một con khác nhưng không nhảy qua hai con. Chúng có thể trở về vị trí ban đầu sau 2n + 1 bước không?
Lời giải:
Sau mỗi lần nhảy thì luôn có một con giữ nguyên vị trí. Sau số chẵn lần nhảy thì có 0 hoặc 3 con cùng đúng vị trí ban đầu. Nhưng 2n + 1 là số lẻ lần không thể thực hiện được.
Bài 3: Một số tự nhiên gồm 17 chữ số. Một học sinh đảo ngược thứ tự các chữ số của số đó rồi đem cộng với số ban đầu. Chứng minh tổng tạo thành có ít nhất một chữ số chẵn.
 Giải:
Gọi số đó là:
$A=\overline{a_1a_2..a_{17}}, B=\overline{a_{17}..a_1a_2}, C=A+B$
Đặt: $x_i=a_i+a_{18-i}$. Xét dãy:
$x_1x_2..x_8x_9x_8x_7..x_1$
Giả sử các chữ số của C gồm toàn số lẻ.Cộng theo hàng dọc ta thấy: x9 chẵn nên x8 phải nhớ 1 sang suy ra: x7 chẵn, x6 nhớ 1 sang, x5 chẵn,..., x1 chẵn. Do đó chữ số đơn vị của C là chẵn. Mâu thuẫn.
Bài 4: Có 100 người lính trong một doanh trại. Mỗi tối 3 người trong số họ có ca trực. Hỏi có thể xảy ra tình huống sau một khoảng thời gian nào đó mỗi người đều trực với tất cả những người còn lại đúng một lần hay không?
Lời giải: Giả sử có thể xảy ra tình huống trên. Xét một người lính A nào đó, từ gt suy ra số người còn lại sẽ được phân hoạch thành các cặp trực cùng A. Nhưng khi đó suy ra tổng số lính của doanh trại phải là số lẻ. Vô lý.
Bài 5: Có 9 số được đặt trên một vòng tròn gồm 4 số 1 và 5 số 0. Mỗi hành động sau được coi là một bước: Ta thêm số 0 vào giữa hai số cạnh nhau nếu hai số đó khác nhau, trường hợp ngược lại ta thêm số 1. Hai số cũ sau đó bị xóa. Hỏi sau một số bước đi các số còn lại có thể bằng nhau được hay không?
Bài 6: Có 25 bạn nam và 25 bạn nữ ngồi quanh một bàn tròn. Chứng minh tồn tại một bạn có cả hai “hàng xóm” là nam. (Tương tự có một bạn có hai hàng xóm đều là nữ).
Lời giải
Kí hiệu 25 bạn nam là N1, N2, ..., N25. Gọi x1, x2,..., x25 là số bạn nữ ngồi giữa hai bạn nam (Ni, Ni+1) với N1 = N26. Ta có: x1+ x2+...+ x25 = 25. (1) Nếu tồn tại xi = 1 thì bài toán được chứng minh. Trường hợp ngược lại: Từ (1) có ít nhất 13 số xi bằng 0. Nếu x1 = x25 = 0 thì N25 chính là người cần tìm. Nếu x1, x25 không đồng thời bằng 0 thì theo nguyên lý Diricle sẽ có một cặp xj = xj+1 = 0 khi đó Nj+1 là người cần tìm.
Bài 7: Hai người chơi cờ. Sau mỗi ván người thắng được 2 điểm, người thua được 0 điểm, nếu hòa thì mỗi người được 1 điểm. Hỏi sau một số ván cờ liệu có 10 xảy ra tình huống một người được 10 điểm, một người được 13 điểm hay không?
Lời giải:
Câu trả lời ở đây là không. Bất biến là tính chẵn lẻ của tổng số điểm của hai người chơi là không đổi.
Bài 8: Trên mặt bàn có 2017 viên bi gồm 667 viên xanh, 669 viên đỏ và 671 viên vàng. Thực hiện thuật toán như sau: Mỗi lần lấy đi hai viên bi khác màu và đặt thêm hai viên bi có màu còn lại. Hỏi có nhận được trạng thái tất cả các viên bi trên bàn có cùng một màu được không?
Lời giải:
Kí hiệu X(n), Đ(n), V(n) tương ứng với số bi màu xanh, đỏ, vàng sau bước đi thứ n. Như vậy X(0) = 667, Đ(0) = 669 , V(0) = 671. Từ thuật toán đề ra ta thấy bất biến ở đây là số dư của các hiệu X(n) – Đ(n), Đ(n) – V(n), V(n) – X(n) không đổi trong phép chia cho 3. Xuất phát từ trạng thái ban đầu ta có các số dư này là 1;2;1. Nhưng ở trạng thái kết thức số bi của ba loại trên là một hoán vị của {0;0;2007} nên không thể thực hiện được.
Bài 9 Trong dãy 1, 9, 9, 9, 8, . . . , mỗi chữ số bắt đầu từ chữ số thứ năm bằng chữ số hàng đơn vị của tổng bốn chữ số liền trước nó. Hỏi trong dãy này có gặp các bộ 1234 và 5678 không?
Lời giải:
Ta thay mỗi chữ số của dãy đã cho bằng số 0 nếu nó là số chẵn và bằng số 1 nếu nó là số lẻ. Ta nhận được dãy số 111101111011110..., trong đó cứ sau bốn chữ số 1 có một chữ số 0 và cứ sau mỗi số 0 có bốn chữ số 1. Các bộ số 1234 và 5678 ứng với các bộ 4 chữ số 1010 và 1001 nên không thể có mặt trong dãy số đã cho.

Tài liệu tham khảo
 1) Mathematical – Circles – Russian Experience
 2) Giải toán bằng đại lượng bất biến – Nguyễn Hữu Điển
 3) Một số chuyên đề trên mạng

Dùng cấp để tìm các số thỏa mãn bài toán

Đề bài: Tìm $p,q$ nguyên tố sao cho $2^{p}+2^{q}\vdots (pq).$

Lời giải:

Dễ thấy $(p,q)=(2,2),(3,2),(2,3)$.

Nếu $p,q \ge 3$. Dùng định lý Fermat nhỏ, ta có $2^{p} \equiv 2 \pmod{p}$. Vì thế $p|2^{q-1}+1$. Ta được $2^{q-1} \equiv -1 \pmod{p}$.

Đặt $q-1=2^x \cdot y$ với $x,y \in \mathbb{N}^*, \; \gcd(y,2)=1$ và đặt $2^y=k$, ta được $2^{q-1}=(2^y)^{2^x} \equiv -1 \pmod{p} \Rightarrow k^{2^{x+1}} \equiv 1 \pmod{p}$.

Ta có $\text{ord}_p(k) |2^{x+1}$.

Vì $k^{2^x} \equiv -1 \pmod{p}$ nên $p \nmid k^{2^x}$. Vì thế $\text{ord}_p(k) \nmid 2^x$. 

Vậy $\text{ord}_p(k)=2^{x+1}$. 

Ta cũng có $2^{p-1} \equiv 1 \pmod{p}$. Nên $2^{x+1}|p-1$. Đặt $p=2^{u} \cdot l+1$ với $u,l \in \mathbb{N}^*, \; \gcd (l,2)=1$ thì $u \ge x+1$.

Tương tự ta cũng được $x \ge u+1$, mâu thuẫn

Vậy câu trả lời là $\boxed{ (x,y)=(2,2),(3,2),(2,3) $

Bài tập tương tự: Tìm $p,q$ nguyên tố sao cho $5^p+5^q \vdots pq$ ( lưu ý là phải xét thêm $p,q =2$)

Một số hàm số học và ứng dụng

I) Hàm phần nguyên:

1) Định nghĩa

Phần nguyên của một số thực x là số nguyên lớn nhất không vượt quá x. Kí hiệu là [x].

2) Tính chất:

a) nếu x>y thì [x] $\ge$ [y]

b) [n+x]=n+[x] (với n nguyên)

c) [x+y] $\ge $ [x]+[y]

d)[2x]+[2y] $ \ge $ [x]+[y]+[x+y]

e) [([x]/d)]=[x/d]

f) Cho x là một số thực dương và d là một số nguyên dương. Khi đó các số nguyên dương là bội của d không vượt qua x là [x/d].

Từ đây ta có định lý:

Trong phân tích tiêu chuẩn của: $n!=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ số mũ $a_i$ của $p_i$ được tính theo công thức:

$a_i=\left [ \frac{n}{p_i} \right ]+\left [ \frac{n}{p_i^2} \right ]+\left [ \frac{n}{p_i^3} \right ]...$

3) Ứng dụng:

Bài 1: Chứng minh rằng với mọi số nguyên dương m,n ta có (2m)!(2n)! chia hết cho m!n!(m+n)!.

Lời giải:

Gọi p là một số nguyên tố bất kì. Theo định lí thì số mũ của p trong phân tích tiêu chuẩn của m!n!(m+n)! là:

$a=\sum_{k=1}^{\infty }\left [ \frac{m}{p^k} \right ]+\left [ \frac{n}{p^k} \right ]+\left [ \frac{m+n}{p^k} \right ]$

số mũ của p trong phân tích tiêu chuẩn của (2m)!(2n)! là:

$b=\sum_{k=1}^{\infty }\left [ \frac{2m}{p^k} \right ]+\left [ \frac{2n}{p^k} \right ]$

Theo tính chất d) ta có:

$\left [ \frac{m}{p^k} \right ]+\left [ \frac{n}{p^k} \right ]+\left [ \frac{m+n}{p^k} \right ] \le \left [ \frac{2m}{p^k} \right ]+\left [ \frac{2n}{p^k} \right ]$

Từ đó $b \ge a$. Vậy ta có đpcm.

Bài 2:

Cho số nguyên dương $a, n$ sao cho tất cả các ước nguyên tố của $a$ đều lớn hơn $n.$ Chứng minh rằng $(a-1)(a^{2}-1)...(a^{n-1}-1)$ chia hết cho $n!.$

Cách 1:

Gọi $p$ là 1 ước nguyên tố của $n$.

Có $a^{p-1}\equiv 1(modp)$ nên $V_{p}(VT)\geq V_{p}(\prod_{i=1}^{[\frac{n}{p-1}]}(a^{(p-1)i}-1))\geq [\frac{n}{p-1}] \\ V_{p}(n!)=[n/p]+[n/p^{2}]+...[n/p^{s}]\leq n/p+n/p^{2}+...+n/p^{s}=\frac{n-n/p^{s}}{p-1}\leq [\frac{n}{p-1}] \\ --> Q.E.D.\blacksquare$

Cách 2
Bổ đề : Cho $p$ là một số nguyên tố và $n$ là số nguyên dương . Kí hiệu $s_p(n)$ là tổng các chữ số của $n$ viết trong hệ cơ số $p$
Khi đó $v_p(n!)=\frac{n-s_p(n)}{p-1}$
Chứng minh bổ đề : Đặt $n=a_kp^k+a_{k-1}p^{k-1}+..+a_1p+a_0,a_i \in \{1,2,..,p-1\},i=\overline{1,k}$
Theo định lí Legendre : $v_p(n!)=\sum_{i=0}^k [\frac{n}{p_i}]=a_k\frac{p^k-1}{p-1}+a_{k-1}\frac{p^{k-1}-1}{p-1}+a_1$
$=\frac{(a_kp^k+a_{k-1}p^{k-1}+..+a_0)-(a_k+a_{k-1}+..+a_0}{p-1}=\frac{n-s_p(n)}{p-1}$ (đpcm)
Đi vào bài toán
Vì tất cả các ước nguyên tố của $a$ đều lớn hơn $n$ nên $(a,n)=1$ . Giả sử $p$ là ước nguyên tố của $n!$ thì ta có $(a,p)=1$.
Theo định lí Fermat ta có $a^{k(p-1)} \equiv 1 \pmod{p},k \ge 1$ . Mặt khác ta có $v_p(n!)=\frac{n-s_p(n)}{p-1} \le [\frac{n-1}{p-1}]$
Ta có
$v_p(\prod_{k=1}^{n-1}(a^k-1))=\sum_{k=1}^{n-1}v_p(a^k-1) \ge \sum_{k=1}^{k(n-1) \le n} v_p(a^{k(p-1)}-1) \ge [\frac{n}{p-1}] \ge [\frac{n-1}{p-1}] \ge v_p(n!)$
Vậy $n!|\prod_{k=1}^{n-1}(a^k-1)$

II) Hàm số các ước của một số tự nhiên.

1) Định nghĩa: Cho số nguyên dương n. Kí hiệu d(n) là số các ước của n

2) Định lí:

a) Giả sử $n=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ là phân tích tiêu chuẩn của n>1.

Khi đó $d(n)=(a_1+1)(a_2+1)..(a_k+1)$

b) Với mọi n ta có bất đẳng thức $d(n) < 2 \sqrt{n}$

III) Hàm tổng các ước

1) Định nghĩa: Cho số nguyên dương n. Ta kí hiệu $\sigma (n)$ là tổng các ước của n.

2) Định lí:

a) Hàm số $\sigma (n)$ có tính chất nhân tính. Nghĩa là nếu a,b là hai số nguyên tố cùng nhau thì:

$\sigma (ab)=\sigma (a).\sigma (b)$

b) Giả sử $n=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ là phân tích tiêu chuẩn của n>1. Khi đó:

$\sigma (n)=\left (\frac{p_1^{a_1+1}-1}{p_1-1}  \right )\left (\frac{p_2^{a_2+1}-1}{p_2-1}  \right )..\left (\frac{p_k^{a_k+1}-1}{p_k-1}  \right )$

c) n là số nguyên tố khi và chỉ khi $\sigma (n)=n+1$.

d) $\sigma (n)$ là một số lẻ nếu và chỉ nếu n là số chính phương hoặc $\frac{n}{2}$ là số chính phương.

Liên quan đến hàm $\sigma (n)$ ta có số hoàn chỉnh.

Định lý về số hoàn chỉnh:

e) Nếu k là số tự nhiên sao cho $2^k-1$ là một số nguyên tốt thì số $n=2^{k-1}(2^k-1)$ là một số hoàn chỉnh.

f)Nếu n là một số hoàn chỉnh chẵn thì n có dạng:

$n=2^k.(2^{k+1}-1)$

IV) Hàm số Euler:

1) Định nghĩa: 

Cho số tự nhiên $n \ge 1$. ta kí hiệu $\varphi (n)$ là  số các số tự nhiên bé hơn n và nguyên tố cùng nhau với n.

2) Định lý:

Hàm $\varphi (n)$ có tính chất nhân tính theo nghĩa: Nếu a,b là hai số nguyên tố cùng nhau thì:

$\varphi (ab)=\varphi (a)\varphi (b)$

Chú ý rằng những định lý và các khái niệm đều được dùng thẳng trong kì thi VMO ( Theo công văn số 1447/ KTKĐCLGD-KT ngày 27/10/2015). Một điều lạ là kì thi VMO 2016 cho chứng minh định lí e) và f).

Chứng minh tồn tại vô hạn trong số học

Đề bài: Cho m là một số nguyên dương. Chứng minh rằng tồn tại vô số nguyên dương n sao cho $m|3.2^n+n$

Lời giải:

Ta sẽ chứng minh quy nạp theo $m$, rõ ràng $m=1,2,3,4$ là hiển nhiên
Giả sử khẳng định đúng với mọi $m\leq t$ với số nguyên $t>3$
Đặt $d=ord_{t+1}{2}$ và $e=gcd(d,t+1)$, rõ ràng $e\leq d \leq \phi (t+1) \leq t$
Theo nguyên lí quy nạp phải tồn tại vô hạn số nguyên $a$ sao cho $e\mid 3\times 2^a+a$
Đặt $3\times 2^a+a=ef$ ( $f\in \mathbb{Z}^+$ )
Với mọi $g\in \mathbb{Z}^+$ Ta có $3\times 2^{a+dg}+(a+dg) \equiv 3  \times 2^a+a+dg =ef+dg (mod t+1)$
Ta cần chứng minh rằng tồn tại $g\in \mathbb{Z}^+$ sao cho $ef+dg\equiv 0 (mod t+1)$
Tương đương với $gcd(d,t+1) \mid -ef\Leftrightarrow e\mid -ef$ (luôn đúng) 9 (điều kiện cần và đủ của phương trình đồng dư)
vậy ta đã chứng minh tồn tại $n_1=a+dg\in \mathbb{Z}^+$ sao cho $t+1 \mid 3\times 2^{n_1}+{n_1}$
Nhưng vì tồn tại vô số nguyên dương a $a$, ta lấy $a$ lớn hơn $n_1$ ta lại có một số nguyên dương khác thỏa mãn đề bài,
Điều này có nghĩa là tồn tại vô số $n\in \mathbb{Z}^+$ sao cho $t+1\mid 3\times 2^n+n$ Điều phải chứng minh.

Hai bài toán trên tạp chí toán học về tuổi trẻ

Bổ đề bất đẳng thức số học và đề USA MO 1995

Ta có một bổ đề bất đẳng thức số học dùng để đánh giá bội chung nhỏ nhất như sau:
Với mọi số nguyên dương n tồn tại một số $c_n >0$ sao cho:

$lcm(m,m+1,m+2,..m+n)>c_nm(m+1)(m+2)..(m+n)$ (ký hiệu lcm, gcd lần lượt là bội chung nhỏ nhỏ và ước chung lớn nhất)

Chứng minh:

Ta có:

$lcm(m,m+1,m+2,..m+n)=lcm(lcm(m,m+1,..m+n-1),m+n)\\=\frac{lcm(m,m+1,..m+n-1)(m+n)}{gcd(lcm(m,m+1,..m+n-1),m+n)} \\ \ge \frac{lcm(m,m+1,..m+n-1)(m+n)}{gcd(m(m+1)(m+2)..(m+n-1),m+n)}\\ \geq \frac{lcm(m,m+1,..m+n-1)(m+n)}{n!}$

Bằng quy nạp ta chứng minh được:
$lcm(m,m+1,m+2,..m+n)\ge\frac{m(m+1)(m+2)..(m+n)}{n!(n-1)!..1!}$

Như vậy bổ đề được chứng minh.
Ta xét bài toán sau:

(USA MO 1995) Cho dãy số nguyên $(a_n)_{n \ge 0}$ thỏa mãn điều kiện sau:

i) $m-n | a_m -a_n$

ii) tồn tại đa thức f(x) sao cho |a_n| \le $f(n)$ với mọi $n \ge 0$

Chứng minh rằng tồn tại đa thức g(n) sao cho $g(n)=a_n$ với mọi $n \ge 0$

Lời giải:



Giả sử $P$ có bậc $d$. Đặt $Q$ là đa thức bậc cao nhất $d$ với $Q(x)=q_x$ cho $0\leq x\leq d$. Vì $q_x$ là những số nguyên, $Q$ là đa thức hệ số hữu tỉ và tồn tại $k$ để $kQ$ có hệ số nguyên. Vì thế $m-n|kQ(m)-kQ(n)$ với mọi $m,n\in \mathbb N_0$.




Ta sẽ chứng minh rằng $Q$ là đa thức cần tìm


Cho $x>n$ Ta có

$ kq_x \equiv kq_m\pmod{x-m}\text{với mọi }m\in[0,d]$

Vì $kQ(x)$ thỏa mãn điều kiện nên $kq_m=kQ(m)$,

$kq_x\equiv kQ(x)\pmod{x-m}\text{ với mọi }m\in [0,d] $
( lưu ý kQ(x) -kQ(m) chia hết x-m)
và vì thế

$ kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1) $

Vì $P(x), Q(x)$ có bậc là $d$, Vì thế với $x$ đủ lớn ( $x>L$) Ta có $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. Vì (1) $kq_x$ phải lớn hơn một bội của $\text{lcm}(x,x-1,\ldots, x-d)$ so với $kQ(x)$; vì thế $q_x$ phải lớn hơn một bội của $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ với $Q(x)$, với $x>L$ Ta phải có $q_x=Q(x)$.




Bây giờ với mọi $y$ ta có $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ với $x>L$. Vì $x-y$ có thể lớn tùy ý nên ta phải có $Q(y)=q_y$, đpcm

Thặng dư bình phương và các tính chất

Định nghĩa 1: Một số nguyên a được gọi là thặng dư bình phương mod n nếu tồn tại số nguyên x sao cho

$x^2 \equiv a (mod n)$
Ta cũng có thể gọi a là số chính phương mod p
Định nghĩa 2: Giả sử p là một số nguyên tố lẻ, a là một số nguyên, Kí hiệu Legendre $\left ( \frac{a}{p} \right )$được xác định như sau:

$\left ( \frac{a}{p} \right )=1$ Khi (a,p)=1 và a là thặng dư bình phương mod p

$\left ( \frac{a}{p} \right )=-1$ Khi (a,p)=1 và a không là số chính phương mod p

$\left ( \frac{a}{p} \right )=0$ nếu $a \vdots p$

Định lý:
1) (Tiêu chuẩn Euler) Cho p là một số nguyên tố và a là một số nguyên. Khi đó ta có $a^{\frac{p-1}{2}}\equiv \left ( \frac{a}{p} \right ) (mod p)$

Chứng minh:

Gọi g là một căn nguyên thủy của p (có nghĩa là g là một số nguyên sao cho p-1 là số mũ lớn nhất để $g^{p-1} \equiv 1 (mod p)$ Khi đó ta được hệ thặng dư thu gọn mod p {$1,g,g^2,..g^{p-2}$}.

Giả sử $a=g^i$ Ta cần chứng minh:

$a^{\frac{p-1}{2}} \equiv (g^i)^{\frac{p-1}{2}} \Rightarrow i.\frac{p-1}{2}\equiv 0 (mod p-1)$

$\Rightarrow$ i là số chẵn

Suy ra tồn tại j sao cho i=2j $\Rightarrow a=(g^j)^2 \Rightarrow \left ( \frac{a}{p} \right )=1 $

Ngược lại  $\left ( \frac{a}{p} \right )=1 \Rightarrow $ tồn tại j sao cho $a \equiv (g^j)^2 (mod p) \Rightarrow g^i\equiv (g^j)^2 (mod p) \Rightarrow i \equiv 2j(mod p-1) \Rightarrow i\equiv 0(mod 2) $

Do đó $a^{\frac{p-1}{2}}\equiv (g^i)^{\frac{p-1}{2}}=g^{(p-1)k}\equiv 1 (mod p)$

Bài tập áp dụng:
Cho $f_n$ là số Fermat chứng minh rằng ước nguyên tố p của $f_n$ có dạng $p=s.2^{n+2}+1$ với s là số tự nhiên.

Giải
Gọi $m=ord_2(p)$ suy ra m có dang $2^k$ rõ ràng k không thể $\le n$
Vậy $k=n+1$, áp dụng định lý Fermat bé ta có $p=h.2^{n+1}+1$

Ta xét $p=8t+1$ khi đó theo tiêu chuẩn euler thì 2 là số chính phương mod p.

Suy ra $2^{n+1} | (p-1)/2$ suy ra điều phải chứng minh
Định lí 2: Luật tương hỗ Gauss;


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

Chứng minh

Đặt A={a|(a,pq)=1,$1 \le a \le \frac{pq-1}{2}$}, $B=\prod_{x \in A}x$

Còn tiếp ...

Số Fermat và các tính chất

Các số tự nhiên có dạng $f_n=2^{2^n} +1$ được gọi là số Fermat

Ta có $f_0=1$

$f_1=5$

$f_2=17$

$f_3=257$

$f_4=65537$

$f_5=4294967295=641.6700417$

Như vậy ta có các tính chất sau:

i) $f_n=f_0.f_1..f_{n-1}+2$

ii) $(f_k,f_h)=1$

iii) $f_n$ tận cùng là 7 với n>1

i) ta có: $f_k=(2^{2^{k-1}})^2+1=(f_{k-1}-1)^2+1=f_{k-1}^2-2f_{k-1}+2$

Suy ra $f_n-2=f_0f_1..(f_0-2)=f_0.f_1...f_{n-1}$

ii) Suy ra từ i)

iii) Ta có $f_1=5$, các $f_n$ đều lẻ nên $f_n \equiv 5+2=7 (mod 10)$

Bài toán về sự phân bố số chính phương và số nguyên tố

Bài toán: Xét tất cả các số nguyên tố $p_1 < p_2 <..p_n<..$ Đặt $a_n=p_1+p_2+..+p_n$. Chứng minh rằng với mọi n nguyên dương, nằm giữa $a_n$ và $a_{n+1}$ có ít nhất một số chính phương.

Giải:
Bổ đề: Với $n \ge 4$ thì $p_{n+1} > 2\sqrt{p_1+p_2+..+p_n}+1$
Chứng minh:
Với n=4, đúng.

Giả sử đúng với n=k tức là:
$p_{k+1} > 2\sqrt{p_1+p_2+..+p_k}+1$

Hay là $(p_{k+1}-1)^2 >4 (p_1+p_2+..+p_k)$

Ta cần chứng minh: $(p_{k+2}-1)^2 >4 (p_1+p_2+..+p_{k+1})$

Hay chỉ cần chứng minh: $(p_{k+2}-1)^2 \ge (p_{k+1}-1)^2 +4p_{k+1}$

Điều này tương đương $(p_{k+2}-p_{k+1})(p_{k+2}+p_{k+1}-2) \ge 4p_{k+1}$

Điều này là hiển do khoảng cách 2 số nguyên tố liên tiếp bé nhất là 2. Vậy ta có đpcm

Quay lại bài toán
Với n=1, thì giữa 2 và 5 tồn tại 4 là số chính phương.
Tương tự cho n=2,3,4

Giả sử đúng với n=k tức là giữa $a_k$ và $a_{k-1}$ tồn tại ít nhất một số chính phương, ta gọi $a^2$ là số chính phương lớn nhất trong các số chính phương đó.

$(a+1)^2 > a_{k}$

Áp dụng bổ đề thì $p_{k+1}>2a+1$ nên $a_{k+1} >(a+1)^2$.

Câu dãy số số học trong IMO và phương pháp suy luận

Đề bài: (IMO 18th) Cho dãy $(u_n)$ xác định như sau: $u_o=2$, $u_1=\frac{5}{2}$ và

$u_{n+1}=u_n(u_{n-1}^2-2)-u_1$

Chứng minh rằng $[u_n]=2^{\frac{2^n-(-1)^n}{3}}$

Lời giải:

Do đề bài yêu cầu chứng minh $[u_n]=2^{\frac{2^n-(-1)^n}{3}}$

Nên ta sẽ cố gắng biểu diễn $u_n$ dưới dang $2^x+a$

Bắt đầu với $u_1$

$u_1=\frac{5}{2}=2+\frac{1}{2}$

$u_2=(2+\frac{1}{2})(2^2-2)-(2+\frac{1}{2})=2+\frac{1}{2}$

$u_3=(2+\frac{1}{2})[(2+\frac{1}{2})^2-2]-(2+\frac{1}{2})$

Ta có thể đoán trước được $u_3=2^3+a (a<1)$ do thay 3 vào điều kiện đề bài

Nên ta tìm cách lấy số $2^3$ ra khỏi $u_3$, ta được:

$u_3=2^3+\frac{1}{2^3}$

Tương tự $u_4=2^5+\frac{1}{2^5}$

Bây giờ ta sẽ chứng minh: $u_n=2^{a_n}+\frac{1}{2^{a_n}}$

Do bài toán cần chứng minh $[u_n]=2^{\frac{2^n-(-1)^n}{3}}$  ta sẽ chứng minh:

Với $a_n=\frac{2^n-(-1)^n}{3}$ đây là công thức tổng quát của $a_n$ tuyến tính bậc 2 nên ta viết lại $a_{n+1}=a_n+2a_{n-1}$

Dễ thấy mệnh đề đúng với n=1,2,3,4,5.

Với n+1 thì:

$u_{n+1}=(2^{a_n}+2^{-a_{n}})(2^{a_{n-1}}+2^{-a_{n-1}-2}-(2+\frac{1}{2})$

Nhân ra ta được:

$u_{n+1}=2^{a_n+2a_{n-1}}+2^{-a_{n}-2a_{n-1}}+2^{2a_{n-1}-a_n}+2^{a_n-2a_{n-1}}-2-2^{-1}$

Mặt khác  Do: $a_{n+1}=a_n+2a_{n-1} \Rightarrow 2a_{n-1}-a_n=(-1)^n$

Thay vào ta có đpcm.

Dùng bước nhảy Vi-et để giải bài toán chia hết

Đề bài: Chứng minh rằng nếu a,b là 2 số nguyên dương thỏa mãn $4ab-1$ là ước của $(a+b-1)(a+b+1) $thì $a=b$

Lời giải:

$4ab-1 \mid (a+b-1)(a+b+1) \iff 4ab-1\mid (a-b)^2+(4ab-1)$

Đến đây ta suy ra: $k_0=\frac{(a-b)^2}{4ab-1} \in Z$

Đến đây hướng giải bằng bước nhảy vi-et xuất hiện, ta tìm cách loại bỏ số hạng ab ở tử.

$k=2k_0+1=\frac{2(a^2+b^2)-1}{4ab-1}$

Với k=1 thì $k_o=0$ kéo theo $a=b$

Tiếp tục phần $k>1$

Phương trình $ \iff 2a^2-4kba+2b^2-k=0$ (1)

Ta giả sử $a+b$ nhỏ nhất và $a > b$ (Vì nếu $a=b$ thì $k=1$)

Và theo Vi-et thì, tồn tại t sao cho:
$\left\{\begin{matrix}t+a=2kb\\ ta=b^2-\frac{k}{2}\end{matrix}\right.$

$ \Rightarrow a+b \le b+t \Rightarrow t \ge a > b$
$ \Rightarrow 2kb=t+a \le 2t \Rightarrow 2kab \le 2at$

Mà do (1) thì $2kab=a^2+b^2-\frac{k}{2}$ và $2at=2b^2-\frac{k}{2}$

Từ đây suy ra $b \ge a$ Vô lí
Vậy ta có đpcm.

Chứng minh tồn tại vô số số $n$ thỏa mãn: $n^2+2^n$ chia hết cho 1994

Lời giải:

Để $n^2+2^n$ chia hết cho 1994 thì trước hết n phải chẵn.

Ta chỉ cần chứng minh tồn tại số n sao cho $n^2+2^n$ chia hết cho 997.

Mà theo tiêu chuẩn Euler thì ta có:

$\left ( \frac{-1}{997} \right )=(-1)^{\frac{997-1}{2}}=1 (mod 997)$

Nên 997 có một bội dạng $a^2+1$. Do (996,997)=1 nên tồn tại hệ thặng dư thư gọn có dạng {996.1;996.2,...;996.996} mod 7

Suy ra tồn tại t để $(996t)^2+1$ chia hết  997

Mặt khác $2^{996t} \equiv 1 (mod 997)$

Vậy tồn tại vô số số n sao cho $n^2+2^n \vdots 1994$ 

Trường hợp nhỏ của định lý nổi tiếng của Erdos và Selfridge

Một định lý nổi tiếng của Erdos và Selfridge, một giả thuyết hơn 150 năm, nói rằng: Tích các số tự nhiên liên tiếp không thể là lũy thừa của một số nguyên.

Ta xét trường hợp tích 3 số tự nhiên liên tiếp.

Gọi n là số nguyên, và ta viết bài toán lại:

$n(n+1)(n+2)=x^z(x,z \in N, z \ge 2)$

Chú ý rằng: $n(n+2)=(n+1)^2-1$

Nên:

$\left\{\begin{matrix}
n+1=a^z & \\
(n+1)^2-1=b^z &
\end{matrix}\right.(a,b)=1\Rightarrow a^{2z}-b^z=1\Rightarrow (a^2-b)(..)=1\Rightarrow a^2=b+1\\\Rightarrow (b+1)^z-b^z=1 \Rightarrow z=1$

Vậy không tồn tại z thỏa mãn đề bài hay ta đã cm cho trường hợp $n=3$

Dùng bước nhảy Vi-et để giải bài toán

Bài toán : Cho các số nguyên dương  thỏa mãn hệ thức  . Chứng minh rằng  là lũy thừa bậc năm của một số nguyên.

Lời giải :

Gọi  là cặp số thỏa mãn đề bài và có tổng  nhỏ nhất. Ta giả sử .

Xét phương trình bậc hai ẩn  :

Vì  thỏa mãn đề bài nên  là một nghiệm của phương trình . Gọi nghiệm còn lại là . Theo định lí  :

Ta có  nên từ  suy ra .

Các cặp  đều thỏa mãn  mà  nhỏ nhất nên :

.

Như vậy 

• Trường hợp 1 :   thay vào  thì 
• Trường hợp 2 :  thì từ  ta được :

Dễ thấy  cùng tính chẵn lẻ mà 

Trường hợp này không xảy ra

• Trường hợp 3 : 

Suy ra 

Do đó từ  suy ra 

Khi  thì từ  suy ra , vì . Vô lí vì phải có .

Tương tự khi xét . Tất cả đều dẫn đến vô lí. Trường hợp này loại.

Do đó ta luôn có  là lũy thừa bậc năm của một số nguyên. Đây là điều phải chứng minh.

Bài toán về "số chính phương tự do"

Ta định nghĩa: số nguyên dương n là "số chính phương tự do" - "square-free" khi n không có dạng $n=mp^2$ với m là số nguyên dương nào đó, $p$ là số nguyên tố.

Bài toán: (India MO 1995). Gọi n là số nguyên không âm sao cho n là ước của tổng:

$1+\sum_{i=1}^{n-1}i^{n-1}$.

Chứng minh rằng: n là một số chính phương tự do.

Lời giải:

Giả sử $n=mp^2$ khi đó:

$1+\sum_{i=1}^{n-1}i^{n-1}=1+\sum_{j=0}^{p-1}\sum_{k=0}^{mp-1}(kp+j)^{n-1}\equiv1+mp(\sum_{j=0}^{p-1}j^{n-1})\equiv1(mod p)$

Suy ra tổng đó không chia hết cho $p$, mâu thuẫn với đề bài. Vậy ta có đpcm

Bài toán về số "tốt"

1) (T11/461): Cho n số nguyên dương khác nhau. Mỗi cặp số được lấy từ n số nguyên dương đã cho được gọi là tốt nếu tỉ số giữa hai số này là 2 hoặc 3. Hỏi khi cho $n=m^2$ số nguyên dương khác nhau tuỳ ý thì số cặp số tốt lớn nhất bằng bao nhiêu ?

Lời giải

Đặt $a_i=2^r_i.3^s_i.t_i, (t_i,6)=1$

Ta thấy $(a_i,a_r)$ thoả đề bài khi $t_i=t_r$ do đó số cặp số tốt trong n số $a_i$ không vượt quá số cặp số tốt trong n số $2^r_i.3^s_i$ (i từ 1 đến n)

Cặp $(2^r_i.3^s_i,2^r_j.3^s_j)$ tốt khi và chỉ khi

$r_i=r_j$ và $|s_i-s_j|=1$ hoặc $s_i=s_j$ và $|r_i-r_j|=1$

Xét n điểm $A_i=(r_i, s_i)$ ( trong tạp chí ghi sai $"A_i=(r_i,r_j)"$)

Như vậy cặp cặp $(2^r_i.3^s_i,2^r_j.3^s_j)$ tốt khi và chỉ khi $A_iA_j=1$.

Giả sử n điểm $A_i$ nằm trên k đường thẳng song song với trục Ox kí hiệu là $d_1,..d_k$

Gọi $m_l$ là số điểm $A_i$ nằm trên $d_l$ (l=1,..k) và $d_h$ chưa nhiều điểm $A_i$ nhất, Khi đó

$n=\sum m_i \le k m_h$

2) Cho $m \ge 2$ là một số nguyên. Số n nguyên không âm gọi là m-tốt nếu mỗi a nguyên tố cùng nhau với n, có $n | (a^m-1)$. Chứng minh rằng mọi số m-tốt lớn nhất bằng $4m(2^m-1)$

Giải.

Nếu m lẻ thì $n | (n-1)^m-1$ tương đương $n|2$ (khai triển).

$m=2^t.q (t \ge 1)$, q lẻ. Đặt $n=2^u(2v+1)$. Giả sử n là m-tốt khi đó $(2v-1)^m-1 \equiv 2^m-1 (mod 2v+1)$ (*). Nếu chọn $a=2(2v+1)+1=4v+3$ thì

$n | (a^{q})^{2t}-1)$  mà $v_2 (a^{q})^{2t}-1)=t+2$ do $v2(a^q-1)=1, v_2(a^q+1)=2$ (không được)

Nên chọn $a=8v+5$ ta có $v2(n)=u$ nên $u \le t+2$ vì thế kết hợp với  ta có điều phải chứng minh.

Bất đẳng thức Bonse

Cho $p_1=2, p_2=3,..$ là dãy tăng các số nguyên tố. Chứng minh rằng:

$p_1p_2..p_n >p_{n+1}^2$

Giải.

Đặt $A_k=p_1p_2...p_k$ và $a_k=k.p_1p_2..p_{n-1}-p_n$ với $1 \le k \le p_n -1$. Ta thấy rằng $a_k$ không chia hết cho $p_i$ (với i=1,..n) suy ra $a_k \ge p_{n+k}$ (Do là dãy tăng). Chọn k=$p_n-1$ ta được $a_k=A_n-A_{n-1}-p_n>p_{p_n+n-1}>p_{3n-1}$ ( có thể chứng minh $p_n \ge 2n$ bằng quy nạp). Từ đây ta nhận thấy với $n \ge 6$ thì

$p_1..p_n>(p_1..p_{[n/2]})^2>p_{3[n/2]-1}^2>p_{n+1}^2$