新式算術講義/第四章

第四章　整除に關する整數の性質

整除，倍數，相合式及ガウスの記法，剩餘の擴張，相合式の性質○十進法に於ける特殊なる整數の倍數の鑑識○最小公倍數及最大公約數○二つの數の最小公倍數及最大公約數，ポアンソーの幾何學的說明○一次不定方程式，一般の解答の決定，オイラーの解法○素數及合成數，合成數の素數分解，エラトステネスの篩，素數の數に限りなし○素數分解の應用

（一）

$b$ を正數とし，其倍數

$\ldots -3b,-2b,-b,0,b,2b,3b\ldots$

を大さの順序に排列するとき，$a$ 若し $b$ の倍數ならずば，$a$ は必ず二個の接續せる $b$ の倍數の中間に落つ．今

$qb<a<(q+1)b$

なりとせば

$a-qb=r$

は $b$ より小なる正數なり．

此觀察より直ちに次の定理を得．

一，$a$，$b\ (b>0)$ の與へられたるときは

$a=qb+r,\qquad b>r\geqq 0$

なる條件に適すべき整數 $q$，$r$ は必ず，然も唯一組に限り存在す．（第二章（七）を參照すべし．）

例へば $a=-12$，$b=5$ となさば

$-3\times 5<-12<-2\times 5$

$q=-3,\quad r=3.$

$b$ 個の連續せる整數

(1)

$a,a+1,a+2,a+3,\ldots a+b-1\qquad (b>0)$

の中，$b$ を以て整除し得べきものは唯一個に限り存在す．其故如何にといふに，先づ

$a=bq+r,\qquad 0\leqq r<b$

より $q$ 及 $r$ を定むるとき，$r$ 若し $0$ に等しからば，$a$ 旣に $b$ を以て整除し得べし．$r$ 若し $0$ に等しからずば $k=b-r$ は $1,2,3\ldots b-1$ の中の一つに等しく，而して．$a+k=b(q+1)$ は $b$ を以て整除し得べし．是故に前に揭げたる $b$ 個の數の中少くとも一個は $b$ を以て整除し得べし．然れども前に揭げたる $b$ 個の數の中 $b$ を以て整除し得べき者一個より多くあることなし，其故如何にといふに $b$ を以て整除し得べき數二個の差は其絕對値少くとも $b$ を下らず，然るに (1) の諸數の中いづれの二個をとるも其差の絕對値は $b$ より小なり．

是によりて考ふるに或整數が他の整數にて整除し得べきは極めて特別なる場合に限れり．整除といふ事が整數論に於て甚だ重要なる位置を占むること，誠に故ありと謂ふべし．

$a$ が $d$ にて整除せらるゝときは $a$ を $d$ の倍數 $d$ を $a$ の約數と云ふ．

二，$a$，$a'$ 共に $d$ の倍數なるときは $a$，$a'$ の和及差は共に $d$ の倍數なり．

證，$a$ は $d$ の倍數又 $a'$ は $d$ の倍數なるが故に，$a=qd$，$a'=q'd$ なる如き整數 $q$，$q'$ は存在す．さて $a\pm a'=(q\pm q')d$ にして $q\pm q'$ は亦整數なるが故に $a\pm a'$ は $d$ の倍數なり．此定理は又 $d$ の倍數二個以上の場合にも適用せられ得べし．

三，$a$ は $b$ の倍數，$b$ は $d$ の倍數ならば，$a$ は又 $d$ の倍數なり．

證，$a=a'b$，$b=b'd$ なる如き，整數 $a'$，$b'$ 存在するにより $a=a'\cdot (b'd)$ 卽ち $a=(a'b')d$ 而して $a'b'$ は整數なるが故に $a$ は $d$ の倍數なり．

一般に $a_{1},a_{2},a_{3}\ldots a_{n}$ 等の整數ありて各の $a$ は其次の $a$ の倍數なるときは，最初の $a_{1}$ は最後の $a_{n}$ の倍數なり．

尙汎く $a_{1},a_{2}\ldots a_{n}$ は各 $d$ の倍數にして，$q_{1},q_{2}\ldots q_{n}$ は隨意に定められたる整數なるときは

$q_{1}a_{1}+q_{2}a_{2}+\cdots +q_{n}a_{n}$

も亦 $d$ の倍數なり．

$a$，$b$ なる二個の整數の差が $m$ の倍數なるときは，$a$，$b$ は $m$ を法として相合へり，又は $m$ を法として $a$ は $b$ の剩餘，$b$ は $a$ の剩餘なりと云ふ．此事實を書き表はさんが爲にガウスは次の記法を用ゐたり．

$a\equiv b\qquad {\pmod {m}}$

${\mbox{mod}}\ m\ ({\mbox{modulo}}\ m)$ とはなほ「$m$ を法として」と云ふが如し．斯の如き式を相合式と云ふ．

$a$，$b$ が $m$ を法として相合へる數なるときは $a-b=qm$ 隨て

$a=b+qm,\qquad b=a+(-q)m$

なり．但こゝに $q$ と書けるは正又は負の整數なり．此場合に $a$ を $b$ の剩餘，$b$ を $a$ の剩餘（勿論 $m$ を法として）なりと云ふは，普通の除法に於ける剩餘といふ語の意義を擴張せるなり．實にも $a$ を $m$ にて除して剩餘 $r$ を得たりとせば $a$ と $r$ との差は $m$ の倍數なり，卽ちこゝに謂ふ所の意義に於て $r$ は $m$ を法として $a$ の剩餘なり．

$a$ が與へられたる整數なるときは

$a+mt$

なる數は，$t$ が如何なる整數なりとも，必ず $m$ を法としての $a$ の剩餘なり．$a$ を $m$ にて除して得べき剩餘（除法の剩餘）は卽ち $a+mt$ の如き數の中にて最小なる正の整數に外ならず．故に之を $m$ を法としての $a$ の最小の正の剩餘と云ふ．$r$ が $m$ を法としての $a$ の最小の剩餘なるときは

$r=a+mt_{0},\qquad 0\leqq r<m$

にして

