雑感 馬鹿企画, 2018/6/23 数学, 整数論の序論は暗号理論にとって大切である。今回は特に古典的整数論によって、ユークリッドの互除法を証明するあたりから、オイラーの定理を簡潔に解説し概論としてこれを会得してもらう。余裕があれば、オイラーの定理の証明まで行い、身に着けることを強く推奨する。, まず、合同式の定義だが、ここは変数をつかって説明する。まず、二つの整数を考える。自然数とは0を含まない正の整数のことを言う。例えば1、2、3、4、5、6、7、8、9・・・というようにである。これは集合として表せば…. これを、ユークリッド互除法の拡張・拡張ユークリッドの互除法などという。 「整数m,nのGCD(m,n)のとき、mx+ny=GCD(m,n)となるような整数xとyとの組みが見つかる」 オイラーの定理はφなどを使って、素の数を表していくから面倒だが、こういう証明はある。 よって「$a$ と $b$ の公約数」は「$b$ と $r$ の公約数」でもある。したがって, 任意の素数を $p$ として、$p$ より大きな素数が存在することを示せばよい。$p$ 以下のすべての素数の積に $1$ を加えて, しかしながら、前節のフェルマー数を利用した鮮やかな別証明方法があります。すなわち、フェルマー数 $F_n = 2^{2^n} + 1$ はどの 2 つも互いに素であることを利用します。どのフェルマー数も少なくとも 1 つの素因子を持っていて、それらはどの 2 つも互いに異なる必要があるため、素数が無限にあることになります。 =3-(8-3\cdot 2)\cdot 1\\ で与えられる ($x$ と $y$ を入れ替えたものを含む)。, 具体例として、$m = 2$, $n = 1$ とすると、$x = 3, y = 4, z = 5$ と有名な直角三角形が登場します。ピタゴラス数は実は普通の整数論でも導くことができるのですが、整数を拡張して複素整数を考えると明快に導くことができます。, 【解】 思想評論 ただし n3 − 34n2 + 381n − 1511 の n = 9, 12, 13 で −107 を取るなど、同じ素数が何度も出現する場合がある。, 多変数の多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、k + 2 が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである[22]:, 長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブルや擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。, 公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの(大きな)素数の掛け算は比較的簡単に(効率的に)行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。, 自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がズレてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる[30]。, また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。, 自然数で素数でないものが連続している区間を「素数砂漠」という。例えば{24, 25, 26, 27, 28} は「長さ 5 の素数砂漠」である。素数砂漠を挟む2個の素数は 3 以上であるため、共に奇数である。このことから、素数砂漠の長さは必ず奇数である。いくらでも長い素数砂漠が構成できる(#分布を参照)。, 30030, 255255, 1616615, 7436429, 30808063, 86822723, …, Jones, James P.; Sato, Daihachiro; Wada, Hideo; Wiens, Douglas (1976), "Diophantine representation of the set of prime numbers", American Mathematical Monthly, en:Furstenberg's proof of the infinitude of primes, https://users.renyi.hu/~p_erdos/1938-12.pdf, "Arguments for and against the primality of 1", https://primes.utm.edu/notes/proofs/infinite/Saidak.html, https://www.humboldt-professur.de/en/preistraeger/preistraeger-2015/harald-andres-helfgott, https://www.springer.com/jp/book/9783642008566, https://www.springer.com/jp/book/9780387201696, https://ja.wikipedia.org/w/index.php?title=素数&oldid=80436047. よって「$b$ と $r$ の公約数」は「$a$ と $b$ の公約数」でもある。したがって, 4 $) である。, 通常の平方数が $4$ で割って $2$ 余ることはありえないので $z^2$ は $4$ の倍数であることになる。しかし、$x$ と $y$ のどちらかは奇数であるから、$x^2 + y^2$ を $4$ で割った余りとしてあり得るのは、$1$ か $2$ のみである。これは矛盾である。, したがって、$x + yi$ が $\lambda$ で割り切れることはない。また実は $\lambda$ は複素整数の世界では素数である。したがって $x + yi$ と $\lambda$ は互いに素である。このことを利用してユークリッドの互除法を適用すると、, ${\rm gcd}(x - yi, x + yi)$ + 2, …, n! ユークリッドの互除法は整数問題を解く上で避けることができないテーマであり、センター試験でも頻出します。, ユークリッドの互除法の使い方をマスターすることで、2つの数の最大公約数を簡単に求めることができるようになります。, 最大公約数とは、公約数のうち最大の数のことですね。例えば、21と35の最大公約数は7であり、221と169の最大公約数は13となります。, この最大公約数を求める時に、ユークリッドの互除法を使えば、221と169という大きな数でも最大公約数は13であるというように、最大公約数を求めることができます。, 小さな数であれば素因数分解をすることで求めることができますが、大きな数になるとユークリッドの互除法に頼る方が圧倒的に早くなります。, ユークリッドの互除法のやり方は以下のようになります。具体例と一緒に確認して覚えましょう!, このように余りを求める計算を繰り返していくことで、2つの数の最大公約数を求めることができます。, 整数問題の証明は少し抽象的になって難しいですが、ユークリッドの互除法の証明は2次試験が記述試験でない限り必要ないでしょう。, 最終的に証明したいのは、(a,b)の最大公約数と(b,r)の最大公約数が等しいことです。(rはaをbで割った余り), そこで、(a,b)の最大公約数が(b,r)の最大公約数以下であり、かつ以上であることを証明します。, (a,b)の最大公約数を\(G_1\)、(b,r)の最大公約数を\(G_2\)とする。, これより、紹介した方法を繰り返すと、いずれ余りが0になるのでユークリッドの互除法が成り立ちます。, 「ユークリッドの互除法は最大公約数を見つけるのに便利な手法である」と紹介しましたが、入試で問われることが多いのは一次不定方程式と呼ばれる問題への応用です。, 例えば、「\(3x+5y=1\)を満たす整数x,yの組を求めよ」といった問題です。, この問題の答えは\((x,y)=(-5k+2,3k-1)(kは整数)\)となります。, つまり、任意の整数kに対して\((x,y)=(-5k+2,3k-1)\)が成り立つということです。, (7,-4)(2,-1),(-3,2)など、特定の整数の組が成り立つことを上のように表現するので覚えておきましょう。, ユークリッドの互除法を用いて\(29x-17y=1\)を満たす整数のx,yの組を求めます。, この組を求めるためにランダムに数字を入れて確かめても良いのですが、数字が大きいと見つけるのは大変なので互除法を利用します。, よってこれより、(x,y)=(-7,-12)が解の組の1つであることがわかります。, x+7=17k(kは整数)と表すことができます。なぜなら右辺より29(x+7)は17の倍数であり、29は17の倍数ではないためです。, この問題を解くためのポイントは「方程式をみたす値を見つけること」と、「互いに素であることを利用して文字を用いてx,yを表すこと」です。, 運が良ければユークリッドの互除法を利用する前に値を見つけることができますが、値が大きな場合はユークリッドの互除法を利用しましょう。, ユークリッドの互除法そのものはそんなに難しいわけではないですが、整数問題は受験生が苦手とする分野で攻略しにくいので注意が必要です。, 不定方程式のような馴染みがない問題も出題されますが、演習を繰り返して当たり前のように解けるようにしていきましょう。.