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$
Hiển thị các bài đăng có nhãn ước số. Hiển thị tất cả bài đăng
Hiển thị các bài đăng có nhãn ước số. Hiển thị tất cả bài đăng
Thứ Hai, 6 tháng 2, 2017
Thứ Hai, 2 tháng 5, 2016
Hai bài số học của Mỹ và Trung Quốc.
1/ (Mỹ) Chứng minh rằng với mỗi số nguyên $n \ge 2$ đều tồn tại một tập S gồm n số nguyên thoả mãn $(a-b)^2$ là ước của ab với mọi a,b thuộc S phân biệt.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab
Giải
1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.
Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:
$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}
Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.
Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$
Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)
Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):
(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);
(12, 4); (24, 8); (36, 12); (48, 16)
(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)
(30, 6)
(42, 7), (35, 14), (28, 21)
(40, 24)
(45, 36)
Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.
Vậy K nhỏ nhất là 39.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab
Giải
1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.
Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:
$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}
Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.
Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$
Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)
Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):
(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);
(12, 4); (24, 8); (36, 12); (48, 16)
(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)
(30, 6)
(42, 7), (35, 14), (28, 21)
(40, 24)
(45, 36)
Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.
Vậy K nhỏ nhất là 39.
Chủ Nhật, 1 tháng 5, 2016
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ý.
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ý.
Đăng ký:
Bài đăng (Atom)