ガランガラのブログ

数学や好きな音楽について書くことが多いです。

n-1 と (n^p-1)/(n-1) の最大公約数

整数論小ネタ

ここでは $n$ を整数, $p$ を奇素数として $n-1$ と $\dfrac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+ \cdots + n+1$ の最大公約数を求めたいと思います.

少し具体例を見てみましょう.

$p=3$ のとき：

$n=1$ のとき $gcd(n-1, n^2+x+1)=gcd(0, 3)=3$

$n=2$ のとき $gcd(n-1, n^2+x+1)=gcd(1, 7)=1$

$n=3$ のとき $gcd(n-1, n^2+x+1)=gcd(2, 13)=1$

$n=4$ のとき $gcd(n-1, n^2+x+1)=gcd(3, 21)=3$

$n=5$ のとき $gcd(n-1, n^2+x+1)=gcd(4, 31)=1$

$n=6$ のとき $gcd(n-1, n^2+x+1)=gcd(5, 43)=1$

$n=7$ のとき $gcd(n-1, n^2+x+1)=gcd(6, 57)=3$

$p=5$ のとき：

$n=1$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(0, 5)=5$

$n=2$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(1, 31)=1$

$n=3$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(2, 121)=1$

$n=4$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(3, 341)=1$

$n=5$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(4, 781)=1$

$n=6$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(5, 1555)=5$

$n=7$ のとき $gcd(n-1, n^4+n^3+n^2+n+1)=gcd(6, 2801)=1$

少しだけですがなにやら「 $1$ と $p$ 」のどちらかになりそうですね. 証明しましょう.

命題 1. $n$ を整数, $p$ を奇素数として $n-1$ と $\dfrac{n^p-1}{n-1}=n^{p-1}+n^{p-2}+ \cdots + n+1$ の最大公約数は $1$ または $p$ である.

証明まず, 因数定理よりある多項式 $Q(x) \in \mathbb{Z} [ x ]$ が存在して

$x^{p-1}+x^{p-2}+ \cdots + x+1=Q(x)(x-1)+p$

となる. $d$ を任意の公約数とすると

$p= (x^{p-1}+x^{p-2}+ \cdots + x+1)-(Q(x)(x-1)) = d$ の倍数

より $d$ は $p$ を割る. よって最大公約数は $1$ または $p$ である. (終)

何か間違いなどあれば教えてください