整数の操作と整数論に関連した関数

Mod[k,n]n を法とする kkn で割ったときの剰余)
Quotient[m,n]mn の商( の整数部)
QuotientRemainder[m,n]商と剰余のリスト
Divisible[m,n]mn で割り切れるかどうかのテスト
CoprimeQ[n1,n2,] が対で互いに素であるかどうかのテスト
GCD[n1,n2,], , の最大公約数
LCM[n1,n2,], , の最小公倍数
KroneckerDelta[n1,n2,] がすべて等しければクロネッカーのデルタ は1,そうでなければ0
IntegerDigits[n,b]nb 進法で表したとき各桁に現れる数
IntegerExponent[n,b]bn で割ったときの最大のベキ

整数に関する関数の例

17を3で割ったときの余り.
In[1]:=
Click for copyable input
Out[1]=
17/3の整数部.
In[2]:=
Click for copyable input
Out[2]=
Modには実数を使うこともできる.
In[3]:=
Click for copyable input
Out[3]=
Modの結果は,第2引数の符号を引き継ぐ.
In[4]:=
Click for copyable input
Out[4]=

任意の整数 ab に対して,b*Quotient[a,b]+Mod[a,b]は常に に等しい.

Mod[k,n]結果は0から の範囲
Mod[k,n,1]結果は1から n の範囲
Mod[k,n,-n/2]結果はからの範囲
Mod[k,n,d]結果は d から の範囲

オフセットを含む整数剰余

特にModを使いオブジェクトの部分の指標を得る場合はオフセットを指定すると便利なことがある.

リストを循環的に扱い,18番目の部分を抽出できる.
In[5]:=
Click for copyable input
Out[5]=

最大公約数(greatest common divisor)の関数GCD[n1,n2,]は,すべての を割り切ることができる最大整数を与える.2つの整数を比の形で入力したなら,Wolfram言語は,GCDを使い共通因数をキャンセルし,約分し尽くした形の有理数を返す.

最小公倍数(least common multiple)の関数LCM[n1,n2,]は,各 のすべての因数を含んだ最小整数を与える.

24と15の最大公約数を求めると,3が得られる.
In[6]:=
Click for copyable input
Out[6]=

クロネッカー(Kronecker)のデルタ関数KroneckerDelta[n1,n2,] すべてが等しいなら1でそうでなければ0である.は完全対称テンソルと考えられる.

階数が3の完全対称テンソルを与える.
In[7]:=
Click for copyable input
Out[7]=
FactorInteger[n]整数 n の素因数とその指数のリスト
Divisors[n]n を整除する整数のリスト
Prime[k]k 番目の素数
PrimePi[x]x 以下の素数がいくつあるか調べる
PrimeQ[n]n が素数ならTrue,そうでなければFalse
PrimeNu[n]n における異なる素数の の個数
PrimeOmega[n]n における重複を数えた素因数 の個数
LiouvilleLambda[n]リウヴィル(Liouville)関数
MangoldtLambda[n]マンゴルト(Mangoldt)関数
FactorInteger[n,GaussianIntegers->True]ガウスの整数 n のガウスの素因数と指数のリスト
PrimeQ[n,GaussianIntegers->True]n がガウスの素数ならTrue,そうでなければFalse

素因数分解と関連する関数

24の因数はである.因数は,各リストの第1要素で,指数は第2要素である.
In[8]:=
Click for copyable input
Out[8]=
もっと大きい整数について因数を探す.
In[9]:=
Click for copyable input
Out[9]=

数学的に見て,素因数分解は根本的に難解な問題である.このため,キーボードから簡単にタイプできるような整数でも,天文学的に長い時間をかけなければ分解できないことがある.与えられる整数が50桁程度までの大きさならば,Wolfram言語はFactorIntegerを使うことで難なく分解することができる.特別な場合は,それより大きい整数でも分解できる.

これは大きいが,やや特殊な整数である.
In[10]:=
Click for copyable input
Out[10]=
この整数は特別なため,簡単に因数分解される.
In[11]:=
Click for copyable input
Out[11]=

Wolfram言語は,整数が大きくなるとそれを分解できないかもしれないが,それでも,それが素数かどうかの判定は行うことができる.また, 番目の素数を素早く探せるようにもなっている.

数を素数に分解するより,それが素数かどうかを判定する方が断然速い.
In[12]:=
Click for copyable input
Out[12]=
最初の100個の素数を探させ,値をプロットさせる.
In[13]:=
Click for copyable input
Out[13]=
100万番目の素数を探させる.
In[14]:=
Click for copyable input
Out[14]=

