整数の操作と整数論に関連した関数
| Mod[k,n] | k modulo n （k をn で割ったときの剰余） |
| Quotient[m,n] | m とn の商（m/n の整数部） |
| QuotientRemainder[m,n] | 商と剰余のリスト |
| Divisible[m,n] | m がn で割り切れるかどうかのテスト |
| CoprimeQ[n1,n2,...] | ni が対で互いに素であるかどうかのテスト |
| GCD[n1,n2,...] | n1, n2, ...の最大公約数 |
| LCM[n1,n2,...] | n1, n2, ...の最小公倍数 |
| KroneckerDelta[n1,n2,...] | ni がすべて等しければクロネッカーのデルタ n1n2...は1，そうでなければ0 |
| IntegerDigits[n,b] | n をb 進法で表したとき各桁に現れる数 |
| IntegerExponent[n,b] | b をn で割ったときの最大のベキ |
整数に関する関数の例
| Out[1]= |  |
|
| Out[2]= |  |
|
| Out[3]= |  |
|
| Out[4]= |  |
|
任意の整数
a と
b に対して，
b*Quotient[a, b]+Mod[a, b]は常に
a に等しい．
| Mod[k,n] | 結果は0からn-1の範囲 |
| Mod[k,n,1] | 結果は1からn の範囲 |
| Mod[k,n,-n/2] | 結果は -n/2 から +n/2 の範囲 |
| Mod[k,n,d] | 結果はd からd+n-1の範囲 |
オフセットを含む整数剰余
特に
Modを使いオブジェクトの部分の指標を得る場合はオフセットを指定すると便利なことがある．
リストを循環的に扱い，18番目の部分を抽出できる．
| Out[5]= |  |
|
最大公約数(greatest common divisor)の関数
GCD[n1, n2, ...]は，すべての
ni を割り切ることができる最大整数を与える．2整数を比の形で入力したなら，
Mathematica は，
GCDを使い共通因数をキャンセルし，約分し尽くした形の有理数を返す．
最小公倍数(least common multiple)の関数
LCM[n1, n2, ...]は，各
ni のすべての因数を含んだ最小整数を与える．
| Out[6]= |  |
|
クロネッカー(Kronecker)のデルタ関数
KroneckerDelta[n1, n2, ...]は
ni すべてが等しいなら1でそうでなければ0である．
n1n2... は完全対称テンソルと考えられる．
| Out[7]= |  |
|
素因数分解と関連する関数
24の因数は 23と 31である．因数は，各リストの第1要素で，指数は第2要素である．
| Out[8]= |  |
|
| Out[9]= |  |
|
数学的に見て，素因数分解は根本的に難解な問題である．このため，キーボードから簡単にタイプできるような整数でも，天文学的に長い時間をかけなければ分解できないことがある．与えられる整数が50桁程度までの大きさならば，
Mathematica は
FactorIntegerを使うことで難なく分解することができる．特別な場合は，それより大きい整数でも分解できる．
| Out[10]= |  |
|
| Out[11]= |  |
|
Mathematica は，整数が大きくなるとそれを分解できないかもしれないが，それでも，それが素数かどうかの判定は行うことができる．また，
k 番目の素数を素早く探せるようにもなっている．
数を素数に分解するより，それが素数かどうかを判定する方が断然速い．
| Out[12]= |  |
|
最初の100個の素数を探させ，値をプロットさせる．
| Out[13]= |  |
|
| Out[14]= |  |
|
整数論では，素数の実際の値より素数がどう分布しているかを知る方が重要なことが多い．関数
PrimePi[x]を使えば，
x 以下の素数の個数
(x)を知ることができる．
| Out[15]= |  |
|
デフォルト設定では，
FactorInteger は実整数だけを扱う．しかし，
GaussianIntegers->Trueのオプション設定が加えられたなら，整数実数部と整数虚数部からなる複素数のガウス整数も扱うことができるようになる．実素数で一意的に分解することが可能なように，ガウス素数で一意的に分解することが可能である．それでもガウス素数を選択するときは潜在的な曖昧さが残る．このため，
Mathematica では，常に正の実部と負でない虚数部を持つガウス素数が選択される．ただし，最初の素数としては
-1と
±i を許容することとする．
ガウス整数の中でなら，2は (-i) (1+i)2として因数分解することができる．
| Out[16]= |  |
|
| Out[17]= |  |
|
| PowerMod[a,b,n] | モジュラベキ（ab をn で割った余り） |
| EulerPhi[n] | オイラーの関数  (n) |
| MoebiusMu[n] | メービウスの関数  (n) |
| DivisorSigma[k,n] | 約数関数  k (n) |
| JacobiSymbol[n,m] | ヤコビの記号  |
| ExtendedGCD[n1,n2,...] | n1, n2, ...の拡張最大公約数 |
| MultiplicativeOrder[k,n] | k をn で割った余りの乗積順序 |
| MultiplicativeOrder[k,n,{r1,r2,...}] |
| 剰余ri の一般化された乗積順序 |
| CarmichaelLambda[n] | カーマイケル関数  (n) |
| PrimitiveRoot[n] | n の原始根 |
数論関数
モジュラベキ関数
PowerMod[a, b, n]は，
b>0なら
Mod[a^b, n]と同じ結果を与える．しかし，
PowerModは
a^b の完全形を生成することを避けられるので，より効果的である．
PowerModを使えば，正のモジュラベキばかりでなく有限体の逆数も求めることができる．例えば，
PowerMod[a, b, n]において
b が負の値を取る場合，式
ka-b
1modn の関係を満たす整数
k が存在すればそれを与える．（このような整数が存在する場合，それは，必ず
n を法(modulo)として一意である．）一方，そのような
k が存在しない場合，
PowerModは未評価のまま残される．
| Out[18]= |  |
|
| Out[19]= |  |
|
この逆数に3をかけ，7を法とすると，期待した通りに1が求まる．
| Out[20]= |  |
|
x2が3 mod 11に等しくなるような最小の非負の整数 x を見付ける．
| Out[21]= |  |
|
| Out[22]= |  |
|
これは関係を満足する，11より小さい整数すべてを返す．
| Out[23]= |  |
|
| Out[24]= |  |
|
| Out[25]= |  |
|
法が大きい場合でも，平方根は非常に速く計算できる．
| Out[26]= |  |
|
| Out[27]= |  |
|
オイラー(Euler)の関数
(n)は，
n より小さく，かつ，
n に対して素となる整数の個数を返す．また，
n と
a が互いに素ならば
a (n)1modn が成り立つ（フェルマ(Fermat)の小定理）．
メービウス(Möbius function)の関数
(n)は，
n が
k 個の異なる素数の積であるとき
(-1)k となり，1ではない2乗因数を含む場合に
0となるよう定義される．もし，すべての
n に対して
ならば，
が成り立つ（メービウスの反転公式）．ただし，
n を割り切る正の整数
d について和を取る．
約数関数
k (n)は，
n のすべての約数を
k 乗して加えた和を与える．関数
0 (n)は
n の約数の個数を与え，
d (n)，
(n)，
(n)等と書かれることもある．また，
1 (n)は
n の除数の総和と等しく，
(n)と書かれることもある．
素数 n に対しては (n)=n-1の関係が成り立つ．
| Out[28]= |  |
|
| Out[29]= |  |
|
| Out[30]= |  |
|
0 (n)を使い24の約数がいくつあるか調べる．
| Out[31]= |  |
|
ヤコビ(Jacobi)の記号
JacobiSymbol[n, m]は，
m が奇数で，かつ，素数のとき，
ルジャンドルの記号
に帰着する．また，ルジャンドルの記号は，
n が
m で割り切れるとき0に等しい．そうでない場合，
n が素数
m を法とした平方剰余のとき
1に等しく，そうでなければ
-1に等しい．ここで，
m に対して素となる整数
n は，
k2nmodm の関係を満たす整数
k が存在するとき，
m を法とする平方剰余である，という．一般の場合のヤコビの記号は，
となる各素因数
pi に関するルジャンドルの記号
の全体の積である．
拡張最大公約数
ExtendedGCD[n1, n2, ...]は，
g を
ni の最大公約数とし，
ri を
g=r1n1+r2n2+....となる整数としたときのリスト
{g, {r1, r2, ...}}を返す．拡張最大公約数は，線形（不定）方程式の整数解を求める際に重要な役割を果たす．
リストの第1要素が105と196の最大公約数である．
| Out[32]= |  |
|
| Out[33]= |  |
|
乗積順序関数
MultiplicativeOrder[k, n]は
km1modn となるような最小の整数
m を与える．この関数は
k の次数または離散対数とも言われることがある．
ordn (k)という表記もしばしば使用される．
一般化された乗積順序関数
MultiplicativeOrder[k, n, {r1, r2, ...}]は任意の
i に対して
kmrimodn が成り立つような最小の整数
m を与える．
MultiplicativeOrder[k, n, {-1, 1}]は
sordn (k)と表記され
k を
n で法とする部分順序関数として知られている．
カーマイケル(Carmichael)関数あるいは最小普遍指数
(n)は
n と互いに素であるようなすべての整数
kに対して
km1modn であるような最小の整数
m を与える．
連分数
の連分数表現の最初の10項を生成する．
| Out[34]= |  |
|
| Out[35]= |  |
|
結果は に近い．
| Out[36]= |  |
|
これは の有理近似を直接与える．
| Out[37]= |  |
|
連分数は数論でよく現れる．有理数の連分数表現は途中で打ち切られる．2次無理数は連分数表現を持ち，それは反復する．
数値の完全な表現
 の連分数表現は8で始まり，限りなく反復される数列からなる．
