NumberTheory`NumberTheoryFunctions`

このパッケージには数論分野で便利な種々の関数が含まれている．これらの関数に関連した数学的な詳細情報はG. H. Hardy，E. M. Wright共著「An Introduction to the Theory of Numbers」（Oxford University Press出版，1988），D. E. Knuth著「Seminumerical Algorithms」（Addison-Wesley出版，1981），E. Grosswald著「Representations of Integers as Sums of Squares」（Springer出版，1985），H. Cohen著「A Course in Computational Algebraic Number Theory」（Springer-Verlag出版，1993）等の参考文献を参照されたい．

平方因子のテスト

SquareFreeQ[n]はが平方の素因数を持つかどうかを確認する．これはを計算し，結果がゼロであるかどうかを見て行われる．ゼロの場合はは無平方ではなく，ゼロでない場合は無平方である．MoebiusMu[n]の計算を行うと，の最小の素因数が求められる．が以下の小さな素因数を持つ場合は，この計算は非常に速い．持たない場合は，を求めるのにFactorIntegerが使われる．

パッケージをロードする．

In[1]:= <<NumberTheory`NumberTheoryFunctions`

次の素数の積は平方因子を含まない．

In[2]:= SquareFreeQ[2*3*5*7]

Out[2]=

は平方数で割り切れる．

In[3]:= SquareFreeQ[60]

Out[3]=

SquareFreeQは大きな整数にも対応できる．

In[4]:= SquareFreeQ[2^101 - 1]

Out[4]=

次の素数を求める

NextPrime[n]はである最小のを，PreviousPrime[n]はである最大のを求める．20桁未満のについては，このアルゴリズムはより大きい奇数にPrimeQを適用して直接探す．20桁より大きいについては，アルゴリズムは小さなふるいを作り，PrimeQを使う前にまず候補となる素数が小さな素数で割り切れるかどうかを確認する．これは直接検索するよりわずかに速いと考えられている．

より大きい最初の素数．

In[5]:= NextPrime[10]

Out[5]=

大きな数についても，比較的素早く計算できる．

In[6]:= NextPrime[10^100]//Timing

Out[6]=

より小さい最大の素数を求める．

In[7]:= PreviousPrime[34]

Out[7]=

Random[Prime, range]については，ランダムな素数は，まずがその範囲内のランダムな整数を求め，次にである最小の素数を計算して求められる．がその範囲外である場合は，その範囲内の素数が見付かるまで処理が繰り返される．指定の範囲に素数が存在しない場合は，入力は評価されずに返され，警告メッセージが表示される．

からまでの間の素数．

In[8]:= Random[Prime, {10, 100}]

Out[8]=

素数を使った操作

の素因数のリスト．

In[9]:= PrimeFactorList[713]

Out[9]=

最小の素因数は直接求めることができる．

In[10]:= LeastPrimeFactor[713]

Out[10]=

PrimeFactorListは有理数について使う．

In[11]:= PrimeFactorList[78/41]

Out[11]=

PrimePowerQのアルゴリズムは，まずの最小の素因数を計算し，次にが得られるまで（この場合はは素数のベキ乗），または可能な限り（この場合はは素数のベキ乗ではない）による除算を試みる．

1つの素数のベキ乗である数．

In[12]:= PrimePowerQ[12167]

Out[12]=

これは素因数のリストに要素が1つしか含まれていないことから確認できる．

In[13]:= PrimeFactorList[12167]

Out[13]=

連立合同式の解法

中国人の余剰定理(Chinese Remainder Theorem)」によると，連立合同式のある特定のクラスには常に解が存在する．ChineseRemainder[, ]を使うと，Mod[r, ]がである非負の最小の整数が求められる．解はの要素の最小公倍数の唯一のモジュロである．ChineseRemainderのコードはマカラスター大学 (Macalaster College)のStan Wagon氏より無料で提供されている．

次の式は，，およびであることを示している．

In[14]:= ChineseRemainder[{0, 1, 2}, {4, 9, 121}]

Out[14]=

結果を検証する．

In[15]:= Mod[244, {4, 9, 121}]

Out[15]=

このルーチンは長いリストについても極めて速く計算を行う．