整数論では,素数の実際の値より素数がどう分布しているかを知る方が重要なことが多い.関数PrimePi[x]を使えば, 以下の素数の個数 を知ることができる.

10億以下の素数がいくつあるかを調べる.
In[15]:=
Click for copyable input
Out[15]=
PrimeNuは異なる素数の数を与える.
In[16]:=
Click for copyable input
Out[16]=
PrimeOmegan における重複を数えた素因数 の数を与える.
In[17]:=
Click for copyable input
Out[17]=
リウヴィル関数は, が重複を数えた素因数であるときの を与える.
In[18]:=
Click for copyable input
Out[18]=
マンゴルト関数は,合成の場合は素数ベキを基底とする対数またはゼロを返す.
In[19]:=
Click for copyable input
Out[19]=

デフォルト設定では,FactorInteger は実整数だけを扱う.しかし,GaussianIntegers->Trueのオプション設定が加えられたなら,整数実数部と整数虚数部からなる複素数のガウス整数も扱うことができるようになる.実素数で一意的に分解することが可能なように,ガウス素数で一意的に分解することが可能である.それでもガウス素数を選択するときは潜在的な曖昧さが残る.このため,Wolfram言語では,常に正の実部と負でない虚数部を持つガウス素数が選択される.ただし,最初の素数としては を許容することとする.

ガウス整数の中でなら,2はとして因数分解することができる.
In[20]:=
Click for copyable input
Out[20]=
ガウス整数の因数を探させる.
In[21]:=
Click for copyable input
Out[21]=
PowerMod[a,b,n]モジュラベキ(n で割った余り)
DirichletCharacter[k,j,n]ディリクレ記号
EulerPhi[n]オイラー関数
MoebiusMu[n]メービウスの関数
DivisorSigma[k,n]約数関数
DivisorSum[n,form]n を割り切るすべての i についての の総和
DivisorSum[n,form,cond]Trueを与える除数のみの総和
JacobiSymbol[n,m]ヤコビの記号
ExtendedGCD[n1,n2,], , の拡張最大公約数
MultiplicativeOrder[k,n]kn で割った余りの乗積順序
MultiplicativeOrder[k,n,{r1,r2,}]剰余 の一般化された乗積順序
CarmichaelLambda[n]カーマイケル関数
PrimitiveRoot[n]n の原始根

数論関数

モジュラベキ関数PowerMod[a,b,n]は,b>0ならMod[a^b,n]と同じ結果を与える.しかし,PowerMod の完全形を生成することを避けられるので,より効果的である.

PowerModを使えば,正のモジュラベキばかりでなく有限体の逆数も求めることができる.例えば,PowerMod[a,b,n]において b が負の値を取る場合,式 の関係を満たす整数 が存在すればそれを与える.(このような整数が存在する場合,それは,必ず n を法(modulo)として一意である.)一方,そのような が存在しない場合,PowerModは未評価のまま残される.

PowerModを使えば,PowerModを組で使ったときと同じ機能を得ることができ,また,より効率よく計算することができる.
In[22]:=
Click for copyable input
Out[22]=
7を法とした3の逆数を求める.
In[23]:=
Click for copyable input
Out[23]=
この逆数に3を掛け7を法とすると,期待した通りに1が求まる.
In[24]:=
Click for copyable input
Out[24]=
が11を法とする3に等しくなるような最小の非負の整数 を見付ける.
In[25]:=
Click for copyable input
Out[25]=
結果を検証する.
In[26]:=
Click for copyable input
Out[26]=
これは関係を満足する,11より小さい整数すべてを返す.
In[27]:=
Click for copyable input
Out[27]=
dn を法とする平方根を持たないならば,PowerMod[d,n]は評価されないままでPowerModListは空リストを返す.
In[28]:=
Click for copyable input
Out[28]=
In[29]:=
Click for copyable input
Out[29]=
3が5を法とする平方ではないことを検証する.
In[30]:=
Click for copyable input
Out[30]=
法が大きい場合でも,平方根は非常に速く計算できる.
In[31]:=
Click for copyable input
Out[31]=
PowerMod[d,n]は合成数 にも使える.
In[32]:=
Click for copyable input
Out[32]=

与えられた法 k に対して,指標 j でラベル付けされるように, 個の異なるディリクレ記号がある.可能な記号の順序は,慣習により異なることがある.

DirichletCharacterは非常に長い数にも使える.
In[33]:=
Click for copyable input
Out[33]=

