【2022京都府立大学】nが30と互いに素であるとき、n^2を12で割った余り

解答・解説

解答には合同式を利用します。

合同式は整数問題を扱う上で必須アイテムになりますので、不安がある方は

「合同式とは？合同式の基本性質を理解し、使えるようにする」を参考に！

自然数 \(n\) が \(30\) と互いに素であるとき，\(0\) 以上の整数 \(x\)，\(y\) を用いて

\(n=30x+y\) と表せ，

\(30=2\times 3\times 5\) より，

\(y\) は 「\(29\) 以下の整数」かつ「 \(2\)，\(3\)，\(5\) と互いに素 」となる．

よって \(y=1,7,11,13,17,19,23,29\) のいずれかとなる．

\(n^2=(30x+y)^2=900x^2+60xy+y^2\)

ここで，以下 \(mod 12\) として考えると

\(n^2≡y^2\) であるから，\(y=1,7,11,13,17,19,23,29\) のとき

\(y^2≡1\) となることを示せば良い．

(ア)　\(y=1\) のとき

\(y^2≡1\) より成立

(イ)　\(y=7\) のとき

\(y^2=7^2=49≡1\) より成立

(ウ)　\(y=11\) のとき

\(y≡-1\) より \(y^2≡1\) となり成立

(エ)　\(y=13\) のとき

\(y≡1\) より \(y^2≡1\) となり成立

(オ)　\(y=17\) のとき

\(y≡5\) より \(y^2≡5^2≡1\) となり成立

(カ)　\(y=19\) のとき

\(y≡-5\) より \(y^2≡(-5)^2≡1\) となり成立

(キ)　\(y=23\) のとき

\(y≡-1\) より \(y^2≡1\) となり成立

(ク)　\(y=29\) のとき

\(y≡5\) より \(y^2≡5^2≡1\) となり成立

以上より，題意は示された．