MathLabs

第6問

整数の順序対 (x,y)(x,y) を、gcd⁡(x,y)=1\gcd(x,y)=1 を満たすとき原始点と呼ぶ。原始点の有限集合 SS に対し、正の整数 nn と整数 a0,a1,…,ana_0,a_1,\ldots,a_n が存在して、すべての (x,y)∈S(x,y)\in S について a0xn+a1xn−1y+a2xn−2y2+⋯+an−1xyn−1+anyn=1a_0x^n+a_1x^{n-1}y+a_2x^{n-2}y^2+\cdots+a_{n-1}xy^{n-1}+a_ny^n=1 となることを証明せよ。
ステップ 4/8: 決定的な互いに素性を示す
前のステップ次のステップ
ざっくり言うと

素数 modulo で行列式が0ならベクトルは比例する。

gcd⁡(P(xk,yk),D)=1\gcd(P(x_k,y_k),D)=1
詳しい解説

P(xk,yk)P(x_k,y_k) とある di=yixk−xiykd_i=y_ix_k-x_iy_k の両方を割る素数 pp を固定する。両点は原始点なので、pp modulo での還元は零ベクトルでない。行列式が0なので比例し、零でない λ\lambda により (xi,yi)≡λq(modp)(x_i,y_i)\equiv\lambda q\pmod p となる。斉次性から P(xi,yi)=1P(x_i,y_i)=1 ≡λnP(xk,yk)≡0(modp)\equiv\lambda^nP(x_k,y_k)\equiv0\pmod p となり矛盾する。よって P(xk,yk)P(x_k,y_k) と各 di=yixk−xiykd_i=y_ix_k-x_iy_k は互いに素であり、gcd⁡(P(xk,yk),D)=1\gcd(P(x_k,y_k),D)=1 である。