42
大学数学基礎解説
文献あり

整数のマイナー知識達

2696
1

OMCとかで役立って欲しいです.たまに追加したい.記述問題で用いると大幅減点される(だろう)ものも含んでいます.補足等あれば教えてください.
pを素数とし,vp(x)xpで割り切れる回数を表す.

ルジャンドルの定理

vp(n!)=k=1[npk]

クンマーの定理

k(ab)(p)+b(p)を計算したときに起こる繰り上がりの回数とするとき
vp(aCb)=k

Lucasの定理

a(p)=akak1...a1a0, b(p)=bkbk1...b1b0とすると
aCbi=0kaiCbi (modp)

この記事 に一般化らしきものがあるので気が向いたら書きたい.

LTEの補題

vp(ab)>1p1, vp(a)=0のとき
vp(anbn)=vp(ab)+vp(n)

これは次のような一般化を持つ(はず)

Kを代数体,v(p)=eとする.
x,yKv(x)=v(y)=0,v(xy)>0を満たすとき,nを任意の整数とすると,以下が成立する.

(1)v(xy)>ep1のときv(xnyn)=v(xy)+v(n)
0<v(xy)ep1のときはL=logp(pe(p1)v(xy))とすると
(2)v(n)Lのときv(xnyn)=pv(n)v(xy)
(3)v(n)>Lのときv(xnyn)=v(xp[L]yp[L])+v(n)e[L]
特にLが整数でないならv(xnyn)=p[L]v(xy)+v(n)e[L]

特に次の結果はたまに使える

α,βx2+px+q=02解とし,an=αnβnαβとおく.anpで割り切れるとき, 任意のmについて
vp(anm)=vp(an)+vp(m)
ただし,p=2のときはan4で割り切れることを要請するものとする.

原始的素因数

{an}を整数列とする.anの素因数pであってk<nに対してakpで割り切れないときpanの原始的素因数という.逆に原始的素因数を持たないときn-defectiveと呼ぶ.

ジグモンディーの定理

x,y (x>y>0)を互いに素な整数とする.an=xnynは以下の例外を除いて原始的素因数を持つ.

  • n=1, xy=1のとき(a1=1)
  • n=2かつx+y=2kのとき(a2=2ka1)
  • n=6, x=2, y=1のとき(a6=63=a22a3)

またan=xn+ynとするとn=3, x=2, y=1のとき(a3=9=a22)を除いてanは原始的素因数を持つ.

前半の主張が有名だが後半はa2n=x2ny2nに対して前半の主張を用いれば容易に示せる.

これには一般化や原始的素因数の値の範囲に関する研究がなされているが強力な以下の定理を紹介する.

Lucas数列,Lehmer数列

α+β, αβ0でない互いに素な整数で,αβ1の冪根でないときこの(α,β)をLucasペアと呼ぶ.さらに
un=αnβnαβと定義し,これをLucas数列と呼ぶ.
(α+β)2, αβ0でない互いに素な整数で,αβ1の冪根でないとき(α,β)をLehmerペアと呼ぶ.さらに

  • nが奇数のときu~n=αnβnαβ
  • nが偶数のときu~n=αnβnα2β2
    と定義し,これをLehmer数列と呼ぶ.
    α1α2=β1β2=±1,±iのときこれが定める数列は±の差などを除いて同じなので同値という.
Bilu-Hanrot-Voutier
  • n>30のとき任意のLucas数列,Lehmer数列は原始的素因数を持つ.
  • 全てのn-defectiveなLucasペア(ab2,a+b2)は表1で与えられる.
  • n3,4,5,6,8,10,12とするときn-defectiveなLehmerペア(ab2,a+b2)は表2で与えられる.
  • n=3,4,5,6,8,10,12のときn\defectiveなLehmerペア(ab2,a+b2)は図1によって与えられる.
n(a,b)
1全ての(a,b)
2(1,14q)(q1), (2k,4k4q)(q1(mod2),(k,q)(1,1))
3(m,43m2)(m>1), (m,43k3m2)(m0(mod3),(k,m)(1,2)))
4(m,2m2)(m>1,m1(mod2)), (m,4m2)(m>2,m0(mod2))
5(1,5),(1,7),(2,40),(1,11),(12,76),(12,1364)
6(m,(4m2)/3)(m>3,m0(mod3)), (m,(4k+1m2)/3)(m±1(mod6))
6(m,4m2/3)(m0(mod3)), (m,2k+2m2/3,(m3(mod6)))
7(1,7),(1,19)
8(2,24),(1,7)
10(2,8),(5,3),(5,47)
12(1,5),(1,7),(1,11),(2,56),(1,15),(1,19)
13(1,7)
18(1,7)
30(1,7)

(表1 n-defectiveなLucasペアとなる(a,b).ただしn=1,2,3,4,6は除く,qは非零整数k,mは正整数)

n(a,b)
1全ての(a,b)
2全ての(a,b)
7(1,7),(1,19),(3,5),(5,7),(13,3),(14,22)
9(5,3),(7,1),(7,5)
13(1,7)
14(3,13),(5,3),(7,1),(7,5),(19,1),(22,14)
15(7,1),(10,2)
18(1,7),(3,5),(5,7)
24(3,5),(5,3)
26(7,1)
30(1,7),(2,10)

(表2 n-defectiveになる(a,b))

!FORMULA[127][38042][0]-defectiveな(a,b)(書くのが大変だったので本文にあったやつをそのまま貼りました) n-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より引用した

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

p=n2+m2と表される p1,2(mod4)
左辺の分解の仕方は符号やn,mの置換を除き一意である.

ヤコビの二平方和定理

nを正整数とする.このときx2+y2=n(x,yZ)の解の個数は
r2(n)=42| ̸d|n(1)d12

ラグランジュの4平方和定理,ヤコビの四平方和定理

(1)全ての正整数n4つの(0を含む)平方数の和で表される.
(2) x2+y2+z2+w2=nの解の個数は
r4(n)=84| ̸d|nd

とりあえずこの辺りにしておきます.

参考文献

投稿日:2021113
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

整数が好きです

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中