オイラー(Euler)の関数 は, より小さく,かつ, に対して素となる整数の個数を返す.また, が互いに素ならば が成り立つ(フェルマ(Fermat)の小定理).

メービウス(Möbius)の関数 は, 個の異なる素数の積であるとき となり,1ではない二乗因数を含む場合にとなるよう定義される.もし,すべての に対して ならば,が成り立つ(メービウスの反転公式).ただし, を割り切る正の整数 について和を取る.

約数関数 は, のすべての約数を 乗して加えた和を与える.関数 の約数の個数を与え,等と書かれることもある.また, の除数の総和と等しく,と書かれることもある.

素数 に対しては の関係が成り立つ.
In[34]:=
Click for copyable input
Out[34]=
フェルマの小定理により,この結果は必ず1になる.
In[35]:=
Click for copyable input
Out[35]=
24のすべての約数をリストに列挙する.
In[36]:=
Click for copyable input
Out[36]=
を使い24の約数がいくつあるか調べる.
In[37]:=
Click for copyable input
Out[37]=

関数DivisorSum[n,form]n を割り切るすべての i についての の総和を表す.DivisorSum[n,form,cond]Trueを与える除数だけを含む.

5つの正の整数の除数の和のリストを返す.
In[38]:=
Click for copyable input
Out[38]=
次はそれぞれの除数 i の値が6より小さくなければならないという条件を課す.
In[39]:=
Click for copyable input
Out[39]=

ヤコビ(Jacobi)の記号JacobiSymbol[n,m]は, が奇数で,かつ,素数のとき,ルジャンドルの記号に帰着する.また,ルジャンドルの記号は, で割り切れるとき0に等しい.そうでない場合, が素数 を法とした平方剰余のときに等しく,そうでなければに等しい.ここで, に対して素となる整数 は, の関係を満たす整数 が存在するとき, を法とする平方剰余である,という.一般の場合のヤコビの記号は, となる各素因数 に関するルジャンドルの記号の全体の積である.

拡張最大公約数ExtendedGCD[n1,n2,]は, の最大公約数とし,となる整数としたときのリストを返す.拡張最大公約数は,線形(不定)方程式の整数解を求める際に重要な役割を果たす.

リストの第1要素が105と196の最大公約数である.
In[40]:=
Click for copyable input
Out[40]=
数の第2ペアは の関係を満たす.
In[41]:=
Click for copyable input
Out[41]=

乗積順序関数MultiplicativeOrder[k,n] となるような最小の整数 を与える.この を法とする の次数としても知られている.という表記もしばしば使用される.

一般化された乗積順序関数MultiplicativeOrder[k,n,{r1,r2,}]は任意の に対して が成り立つような最小の整数 を与える.MultiplicativeOrder[k,n,{-1,1}]と表記され で法とする部分順序関数として知られている.MultiplicativeOrder[k,n,{a}] を法とする基底 に関する の離散対数としても知られている.

カーマイケル(Carmichael)関数あるいは最小普遍指数 と互いに素であるようなすべての整数 に対して であるような最小の整数 を与える.

ContinuedFraction[x,n]x の連分数表現の最初の n 項を生成する
FromContinuedFraction[list]連分数表現から数値を再構築する
Rationalize[x,dx]許容率 dxx の有理近似を求める

連分数

の連分数表現の最初の10項を生成する.
In[42]:=
Click for copyable input
Out[42]=
連分数項のリストで代表される数値を再構築する.
In[43]:=
Click for copyable input
Out[43]=
結果は に近い.
In[44]:=
Click for copyable input
Out[44]=
これは の有理近似を直接与える.
In[45]:=
Click for copyable input
Out[45]=

連分数は数論でよく現れる.有理数の連分数表現は途中で打ち切られる.二次無理数は連分数表現を持ち,それは反復する.

ContinuedFraction[x]有理数または二次無理数の完全な連分数表現
QuadraticIrrationalQ[x]x が二次無理数であるかどうかをテストする
RealDigits[x]有理数の完全な数列
RealDigits[x,b]b を基底とする完全な数列

数値の完全な表現

の連分数表現は8で始まり,限りなく反復される数列からなる.
In[46]:=
Click for copyable input
Out[46]=
が連分数表現から再構築される.
In[47]:=
Click for copyable input
Out[47]=
次は二次無理数である.
In[48]:=
Click for copyable input
Out[48]=
3/7を循環小数で表す.
In[49]:=
Click for copyable input
Out[49]=
FromDigitsはもとの数値を再構築する.
In[50]:=
Click for copyable input
Out[50]=

