风车停转，天堂坠落，风车停转，天堂坠落，

D2T1 · 2024-07-30 12:58:03 · 学习·文化课

《九章算术》作为世界古典数学名著，其中所载问题与方法历久弥新，书中涉及的一些内容即使放在当代数学的背景下，仍然具有很好的启发性。在这个学习任务中，请大家阅读《九章算术》，从中撷取自己感兴趣的问题，将它用现行的数学符号表示出来，进而求解并做一定推广。

选择一个问题并摘录原题与解。

问题（卷一·方田）：又有九十一分之四十九，问约之得几何？

答曰：十三分之七。

术曰：可半者半之；不可半者，副置分母、子之数，以少减多，更相减损， 求其等也。以等数约之。

用所学的数学语言重新表述问题。

问题：将 \dfrac {49}{91} 化为最简分数。

运用你掌握的数学知识求解问题。

解答：求解 (49,91)=(49,42)=(7,42)=(7,35)=...=(7,7)，所以 \dfrac{49}{91}=\dfrac{49\div 7}{91\div 7}=\dfrac{7}{13}。

推广该问题到一般的情形并求解。

推广一：将 \dfrac {a}{b} 化为最简分数。

解：设 g=(a,b)，使用更相减损术求解，答案即为 \dfrac{a\div g}{b\div g}。

当 a,b 差过大时，(a,b)=(a,b-a)=(a,b-2a)=...=(a,b-ka)。设 b-(k-1)a\geq a>b-ka，则 k=\lfloor{\dfrac ba}\rfloor。可直接令 (a,b)=(a,b-\lfloor{\dfrac ba}\rfloor a)。

推广二：给定 a,b,c 求 ax+by=c 是否有整数解；若有则给出一组解。

设 g=(a,b)，易证 g|ax+by。若 g\nmid c，则无解。

否则，设 p = \dfrac ag,q=\dfrac bg，考虑 px+qy=1(p⊥q) 的解。

若 q>0，不妨 p>q,p=kq+j(k,j\in \mathbb Z,j<q)。若解得 qx'+jy'=1，易证下列 x,y 为解：

根据更相减损术，1=(p,q)=(q,p-q)=...=(q,j)，所以 q=0 时 p=1，此时 x=1,y=0 为 px+qy=1 的解。

于是可以求得 px+qy=1 的一组解 x',y'。则 ax+by=c 的解为 x=\dfrac{cx'}g,y=\dfrac{cy'}g。还可证明其为 |x|+|y| 最小的一组解。