整数問題

    更新日時 2021/03/11

    連続するn個の整数の積と二項係数

    整数論の有名な公式:

    連続する nn 個の整数の積は n!n! の倍数である。

    上記の公式について,3通りの証明を紹介します。

    → 連続するn個の整数の積と二項係数

    ルジャンドルの定理(階乗が持つ素因数のべき数)

    ルジャンドルの定理:

    n!n! に含まれる素因数 pp の数は以下の式で計算できる:

    i=1npi=np+np2+np3+{\displaystyle \sum_{i=1}^{\infty}\Big\lfloor \dfrac{n}{p^i} \Big\rfloor}=\Big\lfloor \dfrac{n}{p} \Big\rfloor+\Big\lfloor \dfrac{n}{p^2} \Big\rfloor+\Big\lfloor \dfrac{n}{p^3} \Big\rfloor+\cdots

    ただし,x\lfloor x \rfloorxx を超えない最大の整数を表す。

    → ルジャンドルの定理(階乗が持つ素因数のべき数)

    無限降下法の整数問題への応用例

    このページでは,無限降下法について解説します。

    • 無限降下法とは何か?

    • 無限降下法の簡単な応用例:3\sqrt{3} が無理数であることの証明

    • 無限降下法の難しい応用例:フェルマーの最終定理の n=4n=4

    → 無限降下法の整数問題への応用例

    ピタゴラス数の求め方とその証明

    ピタゴラス数とは,直角三角形の3辺の長さとなるような3つの整数の組のことです。例えば,3辺の長さが (3,4,5)(3,4,5) であるような直角三角形が存在するので,(3,4,5)(3,4,5) はピタゴラス数です。

    → ピタゴラス数の求め方とその証明

    オイラーのファイ関数のイメージ

    オイラーのファイ関数:

    自然数 nn に対して,11 から nn までの自然数の中で nn と互いに素なものの数 ϕ(n)\phi(n) は,

    ϕ(n)=ni=1k(11pi)\phi(n)=n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)

    ただし,pip_inn の素因数。

    オイラーの ϕ\phi 関数(トーシェント関数)についての話です。

    → オイラーのファイ関数のイメージ

    ユークリッドの互除法の証明と不定方程式

    ユークリッドの互除法(ごじょほう)とは,大きな数字たちの最大公約数を素早く計算する方法です。

    この記事では, ユークリッドの互除法のやり方ユークリッドの互除法の不定方程式への応用方法 などを解説します。

    → ユークリッドの互除法の証明と不定方程式

    一次不定方程式ax+by=cの整数解

    不定方程式とは,3x+5y=23x+5y=2 のように,方程式の数よりも未知変数の数が多いような方程式のことです。

    この記事では,ax+by=cax+by=c という不定方程式の整数解について,重要な定理の証明と,実際に不定方程式の一般解を求める方法を説明します。

    → 一次不定方程式ax+by=cの整数解

    フェルマーの小定理の証明と例題

    フェルマーの小定理:

    pp が素数,aa が任意の自然数のとき

    apa(modp)a^{p}\equiv a \pmod{p}

    特に pp が素数で,aapp と互いに素な自然数のとき

    ap11(modp)a^{p-1}\equiv 1\pmod{p}

    → フェルマーの小定理の証明と例題

    平方剰余と基本的な問題

    平方数に関する重要な性質:

    1:平方数を3で割った余りは必ず0か1。余りが2になることはない。

    2:平方数を4で割った余りは必ず0か1。余りが2か3になることはない。

    → 平方剰余と基本的な問題

    因数分解公式(ソフィージェルマンの恒等式)

    ソフィー・ジェルマン(Sophie Germain)の恒等式:

    a4+4b4=(a2+2ab+2b2)(a22ab+2b2)a^4+4b^4=(a^2+2ab+2b^2)(a^2-2ab+2b^2)

    一見因数分解不可能な式も因数分解できるので,整数問題で威力を発揮します。

    → 因数分解公式(ソフィージェルマンの恒等式)

    フェルマー数とその性質

    非負の整数 nn を用いて Fn=22n+1F_n=2^{2^n}+1 と表される整数をフェルマー数と呼ぶ

    フェルマー数には様々な性質があります。このページでは特に重要な性質を3つ紹介します。

    → フェルマー数とその性質

    ウィルソンの定理とその2通りの証明

    ウィルソン(Wilson)の定理:

    22 以上の整数 pp について,pp が素数     (p1)!1(modp)\iff (p-1)!\equiv -1 \pmod{p}

    → ウィルソンの定理とその2通りの証明

    クロネッカーの稠密定理とその証明

    クロネッカーの稠密定理:

    任意の無理数 xx0a<b10\leq a <b\leq 1 を満たす任意の実数 a,ba, b に対して a{nx}ba \leq \{nx\} \leq b を満たす自然数 nn が存在する。

    {X}\{X\}XX の小数部分という意味です。

    → クロネッカーの稠密定理とその証明

    ペル方程式に関する基本的な性質まとめ

    整数 xxyy に関する不定方程式: x2dy2=1x^2-dy^2=1 をペル方程式と言う

    ペル方程式について入試レベルで知っておくと便利な知識を整理しました。

    → ペル方程式に関する基本的な性質まとめ

    中国剰余定理の証明と例題(二元の場合)

    中国剰余定理(二元の場合):

    n1n_1n2n_2 が互いに素なとき,

    xa1(modn1),x\equiv a_1 \pmod{n_1},

    xa2(modn2)x\equiv a_2 \pmod{n_2}

    を満たす xx00 以上 n1n2n_1n_2 未満の範囲に唯1つ存在する。

    連立合同式,中国剰余定理の本質的な部分を理解するためにこのページでは二元の場合で n1,n2n_1, n_2 が互いに素な場合のみを考えます。より一般の場合は→中国剰余定理と法が互いに素でない場合への拡張

    → 中国剰余定理の証明と例題(二元の場合)

    中国剰余定理と法が互いに素でない場合への拡張

    中国剰余定理(一般の場合):

    ni(i=1,2,,k)n_i\: (i=1,2,\cdots, k) たちが互いに素なとき,kk 本の連立合同式

    xai(modni)x\equiv a_i \pmod{n_i}

    を満たす xx0x<n1n2nk0\leq x <n_1n_2\cdots n_k の範囲にただ1つ存在する。

    → 中国剰余定理と法が互いに素でない場合への拡張

    原始根の定義と具体例(高校生向け)

    原始根の定義:

    33 以上の)素数 pp11 以上 pp 未満の整数 rr が以下の性質を満たすとき rr を法 pp に対する原始根と呼ぶ。

    r,r2,,rp2r,r^2,\cdots,r^{p-2} のいずれもが pp で割って余り 11 でない」

    (また,r=1r=1p=2p=2 に対する原始根である,とする。)

    → 原始根の定義と具体例(高校生向け)

    フェルマーの二平方和定理

    定理: 22 つの整数 x,yx,y を用いて n=x2+y2n=x^2+y^2 と表される

    nn を素因数分解したときの 4k+34k+3 型の素数の指数が全て偶数

    高々2つの整数の二乗和で表される整数はどんなものか?という疑問に答える非常に有名な定理です。

    → フェルマーの二平方和定理

    完全数の一覧と性質

    完全数 とは「約数の総和が自分の2倍になる」ような正の整数のことです。

    → 完全数の一覧と性質

    数オリのテクニック〜Vieta jumping〜

    Vieta jumping

    ある文字について二次式であるような不定方程式を,解と係数の関係を用いて解くテクニック

    数学オリンピックの不定方程式の中でも難し目の問題に使えるテクニックです。

    → 数オリのテクニック〜Vieta jumping〜

    約数の個数の公式と平方数の性質

    約数の個数を求める公式:

    約数の個数は「素因数分解して」「それぞれの指数に1を足して」「全部かけあわせる」ことで計算することができます。

    約数の個数の公式について,計算例や証明を説明します。また,この公式から導ける平方数に関する重要な定理を解説します。

    → 約数の個数の公式と平方数の性質

    位数の性質と原始根の応用

    位数の性質: modp\mathrm{mod}\:p における aa の位数を nn とする。

    am1modpa^m\equiv 1\:\mathrm{mod}\:p を満たすなら mmnn の倍数である。

    位数や原始根の話題は高校範囲を逸脱しますが,整数論の様々な定理の証明に役立ちます。上記の性質は特によく使うものです。

    → 位数の性質と原始根の応用

    ガウス記号の定義と3つの性質

    ガウス記号

    実数 xx に対して,nx<n+1n\leq x <n+1 なる整数 nn がただ一つ存在するので,その nnx\lfloor x\rfloor と書く。

    例: 2.1=2\lfloor 2.1\rfloor=23=3\lfloor 3\rfloor=32.3=3\lfloor -2.3\rfloor=-3

    ガウス記号,フロアー関数,床関数,整数部分,など様々な呼び方があります。また,x\lfloor x\rfloor ではなく [x][x] と書くこともあります(むしろ大学入試では後者の記号を用いることが多い)。

    → ガウス記号の定義と3つの性質

    素数の逆数和が発散することの証明

    素数の逆数和 12+13+15+17+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{7}+\cdots は発散する。

    非常に美しい結果です。一見難しそうですが,初等的に(高校数学の範囲で)示せます。

    → 素数の逆数和が発散することの証明

    整数論の美しい定理7つ

    整数論(数論)の美しい7つの定理を紹介します。素数にまつわる定理が多いです。いずれも証明は難しいので定理の鑑賞にとどめておきます。

    → 整数論の美しい定理7つ

    数オリの整数論(難問)に対するテクニック

    数学オリンピックの整数問題の中でも難問〜超難問レベルに対してときどき使う,有名なテクニックを解説します。 pp 進付値,オーダーの話,Lifting The Exponent Lemma,LTEの補題,などと言われているものです。

    JMO本選以降の対策にどうぞ。

    → 数オリの整数論(難問)に対するテクニック

    約数の総和を求める二つの公式と証明

    正の整数の約数の総和を表す公式を二つ紹介します。一つ目は入試でも頻出の必須公式です。

    二つ目はコサインとか出てくる観賞用の公式です。玄人向け。

    → 約数の総和を求める二つの公式と証明

    素因数分解の一意性とその証明について

    素因数分解の一意性: 全ての正の整数は素数の積として(順番を除いて)一意に表せる。

    算術の基本定理とも呼ばれる重要な定理です。 一見当たり前ですが実は当たり前ではありません。きちんと証明しようとするとけっこう大変です。

    → 素因数分解の一意性とその証明について

    フロベニウスの硬貨交換問題

    AABB が互いに素なとき,AA 円の硬貨と BB 円の硬貨を使って支払えない金額の最大値は (ABAB)={(A1)(B1)1}(AB-A-B)=\{(A-1)(B-1)-1\} 円。

    フロベニウスの硬貨交換問題(硬貨が二種類の場合)についての美しい結果とその証明の解説。

    → フロベニウスの硬貨交換問題

    リーマン予想の意味,素数分布との関係

    リーマン予想:ゼータ関数の非自明な零点の実部は 12\dfrac{1}{2} である。

    自明な零点(ゼロ点)とは?リーマン予想に関して現在分かっている基本的なこと,素数との関係,暗号との関係について。

    → リーマン予想の意味,素数分布との関係

    エラトステネスのふるいとその計算量

    エラトステネスのふるい:nn 以下の素数を全て見つけ出す高速な方法。

    エラトステネスの篩(ふるい)の概要と,愚直に計算するよりも速いこと(計算量が O(nloglogn)O(n\log\log n) であること)を解説します。

    → エラトステネスのふるいとその計算量

    平方剰余の相互法則の意味と応用

    平方剰余の相互法則(など)を用いることで,与えられた素数 pppp未満の非負整数aaに対してpp で割って aa 余るような平方数が存在するか否かを素早く判定することができる。

    平方剰余の相互法則の意味と応用について解説します。

    → 平方剰余の相互法則の意味と応用

    レイリーの定理とその自然な証明

    レイリー(Rayleigh)の定理

    1r+1s=1\dfrac{1}{r}+\dfrac{1}{s}=1 を満たす正の無理数 r,sr,s に対して以下が成立する。

    全ての正の整数は二つの数列

    mr(m=1,2,3)\lfloor mr\rfloor \:(m=1,2,3\cdots)

    ns(n=1,2,3)\lfloor ns\rfloor \:(n=1,2,3\cdots)

    のいずれかに必ず一回だけ登場する。

    → レイリーの定理とその自然な証明

    最大公約数と最小公倍数の積の性質の2通りの証明

    最大公約数と最小公倍数の関係:

    正の整数 a,ba,b に対して,それらの最大公約数を gg ,最小公倍数を ll とおくと ab=glab=gl

    (最大公約数と最小公倍数の積がもとの二つの数の積に等しい)

    → 最大公約数と最小公倍数の積の性質の2通りの証明

    フェルマーの最終定理

    フェルマーの最終定理:

    nn を3以上の整数とするとき,xn+yn=znx^n+y^n=z^n を満たす正の整数 x,y,zx,y,z の組は存在しない。

    この記事では,フェルマーの最終定理について,高校数学の範囲で簡単に紹介します。

    → フェルマーの最終定理

    互いに素の意味と関連する三つの定理

    互いに素とは,2つの整数の最大公約数が1であることを言う。例えば,3355 の最大公約数は 11 なので,3355 は互いに素。

    「互いに素」の意味と,関連する定理を解説します。定理1,2は基本的な内容ですが,定理3は数学マニア向け(美しい!)です。

    → 互いに素の意味と関連する三つの定理

    双子素数にまつわるいくつかの話題

    ppp+2p+2 がいずれも素数であるときそれらを双子素数と言う。

    (3,5)(3,5)(5,7)(5,7)(11,13)(11,13) などが双子素数です。

    → 双子素数にまつわるいくつかの話題

    ナルシシスト数について

    ナルシシスト数(Narcissistic Number)の意味,有限個しかないことの証明などを解説します。

    → ナルシシスト数について

    メビウスの反転公式の証明と応用

    前半は準備(メビウス関数の定義,簡単な性質)です。後半はメビウスの反転公式という美しい定理とその応用例を解説します。

    → メビウスの反転公式の証明と応用

    正多角形の作図可能性の条件

    nn 角形が定規とコンパスで作図可能     \iff

    n=2Np1pkn=2^Np_1\cdots p_k となる 00 以上の整数 NN と互いに異なるフェルマー素数 p1,,pkp_1,\cdots,p_k が存在する。

    → 正多角形の作図可能性の条件

    ゴールドバッハ予想と関連する命題

    命題1(ゴールドバッハ予想):

    22 より大きな偶数は2つの素数の和で表すことができる。

    命題1が真なのか偽なのかは分かっていません。整数論における有名な未解決問題です。

    → ゴールドバッハ予想と関連する命題

    Lucasの定理とその証明

    Lucasの定理:

    任意の素数 pp と非負整数 m,nm,n に対して,

    mCni=0kmiCni(modp)\displaystyle{}_{m}\mathrm{C}_{n}\equiv\prod_{i=0}^k{}_{m_i}\mathrm{C}_{n_i}\pmod{p}

    ただし,mkmk1m1m0m_km_{k-1}\cdots m_1m_0mmpp 進数表示,nknk1n1n0n_kn_{k-1}\cdots n_1n_0nnpp 進数表示。

    なお,mnm\geq n のときは mCn=m!n!(mn)!{}_{m}\mathrm{C}_{n}=\dfrac{m!}{n!(m-n)!} ですが,このページではさらに m<nm < n のときは mCn=0{}_{m}\mathrm{C}_{n}=0 とします。

    → Lucasの定理とその証明

    カプレカ数(特に3桁の場合)について

    3桁のカプレカ数は 495495 のみである。

    4桁のカプレカ数は 61746174 のみである。

    カプレカ数の意味,および関連する性質について解説します。

    → カプレカ数(特に3桁の場合)について

    クンマーの定理とその証明

    クンマーの定理(Kummer's theorem)

    mCn{}_m\mathrm{C}_n が素数 pp で割り切れる回数は mnm-nnnpp 進数表示して足し算をしたときの繰り上がりの回数と等しい。

    整数の美しい定理です!

    → クンマーの定理とその証明

    リウヴィル数の具体例と性質

    以下を満たす実数 rr をリウヴィル数(リュービル数)と言う:

    任意の正の整数 nn に対して,ある正の整数 p,q(q2)p,q\:(q\geq 2) が存在して

    0<rpq<1qn0< \left|r-\dfrac{p}{q}\right| < \dfrac{1}{q^n} を満たす。

    定義がやや複雑ですが「 rr が有理数 pq\dfrac{p}{q} でかなり精度よく近似できる」というイメージです。

    → リウヴィル数の具体例と性質

    円分多項式とその性質

    ζn=e2πin=cos2πn+isin2πn\zeta_n=e^{\frac{2\pi i}{n}}=\cos \dfrac{2\pi}{n}+i\sin\dfrac{2\pi}{n}nn 乗して 11 になる数のうちの一つ)とおく。多項式

    Fn(x)=kAn(xζnk)F_n(x)=\displaystyle\prod_{k\in A_n} (x-\zeta_n^k)

    を円分多項式(円周等分多項式)と言う。

    ただし,AnA_n11 以上 nn 以下の整数で,nn と互いに素なもの全体の集合です。

    → 円分多項式とその性質

    ガウス整数とその応用

    整数 a,ba,b を用いて a+bia+bi と表される複素数をガウス整数(複素整数)と呼ぶ。

    → ガウス整数とその応用

    レプユニット数

    全ての桁が 11 である整数をレプユニット数と言う。

    111111111111 などです。Rep(繰り返し)Unit(11 )という意味です。

    → レプユニット数

    フォードの円

    フォードの円

    中心が (qp,12p2)\left(\dfrac{q}{p},\dfrac{1}{2p^2}\right) で直径が 1p2\dfrac{1}{p^2} である円を並べると美しい。

    フォードの円と呼ばれる美しい円たちについて紹介します。

    → フォードの円

    数列における余りの周期性(特にフィボナッチ数列)

    数列における余りの周期性について,以下の2つの話題を紹介します。

    • 漸化式で表される数列における,割り算の余りの周期性(受験レベル)

    • 特に,フィボナッチ数列における周期について(難しい)

    → 数列における余りの周期性(特にフィボナッチ数列)

    原始ピタゴラス数の木

    定理:

    すべての原始ピタゴラス数は,(345)\begin{pmatrix}3\\4\\5\end{pmatrix} に対して,3つの行列 A,B,CA,B,C のどれかをかける操作を何度か繰り返すことで作れる。ただし,

    A=(122212223)A=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix}

    B=(122212223)B=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix}C=(122212223)C=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}

    ピタゴラス数に関する非常におもしろい定理です。この定理の主張と証明を詳しく解説します。

    → 原始ピタゴラス数の木

    n進法・n進数の解説と問題例

    n進法とは,n種類の記号を用いて数を表現する方法。また,n進法で表された数をn進数という。

    n進法は「n進位取り記数法」とも呼ばれます。

    → n進法・n進数の解説と問題例