In[16]:= ChineseRemainder[Range[20], Prime[Range[20]]]

Out[16]=

モジュロnの平方根

SqrtMod[d, n]はの平方根を計算する．つまり，である非負の最小の整数が存在するならを返すということである．

指定のとについて，となるが存在しないこともある．明らかには完全平方でなければならない．そのため，解が存在するためにはJacobiSymbol[d, n]が1とならなければならない．これはが素数の場合は十分条件でもある．が素数である場合に用いられるアルゴリズムはShanksにより発見された．

の平方根は唯一である必要はない．SqrtModは2乗するとに等しくなる，より小さい非負の最小の整数を返す．SqrtModListはこの関係を満たす整数をすべて返す．

がと等しくなるような非負の最小の整数を求める．

In[17]:= SqrtMod[3, 11]

Out[17]=

結果を検証する．

In[18]:= Mod[5^2, 11]

Out[18]=

関係を満たす11未満のすべての整数を返す．

In[19]:= SqrtModList[3,11]

Out[19]=

がモジュロの平方根を持たない場合は，SqrtMod[d, n]は評価されない．SqrtModList はこの場合，空のリストを返す．

In[20]:= SqrtMod[3, 5]

Out[20]=

3が2乗のモジュロ5でないことを示す．

In[21]:= Mod[{0, 1, 2, 3, 4}^2, 5]

Out[21]=

大きなモジュロについても，平方根は比較的素早く計算できる．

In[22]:= SqrtMod[2, 10^64 + 57]//Timing

Out[22]=

SqrtMod[d, n]のには合成数も適用できる．

In[23]:= SqrtMod[3, 11^3]

Out[23]=

このアルゴリズムはを因数分解するので，SqrtMod[d, n]は非常に大きい合成数については結果を返さないこともある．

原始根の計算

PrimitiveRoot[n]は積のにおいて，相対的に素である数のグループの生成元を返す．生成元はが2，4，奇数の素数のベキ乗，または奇数の素数のベキ乗の2倍である場合にのみ存在する．アルゴリズムは決定論的で，FactorIntegerを使う．が素数または素数のベキ乗の場合は，正の最小の原始根が返される．

の原始根．

In[24]:= PrimitiveRoot[5]

Out[24]=

群を生成することを確認する．

In[25]:= Sort[Mod[2^Range[4], 5]]

Out[25]=

素数のベキ乗の原始根．

In[26]:= PrimitiveRoot[1093^3]

Out[26]=

素数の2倍のベキ乗の原始根．

In[27]:= PrimitiveRoot[2*5^5]

Out[27]=

引数が合成数であり，素数のベキ乗でも素数の2倍のベキ乗でもない場合，この関数は評価されない．

In[28]:= PrimitiveRoot[11*13]

Out[28]=

PrimitiveRootはサブルーチンとしてFactorIntegerを使用するため，非常に大きい引数については結果を返さないことがある．

2次式表記

QuadraticRepresentation[d, n]は，もし存在するならとなるx, yを返す．ここでは正の整数，は奇数でなければならない．このアルゴリズムはユークリッド(Euclid)のアルゴリズムに類似している．がCornacchiaにより発見された素数の場合については，S. Wagon,著「The Euclidean Algorithm Strikes Again」（American Mathematical Monthly 97，1990）の124-125ページを参照されたい．すべてのについての一般化はK. Hardy，J. B. Muskat，K. S. Williamsの論文「A Deterministic Algorithm for Solving in Coprime Integers and 」（Mathematics of Computation 55，1990）の327-343ページで述べられている．このアルゴリズムはサブルーチンとしてSqrtMod[-d, n]を用いるので，の因数分解が必要である．

QuadraticRepresentation[d, n]は以下の2つの理由により解を返さないことがある．

(1) がの完全平方ではない．つまり，JacobiSymbol[-d, n]がである．

(2) 拡大体のクラス数が1より大きく，の素因子が主クラスではなく素イデアルに分けられる．

条件(1)から表記が存在しないということが暗示される理由は，が完全平方の（ここで除算はである）となるように，式がを暗示しているということにある．つまり，このような表記が存在するためには，を割り切ることができ，かつが完全平方でない各素数は，を割ると偶数のベキ乗にならなければならない．

