OMCとかで役立って欲しいです.たまに追加したい.記述問題で用いると大幅減点される(だろう)ものも含んでいます.補足等あれば教えてください.
を素数とし,でがで割り切れる回数を表す.
クンマーの定理
をを計算したときに起こる繰り上がりの回数とするとき
この記事
に一般化らしきものがあるので気が向いたら書きたい.
これは次のような一般化を持つ(はず)
を代数体,とする.
がを満たすとき,を任意の整数とすると,以下が成立する.
のとき
のときはとすると
のとき
のとき
特にが整数でないなら
特に次の結果はたまに使える
をの解とし,とおく.がで割り切れるとき, 任意のについて
ただし,のときはがで割り切れることを要請するものとする.
原始的素因数
を整数列とする.の素因数であってに対してがで割り切れないときをの原始的素因数という.逆に原始的素因数を持たないとき-defectiveと呼ぶ.
ジグモンディーの定理
を互いに素な整数とする.は以下の例外を除いて原始的素因数を持つ.
またとするとのとき()を除いては原始的素因数を持つ.
前半の主張が有名だが後半はに対して前半の主張を用いれば容易に示せる.
これには一般化や原始的素因数の値の範囲に関する研究がなされているが強力な以下の定理を紹介する.
Lucas数列,Lehmer数列
がでない互いに素な整数で,がの冪根でないときこのをLucasペアと呼ぶ.さらに
と定義し,これをLucas数列と呼ぶ.
がでない互いに素な整数で,がの冪根でないときをLehmerペアと呼ぶ.さらに
- が奇数のとき
- が偶数のとき
と定義し,これをLehmer数列と呼ぶ.
のときこれが定める数列はの差などを除いて同じなので同値という.
Bilu-Hanrot-Voutier
- のとき任意のLucas数列,Lehmer数列は原始的素因数を持つ.
- 全ての-defectiveなLucasペアは表1で与えられる.
- とするとき-defectiveなLehmerペアは表2で与えられる.
- のとき\defectiveなLehmerペアは図1によって与えられる.
(表 -defectiveなLucasペアとなる.ただしは除く,は非零整数は正整数)
(表2 -defectiveになる)
-defectiveな(a,b)(書くのが大変だったので本文にあったやつをそのまま貼りました)
この定理,表はYuri Bilu, Guillaume Hanrot, Paul Voutier. Existence of Primitive Divisors of Lucas and Lehmer
Numbers. [Research Report] RR-3792, INRIA. 1999, pp.41. ffinria-00072867より引用した
フェルマーの二平方和定理
と表される
左辺の分解の仕方は符号やの置換を除き一意である.
ラグランジュの4平方和定理,ヤコビの四平方和定理
全ての正整数はつの(を含む)平方数の和で表される.
の解の個数は
とりあえずこの辺りにしておきます.