連分数の近似分数は無理数を有理数で近似するときによく使われる.この近似は上と下から交互に起り,項の数で指数関数的に収束する.さらに,単純な連分数の近似分数 は分母が 以下の他のどのような有理近似よりもよいものとなる.

Convergents[x]x の有理近似のリストを与える
Convergents[x,n]最初の n 個の近似だけを与える

連分数の近似分数

次は,連分数展開から派生した,101/9801の有理近似のリストを与える.
In[51]:=
Click for copyable input
Out[51]=
最初の10の近似分数だけをリストする.
In[52]:=
Click for copyable input
Out[52]=
数値精度が尽きるまで,連続した の有理近似をリストする.
In[53]:=
Click for copyable input
Out[53]=
厳密な無理数の場合は,項の数を明示的に与えなければならない.
In[54]:=
Click for copyable input
Out[54]=
LatticeReduce[{v1v2,}]整数ベクトル の集合に対する格子基底縮小
HermiteDecomposition[{v1,v2,}]整数ベクトル の集合に対する階段型

整数格子の関数

格子縮小関数LatticeReduce[{v1,v2,}]は,現代のアルゴリズムの数種類で使われる.この基本的な考え方は,整数のベクトル を数学的な「格子」として考えることである.格子の中の点を表すベクトルはすべて形式 は整数)の線形結合として書くことができる.特定の格子では,「基底ベクトル」 に対して多くの選択肢がある.LatticeReduceが行うのは,ある特定の性質を持つ,この格子の基底ベクトル の縮小集合を見付けることである.

3つの座標軸に沿った3つの単位ベクトルはすでに縮小基底を形成している.
In[55]:=
Click for copyable input
Out[55]=
3つのベクトルにより指定された四次元の格子に対する縮小基底を与える.
In[56]:=
Click for copyable input
Out[56]=

最後の例では,LatticeReduceはほぼ平行なベクトルをより垂直なベクトルで置き換えている.この過程で,非常に短い基底ベクトルが見付かる.

行列 では,HermiteDecomposition がユニモジュラ, が行縮小形式となるような行列 を与える.RowReduceとは対照的に,整数環には分数はないので,軸は1より大きいことがある.軸より上の要素は,軸の行の適切な倍数を引くことにより最小化される.

この場合,もとの行列は行階段型だったので,復元される.
In[57]:=
Click for copyable input
Out[57]=
これは必要とされる条件を満たす.
In[58]:=
Click for copyable input
Out[58]=
ここでは,2つ目の行列が1より大きい軸と,軸の上に非零の要素を持つ.
In[59]:=
Click for copyable input
Out[59]=
DigitCount[n,b,d]n を基底 b で表現したときに現れる数 d の個数

数カウント関数

数77の基底2による表現.
In[60]:=
Click for copyable input
Out[60]=
基底2による表現での1の個数を直接計算する.
In[61]:=
Click for copyable input
Out[61]=
数カウント関数のプロットは自己相似となる.
In[62]:=
Click for copyable input
Out[62]=
BitAnd[n1,n2,]整数 のビットごとのAND
BitOr[n1,n2,]整数 のビットごとのOR
BitXor[n1,n2,]整数 のビットごとのXOR
BitNot[n]整数 n のビットごとのNOT
BitLength[n]整数 n のバイナリビットの数
BitSet[n,k]整数 n でビット k を1に設定する
BitGet[n,k]整数 n からビット k を得る
BitClear[n,k]整数 n のビット k を0に設定する
BitShiftLeft[n,k]整数 nk ビットだけ左にシフトし,ゼロで充填する
BitShiftRight[n,k]右にシフトし,最後の k ビットを削除する

ビットごとの演算

ビットごとの演算はバイナリビットで表現された整数に施される.BitAnd[n1,n2,]はバイナリビット表現で のすべてに1がある場所に,バイナリ表現で1がある整数を与える.BitOr[n1,n2,]はバイナリビット表現で任意の に1がある場所に1がある整数を与える.BitXor[n1,n2]または のどちらかだけに1がある場所にバイナリビット表現で1がある整数を与える.BitXor[n1,n2,]は奇数個の に1がある場所に1がある整数を与える.

基底2で入力された数値23と29のビットごとのANDを計算する.
In[63]:=
Click for copyable input
Out[63]//BaseForm=

