大問Ⅰ　素因数分解と最大公約数、1次不定方程式の自然数解、連立合同式、互いに素な数の個数数学A(整数の性質)・難易度 標準　

(1) ［1］ = 5

　b = 455 を小さい素数から順に割ると 455 = 5·91 = 5·7·13 と素因数分解できる。素因数は 5, 7, 13 で、その最小は 5 である。

(2) ［2］［3］ = 13

　a = 507 = 3·169 = 3·13²、b = 455 = 5·7·13 である。共通の素因数は 13 のみで、指数の小さいほうをとると 13¹。よって d = 13。

(3) ［4］ = 9、［5］［6］ = 10、［7］［8］ = 44、［9］［10］ = 49

　ax - by = d は 507x - 455y = 13。両辺を最大公約数 13 で割ると 39x - 35y = 1 となり、もとの式と同値である。

　この式を 35 を法として考えると 39x ≡ 1、すなわち 4x ≡ 1 (mod 35)。4·9 = 36 = 35 + 1 なので x ≡ 9 (mod 35)。

　x = 9 のとき 35y = 39·9 - 1 = 350 より y = 10 となり、x が最小の自然数解は (x, y) = (9, 10)。

　一般解は整数 k を用いて x = 9 + 35k, y = 10 + 39k と書けるので、x が2番目に小さいのは k = 1 のときで (x, y) = (44, 49)。

(4) ［11］［12］［13］［14］ = 4108

　求める自然数を N とすると、a = 507 で割った余りが 4d = 52 だから N = 507k + 52（k は 0 以上の整数）と表せる。

　さらに b = 455 で割った余りが d = 13 だから N ≡ 13 (mod 455)。507 ≡ 52 (mod 455) なので 52k + 52 ≡ 13、すなわち 52k ≡ -39 (mod 455)。

　52, 39, 455 はいずれも 13 の倍数なので 13 で割って 4k ≡ -3 ≡ 32 (mod 35)。4·8 = 32 より k ≡ 8 (mod 35)。

　最小は k = 8 で N = 507·8 + 52 = 4108。実際 4108 = 455·9 + 13 であり、両方の条件を満たす。

(5) ［15］［16］［17］ = 616

　a = 507 = 3·13² なので、a と互いに素であることは「3 の倍数でも 13 の倍数でもない」ことと同値である。

　1000 以下の自然数のうち 3 の倍数は 333 個、13 の倍数は 76 個、3 と 13 の公倍数すなわち 39 の倍数は 25 個。

　包除原理より 1000 - (333 + 76) + 25 = 616 個。