数论初步

<div> <h2>最大公约数 (Greatest Common Divisor, GCD)</h2> <p>两个或多个整数共有约数中最大的一个称为它们的最大公约数。</p> <p><strong>符号表示：</strong>通常用 gcd(a, b) 或者 (a, b) 表示两个整数 a 和 b 的最大公约数。</p> <h3>例题1：求48和60的最大公约数</h3> <p>解：48 = 2⁴ × 3¹, 60 = 2² × 3¹ × 5¹</p> <p>则 gcd(48, 60) = 2^min(4,2) × 3^min(1,1) = 2² × 3¹ = 12</p> <h2>最小公倍数 (Least Common Multiple, LCM)</h2> <p>两个或多个整数共有倍数中最小的一个称为它们的最小公倍数。</p> <p><strong>符号表示：</strong>通常用 lcm(a, b) 或者 [a, b] 表示两个整数 a 和 b 的最小公倍数。</p> <h3>例题2：求48和60的最小公倍数</h3> <p>解：48 = 2⁴ × 3¹, 60 = 2² × 3¹ × 5¹</p> <p>则 lcm(48, 60) = 2^max(4,2) × 3^max(1,1) × 5^max(0,1) = 2⁴ × 3¹ × 5¹ = 240</p> <h2>最大公约数和最小公倍数的关系</h2> <p>对于任意两个正整数 a 和 b，有以下关系式：</p> <p>gcd(a, b) × lcm(a, b) = a × b</p> <h3>例题3：验证gcd(48, 60) × lcm(48, 60) = 48 × 60</h3> <p>解：gcd(48, 60) = 12, lcm(48, 60) = 240</p> <p>则 12 × 240 = 2880, 而 48 × 60 = 2880</p> <p>所以 gcd(48, 60) × lcm(48, 60) = 48 × 60 成立。</p> </div>

上一条 下一条