条件(2)の詳しい解析は「Primes of the Form 」（D. A. Cox著，Wiley出版，1989）を参照のこと．

の2次式表記．

In[29]:= QuadraticRepresentation[1, 13]

Out[29]=

結果を検証する．

In[30]:= (%^2) . {1, 1}

Out[30]=

の場合は，本質的にはFactorInteger[n, GaussianIntegers -> True]と同じである．

In[31]:= FactorInteger[13, GaussianIntegers -> True]

Out[31]=

非常に大きな合成数の場合．

In[32]:= 13*31*61*Prime[10^7]

Out[32]=

次の式はを使って2次式表記を求める．

In[33]:= QuadraticRepresentation[3, %]

Out[33]=

結果を検証する．

In[34]:= (%^2) . {1, 3}

Out[34]=

大きな数についても非常に素早く2次式表記が得られる．

In[35]:= QuadraticRepresentation[1, 10^64+57]//Timing

Out[35]=

ClassListの使用

が奇数で無平方であり，かつに等しいとき，またはが偶数でが無平方であり，かつがに等しいとき，整数は基本判別式である．

ClassList[d]は負の整数の2進2次形式の合成において，同等クラスの代表のセットを返す．このリストは無平方でまたはという形式のについての要素を持つ．2次形式はリスト a, b, cで表される．このアルゴリズムは最も簡単なもののひとつで，よりはるかに大きい入力については遅い．

ClassNumber[d]は2次数体のクラス数を返す．ここでは基本判別式である．これは負のについてのClassList[d]の長さに等しい．ClassNumberは解析的な公式を使う．これは強引な検索よりも漸近的に速い．

判別式がである3つの2次形式．

In[36]:= ClassList[-23]

Out[36]=

入力が基本判別式であることを確認する．

In[37]:= FundamentalDiscriminantQ[-10099]

Out[37]=

判別式が基本的である場合，クラス数は指定の判別式を持つ，同等でない2次形式の数である．

In[38]:= ClassNumber[-10099]

Out[38]=

ClassNumberはClassListとは異なり，正の判別式を取る．

In[39]:= ClassNumber[65]

Out[39]=

次の数は，クラス数が1となる最後の負の判別式であるとガウス(Gauss)が予測し，H. Starkが1968年に証明した．

In[40]:= ClassNumber[-163]

Out[40]=

クロネッカー記号

クロネッカー記号はヤコビ(Jacobi)記号の延長で，あらゆる整数およびについて使用できる．これは2次数体の判別式を扱う操作で使用される．

クロネッカー記号を求める．

In[41]:= KroneckerSymbol[5, 3]

Out[41]=

平方の和としての整数の表記

SumOfSquaresRepresentations[d, n]は個の2乗の数の和としての整数の表記一式を返す．また，OrderedSumOfSquaresRepresentations[d, n]は非減少・非負の個の2乗の数の和としての表現のみ返す．SumOfSquaresR[d, n]は個の2乗の数の和としての整数の表記の数を返す．については，が因数分解できるならSumOfSquaresR[d, n]はの大きな整数値を扱うことができる．の他の値については，SumOfSquaresR[d, n]は反復を用いるので，適度な大きさのおよびだけが使用できる．

を個の平方の数の和として表す．

In[42]:= SumOfSquaresRepresentations[3, 100]

Out[42]=

この表記が有効であることを確認する．

In[43]:= Apply[Plus, (%^2), 2]

Out[43]=

同じ表記だが，こちらは順に並んだリストである．

In[44]:= OrderedSumOfSquaresRepresentations[3, 100]

Out[44]=

の漸近的な平均はである．

In[45]:= Sum[N[SumOfSquaresR[2, k]], {k, 200}] / 200

Out[45]=

SumOfSquaresRepresentationsとSumOfSquaresRはStan Wagonにより無料で提供されているアルゴリズムを改良したものである．

ド・モアブル(de Moivre)数の識別

円分方程式 の解は，一般の多角形の頂点を形成する単位円上にある代数的数である．これはド・モアブル数または1のベキ根と呼ばれるもので，という形で表せる．ここでとは数がどの根に対応するかを表すものである．WhichRootOfUnityはn, kのペアを返す．