$r'=r-m=a+(m-1)t_{0}$

は其絕對値 $m$ よりも小なる負數なり．さて $r$，$r'$ の中少なくとも一方は絕對値に於て $m$ の半を超えず，唯，$m$ が偶數なる場合に於て $r+r'=0$ なることあり得べし．

$\rho \equiv a{\pmod {m}}\qquad 2|\rho |\leqq m$

なる二個の條件に適する數 $\rho$ を $m$ を法としての $a$ の絕對的最小剩餘と云ふ．

例へば $m$ を $12$ となすときは

$32\equiv 8\equiv -4{\pmod {12}}$

にして $8$ は $32$ の最小の正剩餘，$-4$ は絕對的最小の剩餘なり．又

$-42\equiv -6\equiv 6\qquad {\pmod {12}}$

にして $6$ は $-42$ の最小の正剩餘，又 $6$ も $-6$ も共に $-42$ の絕對的最小の剩餘なり．

$a$ が $m$ の倍數なりといふ事實を

$a\equiv 0{\pmod {m}}$

といふ相合式にて書き表はすことを得べし．

相合式は等式に類似せる性質を有し，加法減法，乘法に關しては恰も等式の如くに取扱ふことを得べし．

一，$a\equiv a',\ b\equiv b'{\pmod {m}}$ ならば $a\pm b\equiv a'\pm b'{\pmod {m}}$ なり．

證，$a-a',\ b-b'$ は共に $m$ の倍數なりと云ふが故に $(a\pm b)-(a'\pm b')$ 卽ち $(a-a')\pm (b-b')$ も亦 $m$ の倍數なり．

同一の數を法とせる二個の相合式を邊々相加へ又は減じて，仍同一の數を法とせる一の相合式を得．乘法につきても亦然り，卽ち

二，$a\equiv a',\ b\equiv b'{\pmod {m}}$ ならば $ab\equiv a'b'{\pmod {m}}$ なり．

證，$a-a'$ は $m$ の倍數なりと云ふが故に $(a-a')b$ 卽ち $ab-a'b$ も亦 $m$ の倍數なり，卽ち

$ab\equiv a'b{\pmod {m}}$

又 $b-b'$ は $m$ の倍數なりと云ふが故に

$a'b\equiv a'b'{\pmod {m}}$

よりて（一）によりて

$ab\equiv a'b'{\pmod {m}}$

一及二の前提を成せる相合式の數二個より多くとも，同樣の定理は必ず成立すべし，一般に

$a\equiv a',\quad b\equiv b',\quad c\equiv c',\ldots {\pmod {m}}$

なるときは

