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$

Tính chất của số nguyên tố có dạng $3k+2$

Cho $p$ là số nguyên tố thỏa mãn $3 | p-2$ khi đó $p | x^3 -y^3$ khi và chỉ khi $p | x-y$

Chứng minh:

Ta xét $ x,y $ không chia hết cho $p$ vì nếu chia hết cho p là hiển nhiên.
Nếu $ x \equiv y (mod p)$ thì $ x^3 \equiv y^3 (mod p)$
Ta chứng minh Nếu $ x^3 \equiv y^3 (mod p)$ thì $ x \equiv y (mod p)$

$x^{3} \equiv y^3 (mod p)  \Rightarrow x^{p-2}\equiv y^{p-2}(mod p)$

Theo định lý Fermat nhỏ:

$x^{p-1}\equiv y^{p-1} \equiv 1(mod p) \Rightarrow x^{p-2}(x-y) \equiv 0 (mod p) \Rightarrow x \equiv y (mod p)$

Xét ứng dụng của bổ đề trên:

Bài toán ( Chọn đội tuyển QG tỉnh Lạng Sơn 2016): Cho đa thức $P(x)=4x^3-18x^2+27x+m$. CMR: Với mỗi $m\in\mathbb{Z}$, $\exists n\in\mathbb{Z}$ sao cho $P(n)\vdots 107$

Lời giải:
Do (2, 107)=1 nên:
$P(n)\vdots 107 \Leftrightarrow  2P(n)\vdots 107$

Xét $G(x)=2P(x)=(2x-3)^2+27+2m$

Với mỗi $m$ ta có $G(0), G(1), . G(106)$ lập thành một hệ thặng dư đầy đủ mod 107. Thật vậy:

Nếu có $i ,j $ mà $  0\ge i, j \le 106$ mà $G(i) \equiv G(j) (mod 107)$ Thì khi đó theo bổ đề trên:
 $i \equiv j (mod 107)$ hay $ i=j$.

Vậy luôn tồn tại $n$ sao cho $P(n)\vdots 107$

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

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).