一种求解最大公因数与最小公倍数的直观方法——魏欧法
魏华辰
哈尔滨工业大学附属中学，哈尔滨150000，中国
摘要：最大公因数与最小公倍数的计算是初等数学中的基本问题。传统方法包括质因数分解法、短除法和欧几里得算法。本文提出的魏欧法本质上等同于欧几里得算法，但通过“几倍多几” 的余数递推方式进行直观化处理，更符合中学生的思维特点。本文在阐述魏欧法的数学原理基础上，给出计算步骤和典型实例，并利用C++程序进行验证，列出典型数对的表格化结果，表明该方法正确可靠。魏欧法不仅能够同步求得最大公因数与最小公倍数，而且在教学中有助于学生直观理解数论思想，具有一定的推广价值。
参考文献
[1] Martinez S, Sánchez-Matamoros G, Moreno A, et al. Influence of context on greatest common divisor problem solving: a qualitative study. Mathematics, 2022, 10(8): 1325.
[2] Heyman R, Shonhiwa T. Hyperbolic summation for functions of the GCD and LCM of several integers. The Ramanujan Journal, 2023, 62: 273-290.
[3] Backhouse R, Ferreira JF. On Euclid’s algorithm and elementary number theory. Science of Computer Programming, 2011, 76(3): 160-180.
[4] Sedjelmaci SM. A parallel extended GCD algorithm. Journal of Discrete Algorithms, 2008, 6(3): 526-538.
[5] Maze G. Existence of a limiting distribution for the binary GCD algorithm. Journal of Discrete Algorithms, 2007, 5(1): 176-186.
[6] Collins GE. A fast Euclidean algorithm for Gaussian integers. Journal of Symbolic Computation, 2002, 33(3): 385-392.
[7] Morris ID. A rigorous version of R. P. Brent’s model for the binary Euclidean algorithm. Information and Computation, 2016, 248: 22-46.
[8] Stein J. Computational problems associated with Racah algebra. Journal of Computational Physics, 1967, 1(3): 397-405.
[2] Heyman R, Shonhiwa T. Hyperbolic summation for functions of the GCD and LCM of several integers. The Ramanujan Journal, 2023, 62: 273-290.
[3] Backhouse R, Ferreira JF. On Euclid’s algorithm and elementary number theory. Science of Computer Programming, 2011, 76(3): 160-180.
[4] Sedjelmaci SM. A parallel extended GCD algorithm. Journal of Discrete Algorithms, 2008, 6(3): 526-538.
[5] Maze G. Existence of a limiting distribution for the binary GCD algorithm. Journal of Discrete Algorithms, 2007, 5(1): 176-186.
[6] Collins GE. A fast Euclidean algorithm for Gaussian integers. Journal of Symbolic Computation, 2002, 33(3): 385-392.
[7] Morris ID. A rigorous version of R. P. Brent’s model for the binary Euclidean algorithm. Information and Computation, 2016, 248: 22-46.
[8] Stein J. Computational problems associated with Racah algebra. Journal of Computational Physics, 1967, 1(3): 397-405.