Chủ đề này có 2 trả lời

[nmlinh16]

Cho $a, b, c, d$ là các số tự nhiên sao cho $ad - bc > 0$ và $\gcd(a,b) = \gcd(c,d) = 1$. Chứng minh rằng tồn tại hai dãy hữu hạn các số tự nhiên $a_0,\ldots,a_n$ và $b_0,\ldots,b_n$ sao cho $a_0 = a, b_0 = b, a_n = c, b_n = d$ và $a_i b_{i+1} - a_{i+1}b_i = 1$ với mọi $i = 0,1,\ldots,n-1$.

 

Đây là một bài toán nhỏ mà mình gặp khi nghiên cứu toric geometry.

[nmd27082001]

Lời giải

Em xin góp một chứng minh ạ. Ở đây em sẽ coi số tự nhiên không bao gồm số $0$.
Đặt $r=ad-bc>0$, ta chứng minh tồn tại hai số tự nhiên $p,q$ thỏa mãn $aq-bp=1$ và $0<pd-qc<r$. Nếu ta chỉ ra được sự tồn tại của hai số tự nhiên trên, bài toán chỉ còn quy nạp theo $r$ là xong.

 

Thật vậy, theo Định lý Bezout, tồn tại hai số tự nhiên $u,v$ với $0<u<a,0<v<b$ thỏa mãn $av-bu=1$. 

Nếu $\dfrac{u}{v}=\dfrac{c}{d}$ thì $u=c,v=d$ và $r=1$. Trường hợp này mệnh đề hiển nhiên đúng.

 

Nếu $\dfrac{u}{v}>\dfrac{c}{d}$ thì $0<ud-vc$ và $a(ud-vc)=(bc+r)u-(bu+1)c=ru-c<ru$ nên

\[0<ud-vc<r.\]

Do đó trường hợp này ta chọn $p=u,q=c$ là xong.

 

Nếu $\dfrac{u}{v}<\dfrac{c}{d}$ hay $vc-ud>0$. Khi đó gọi $k$ là số tự nhiên duy nhất thỏa mãn

\[k-1<\dfrac{vc-ud}{r}<k.\]

Chọn $p=u+ka, q=v+kb$ thì $aq-bp=av-bu=1$ và

\[pd-qc=ud+kad-vc-kbc=kr-(vc-ad).\]

Khi đó theo cách chọn $k$ ta có $0<pd-qc<r$.

[nmlinh16]

Em xin góp một chứng minh ạ. Ở đây em sẽ coi số tự nhiên không bao gồm số $0$.
Đặt $r=ad-bc>0$, ta chứng minh tồn tại hai số tự nhiên $p,q$ thỏa mãn $aq-bp=1$ và $0<pd-qc<r$. Nếu ta chỉ ra được sự tồn tại của hai số tự nhiên trên, bài toán chỉ còn quy nạp theo $r$ là xong.

 

Thật vậy, theo Định lý Bezout, tồn tại hai số tự nhiên $u,v$ với $0<u<a,0<v<b$ thỏa mãn $av-bu=1$. 

Nếu $\dfrac{u}{v}=\dfrac{c}{d}$ thì $u=c,v=d$ và $r=1$. Trường hợp này mệnh đề hiển nhiên đúng.

 

Nếu $\dfrac{u}{v}>\dfrac{c}{d}$ thì $0<ud-vc$ và $a(ud-vc)=(bc+r)u-(bu+1)c=ru-c<ru$ nên

\[0<ud-vc<r.\]

Do đó trường hợp này ta chọn $p=u,q=c$ là xong.

 

Nếu $\dfrac{u}{v}<\dfrac{c}{d}$ hay $vc-ud>0$. Khi đó gọi $k$ là số tự nhiên duy nhất thỏa mãn

\[k-1<\dfrac{vc-ud}{r}<k.\]

Chọn $p=u+ka, q=v+kb$ thì $aq-bp=av-bu=1$ và

\[pd-qc=ud+kad-vc-kbc=kr-(vc-ad).\]

Khi đó theo cách chọn $k$ ta có $0<pd-qc<r$.

 

Phát biểu ở đề bài vẫn đúng với $(a,b) = (1,0)$ hoặc $(c,d) = (0,1)$. Tất nhiên 2 trường hợp này không khó