|
|
問題B-3
pを奇素数、nを自然数とし、f(x)=(x+1)^n-x^n とする。
xが自然数全体を動くとき、f(x)をpで割った余りが0,1,2,…,p-1のすべての値をとることを、
f(x)は全域性をもつと呼ぶことにする。
このとき、pに対してf(x)が全域性をもつnの値をすべて求めよ。
（nが求めた値のときf(x)は全域性をもつこと。およびそれ以外の値のときf(x)は全域性をもたないことを証明すること）
参考サイト
まずは探してみる。
OPTION ARITHMETIC RATIONAL
LET P=3 !素数
DIM F(0 TO P-1) !数字0から(p-1)
FOR N=1 TO 50
PRINT STR$(N);": ";
MAT F=ZER
FOR X=1 TO P
LET T=1 !1+Σ[r=1,n-1]C(n,r)x^r
FOR R=1 TO N-1
LET T=T+MOD(COMB(N,R),P)*MOD(X^R, P)
NEXT R
LET T=MOD(T,P)
PRINT T; !debug
IF F(T)=1 THEN EXIT FOR !既出なら
LET F(T)=1
NEXT X
IF X>P-1 THEN PRINT "←題意を満たす";
PRINT
NEXT N
END
考察
p=3のとき、
n=1の場合、f(x)=(x+1)^1-x^1=1
常に1で0,2が現れないので、題意を満たさない。
n=2の場合、f(x)=(x+1)^2-x^2=2x+1
x=1,2,3,4,5,6,7,8,9,…に対して、
f(x)=3,5,7,9,11,13,15,17,19,…（奇数列）なので、0,2,1,0,2,1,0,2,1,…
この並びは、他の奇素数に対しても題意を満たす。
先頭からp個までのxで、f(x)≡3,5,7,9,…,0,2,4,6,8,…,(p-1),1 (mod p)となる。
↑
p
具体的には、
p=5の場合、3,0,2,4,1
p=7の場合、3,5,0,2,4,6,1
p=11の場合、3,5,7,9,0,2,4,6,8,10,1
：
他の解を見つけることを考える。
xのべき乗について
x x^2 x^3 x^4 x^5 x^6 x^7 x^8 … (mod 3)
1: ① 1 1 1 1 1 1 1 …
2: 2 ① 2 1 2 1 2 1 …
3: 0 0 0 0 0 0 0 0 …
4: ① 1 1 1 1 1 1 1 …
5: 2 ① 2 1 2 1 2 1 …
6: 0 0 0 0 0 0 0 0 …
：
すなわち
k=0,1,2,3,…として、x^(2k+1)≡x、x^(2k+2)≡x^2
なので、
n=3の場合
f(x)=(x+1)^3-x^3=3x^2+3x+1≡1 (mod 3)
n=4の場合
f(x)=(x+1)^4-x^4=4x^3+6x^2+4x+1≡4x+6x^2+4x+1≡6x^2+8x+1≡2x+1 (mod 3)
n=5の場合
f(x)=(x+1)^5-x^5=5x^4+10x^3+10x^2+5x+1≡5x^2+10x+10x^2+5x+1≡15x^2+15x+1≡1 (mod 3)
n=6の場合
f(x)=(x+1)^6-x^6=6x^5+15x^4+20x^3+15x^2+6x+1
≡6x+15x^2+20x+15x^2+6x+1≡30x^2+32x+1≡2x+1 (mod 3)
n=7の場合
f(x)=(x+1)^7-x^7=7x^6+21x^5+35x^4+35x^3+21x^2+7x+1
≡7x^2+21x+35x^2+35x+21x^2+7x+1≡63x^2+63x+1≡1 (mod 3)
n=8の場合
f(x)=(x+1)^8-x^8=8x^7+28x^6+56x^5+70x^4+56x^3+28x^2+8x+1
≡8x+28x^2+56x+70x^2+56x+28x^2+8x+1≡126x^2+128x+1≡2x+1 (mod 3)
：
p=3の場合、f(x)は、1、2x+1の繰り返しとなる。
以上より、f(x)=(x+1)^n-x^n≡2x+1 (mod 3)を満たすnを見つける。
これを満たすものは、n=2,4,6,8,…である。
p=5の場合、f(x)は、1、2x+1、3x^2+3x+1、4x^3+x^2+4x+1の繰り返しとなる。
一般に、
f(x)=(x+1)^n-x^n≡2x+1 (mod p)を満たすnを見つける。
xのべき乗について
x=0,1,2,3,…,(p-1)に対して、x,x^2,x^3,…,x^(p-1)を考える。
(1+x)^n=Σ[r=0,n]{C(n,r)x^r}=1+Σ[r=1,n-1]{C(n,r)x^r}+x^nより、
f(x)=(x+1)^n-x^n=1+Σ[r=1,n-1]{C(n,r)x^r}
k=0,1,2,3,…、m=1,2,3,…,(p-1)として、x^((p-1)k+m)≡x^mなので、
x^mの係数をまとめると、Σ[r=(p-1)k+m≦n-1]C(n,r) (mod p)
これが、2x+1すなわち2,0,0,…,0となれば題意を満たす。
2x+1の確認は、n=1,2,3,…,(p-1)の範囲でよい。(p-1)種類の多項式が繰り返される。
よって、n=(p-1)k+2である。
（終り）
OPTION ARITHMETIC RATIONAL
LET P=3 !素数
FOR N=1 TO 15
PRINT "N=";N
FOR M=1 TO P-1 !x^(k(p-1)+m)に対する
LET C=0
FOR R=M TO N-1 STEP P-1 !係数をまとめる
LET C=C+COMB(N,R)
NEXT R
PRINT "x^";STR$(M); C; MOD(C,P)
NEXT M
PRINT
NEXT N
END
|
|