相遇算题

中国古代最大公约数的概念来源于对分母进行约分.

《九章算术》方田章第 题为：“今有九十一分之四十九. 问约之得几何?” 附于题后的约分术为：

​ “可半者半之，不可半者，副置分母子之数，以少减多，更相减损. 求其等也. 以等数约之. "

这里说的 “等数”，就是最大公约数. 此题的等数为 ，约分后为 .

中算家很少将一个整数分解成质因数，分数约分时首先进行观察，如有明显的公约数（如2、3等）则先行约去，然后再应用一套机械化的算法求出等数进行约分. 《张丘建算经》序中说：“凡约法：高者下之，精者半之，者商之. 副置其子及其母，以少减多，求等数而用之. ”与《九章算术》所述约分术大同小异.

注：《张丘建算经》为公元五世纪北朝北魏张丘建所撰，列为《算经十书》之一，现传有由唐李淳风 等注释版本，书中有 题样本题目，包括有关最大公约数、最小公倍数、等差数列、不定方程，如百鸡问题 、封山周栈 、今与人钱等问题，都是当时甚具创见的题目.

等数是中国古代数学中的一个重要概念，古代历法中的分数数据，除非有保持统一分母的特别需要，一般皆以既约分数的形式出现，这就是求等数约分的结果在涉及化多个整数模为两两互素模的算法中，等数也起着重要作用.

《张丘建算经》这本书中涉及分数的公共周期，相当于整数论中的最小公倍数问题，而求解的关键步骤则是利用最大公约数进行化约. 让我们先来看一道书中例题：

例题

古文：“今有封山周栈三百二十五里. 甲、乙、丙三人同绕周栈行，甲日行一百五十里，乙日行一百二十里，丙日行九十里. 问周行几何日会？ ”

现代文：在绕山一周为三百二十五里的栈道上，甲、乙、丙三人同一方向绕山而行. 三人的速度分别 为，甲日行一百五十里，乙日行一百二十里，丙日行九十里. 问三人何时相会？

题解

因为 的最大公约数为30. , , .

由此，若一个虚拟的 “丁” 日行 里，需 日走一圈.

而甲的速度为丁的 倍，所以 在 日内，甲走了 圈，而乙走了 圈，丙走了 圈，甲乙丙三人再在起点相遇.

参考文献：

[1]夏树人, 孙道杠.中国古代数学的世界冠军[M].重庆出版社,1984.

[2] 刘钝. 国学丛书-大哉言数[M].辽宁教育出版社,1993.