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$

Một số tính chất số học của dãy tuyến tính

Cho dãy $(x_n)$ sao cho:
$x_0=1, x_1=1$, $x_{n+2}=ax_{n+1}+bx_n (a,b \in Z)$

Khi đó ta có:

1)$x_{m+n}=bx_{n}x_{m-1}+x_{n+1}x_{m}$

2) $x_{kn} \vdots x_n$

Ứng dụng:

Mở rộng đề thi chọn đội tuyển Ninh Bình 2016: Giả sử $p,q$ là hai số nguyên tố , dãy $(u_n)$ được xây dựng như sau:

$$\left\{\begin{matrix} u_0=0 & & & \\ u_1=1 & & & \\ u_n=pu_{n-1}-qu_{n-2}\forall n\geq 2,n \in \mathbb{N} & & & \end{matrix}\right.$$

Tìm tất cả $p,q$ biết tồn tại số tự nhiên $k$ để $u_{3k}=-3$

áp dụng tính chất 2) suy ra $u_3 |3 $ hay  $p^2-q|3$. Kết hợp điều kiện p,q nguyên tố nên có thể dễ dàng tìm được p,q

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ẻ

Sử dụng số phức trong đa thức

Nghiệm phức của đa thức với hệ số nguyên, trong nhiều trường hợp là chìa khóa để chứng minh tính bất khả quy trên (Z, và Q) của đa thức đó. Chúng ta tìm hiểu các lý luận mẫu trong vấn đề này thông qua các ví dụ sau:

Bài 1: Cho P(x) và Q(x) là 2 đa thức với hệ số nguyên thỏa mãn điều kiện:

$\begin{bmatrix}
P(x^3)+xQ(x^3)
\end{bmatrix}\vdots (x^2+x+1)$ Gọi d là ước chung lớn nhất của P(2007) và Q(2007). Chứng minh rằng $d \vdots 2006$

Lời giải:

Ta sẽ chứng minh rằng P(1)=Q(1)=0

Ta có: $\varepsilon =\frac{-1}{2}+i\frac{\sqrt{3}}{2}$ là nghiệm của đa thức $x^2+x+1$

Suy ra: $\varepsilon^3=1$

Từ điều kiện lần lượt cho $x=-\varepsilon, -\varepsilon^2$ vào ta được
$\left\{\begin{matrix}
P(1)+\varepsilon Q(1)=0 (1)& \\
P(1)+\varepsilon^2Q(1)=0 (2)&
\end{matrix}\right.\Rightarrow \left\{\begin{matrix}
-\varepsilon P(1)-\varepsilon^2 Q(1)=0 (3)& \\
- \varepsilon^2 P(1)-\varepsilon Q(1)=0 (4)&
\end{matrix}\right.$
Cộng (1), (2), (3), (4) và sử dụng $\varepsilon^2+\varepsilon+1=0$ ta được $3P(1)=0$

Ta chỉ còn chứng minh Q(1)=0, mà từ (1), (2):

$\left\{\begin{matrix}
P(1)+\varepsilon Q(1)=0 & \\
P(1)+\varepsilon^2Q(1)=0 &
\end{matrix}\right.\Rightarrow \left\{\begin{matrix}
\overline{\varepsilon} P(1)+Q(1)=0 & \\
\overline{\varepsilon} P(1)+ Q(1)=0&
\end{matrix}\right.$ Đến đây làm tương tự như P(1) ta có điều phải chứng minh.

Bài 2 (USA MO): Cho P(x), Q(x), R(x) là các đa thức sao cho:
$\begin{bmatrix}
P(x^5)+xQ(x^5)+x^2R(x^5)
\end{bmatrix} \vdots(x^4+x^3+x^2+x+1)$

Chứng minh rằng P(x) chia hết cho x-1.

Giải: Đặt $w=e^{\frac{2\pi i}{5}}$ thì $w^5=1$, thay x lần lượt bằng $w, w^2, w^3, w^4$ ta được các phương trình:

$\left\{\begin{matrix}
P(1)+wQ(1)+w^2R(1)=0\\
P(1)+w^2Q(1)+w^4R(1)=0\\
P(1)+w^3Q(1)+w^6R(1)=0\\
P(1)+w^4Q(1)+w^8R(1)=0
\end{matrix}\right.$
Nhân các phương trình từ 1 đến 4 lần lượt với $-w, -w^2, -w^3, -w^4$ ta được:

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$ 

Dùng nguyên lí Dirichlet để giải bài toán tổ hợp - Phần 2

Bài toán: Tìm số tự nhiên n lớn nhát sao cho tồn tại n số nguyên không âm $x_1,x_2,..x_n$ không đồng thời bằng 0, sao cho với mọi $\varepsilon _1, \varepsilon _2,..\varepsilon _n$ $\in$ {-1;0;1} không đồng thời bằng 0 sao cho $n^3$ không chia hết cho $\varepsilon _1x_1+\varepsilon _2x_2+..\varepsilon _nx_n$

Lời giải.

Với n=9 ta chọn $1,2,2^2,..2^8$

Khi đó: $| \varepsilon _1+..+2^9\varepsilon _9|\le 1+2+..2^8<9^3$

Nếu $n\ge10$ không mất tính tổng quát, giả sử $n=10$ khi đó số tập con của S={$x_1,x_2,..z_10$} là $2^{10}$ và vì $2^{10}>10^3$ nên theo nguyên lí Dirichlet tồn tại hai tập A và B là tập con của S sao cho tổng các phần tử của A có cùng số dư với tổng các phần tử của B.

Khi đó đặt $\varepsilon _i=1$ nếu $x_i$ thuộc A nhưng không thuộc B, $\varepsilon _i=-1$ nếu $x_i$ thuôc B nhưng không thuộc A, bằng 0 trong trường hợp còn lại khi đó:

$\sum \varepsilon _ix_i \vdots n^3$

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$

Về hai bài số học trong kì thi vô địch Nga

Bài 1: Tìm số nguyên dương không âm n có đúng 12 ước số, $1=d_1<d_2...<d_{12}=n$ mà $d_{d_4-1}=(d_1+d_2+d_4)d_8$.

Hướng giải.

Theo giả thiết nên tồn tại $i$ sao cho

$d_i=d_1+d_2+d_4$. Vì $d_i >d_4$ nên $13>i>4$

Hiển nhiên ta có: $d_jd_{13-j}=n$ với mọi j và vì $d_id_8=d_{d_4-1}$ suy ra $i \le 5$ vì thế i=5 suy ra $d_4=13$ ta có $d_5=14+d_2$. Do $d_2$ lại là số nguyên tố nhỏ nhất của n mà $d_4=13$

Xét các trường hợp ta có $d_2=3$.

Từ đây dễ dàng tính được $n=1989$ là một nghiệm của bài toán

Bài 2: Tìm tất của các số nguyên dương lẻ n lớn hơn 1 sao cho với mọi a,b là ước của n $(a,b)=1$ thì $a+b-1 $ là ước của n

Hướng giải.

Dễ thấy n là luỹ thừa của một số nguyên tố thì thoả mãn.

Xét $n=p^r.s$ $(p,s)=1$  và p là số nguyên tố nhỏ nhất.

$p+s-1 |n$, xét q là ước nguyên tố của s thì:
$s<p+s-1<s+q$ nên$q \not |p+s-1$. Vì thế $p+s-1=p^c$  suy ra $s=p^c-p+1$ và vì $(p^c,s)=1$ nên $p^c+s-1=2p^c-p | n$. Suy ra $2p^{c-1}-1 | s$ (do không thể là ước của $p^r$) Thay s vào và ta nhận được điều vô lý.