数学--数论--二次探测定理

定理

若 p 为 质 数 , x 2 ≡ 1 ( m o d p ) , 则 x ≡ 1 ( m o d p ) 或 x ≡ p − 1 ( m o d p ) 若p为质数,x2≡1(modp),则x≡1(modp)或x≡p−1(modp)若p为质数,x2≡1(modp),则x≡1(modp)或x≡p−1(modp)

证明:

移 项 可 得 : x 2 − 1 ≡ 0 ( m o d p ) , 也 就 是 ( x + 1 ) ( x − 1 ) ≡ 0 ( m o d p ) . 移项可得:x2−1≡0(modp),也就是(x+1)(x−1)≡0(modp).移项可得:x2−1≡0(modp),也就是(x+1)(x−1)≡0(modp).

这 个 式 子 等 价 于 p ∣ ( x + 1 ) ( x − 1 ) . 这个式子等价于p|(x+1)(x−1).这个式子等价于p∣(x+1)(x−1).

容 易 想 到 p ∣ ( x + 1 ) 或 者 p ∣ ( x − 1 ) 都 是 可 行 的 , 那 么 有 没 有 p ∤ ( x − 1 ) , p ∤ ( x + 1 ) , 而 p ∣ ( x − 1 ) ( x + 1 ) 呢 ? 容易想到p|(x+1)或者p|(x−1)都是可行的,那么有没有p∤(x−1),p∤(x+1),而p|(x−1)(x+1)呢?容易想到p∣(x+1)或者p∣(x−1)都是可行的,那么有没有p∤(x−1),p∤(x+1),而p∣(x−1)(x+1)呢?

若 出 现 上 面 这 种 情 况 , 首 先 要 保 证 的 是 g c d ( p , x − 1 ) > 1 且 g c d ( p , x + 1 ) > 1. 可 以 理 解 为 p 这 个 因 子 被 " 拆 成 " 了 两 份 , 一 份 和 ( x − 1 ) 融 合 在 了 一 起 , 另 一 份 和 ( x + 1 ) 融 合 在 了 一 起 . 而 p 是 质 数 , 只 能 拆 成 p 和 1 两 个 因 子 ; 无 论 怎 么 拆 , 都 不 能 使 得 两 个 g c d 同 时 大 于 1. 这 算 是 一 种 不 严 谨 的 证 法 , 证 明 了 一 定 有 p ∣ ( x − 1 ) 或 p ∣ ( x + 1 ) 若出现上面这种情况,首先要保证的是gcd(p,x−1)>1且gcd(p,x+1)>1.\\可以理解为p这个因子被"拆成"了两份,一份和(x−1)融合在了一起,另一份和(x+1)融合在了一起.而p是质数,只能拆成p和1两个因子;\\无论怎么拆,都不能使得两个gcd同时大于1.这算是一种不严谨的证法,证明了一定有p|(x−1)或p|(x+1)若出现上面这种情况,首先要保证的是gcd(p,x−1)>1且gcd(p,x+1)>1.

可以理解为p这个因子被"拆成"了两份,一份和(x−1)融合在了一起,另一份和(x+1)融合在了一起.而p是质数,只能拆成p和1两个因子;

无论怎么拆,都不能使得两个gcd同时大于1.这算是一种不严谨的证法,证明了一定有p∣(x−1)或p∣(x+1)

接 下 来 就 简 单 了 : p ∣ ( x + 1 ) 等 价 于 x + 1 ≡ 0 ( m o d p ) , 即 x ≡ p − 1 ( m o d p ) . p ∣ ( x − 1 ) 同 理 . 这 样 就 证 明 完 毕 了 . 接下来就简单了:p|(x+1)等价于x+1≡0(modp),即x≡p−1(modp).p|(x−1)同理.这样就证明完毕了.接下来就简单了:p∣(x+1)等价于x+1≡0(modp),即x≡p−1(modp).p∣(x−1)同理.这样就证明完毕了.