Modular-Arithmetic
四個根中的兩個必須大於 N/2
定理：讓 $ y $ 是二次餘數 $ \mathbb{Z}_N $ * 在哪裡 $ N=pq $ .
正好有四個整數 $ x_1, x_2, x_3, x_4 $ 在哪裡 $ 0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N $ 這樣 $ y = x_i^2 \pmod{N} $ 為了 $ i=1,2,3,4 $ .
上面的定理簡單地說明了四個根中的兩個必須大於 $ \frac{N}{2} $ .
大多數論文會說這個結果是眾所周知的，而沒有提供任何詳細的證明。我們如何證明 $ 0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N $ ?
每個根 $ r $ 在 $ (\mathbb{Z}/n\mathbb{Z})^\times $ 有一個“共軛”根 $ -r \equiv n - r $ 因為瑣碎 $ (-r)^2 \equiv r^2 \pmod{n} $ .
如果恰好有四個根（每個素因子通常會產生兩個根，嗯，一個根及其共軛，它們生成模 $ n $ 通過 CRT - 有關更多詳細資訊，請參閱下面的 gammatester 的答案）我們正好有兩對共軛根。在每一對中，恰好有一個根大於 $ n/2 $ .
通過簡單的算術，可以看出 $ r < n/2 \iff n-r > n/2 $ . 因此，假設 $ n $ 是奇怪的（這排除了 $ r = n/2 $ )，因此每對共軛根中恰好有一個大於 $ n/2 $ .