整数のマイナー知識達

定理,整数,OMC

3017

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

ルジャンドルの定理

$v_{p} (n!) = \sum_{k = 1}^{\infty} [\frac{n}{p^{k}}]$

クンマーの定理

$k$ を $(a - b)_{(p)} + b_{(p)}$ を計算したときに起こる繰り上がりの回数とするとき
$v_{p} (_{a} C_{b}) = k$

Lucasの定理

$a_{(p)} = a_{k} a_{k - 1} . . . a_{1} a_{0}, b_{(p)} = b_{k} b_{k - 1} . . . b_{1} b_{0}$ とすると
$_{a} C_{b} \equiv \prod_{i = 0}^{k}_{a_{i}} C_{b_{i}} (mod p)$

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

LTEの補題

$v_{p} (a - b) > \frac{1}{p - 1}, v_{p} (a) = 0$ のとき
$v_{p} (a^{n} - b^{n}) = v_{p} (a - b) + v_{p} (n)$

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

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

$(1)$ $v (x - y) > \frac{e}{p - 1}$ のとき $v (x^{n} - y^{n}) = v (x - y) + v (n)$
$0 < v (x - y) \leq \frac{e}{p - 1}$ のときは $L = \log_{p} (\frac{p e}{(p - 1) v (x - y)})$ とすると
$(2)$ $v (n) \leq L$ のとき $v (x^{n} - y^{n}) = p^{v (n)} v (x - y)$
$(3)$ $v (n) > L$ のとき $v (x^{n} - y^{n}) = v (x^{p^{[L]}} - y^{p^{[L]}}) + v (n) - e [L]$
特に $L$ が整数でないなら $v (x^{n} - y^{n}) = p^{[L]} v (x - y) + v (n) - e [L]$

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

$α, β$ を $x^{2} + p x + q = 0$ の $2$ 解とし, $a_{n} = \frac{α^{n} - β^{n}}{α - β}$ とおく. $a_{n}$ が $p$ で割り切れるとき, 任意の $m$ について
$v_{p} (a_{n m}) = v_{p} (a_{n}) + v_{p} (m)$
ただし, $p = 2$ のときは $a_{n}$ が $4$ で割り切れることを要請するものとする.

原始的素因数

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

ジグモンディーの定理

$x, y (x > y > 0)$ を互いに素な整数とする. $a_{n} = x^{n} - y^{n}$ は以下の例外を除いて原始的素因数を持つ.

$n = 1, x - y = 1$ のとき( $a_{1} = 1$ )
$n = 2$ かつ $x + y = 2^{k}$ のとき( $a_{2} = 2^{k} a_{1}$ )
$n = 6, x = 2, y = 1$ のとき( $a_{6} = 63 = a_{2}^{2} a_{3}$ )

また $a_{n} = x^{n} + y^{n}$ とすると $n = 3, x = 2, y = 1$ のとき( $a_{3} = 9 = a_{2}^{2}$ )を除いて $a_{n}$ は原始的素因数を持つ.

前半の主張が有名だが後半は $a_{2 n} = x^{2 n} - y^{2 n}$ に対して前半の主張を用いれば容易に示せる.

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

Lucas数列,Lehmer数列

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

$n$ が奇数のとき ${\tilde{u}}_{n} = \frac{α^{n} - β^{n}}{α - β}$
$n$ が偶数のとき ${\tilde{u}}_{n} = \frac{α^{n} - β^{n}}{α^{2} - β^{2}}$
と定義し,これをLehmer数列と呼ぶ.
$\frac{α_{1}}{α_{2}} = \frac{β_{1}}{β_{2}} = \pm 1, \pm i$ のときこれが定める数列は $\pm$ の差などを除いて同じなので同値という.

Bilu-Hanrot-Voutier

$n > 30$ のとき任意のLucas数列,Lehmer数列は原始的素因数を持つ.
全ての $n$ -defectiveなLucasペア $(\frac{a - \sqrt{b}}{2}, \frac{a + \sqrt{b}}{2})$ は表1で与えられる.
$n \neq 3, 4, 5, 6, 8, 10, 12$ とするとき $n$ -defectiveなLehmerペア $(\frac{\sqrt{a} - \sqrt{b}}{2}, \frac{\sqrt{a} + \sqrt{b}}{2})$ は表2で与えられる.
$n = 3, 4, 5, 6, 8, 10, 12$ のとき $n$ \defectiveなLehmerペア $(\frac{\sqrt{a} - \sqrt{b}}{2}, \frac{\sqrt{a} + \sqrt{b}}{2})$ は図1によって与えられる.

$n$	$(a, b)$
1	全ての $(a, b)$
2	$(1, 1 - 4 q) (q \neq 1), (2^{k}, 4^{k} - 4 q) (q \equiv 1 (mod 2), (k, q) \neq (1, 1))$
3	$(m, 4 - 3 m^{2}) (m > 1), (m, 4 \cdot 3^{k} - 3 m^{2}) (m ≢ 0 (mod 3), (k, m) \neq (1, 2)))$
4	$(m, 2 - m^{2}) (m > 1, m \equiv 1 (mod 2)), (m, 4 - m^{2}) (m > 2, m \equiv 0 (mod 2))$
5	$(1, 5), (1, - 7), (2, - 40), (1, - 11), (12, 76), (12, - 1364)$
6	$(m, (4 - m^{2}) / 3) (m > 3, m ≢ 0 (mod 3)), (m, (4^{k + 1} - m^{2}) / 3) (m \equiv \pm 1 (mod 6))$
6	$(m, 4 - m^{2} / 3) (m \equiv 0 (mod 3)), (m, 2^{k + 2} - m^{2} / 3, (m \equiv 3 (mod 6)))$
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 = n^{2} + m^{2}$ と表される $\Leftrightarrow p \equiv 1, 2 (mod 4)$
左辺の分解の仕方は符号や $n, m$ の置換を除き一意である.