| Out[38]= |  |
|
 が連分数表現から再構築される．
| Out[39]= |  |
|
| Out[40]= |  |
|
| Out[41]= |  |
|
| Out[42]= |  |
|
連分数の近似分数は無理数を有理数で近似するときによく使われる．この近似は上と下から交互に起り，項の数で指数関数的に収束する．さらに，単純な連分数の近似分数
p/q は分母が
q 以下の他のどのような有理近似よりもよいものとなる．
連分数の近似分数
次は，連分数展開から派生した，101/9801の有理近似のリストを与える．
| Out[43]= |  |
|
| Out[44]= |  |
|
数値精度が尽きるまで，連続した の有理近似をリストする．
| Out[45]= |  |
|
厳密な無理数の場合は，項の数を明示的に与えなければならない．
| Out[46]= |  |
|
整数格子の関数
格子縮小関数
LatticeReduce[{v1, v2, ...}]は，現代のアルゴリズムの数種類で使われる．この基本的な考え方は，整数のベクトル
vk を数学的な「格子」として考えることである．格子の中の点を表すベクトルはすべて形式
ck vk（
ck は整数）の線形結合として書くことができる．特定の格子では，「基底ベクトル」
vk に対して多くの選択肢がある．
LatticeReduceが行うのは，ある特定の性質を持つ，この格子の基底ベクトル
の縮小集合を見付けることである．
3つの座標軸に沿った3つの単位ベクトルはすでに縮小基底を形成している．
| Out[47]= |  |
|
3つのベクトルにより指定された四次元の格子に対する縮小基底を与える．
| Out[48]= |  |
|
最後の例では，
LatticeReduceはほぼ平行なベクトルをより垂直なベクトルで置き換えている．この過程で，非常に短い基底ベクトルが見付かる．
行列
m では，
HermiteDecompositionは
u がユニモジュラ，
u.m=r，
r が行縮小形式となるような行列
u と
r を与える．
RowReduceとは対照的に，整数環には分数はないので，軸は1より大きいことがある．軸より上の要素は，軸の行の適切な倍数を引くことにより最小化される．
この場合，もとの行列は行階段型だったので，復元される．
| Out[49]= |  |
|
| Out[50]= |  |
|
ここでは，2つ目の行列が1より大きい軸と，軸の上に非零の要素を持つ．
| Out[51]= |  |
|
数カウント関数
| Out[52]= |  |
|
| Out[53]= |  |
|
| Out[54]= |  |
|
| BitAnd[n1,n2,...] | 整数ni のビットごとのAND |
| BitOr[n1,n2,...] | 整数ni のビットごとのOR |
| BitXor[n1,n2,...] | 整数ni のビットごとの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] | 整数n をk ビットだけ左にシフトし，ゼロで充填する |
| BitShiftRight[n,k] | 右にシフトし，最後のk ビットを削除する |
ビットごとの演算
ビットごとの演算はバイナリビットで表現された整数に施される．
BitAnd[n1, n2, ...]はバイナリビット表現で
ni のすべてに1がある場所に，バイナリ表現で1がある整数を与える．
BitOr[n1, n2, ...]はバイナリビット表現で任意の
ni に1がある場所に1がある整数を与える．
BitXor[n1, n2]は
n1または
n2のどちらかだけに1がある場所にバイナリビット表現で1がある整数を与える．
BitXor[n1, n2, ...]は奇数個の
ni に1がある場所に1がある整数を与える．
基底2で入力された数値23と29のビットごとのANDを計算する．
Out[55]//BaseForm= |
| |  |
|
ビットごとの演算は様々な組合せ論アルゴリズムで使用される．また低レベルのコンピュータ言語でもビットフィールドの操作によく使用される．しかしそれらの言語では整数は通常は8の倍数であるような限られた桁数しか許されない．
Mathematica でのビットごとの演算では無限の桁数の整数を扱うことができる．負の整数の場合は，左に1の数列が無限にあるような2の補数で表現される．これにより
BitNot[n]は
-1-n と同等となる．
平方因子のテスト
SquareFreeQ[n]は
n が平方の素因数を持つかどうかを確認する．これはを計算し，結果がゼロであるかどうかを見て行われる．ゼロの場合は
n は無平方ではなく，ゼロでない場合は無平方である．
MoebiusMu[n]の計算を行うと，
n の最小の素因数
q が求められる．
n が
1223以下の小さな素因数を持つ場合は，
MoebiusMu[n]の計算は非常に速い．持たない場合は，
q を求めるのに
FactorIntegerが使われる．
| Out[56]= |  |
|
| Out[57]= |  |
|
| Out[58]= |  |
|
素数を求める
NextPrime[n]は
p>n である最小の
p を求める．20桁未満の
n については，このアルゴリズムは
n より大きい奇数に
PrimeQを適用して直接探す．20桁より大きい
n については，アルゴリズムは小さなふるいを作り，
PrimeQを使う前にまず候補となる素数が小さな素数で割り切れるかどうかを確認する．これは直接検索するよりわずかに速いと考えられている．
| Out[59]= |  |
|
| Out[60]= |  |
|
| Out[61]= |  |
|
RandomPrime[{min, max}]とRandomPrime[max]については，ランダムな素数
p は，
max が小さな場合は素数参照表からランダムに選択し，
max が大きな場合にはその範囲内の整数のランダム検索で求める．指定の範囲に素数が存在しない場合は，入力は評価されずに返され，エラーメッセージが表示される．
| Out[62]= |  |
|
素数ベキを含むかどうかのテスト
PrimePowerQのアルゴリズムは，まず
n の最小の素因数
p を計算し，次に1が得られるまで（この場合，
n は素数のベキ乗），または不可能になるまで（この場合，
n は素数のベキ乗ではない）
n による除算を試みる．
| Out[63]= |  |
|
| Out[64]= |  |
|
連立合同式を解く
中国余剰定理(Chinese Remainder Theorem)によると，連立合同式のある特定のクラスには常に解が存在する．
ChineseRemainder[list1, list2]を使うと，
Mod[r, list2]が
list1である非負の最小の整数
r が求められる．解は
list2の要素の最小公倍数の唯一のモジュロである．
次の式は， 2440 mod 4， 2441 mod 9および 2442 mod 121を意味している．
| Out[65]= |  |
|
| Out[66]= |  |
|
| Out[67]= |  |
|
原始根の計算
PrimitiveRoot[n]は，
mod n の乗算で，
n と互いに素である数の群の生成元を返す．生成元は
n が2，4，奇数の素数のベキ乗，または奇数の素数のベキ乗の2倍である場合にのみ存在する．
n が素数または素数のベキ乗の場合は，正の最小の原始根が返される．
| Out[68]= |  |
|
| Out[69]= |  |
|
| Out[70]= |  |
|
| Out[71]= |  |
|
引数が合成数であり，素数のベキ乗でも素数の2倍のベキ乗でもない場合，この関数は評価されない．
| Out[72]= |  |
|
平方の和あるいは他のベキとしての整数の表記
| Out[73]= |  |
|
list1である非負の最小の整数r を返す
