Fermat's 4n+1 Theorem

2 secs 1024 MB
YSatUT's icon YSatUT
Tweet
Problem
Submissions
Test cases
Editorial

p=2p=2ならば、条件を満たす組は(x,y)=(1,1)(x,y)=(1,1)のみです。
また、mod 4{\rm mod}\ 4においてx2,y2≡0,1x^2,y^2\equiv 0,1より、x2+y2≡0,1,2x^2+y^2\equiv 0,1,2です。よって、p≡3(mod 4)p\equiv 3({\rm mod}\ 4)の場合、x2+y2=px^2+y^2=pとなるような(x,y)(x,y)の組は存在しません。
そのため、以下ではp≡1(mod 4)p\equiv 1({\rm mod}\ 4)の場合を考えます。この時、オイラーの規準より、r2≡−1(mod p)r^2\equiv -1({\rm mod}\ p)かつ1≤r<p21\leq r<\frac{p}{2}を満たす整数rrが存在します。具体的なrrの求め方は以下の通りです。

  • まず、1≤z≤p−11\leq z\leq p-1を満たす整数zzをランダムに1つ選択します。
  • 次に、mod p{\rm mod}\ pにおいてzp−12≡1z^\frac{p-1}{2}\equiv 1とzp−12≡−1z^\frac{p-1}{2}\equiv -1のどちらが成立するかを判定します。なお、オイラーの規準より、zp−12≡1z^\frac{p-1}{2}\equiv 1であることは、zzがppの平方剰余となる、すなわちs2≡z(mod p)s^2\equiv z({\rm mod}\ p)を満たす整数ssが存在することと同値です。奇素数ppに対してppの平方剰余はp−12\frac{p-1}{2}個存在するので、zp−12≡1z^\frac{p-1}{2}\equiv 1となる確率は12\frac{1}{2}です。よって、zp−12≡−1z^\frac{p-1}{2}\equiv -1となる確率も12\frac{1}{2}なので、zp−12≡−1z^\frac{p-1}{2}\equiv -1となるzzは平均2回の試行で見つかります。
  • zp−12≡−1z^\frac{p-1}{2}\equiv -1となるzzが見つかった場合、r≡zp−14r\equiv z^\frac{p-1}{4}とすれば、r2≡zp−12≡−1r^2\equiv z^\frac{p-1}{2}\equiv -1となります。最後に、r>p2r>\frac{p}{2}の場合は、r←p−rr\leftarrow p-rとすれば1≤r<p21\leq r<\frac{p}{2}となり、かつr2≡−1(mod p)r^2\equiv -1({\rm mod}\ p)も成立します。

この時、k=r2+1pk=\frac{r^2+1}{p}とすると、12+r2=kp1^2+r^2=kpとなります。また、この時k≤p2k\leq\frac{p}{2}も成立します。
次に、x2+y2=kpx^2+y^2=kpかつ2≤k≤p22\leq k\leq \frac{p}{2}を満たす整数(x,y,k)(x,y,k)の組から、(x′)2+(y′)2=k′p(x')^2+(y')^2=k'pかつ1≤k′≤k21\leq k'\leq\frac{k}{2}を満たす整数(x′,y′,k′)(x',y',k')の組を生成するアルゴリズムPを考えます。

アルゴリズムPの手順

  • x=ak+b,y=ck+dx=ak+b,y=ck+dとします。ただし、a,b,c,da,b,c,dは全て整数であり、また∣b∣,∣d∣≤k2|b|,|d|\leq\frac{k}{2}が成り立っているものとします。
  • この時、mod k{\rm mod}\ kにおいてx2+y2≡b2+d2x^2+y^2\equiv b^2+d^2なので、b2+d2=nkb^2+d^2=nk（nnは整数）とおけます。このnnが1≤n≤k21\leq n\leq\frac{k}{2}を満たすことを、以下で証明します。
    • b,db,dは実数なのでb2+d2≥0  ∴nk≥0  ∴n≥0b^2+d^2\geq 0\ \ \therefore nk\geq 0\ \ \therefore n\geq 0
    • n=0n=0と仮定すると、x=ak,y=ckx=ak,y=ckよりx2+y2=(a2+c2)k2  ∴(a2+c2)k2=kp  ∴p=k(a2+c2)x^2+y^2=(a^2+c^2)k^2\ \ \therefore (a^2+c^2)k^2=kp\ \ \therefore p=k(a^2+c^2)　よって、kkはppの約数なので±1,±p\pm1,\pm pのいずれかですが、どれも2≤k≤p22\leq k\leq \frac{p}{2}を満たさないので矛盾します。よって、n≠0n\neq 0となり、先ほどのn≥0n\geq 0と合わせてn≥1n\geq 1となります。
    • ∣b∣,∣d∣≤k2|b|,|d|\leq\frac{k}{2}よりb2+d2≤k24  ∴b2+d2≤k22  ∴nk≤k22  ∴n≤k2b^2+d^2\leq\frac{k^2}{4}\ \ \therefore b^2+d^2\leq\frac{k^2}{2}\ \ \therefore nk\leq\frac{k^2}{2}\ \ \therefore n\leq\frac{k}{2}
  • このnnについて、np=b2+d2k⋅x2+y2k=(b2+d2)(x2+y2)k2=(bx+dy)2+(by−dx)2k2=(bx+dyk)2+(by−dxk)2=(ab+cd+n)2+(bc−ad)2np=\frac{b^2+d^2}{k}\cdot\frac{x^2+y^2}{k}=\frac{(b^2+d^2)(x^2+y^2)}{k^2}=\frac{(bx+dy)^2+(by-dx)^2}{k^2}=\left(\frac{bx+dy}{k}\right)^2+\left(\frac{by-dx}{k}\right)^2=(ab+cd+n)^2+(bc-ad)^2となります。よって、x′=ab+cd+n,y′=bc−ad,k′=nx'=ab+cd+n, y'=bc-ad,k'=nとすれば、(x′)2+(y′)2=k′p(x')^2+(y')^2=k'pかつ1≤k′≤k21\leq k'\leq\frac{k}{2}が成立します。

k′≤k2k'\leq\frac{k}{2}より、アルゴリズムPを適用するごとにkkの値は半分以下になっていき、いずれ11に収束するので、x2+y2=px^2+y^2=pを満たす(x,y)(x,y)の組が求まります。
r2≡−1(mod p)r^2\equiv -1({\rm mod}\ p)を満たすrrの発見に必要な計算量はO(log⁡p)O(\log p)であり、アルゴリズムPの繰り返し回数もO(log⁡p)O(\log p)なので、全体の計算量はO(log⁡p)O(\log p)となります。

ans.py

参考

本解説で参考にしたサイトは以下の通りです。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378