【NT22】互いに素であることの証明
$n$ を自然数とします。
$n^2$ と $2n+1$ が互いに素であることを示してください。（一橋大）
【ヒント】$a$ と $b$ の最大公約数を $(a,\:b)$ で表すと、$(a,\:b)=1$ であるような $a$ と $b$ は 互いに素 であるといいます。たとえば $2$ と $3$ は最大公約数が $1$ なので互いに素です。連続する 2 つの数が互いに素であることは自明としてかまいません。
【解答準備】解答に入る前に具体的な数値で確認しておきましょう。
$(n^2,\:2n+1)$ を $n$ が小さいほうから並べてみると、
\[(1,\:3),\quad (4,\:5),\quad (9,\:7),\quad (16,\:9),\:\cdots\]
となって、確かにそれぞれのペアは互いに素の関係にあるようです。ここで勘の鋭い人であれば、どの組も２つの数字を足すと
\[4,\quad 9,\quad 16,\quad 25,\:\cdots\]
のように平方数になっていることに気づくと思います。これがわかってしまうと解法の道筋が一気に開けます。
【解答】それでは解答です。
$n^2$ と $2n+1$ の最大公約数を $g$ とすると自然数 $a,\:b$ を使って
\[n^2=ga,\quad 2n+1=gb\]
のように書くことができます。そしてこの２つの数を加えると
\[n^2+2n+1=g(a+b)\]
となります。左辺は因数分解できるので
\[(n+1)^2=g(a+b)\]
となるので、$g$ は $n^2$ と $(n+1)^2$ の共通の約数にもなっています。ヒントにもあるように連続する２つの数について $(n,\:n+1)=1$ ですから、その平方数同士もまた互いに素の関係にあります。■
【補足】証明の最後に用いた、$(a,\:b)=1\Rightarrow (a^2,\:b^2)=1$ は自明であるとして構いません。数の扱いに慣れていれば当たり前のことなのです。ただ、どうしても気になる人もおられるでしょうから、念のために背理法による証明を載せておきます：
$a^2,\:b^2$ が互いに素でないと仮定します。つまり、$a^2,\:b^2$ は 1 以外の公約数 $m$ をもつことになります。$m$ がどのような数であっても素数の積に表せるので、 $a^2,\:b^2$ は何らかの素数 $p$ を約数にもつことになります。すると $a,\:b$ がともに $p$ を約数にもつということになり、これは $a,\:b$ が互いに素であるという仮定に反することになります。よって $a^2,\:b^2$ は互いに素です。[証明終]
エクセルや数学に関するコメントをお寄せください
【AI連載小説】数学のリズム、エクセルの旋律(16)
「互いに素であることを判定するVBA関数」
Excel VBAサークルのメンバーである真琴、村雨研伸、雨宮隆治、そして二階堂月子が集まって、新しいユーザー定義関数を作成することになった。彼らの目標は、与えられた2つの数値が互いに素であるかどうかを判定する関数を作り上げることだった。
サークルのメンバーは、真琴が中心となって意気投合し、プログラミングと数学のスキルを活かして関数を開発することに決めた。彼らは部室でパソコンに向かい、熱心にプログラミングに取り組んでいた。
真琴はまず、数学的なアルゴリズムを考え、それをVBAのコードに落とし込んでいった。村雨研伸と雨宮隆治は、そのコードを理解し、必要な修正や改善点を提案しながら、共同作業を進めていった。二階堂月子は、関数の使いやすさやエラー処理に焦点を当て、ユーザーフレンドリーな関数の形に仕上げることに貢献していた。
彼らは激しい議論や試行錯誤を経て、最終的には素数判定関数を完成させた。その関数は、Excel上で簡単に使え、ユーザーが2つの数値を入力すると、それが互いに素であるかどうかを迅速に判定することができた。
Function AreCoprime(ByVal num1 As Long, ByVal num2 As Long) As Boolean Dim smallerNum As Long Dim i As Long ' 2つの数値のうち、小さい方を取得 If num1 < num2 Then smallerNum = num1 Else smallerNum = num2 End If ' ユークリッドの互除法を用いて最大公約数を求める For i = 2 To smallerNum If num1 Mod i = 0 And num2 Mod i = 0 Then ' 最大公約数が1以外の場合、互いに素でない AreCoprime = False Exit Function End If Next i ' 最大公約数が1の場合、互いに素 AreCoprime = True End Function完成した関数を試すために、サークルメンバーは実際にいくつかの数値の組み合わせを入力し、関数が正しく動作することを確認した。