100と互いに素な数の2乗の和の求め方｜数列と整数の性質を使った解法を徹底解説

「1から100までの自然数の中で100と互いに素な数の2乗の和を求める」という問題は、整数の性質や数列の考え方を組み合わせて解く良問です。本記事では、互いに素の意味からスタートし、効率よく求める方法を具体例とともにわかりやすく解説します。

互いに素とは何かを確認する

まず「互いに素」とは、2つの整数の最大公約数が1であることを意味します。

今回の問題では、「100と互いに素」な数を考えるので、100と共通の素因数を持たない数を選べばよいことになります。

100の素因数分解は、100 = 2² × 5²です。

したがって、2または5で割り切れる数は除外する必要があります。

1から100までの自然数のうち、2の倍数と5の倍数を除いた数が「100と互いに素」な数です。

つまり、偶数と5の倍数を除いた奇数の中で、さらに5で割れない数を選びます。

この条件を満たす数をすべて列挙する代わりに、全体から不要なものを引く考え方が効率的です。

1から100までの平方和は公式で求められます。

1² + 2² + … + 100² = 338350 です。

ここから「2の倍数」「5の倍数」を除いていきます。

2,4,6,…,100 は 2×(1～50) なので、平方和は

4(1²+…+50²) = 4×42925 = 171700

5,10,15,…,100 は 5×(1～20) なので、

25(1²+…+20²) = 25×2870 = 71750

10,20,…,100 は 10×(1～10) なので、

100(1²+…+10²) = 100×385 = 38500

重複して引かれているため、ここは足し戻します。

したがって、求める値は

338350 – 171700 – 71750 + 38500

これを計算すると、

133400

となります。

例えば1から10までで考えると、10と互いに素な数は1,3,7,9です。

このように「素因数を共有しないものを選ぶ」という考え方が基本です。

大きな数でも同じ考え方を応用すれば解けるようになります。

今回の問題では、互いに素の条件を「素因数で考える」ことが重要でした。

さらに、全体から不要なものを引き、重複を調整する（包除原理）ことで効率よく求めることができます。

この考え方を身につけることで、数列や整数問題に強くなります。