quadratic

２次ふるいは以下の定理に基づいている
定理

$\begin{rm} $\exists x$, $y\in\mbox{\bf Z}$\space with $(x\neq y;x+y\neq n;0<x,y<... ...grightarrow \gcd(x\pm y,m)$\space は自明でない $n$\space の因子である。 \end{rm}$

Proof.
$x^2\equiv y^2 (\mathop{\rm mod}m)$ より $x^2-y^2=(x+y)(x-y)\equiv 0 (\mathop{\rm mod}m)$
m|(x²-y²) であるので、

i)
m|(x+y)
ii)
m|(x-y)
iii)
m=m₁m₂ (m₁,m₂>1) m₁|x+y かつ m₂|x-y
のいずれかであることが容易にわかる。
i) の場合 $x+y\equiv 0(\mathop{\rm mod}m)$ より $\exists a\in\mbox{\bf Z}$ such that x+y = am
x = am-y
= (a-1)m+ m-y
ここでa-1=0
∵ $\left\{ \begin{array} {l} a-1\gt なら x\gt m\ a-1<0 なら x<0 \end{array}\right.$
よって x=m-y
しかし、これは $x+y\neq n$ に反する。
ii) の場合 $x-y\equiv 0(\mathop{\rm mod}m)$ より $\exists a\in\mbox{\bf Z}$ such that x-y = am
x = am+y
ここでa=0
∵ $\left\{ \begin{array} {l} a\gt なら x\gt m\ a<0 なら x<0 \end{array}\right.$
よって x=y
しかし、これは $x\neq y$ に反する。
iii) の場合 m=m₁m₂ (m₁,m₂>1) m₁|x+y かつ m₂|x-y
$\gcd(x+y,m)=m_1$
$\gcd(x-y,m)=m_2$

Kensuke Shimokawa
1/13/2001