整除的基本性质
辗转相除法
重要程度：7 分
<div>
<h2>辗转相除法</h2>
<p>辗转相除法又称欧几里得算法，是一种用于计算两个正整数的最大公约数的方法。</p>
<ul>
<li><strong>基本原理：</strong>若a > b，则gcd(a, b) = gcd(b, a % b)</li>
<li><strong>步骤：</strong>
<ol>
<li>用较大数除以较小数。</li>
<li>再用出现的余数（第一轮除法后的余数）去除除数。</li>
<li>循环此过程直到余数为0，此时最后的除数即为两数的最大公约数。</li>
</ol>
</li>
</ul>
<h3>例题说明</h3>
<p>求18和45的最大公约数。</p>
<ol>
<li>首先用45除以18，得到商2和余数9：45 = 18 * 2 + 9</li>
<li>然后用18除以9，得到商2和余数0：18 = 9 * 2 + 0</li>
<li>当余数为0时，上一步的除数9即为最大公约数。</li>
</ol>
<p>因此，18和45的最大公约数是9。</p>
</div>