MathLabs

第3問

n>1n>1 が整数となるすべての整数 (2n+1)/n2(2^n+1)/n^2 を求めよ。
ステップ 2/4: 位数の議論から p=3
前のステップ次のステップ
x=min⁡{r>0:2r≡−1(modp)},y=min⁡{r>0:2r≡1(modp)},x∣nx=\min\{r>0:2^r\equiv-1\pmod p\},\quad y=\min\{r>0:2^r\equiv1\pmod p\},\quad x\mid n
詳しい解説

xx と yy を、2x≡−1(modp)2^x\equiv-1\pmod p および 2y≡1(modp)2^y\equiv1\pmod p を満たす最小の正整数とする。n=ys+rn=ys+r、0≤r<y0\le r<y と書く。2n≡−12^n\equiv-1 と 2y≡12^y\equiv1 より 2r≡−12^r\equiv-1、従って r>0r>0 かつ x≤r<yx\le r<y。さらに n=hx+kn=hx+k、0≤k<x0\le k<x とすると −1≡(−1)h2k(modp)-1\equiv(-1)^h2^k\pmod p。hh 偶数なら 2k≡−12^k\equiv-1 で、k>0k>0 は xx の最小性に反する。hh 奇数なら 2k≡12^k\equiv1 で、0<k<x<y0<k<x<y は yy の最小性に反する。ゆえに k=0k=0、x∣nx\mid n。また x≤r<y<px\le r<y<p で、pp は nn の最小素因子だから x=1x=1。従って 2≡−1(modp)2\equiv-1\pmod p、p=3p=3。