ビットごとの演算は様々な組合せ論アルゴリズムで使用される.また低レベルのコンピュータ言語でもビットフィールドの操作によく使用される.しかしそれらの言語では整数は通常は8の倍数であるような限られた桁数しか許されない.Wolfram言語でのビットごとの演算では無限の桁数の整数を扱うことができる.負の整数の場合は,左に1の数列が無限にあるような2の補数で表現される.これによりBitNot[n] と同等となる.

SquareFreeQ[n]n が平方因子を含んでいない場合はTrue,含んでいる場合はFalseを返す

平方因子のテスト

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

次の素数の積は平方因子を含まない.
In[64]:=
Click for copyable input
Out[64]=
60は平方数4で割り切れる.
In[65]:=
Click for copyable input
Out[65]=
SquareFreeQは大きな整数にも対応できる.
In[66]:=
Click for copyable input
Out[66]=
NextPrime[n]n より大きい最小の素数を返す
RandomPrime[{min,max}]min より大きく max より小さいランダムな素数を返す
RandomPrime[max]max より小さいか等しいランダムな素数を返す
RandomPrime[{min,max},n]min より大きく max より小さい n 個のランダムな素数を返す
RandomPrime[max,n]maxより小さいか等しいランダムな素数を n 個返す

素数を求める

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

これは,10より大きい最初の素数を与える.
In[67]:=
Click for copyable input
Out[67]=
大きな数についても,比較的素早く計算できる.
In[68]:=
Click for copyable input
Out[68]=
34より小さい最大の素数を求める.
In[69]:=
Click for copyable input
Out[69]=

RandomPrime[{min,max}]RandomPrime[max]については,ランダムな素数 p は,max が小さな場合は素数参照表からランダムに選択し,max が大きな場合にはその範囲内の整数のランダム検索で求める.指定の範囲に素数が存在しない場合は,入力は評価されずに返され,エラーメッセージが表示される.

10から100までの間でランダムに選んだ素数.
In[70]:=
Click for copyable input
Out[70]=
PrimePowerQ[n]n が有理数の素数の正の整数ベキであるかどうかを判別する

素数ベキを含むかどうかのテスト

PrimePowerQのアルゴリズムは,まず n の最小の素因数 p を計算し,次に1が得られるまで(この場合,n は素数のベキ乗),または不可能になるまで(この場合,n は素数のベキ乗ではない)p による除算を試みる.

次の数は1つの素数のベキ乗である.
In[71]:=
Click for copyable input
Out[71]=
GaussianIntegers上では,これは素数ベキである.
In[72]:=
Click for copyable input
Out[72]=
ChineseRemainder[list1,list2]Mod[r,list2]==list1である非負の最小の整数 r を返す

連立合同式を解く

中国余剰定理(Chinese Remainder Theorem)によると,連立合同式のある特定のクラスには常に解が存在する.ChineseRemainder[list1,list2]を使うと,Mod[r,list2]である非負の最小の整数 r が求められる.解は の要素の最小公倍数の唯一のモジュロである.

次の式は,およびを意味している.
In[73]:=
Click for copyable input
Out[73]=
結果を検証する.
In[74]:=
Click for copyable input
Out[74]=
リストが長くなっても極めて速く計算できる.
In[75]:=
Click for copyable input
Out[75]=
PrimitiveRoot[n]n の原始根を1つ返す.n は素数のベキか素数のベキの2倍である

原始根の計算

PrimitiveRoot[n]は, の乗算で,n と互いに素である数の群の生成元を返す.生成元は n が2,4,奇数の素数のベキ乗,または奇数の素数のベキ乗の2倍である場合にのみ存在する.n が素数または素数のベキ乗の場合は,正の最小の原始根が返される.

これは5の原始根である.
In[76]:=
Click for copyable input
Out[76]=
群を生成することを確認する.
In[77]:=
Click for copyable input
Out[77]=
次は,素数のベキ乗の原始根である.
In[78]:=
Click for copyable input
Out[78]=
次は,素数のベキ上の2倍の原始根である.
In[79]:=
Click for copyable input
Out[79]=
引数が合成数であり,素数のベキ乗でも素数の2倍のベキ乗でもない場合,この関数は評価されない.
In[80]:=
Click for copyable input
Out[80]=
SquaresR[d,n]整数 nd 個の2乗の数の和として表したときの表記の数を返す
PowersRepresentations[n,k,p]整数 n を非負の p 番目の整数ベキ k 個の和として表す方法を返す

平方の和あるいは他のベキとしての整数の表記

101を3個の数の平方和として表す.
In[81]:=
Click for copyable input
Out[81]=