${\mathit {\Sigma }}(ka^{\alpha }b^{\beta }c^{\gamma }\cdots )\equiv {\mathit {\Sigma }}(ka'^{\alpha }b'^{\beta }c'^{\gamma }\cdots ){\pmod {m}}$

こゝに $k$ は任意の整數にして ${\mathit {\Sigma }}$ は其次に書ける如き積若干の和を表はせるものなり．此事實は一及二の直接の結論なり．

斯の如く加法，減法及乘法に關して相合式は等式と同樣の性質を有せりと雖，除法に關しては必しも然らず．例へば

$2\cdot 5\equiv 2\cdot 1{\pmod {8}}$

より兩節を $2$ にて除して

$5\equiv 1{\pmod {8}}$

となすことを得ず．

（二）

十進法に於ける二三特殊の整數の倍數を鑑識する方法は汎く知られたり．

一，$2$ 及 $5$ の倍數，$10$ を超えざる $2$ の倍數は $0$，$2$，$4$，$6$，$8$ にして $10$ も亦 $2$ の倍數なり．今 $10$ を $t$ と書くときは，凡て正の整數は

$A=(a_{m}\cdots a_{2}a_{1}a_{0})=a_{m}t^{m}+\cdots +a_{2}t^{2}+a_{1}t+a_{0}$

と書くことを得，$a_{0},a_{1},a_{2}\ldots a_{m}$ は十より小なる正の整數又は（$a_{m}$ の外は）$0$ なり．$a_{0}$ は $A$ の一位の「數字」なり．さて，$t=0{\pmod {2}}$ なるにより

$A\equiv a_{0}{\pmod {2}}$

よりて $a_{0}$ が $0$，$2$，$4$，$6$，$8$ の中の一つならば

$A\equiv 0{\pmod {2}}$

卽ち $A$ は $2$ の倍數（偶數）にして，然らざるとき卽ち $a_{0}$ が $1$，$3$，$5$，$7$，$9$ の中の一つなるときは，$A$ は $2$ にて整除し得べからざる數（奇數）なり，此場合に於ては

$A\equiv 1{\pmod {2}}$

又 $10$ は $5$ の倍數なるが故に

$A\equiv a_{0}{\pmod {5}}$

にして十以下の數にて $5$ の倍數なるは $0$ 又は $5$ に限れるが故に $A$ の一の位の數字が $0$ 又は $5$ なる場合に限り $A$ は $5$ の倍數なり．

二，$4$ 及 $25$ の倍數，$10$ は $2$ の倍數なるが故に $100$ は $4$ の倍數なり．$100$ を紀數法の基數となすときは $A$ の一の位の係數は $(a_{1}a_{0})=10a_{1}+a_{0}$ にして

$A\equiv (a_{1}a_{0}){\pmod {4}}$

故に $A$ が $4$ の倍數なるべき完全なる條件は $(a_{1}a_{0})$ 卽ち十進法に於ける $A$ の末二位の數字を其儘にとりて作れる數の $4$ の倍數なるべきことなり．例へば

$78657\equiv 57{\pmod {4}}$

にして $57$ は $4$ の倍數にあらず，$57\equiv 1{\pmod {4}}$ よりて

$78657\equiv 1{\pmod {4}}$

$78657$ を $4$ にて除すれば最小の正剩餘として $1$ を得べし．

$25$ を法とせる場合に於ても

$A\equiv (a_{1}a_{0}){\pmod {25}}$

なる相合式成立すべく，是によりて容易に $25$ の倍數を鑑定することを得べし．

三，$9$ の倍數，十進法にて表はされたる正數を $9$ にて除して得べき最小の正剩餘は次の如くにして容易に求め得らるべし．

先づ

$t\equiv 1{\pmod {t-1}}$

なることは明白なり．相合式の乘法によりて之より

$t^{n}\equiv 1{\pmod {t-1}}$

を得．

今

$A=(a_{m}\cdots a_{2}a_{1}a_{0})=a_{m}t^{m}+\cdots +a_{2}t^{2}+a_{1}t+a_{0}$

となすとき

$S_{1}=a_{0}+a_{1}+\cdots +a_{m-1}+a_{m}$

と置かば

$a_{0}t^{m}\equiv a_{0},\ a_{1}t^{m-1}\equiv a_{1},\ldots a_{m}\equiv a_{m}{\pmod {t-1}}$

より

$A\equiv S_{1}{\pmod {t-1}}$

を得．是故に $A$ を $t-1$ にて除して得らるべき最小の正剩餘は，$A$ の凡ての位の數字の和 $S_{1}$ を $t-1$ にて除して得らるべき最小の正剩餘に等し．$S_{1}$ 若し $t-1$ より小ならば $S_{1}$ は卽ち此剩餘にして $S_{1}$ 若し $t-1$ に等しからば $A$ は $t-1$ の倍數なり．$S_{1}$ 若し $t-1$ より大ならば更に $S_{1}$ のすべての位の係數の和 $S_{2}$ を 作りて此の鑑定法を適用すべし．

例．十進法に於て

$A=1234567$

なる數の與へられたるときは

$A=1+2+3+4+5+6+7=28\equiv 10\equiv 1{\pmod {9}}$

にして實際

$1234567=(9\times 137174)+1$

なり．

$3$ は $9$ の約數なるが故に十進法に於ては

$A\equiv S_{1}{\pmod {3}}$

之よりして $3$ の倍數の鑑定法を得．

一般に $t$ を $1$ より大なる整數とするとき，$t$ を基數とせる紀數法にて表されたる數の $t-1$ の倍數なるや否やを鑑識するにも同樣の方法によることを得．

四，$11$の倍數，又は一般に $t$ を基數とせる命數法に於ける $t+1$ の倍數．

先づ

$t\equiv -1{\pmod {t+1}}$

といへる明白なる相合式より一般に

$t^{n}\equiv (-1)^{n}{\pmod {t+1}}$

を得，$(-1)^{n}$ とは $n$ が偶數なるとき $1$，$n$ が奇數なるとき $-1$ といふに同じ．

$A=(a_{m}\cdots a_{2}a_{1}a_{0})=a_{m}t^{m}+\cdots +a_{1}t+a_{0}$

に於て

$D_{1}=a_{0}-a_{1}+a_{2}-\cdots$

と置くときは

$A\equiv D_{1}{\pmod {t+1}}$

故に十進法に於ける $11$ の倍數を鑑定するには次の法則によるべし．

先づ $A$ の最終の位の數字より始めて隔一の位の數字の和を作り，之より其の他の位の數字の和を引きて得たる數を $D_{1}$ と名づくれば，$A$ を $11$ にて除して得べき最小の正剩餘は $D_{1}$ を $11$ にて除して得べき最小の正剩餘に等し．$D_{1}$ 若し $0$ ならば $A$ は $11$ の倍數なり，$D_{1}$ 若し絕對的に $t$ より大ならずして $0$ にあらずば $D_{1}$ 又は $D_{1}$ 若し負ならば $11+D_{1}$ は卽ち求むる所の最小の正剩餘なり．$D_{1}$ が絕對的に $10$ よりも大なる場合に於ては $D_{1}$ につきて同樣なる（$D_{1}$ が負數なる場合には相當の變更をなして）鑑定法を反復すべし．

例へば

$1234567\equiv 7-6+5-4+3-2+1=4{\pmod {11}}$

$1234567=(11\times 112233)+4$

又

$1929090\equiv -9-9+2-9+1=-24{\pmod {11}}$

さて

$-24\equiv -(4-2)=-2{\pmod {11}}$

よりて

$1929090\equiv -2\equiv 9{\pmod {11}}$

實際

$1929090=(11\times 175371)+9$

（三）

此章に於て向後用ふべき文字は，特に其然らざるを明言せざる限り，常に正數を表せるものなりとす．

$a,b,c\ldots$ 等の數のいづれもの倍數なる數を其公倍數と云ふ．$0$ は凡ての數の倍數と見做し得べきものなれども，姑く之を度外に置かんに，$a,b,c\ldots$ の公倍數の必ず而も限なく存在すべきことは明白なり．現に $a,b,c\ldots$ の積又は其倍數は皆 $a,b,c\ldots$ の公倍數なり．さて $a,b,c\ldots$ の公倍數は $a,b,c\ldots$ のいづれよりも小なることを得ざるにより，此等限りなく存在する公倍數の中に最小なるものなかるべからず．之を $a,b,c\ldots$ の最小公倍數と云ふ．凡ての公倍數は最小公倍數の倍數なり．其故如何にといふに，今 $a,b,c\ldots$ の最小公倍數を $m$ と名づけ，$\mu$ を或一個の公倍數となすとき，若し $\mu$ にして $m$ の倍數ならずば，$m$ を以て $\mu$ を除し，剩餘として $m$ より小にして $0$ にはあらざる數 $m'$ を得べし，卽ち

$\mu =q\cdot m+m'$

さて $\mu$，$m$ 共に $a,b,c\ldots$ のいづれにても割り切るゝが故に $m'$ も亦然らざるを得ず，而もこは $m$ が $a,b,c\ldots$ の最小公倍數なるべしとの約束に牴觸せるにあらずや．是によりて次の定理を得．

一，$\mu$ 若し $a,b,c,\ldots$ のいづれにても割り切れなば $\mu$ は亦 $a,b,c\ldots$ の最小公倍數にても割り切れざるを得ず．

$a,b,c\ldots$ のいづれをも割り切る數を其公約數と云ふ．$1$ は必ず $a,b,c\ldots$ の公約數なり．$a,b,c\ldots$ が $1$ を外にして公約數を有せざるときは $a,b,c\ldots$ を公約數なき一組の數と云ふ．公約數なしとは絕て公約數なきにあらず，當然にして極端なる公約數 $1$ を外にしてはこれなしと言ふなり．公約數なき二つの數を相素なる數と云ふ．

$a,b,c\ldots$ の公約數は $a,b,c\ldots$ のいづれよりも大なることを得ざるにより其數に限あり．是故に其中一個最大なる者なかるべからず．之を $a,b,c\ldots$の最大公約數と云ふ．$a,b,c\ldots$ の最大公約數を $d$ と名づけ

$a=a'd,\quad b=b'd,\quad c=c'd\ldots$

となすときは $a',b',c'\ldots$ には $1$ を外にして公約數あることを得ず．如何にとならば若し $a',b',c'\ldots$ に $1$ より大なる公約數あらば其一を $g$ と名づくべし．しかするときは $gd$ は $a,b,c\ldots$ の公約數にして且 $d$ よりも大なり，而もこれ $d$ が $a,b,c\ldots$ の最大公約數なるべしとの約束に反せるに非ずや．$a,b,c\ldots$ の公約數は凡て其最大公約數 $d$ の約數なり．其故如何にといふに，今 $\delta$ を以て公約數の一となさんに $a,b,c\ldots$ は各 $d$ にても亦 $\delta$ にても割り切るゝが故に前に證明せる定理によりて $a,b,c\ldots$ は各 $d$ と $\delta$ との最小公倍數にても亦割り切れざるを得ず．さて $d$ にして若し $\delta$ の倍數ならずば $d$ と $\delta$ との最小公倍數は $d$ よりも大なり．$d$ の $\delta$ にて割り切るゝこと寔に已むを得ざる所也．是によりて次の定理を得．

二，$a,b,c\ldots$ の公約數は其最大公約數の約數なり．最大公約數は凡ての公約數の最小公倍數なり．

$a$，$b$ なる二個の數與へられたるとき，其最小公倍數又は最大公約數を定むるは，$a$，$b$ の順序に關係なき一の算法なり．卽ち此算法は交換の法則に從へり．又 $a$，$b$，$c$ なる三個の數の與へられたるとき其最小公倍數は $a$，$b$，$c$ の順序に關係なき定まりたる數なり．

今 $a$，$b$ の最小公倍數を $m$ と名づけんに，定理一によりて $a$，$b$，$c$ の公倍數は必ず $m$，$c$ の公倍數にして，又 $m$，$c$ の公倍數は必ず $a$，$b$，$c$ の公倍數なり．是故に $a$，$b$，$c$ の最小公倍數は亦 $a$，$b$ の最小公倍數 $m$ と $c$ との最小公倍數に等し．同一の理由によりて $a$，$b$，$c$ の最小公倍數は又 $a$ と $b$，$c$ の最小公倍數との最小公倍數なり．最小公倍數を定むる算法は組み合せの法則に從へり．最大公約數につきても亦同じ．

是故に多くの數の最小公倍數又は最大公約數を求むるに當て，第二章（四）の方法を適用することを得，隨て此算法は畢竟二個の數の最小公倍數又は最大公約數を求むることを反復するに歸着す．

（四）

$a$，$b$ なる二數の最小公倍數を $m$ と名づけ

$m=ka=hb$

となすときは，$a$，$b$ の公倍數の一なる $ab$ といふ數は，$m$ の倍數卽ち $ab$ は $ka$ の倍數なるが故に $b$ は $k$ の倍數，又同樣にして $h$ は $a$ の倍數にして，而も

$a=hg,\quad b=kg,\quad ab=mg$

$g$ は $a$，$b$ の公約數なり．然れども $g$ は亦 $a$，$b$ の最大公約數なり．げにも $h$，$k$ には公約數なし，若し假に $h=h'd$，$k=k'd\ (d>1)$ なりとせば

$m'=k'a=h'b$

は $a$，$b$ の公倍數にして而も $m$ より小なりとの矛盾の結論に陷るべければなり．是故に次の定理を得．

一，二つの數の積は其最大公約數と最小公倍數との積に等し．

ポアンソーはこの論法に極めて趣味ある幾何學的の解釋を與へたり．一の圓周を $a$ 個に等分し，其分點に順次 $0,1,2\ldots a-1$ の番號を附す．さて $0$ より始め $b$ 個每の分點 $0,b,2b\ldots$ を直線にて連結し行くときは，分點の數は $a$ 個に過ぎざるが故に竟には圓周を幾度か廻りたる後，既に一たび通過せる分點に到着せざるを得ず．而も始めて再度逢着する點は必ず $0$ なり．何とならば再度例へば $b$ 點に來り得べきためには其前必ず $0$ 點を經來らざるを得ざればなり．（圖に於ては $a$ を $16$，$b$ を $6$ となせり．）今分點を通過すること $h$ 囘，其間圓周を廻ること $k$ 囘にして $0$ に復歸せりとせば，

$hb=ka$

なり，$hb$ は $b,2b\ldots$ 等の中始めて $a$ の倍數となれるものにして卽ち $a$，$b$ の最小公倍數なり．同時に又 $h$ と $k$ とに公約數なきを知るべし．さて此手續きによりて圓內に一種の正 $h$ 角形を畫き出せり，是故に $a$ は $h$ の倍數なることを知る，$a=hg$ 隨て前の如くにして $a$，$b$ の最大公約數は $g$ なることを知るべし．

此幾何學的の考究より學び得べき，尙一の重要なる事實あり．上に述べたる作圖の中に於て通過せる分點の中（矢の方向に圓周を廻るものとして） $0$ に最も近きは如何なる點ぞや．若し上の作圖に於て逢着せる分點を更に $0$ より圓周上の分布の順序に從ひて直線にて連結し行くときは（圖にて點線にて示せる 如く）卽ち普通の正 $h$ 角形を得べきが故に，此等の分點の中 $0$ に最も近き者は $a:h$ 卽ち $g$ なる番號を帶べるものに外ならず．然るに此點は最初の作圖に於て， $0$ より $b$ 個每の分點に移り行きつゝ到着することを得たる點なるが故に，

$g=h'b-k'a$

の如き關係成立するを知るべし．但此處 $h'$ は $h$ よりも小，又 $k'$ は $k$ よりも小なること勿論なり．幾何學的の假裝を剝奪するときは，此事實は整數論の重要なる定理となる．曰く，$a$，$b$ の最大公約數を $g$ とし，$a=hg$，$b=kg$ となすときは，$h'$ は $h$ よりも，又 $k'$ は $k$ よりも小にして，而も $g=h'b-k'a$ なるが如き整數 $h'$，$k'$ は必ず，而も唯一對に限り，存在す．然れども又上の硏究に於て，$a$ と $b$ との位置を轉倒するも，$g$ は依然として變ずることなきが故に，$h''<h$，$k''<k$ にして而も $g=k''a-h''b$ なるが如き整數 $h''$，$k''$ も必ず，而も唯一對に限り，存在すべきを知るべし．

此等の事實を總括して次の定理を得．

二，$a$，$b$ の最大公約數を $g$ とし $a=hg$，$b=kg$ と置かば

$ax+by=g$

なる方程式に適合すべき正又は負の整數 $x$，$y$ は必ず存在す．就中 $x$ が $k$ より小なる正數にして $y$ が絕對値に於て $h$ より小なる負數なる者（$x=k''$，$y=-h''$）及 $x$ が絕對値に於て $h$ より小なる負數にして $y$ が $k$ より小なる正數なる者（$x=-k'$，$y=h'$）各唯一對に限り存在す．

例へば $a=16$，$b=6$ とせば $g=2$，$h=8$，$k=3$ にして

$16x+6y=2$

の解答の中上文特筆せる二對は $x=2$，$y=-5$ 及 $x=-1$，$y=3$ なり．

吾輩が幾何學的に證明したる事實を直接に論證せんことも亦容易なり．今

$b,2b,\ldots (h-1)b$

を $a$ にて除して得べき剩餘（最小正剩餘，以下同じ）を考へんに此等の剩餘は $nb-qa=r$の如き數なるが故に何れも $a$，$b$ の公約數なる $g$ の倍數なること明白なり．而も此等の剩餘の中相等しき者決してあることなし．何とならば今假に $n$，$n'$ は $1,2,\ldots h-1$ の中より採りたる二個の相異なる數にして，而も $nb-qa=r$，$n'b-q'a=r$ なりとせば，例へば $n>n'$ となすとき，$(n-n')b=(q-q')a$ を得，$b$ に $h$ よりも小なる數 $n-n'$ を乘じて得たる積が旣に $a$ の倍數なりとの許すべからざる結論を生ずべければなり．吾輩の作れる $b-1$ 個の剩餘は皆相異にして，而も盡く $a$ 卽ち $hg$ より小なりと言ふ上は，此等の剩個餘は其全體に於て $g,2g,\ldots (h-1)g$ なる數と同一ならざるを得ず，卽ち其中一つ而も唯一つが $g$ に等しきなり．さて例へば

$h'b-k'a=g$

なりとせば $h'<h$ 隨て $k'<k$ にして定理一は再び證明せられたり．$a$，$b$ を轉倒するも亦同樣の結果に達し得べきこと勿論なり．或は又 $-k'$ を $k$ を以て除して得べき最小正剩餘を $k''$ と名づけ，卽ち $-k'=-k+k'',\ k>k''>0$ と なすときは

$(h'-h)b+(k-k')a=g$

卽ち

$k''a-h''b=g$

にして，$h''=h-h'$ は $h$ より小なる正數なり．

上の定理を特に $g=1$ の場合につきて繰り返すときは次の事實を得．

三，$a$，$b$ が相素なる數なるときは

$ax+by=1$

なる如き正又は負の整數 $x$，$y$ は必ず存在す．而して定理一に述べたる如き二對の特殊なる解答の此場合に於ても亦成立すべきこと勿論なり．

（五）

前節の定理一は特別の場合として次の事實を包括す．

一，$a$，$b$ が相素なるときは，$a$，$b$ の最小公倍數は其積 $ab$ に等し．

此事實より推して更に整數論に於て最重要なる一個の定理を得．曰く

二，$a$，$b$ は相素なる數にして而も $ac$ が $b$ の倍數なるときは，$c$ は必ず $b$ の倍數なり．

證．$a$，$b$ は相素なる數なるが故に，其最小公倍數は $ab$ なり．$ac$ は $b$ の倍數 なるが故に，こは $a$，$b$ の公倍數，隨て其最小公倍數 $ab$ の倍數なり．卽ち $ac=ab\cdot q$ なる如き整數 $q$ は存在す，隨て $c=b\cdot q$ 卽ち $c$ は $b$ の倍數なり．

前節に於て $a$，$b$ の最大公約數を $g$ となすとき

(1)

$ax+by=g$

なる方程式は必ず正又は負の整數 $x$，$y$ によりて解き得らるべきことを證明 し，且 $x$，$y$ の大さに或る制限を設くるとき，斯の如き解答の唯一組に限り存在すべきを說けり．今定理二を用ゐて上の一次不定方程式（一次のヂオフアント方程式）の最完全なる解答を求めんとす．

方程式 (1) の解答許多あり得べき中の一つを $x$，$y$ となすときは

$ax_{0}+by_{0}=g$

なり．よりて一般に凡ての解答は

$a(x-x_{0})=-b(y-y_{0})$

なる條件に適合すべきを知る．さて例によりて $a=hg,\ b=kg$ となすときは $h$，$k$ は相素にして

$h(x-x_{0})=-k(y-y_{0})$

さて $h(x-x_{0})$ は $k$ の倍數にして而も $h$ は $k$ と相素なりといふが故に，二によりて $x-x_{0}$ は $k$ の倍數なり，今

$x-x_{0}=kt,\quad x=x_{0}+kt$

と置かば

$y-y_{0}=-ht,\quad y=y_{0}-ht$

を得．(1) の解答を求めんと欲せば之を

(2)

$\left\{{\begin{array}{ll}x=x_{0}+kt\\y=y_{0}-ht\end{array}}\right.$

の如き數の中より搜り出すべきなり．

然るに $t$ を如何なる整數となすとも此の如き値はよく (1) に適合すべきが故に (2) は凡て (1) の解答なり．

今一般に

(3)

$ax+by=c$

なるヂオフアント方程式を提供するに，此方程式は $c$ が $a$，$b$ の最大公約數 $g$ の倍數なるにあらずば整數の解答を有することを得ず．$c$ が $g$ の倍數にして，例えば $c=gc'$ なるとき，$x_{0}$，$y_{0}$ を (1) の解答とせば

$x=c'x_{0},\quad y=c'y_{0}$

は (3) の一個の解答にして，其一般の解答は

(4)

$\left\{{\begin{array}{ll}x=c'x_{0}+kt\\y=c'y_{0}-ht\end{array}}\right.$

なり．$t$ に相當の値を與へて $x$，$y$ の中一方が $k$ 又は $h$ より小なる正數なる如き唯一組の解答を得．例へば $x$ を $k$ より小なる正の整數となさんと欲せば，$c'x_{0}$ を $k$ にて除して最小の正剩餘を求むべし．

今

$c'x_{0}=k{\overline {t}}+{\overline {x}},\quad k>{\overline {x}}>0$

なりとせば，$t$ を ${\overline {t}}$ となして得たる $y$ の値を ${\overline {y}}$ となし，こゝに一組の解答 $({\overline {x}},{\overline {y}})$ を得．但此場合に於て ${\overline {x}}$ を $k$ より小なる正數となすことを得たりと雖前の如く同時に ${\overline {y}}$ を絕對的に $h$ よりも小となすことを得たりと誤解すること勿れ．

二個以上の未知數を含めるヂオフアント方程式

(5)

$a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+\cdots =c$

も亦 $c$ が $a_{1},a_{2},a_{3}\ldots$ の最大公約數 $g$ の倍數なるときに限り整數の解答を有す．

未知數の數三個なる場合につきて言はんに，先づ $a_{1}$，$a_{2}$ の最大公約數を $d$ と名づくれば

$a_{1}y_{1}+a_{2}y_{2}=d$

は整數の解答を有す．さて $d$ と $a_{3}$ との最大公約數は卽ち $a_{1}$，$a_{2}$，$a_{3}$ の最大公約數 $g$ にして，$c$ は $g$ の倍數なりとせるが故に

$dz+a_{3}x_{3}=c$

は整數の解答を有す．而して

$x_{1}=y_{1}z,\quad x_{2}=y_{2}z,\quad x_{3}$

は卽ち $a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}=c$ の解答なり．

未知數の數三個以上なるときは唯同樣の手續きを幾囘も反復すべきのみ．

特に $a_{1},a_{2},a_{3}\ldots$ に公約數なきときは

(5')

$a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+\cdots =1$

なるが如き正又は負の整數は必ず存在す．

(5) 又は (5') の如きヂオフアント方程式の一般の解答はオイレルの方法によりて求め得べし．今特別なる例題につきて此方法を說明せんとす．

(a)

$357x+238y+204z=17$

の解答を求めんとするに，先づ最小の係數 $204$ を以て其他の係數を除し

$357=2\times 204-51,\qquad 238=1\times 204+34$

を得．よりて

(b)

$2x+y+z=z'$

と置き (a) を次の形となす，

(a')

$-51x+34y+204z'=17$

(a) の解答を求めんと欲せば，先づ (a') の解答 $x$，$y$，$z'$ を求め，さて (b) によりて $z$ を定むれば可なり．

(a') を解かんが爲に $34$ を以て其他の係數を除し，

$-51=-1\times 34-17,\qquad 204=6\times 34$

を得．よりて

(c)

$-x+y+6z'=y'$

と置き，(a') を更に變形して

(a'')

$-17x+34y'=17$

を得．$17$ を以て $34$ を除し $34=2\times 17$ を得，

(d)

$-x+2y'=x'$

と置き (a'') を改めて

(a''')

$17x'=17$

と書く．

最一般なる場合に於ても，與へられたる方程式の左邊を順次變形して遂に (a''') の如く只一個の未知數のみを含める形となすことを得ること明白なり．何とならば，(a)，(a')，(a'')…等の左邊は其生成上漸次小なる整の係數を得べく，又上に述べたる變形の方法は (a)，(a')…等が少なくとも二個の未知數を含める間は必ず繼續することを得べけれはなり．

最後に得たる唯一個の未知數の係數は卽ち與へられたる方程式の左邊の係數の最大公約數なること，容易に悟り得べき所なり．上の例につきて $357$, $238$, $204$ の最大公約數 $17$ に達する演算を再び記さば次の如し．

${\begin{array}{r|r|r|r}357&-51&17&{\underline {17}}\\238&34&34&0\\204&204&0&0\\\end{array}}$

さて (a''') は $x'=1$ なる解答を有す，よりて (d) より

$x=2y'-1$

隨て (c) より

$-2y'+1+y+6z'=y'$ 卽ち $y=3y'-6z'-1$

を得，更に (b) より

$2(2y'-1)+(3y'-6z'-1)+z=z'$ 卽ち $z=-7y'+7z'+3$

を得．此等の結果を集めて

$x=2y'-1,\quad y=3y'-6z'-1,\quad z=-7y'+7z'+3$

を得．$y'$，$z'$ を如何なる整數となすとも此式より生じ來るべき $x$，$y$，$z$ は必ず (a) の解答にして，又 (a) の解答は盡く此式に網羅せらるゝこと明白なり．

例へば $y'=0$，$z'=0$ となすときは

$x=-1,\quad y=-1,\quad z=3$

又 $y'=1$，$z'=0$ となすときは

$x=1,\quad y=2,\quad z=-4$

にして，果して

$-1\cdot 357-1\cdot 238+3\cdot 204=17$

$1\cdot 357+2\cdot 238-4\cdot 204=17$

なり．

（六）

如何なる整數にても割り切るゝ數は $0$ に限り，唯一個の約數のみを有する整數は $1$ に止まれり．

此二個の特異なる數は姑らく之を度外に置くとき，凡て整數は少なくとも二個の約數を有す，其數自身及 $1$ 卽ち是なり．凡ての數の當然有すべき此二個の約數を假の約數と云ひ，此他の約數を眞の約數と云ふ．

$d$ 若し $a$ の約數なるときは $a=d\cdot d'$ なるべき整數 $d'$ は必ず存在し，$d'$ も亦 $a$ の約數なり，$d$，$d'$ は $a$ の約數として相塡補す．$a$ と $a$ とは $a$ の塡補約數なり．凡て整數は必ず少くとも一對の塡補約數を有せり．

塡補約數僅に一對を有するに止まる數，卽ち眞の約數を有せざる數を素數と云ひ，然らざるを合成數と云ふ．$2$，$3$ は素數にして $6$ は合成數なり．

一，整數 $a$ と素數 $p$ とあるとき，$a$ 若し $p$ の倍數ならずば $a$ と $p$ とは相素なり．

其故如何にといふに $a$，$p$ の公約數は必ず $p$ の約數の中につきて之を索めざるを得ずして，$p$ の約數は $p$ 及 $1$ に限ぎれるが故に，$a$ が $p$ の最大公約數は $p$ ならずば $1$ ならざるを得ざるなり．

$a$ 若し素數 $p$ の倍數ならずば，$am$ の $p$ の倍數なるは $m$ が $p$ の倍數なるときに限れり．一般に

二，$a,b,c\ldots$ の積素數 $p$ の倍數なるときは，因子の中少なくとも一は $p$ の倍數ならざるを得ず．

素數ならざる數を合成數と名づけたる所以は其必ず素數因子の積として表はされ得べきによるなり．今之に關する事實を闡明せんが爲に先次の簡短なる定理を證明せんとす．

合成數 $a$ は少くとも一個の素數を眞の約數となす．

$a$ の眞の約數は皆 $a$ より小なるが故に其數に限あり，是故に其中最小なる者必ずあり．$a$ の眞の約數の中最小なるものを $p$ と名づく，今 $p$ の素數なるべきを論じ，以て當面の定理を證せんとす．$p$ 若し素數ならずば $p$ は（$1$ にも又 $0$ にもあらざるにより）合成數にして少くとも一個の眞の約數を有す．$p$ の眞の約數の一を $d$ と名づくれば，$d$ は $p$ より小にして而も又 $a$ の眞の約數なり．卽ち $a$ は $p$ よりも小なる眞の約數を有せざるを得ず．而も是 $p$ に關する約束に牴觸する事實ならずや．

吾輩は更に進みて

三，凡て合成數は必ず素數因子の積として表はし得べきことを證せんとす．$a$ の素數因子の一を $p$ と名づけ $a=pa'$ と置く．$a'$ 若し素數ならは吾輩の定理旣に成立せり．$a'$ 若し合成數ならば $a'$ の素數因子の一を $p'$ と名づけ $a'=p'a''$ と置くときは $a=pp'a''$ を得．次第に斯の如く考へ行くに $a,a',a''\ldots$ は順次減少するが故に，斯の如き手續きは限なく繼續せらるゝことを得ず．而も其究極する所は卽ち吾輩の定理の成立する時にして畢竟

$a=pp'p''\cdots$

を得．此處 $p,p',p''\ldots$ と稱するは何れも素數なれども，其記號異なるが爲に此等の素數も亦盡く異なりと速斷すべからざること論を俟たず．若し $p,p',p''\ldots$ 等の中より相等しきものを盡く集めて冪となすときは

$a=p^{\pi }q^{\chi }r^{\rho }\cdots$

の如き形を得，此處にては，$p,q,r\ldots$ は相異なる素數を表はせり．

吾輩は凡て合成數の必ず素數冪に分解せられ得べきことを證明せり．然れども $a$ の與へられたるとき此の如き分解は唯一通りに限らるべきや否やは未知の問題なり．今や進で此重大なる問題を解決せんとす．

四，凡て合成數の素數因子分解は唯一なり．

假に $a$ を素數因子に分解して二樣の結果を得たりとし，

$a=pp'p''\cdots =qq'q''\cdots$

と置かんに，先 $a$ 卽ち $pp'p''\cdots$ は素數 $q$ にて割り切るゝにより $pp'p''\cdots$ の中少くとも一は $q$ にて割り切れざるを得ず（定理二）

例へば $p$ は $q$ の倍數なりとせんに $p$ も亦素數なるが故に $p$ は $q$ に等しからざるを得ず．是故に上の式より

$p'p''\cdots =q'q''\cdots$

を得．之に同樣の論法を適用して例へば $p'=q'$ を得，次第に斯の如くにして 結局上の定理の證明を完くすべし．

凡て合成數が素數の積として表はされ得べきのみならず，此分解が唯一樣に限れりといふは，整數論に於ける最重要なる事實にして，又此事實の證明が（五）の定理二を根據とせることは深長なる意義を包藏す．

整數の中より素數を撰み出す方法は既に古希臘の數學者の知れる所にして，所謂エラトステネスの篩是なり．

${\begin{array}{rrrrrrrrrr}&2&3&{\underline {4}}&5&{\underline {6}}&7&{\underline {8}}&{\underline {9}}&{\underline {10}}\\11&{\underline {12}}&13&{\underline {14}}&{\underline {15}}&{\underline {16}}&17&{\underline {18}}&19&{\underline {20}}\end{array}}$

整數を自然の順序に書き列べ先づ $1$ を去るとき，最初に殘れる數 $2$ は素數なり．何とならば $2$ に眞の約數あらば，そは $2$ より小なる整數にして，$2$ より小なる整數は $1$ を外にして之なければなり．さて $2$ より二つ目每の數 $4,6,8,10\ldots$ に符標を附すべし．$2$ の次に符標を帶ばざる數は $3$ にして，$3$ は素數なり，何とならば $3$ に眞の約數あらば，そは $2$ ならざるを得ず，然れども $3$ に符標なきは其 $2$ の倍數に非ざるを示せばなり．さて $3$ より三つ目每の數に符標を附し，殘れる最初の數 $5$ の素數なるを知り，$5$ より五つ目每の數に符標を附し，斯の如く進みて遂に $p$ なる素數に達したりとせよ．さて此時 $p^{\pi }$ 以下の數にして未だ符標を帶ばざるものは盡く素數なり．例へば $a$ を符標なき數の一となさんに，$a$ にして若し合成數ならんには，其塡補眞約數の一對を $d$，$d'$ となすときは，$a$ は $p'$ より小なるが故に $d$，$d'$ の中少とも一方は $p$ より小なり，隨て $a$ は $p$ より小なる素數（$d$，$d'$ 又は其約數）にて割り切れざるを得ず，而も $a$ に符標なきは其然らざるを示すに非ずや．

素數の數に限なきことも亦古希臘人の知れる所にしてユークリツドの證明は甚だ有名なり．

假に素數の數に限ありとせよ，凡ての素數の連乘積に $1$ を加へ

$2\cdot 3\cdot 5\cdots p+1$

なる數を作りて考ふるに，此數若し素數ならば，是 $2,3\ldots p$ 以外仍ほ素數あるなり．又若し此數合成數なりとするも其素數因子は $2,3,5\ldots p$ の中にはなし，何となれば上に揭げたる數を $2,3\ldots p$ の何れにて割るも剩餘 $1$ を得べければなり．素數の數に限ありとの主張は保持すべからず．

（七）

整數 $a$ を素數羃に分解して

$a=p^{\pi }q^{\chi }r^{\rho }\cdots$

なる結果を得たりとするときは，$a$ の約數は凡て

$d=p^{\pi '}q^{\chi '}r^{\rho '}\cdots$

の如き形をなし，$\pi '$ は $0$ より $\pi$ まで，$\chi '$ は $0$ より $\chi$ まで，又 $\rho '$ は $0$ より $\rho$ までの中の整數なり．此故に $a$ の約數の表を作らんとせば，$d$ の式に於て $\pi ',\chi ',\rho '\ldots$ に順次此等の整數の値をあらゆる組み合せに於て配與すれば則ち可なり．

今二個以上の數 $a,a'\ldots$ につきて說かんが爲に，此等の數の中少くとも何れか一つに因子として關係せる素數を盡く採り，之を $p,q,r\ldots$ と名づけ

${\begin{aligned}a&=p^{\pi }q^{\chi }r^{\rho }\cdots \\a'&=p^{\pi '}q^{\chi '}r^{\rho '}\cdots \\a''&=p^{\pi ''}q^{\chi ''}r^{\rho ''}\cdots \end{aligned}}$

と置く．但し $\pi ,\pi ',\pi ''\ldots$，$\chi ,\chi ',\chi ''\ldots$ 等は一般に正の整數なれども其中 $0$ なるものも亦あり得べしとなさゞるを得ず，或數の分解を示せる式の中、或素數の指數の $0$ なるは，卽ち其素數が實は此數の約數に非ざることを示せり．又 $d$ を $a,a',a''\ldots$ の公約數とし

$d=p^{P}q^{Q}r^{R}\cdots$

と置かば，$P$ は $\pi ,\pi ',\pi ''\ldots$ の何れよりも大ならず，$Q$ は $\chi ,\chi ',\chi ''\ldots$ の何れよりも大ならず．是故に $a,a',a''\ldots$ の最大公約數 $g$ を得んと欲せば

$g=p^{m}q^{m'}r^{m''}\cdots$

に於て $m$ をば $\pi ,\pi ',\pi ''\ldots$ の何れよりも大ならざる範圍內に於て成るべく大に，卽ち $m$ を $\pi ,\pi ',\pi ''\ldots$ の中最小の數に等しくなし，又 $m'$ を $\chi ,\chi ',\chi ''\ldots$ の中最小の數に，$m''$ を $\rho ,\rho ',\rho ''\ldots$ の中最小の數に等しくせば可なり．

又 $a,a',a''\ldots$ の公倍數

$v=p^{P'}q^{Q'}r^{R'}\cdots$

にありては $P'$ は $\pi ,\pi ',\pi ''\ldots$ の何れよりも，又 $Q'$ は $\chi ,\chi ',\chi ''\ldots$ の何れよりも小ならず．故に $a,a',a''\ldots$ の最小公倍數

$l=p^{M}q^{M'}r^{M''}\cdots$

を得んと欲せば，$M$ を $\pi ,\pi ',\pi ''\ldots$ の中最大なる者に，又 $M'$ を $\chi ,\chi ',\chi ''\ldots$ の中最大なる者に…等しからしむるを要す．

例一，$60=2^{2}\cdot 3\cdot 5$ の凡ての約數を作らんと欲せば

$d=2^{\pi '}\cdot 3^{\chi '}\cdot 5^{\rho '}$

に於て $\pi '$ を $0$，$1$，$2$，$\chi '$ を $0$，$1$，$\rho '$ を $0$，$1$ の中より，あらゆる組み合はせに撰み出さゞるべからず，其結果は次の如し．

${\begin{array}{l|rrrrrrrrr}\pi '&0&1&2&0&1&2&0&1&2\\\chi '&0&0&0&1&1&1&1&1&1\\\rho '&0&0&0&0&0&0&1&1&1\\\hline d&1&2&4&8&6&12&15&30&60\end{array}}$

例二，$60=2^{2}\cdot 3\cdot 5$，$72=2^{3}\cdot 3^{2}$ の最大公約數及最小公倍數を求めて次の結果を得．

$\left.{\begin{aligned}&p=2,&&q=3,&&r=5\\&\pi =2,&&\chi =1,&&\rho =1\\&\pi '=3,&&\chi '=2,&&\rho '=0\\&m=2,&&m'=1,&&m''=0\\&M=3,&&M'=2,&&M''=1\end{aligned}}\ \ \right\}\ \ {\begin{array}{c}g=2^{2}\cdot 3^{1}\cdot 5^{0}=12,\\l=2^{3}\cdot 3^{2}\cdot 5=360.\end{array}}$