入力が1の最初の6つのベキ根に対応するド・モアブルであることが分かる．

In[46]:= WhichRootOfUnity[(1 + I Sqrt[3])/2]

1のベキ根が十分に簡約されていない場合は，WhichRootOfUnityはそれを認識できないことがあるので注意されたい．

Aliquot数列の操作関数

指定のについて，未満の正の約数を求め，その和を計算することができる．例えばは約数，，を持ち，その総和はである．関数SumOfFactorsは，この総和を直接計算する．ここで，このSumOfFactorsを総和に繰返し適用することを考える．結果の数列はAliquot数列と呼ばれる．この数列は総和がゼロになると止まる．数列は終らないこともあるが，周期的になる．関数AliquotCycleはこの周期的な部分を返す．すべてのAliquot数列は終了するかまたは周期的にならなければならないと考えられているが，これは証明はされていない．またこれは間違っていることを示唆する証拠も存在する．2003年4月の時点で，数列が終了するかどうかが判別していない最小の数はである．

の約数の総和．

In[47]:= SumOfFactors[14]

Out[47]=

SumOfFactors[n]がに等しい場合は，は完全数であると言う．

In[48]:= SumOfFactors[6]

Out[48]=

95で始まるAliquot数列．これは周期的であり，で終了する．

In[49]:= AliquotSequence[95]

Out[49]=

周期的な部分を直接求める．

In[50]:= AliquotCycle[95]

Out[50]=

周期の長さがより大きいとき，これは友愛連鎖と呼ばれ，その要素は社交数と呼ばれる．長さの周期のときは，要素は友愛数と呼ばれる．最小の友愛数はである．

長さ5の友愛連鎖．1918年にPouletにより発見された．

In[51]:= AliquotCycle[12496]

Out[51]=

Aliquot関数のオプション

AliquotSequenceとAliquotCycleの計算方法は，さまざまなオプションを使って変更できる．axIterationsおよびMaxTermsオプションを使うと，数列が保有できる最大項数と項のサイズを指定することで，Aliquot数列における計算サイズが制限できる．ShowProgressをTrueに設定すると，計算の進行状況が監視できる．TermIncrementを使うと，数列の各項の値の計算結果に追加の増分を加えることができる．

オプションはAliquot関数だけでなく，SumOfFactorsにも適用される．これは約数に使用する定義を決定するものである．デフォルトではすべての約数が加算される．このオプションをUnitary，Biunitary，Exponential，ModifiedExponential，ModifiedExponential，またはInfinitaryに設定すると，他の定義も適用できる．

デフォルトの約数での通常の総和．

In[52]:= SumOfFactors[12]

Out[52]=

Unitaryと設定すると，unitary約数だけが加算される．の非自明な約数は，とが互いに素である場合はunitary約数である．

In[53]:= SumOfFactors[12, SumOfFactorsType -> Unitary]

Out[53]=

の素因数すべについて，がを割り切る最大ののベキ乗でない場合，Biunitary dは非自明な約数を表す．ここではを割り切る最大のベキ乗である．

In[54]:= SumOfFactors[12, SumOfFactorsType -> Biunitary]

Out[54]=

ここで，のすべての素因数について，もしがを割り切るの最大のベキ乗であり，またがを割り切るの最大のベキ乗であるため，ゼロであるのすべてのバイナリの数がについてもゼロであるなら，の無限約数はゼロである．

In[55]:= SumOfFactors[12, SumOfFactorsType -> Infinitary]

Out[55]=

Exponential約数はInfinitaryと同じ表記を用いるが，この場合であるか，またははを割り切ることができる．

In[56]:= SumOfFactors[12, SumOfFactorsType -> Exponential]

Out[56]=

ModifiedExponentialはExponentialと似ているが，約数となるについての条件は，はを割り切り，はを割り切るということである．

In[57]:= SumOfFactors[12, SumOfFactorsType -> ModifiedExponential]

Out[57]=

この場合，のベキ乗は完全数となる．これはの非自明の約数の総和がであるからである．

In[58]:= AliquotSequence[16, TermIncrement -> 1]

Out[58]=