[정수론](16)[이차잉여의 성질]

페르마 소정리의 제곱근

페르마의 소정리
gcd(a, p) = 1, p = 소수 => a^(p-1) ≡ 1 (mod p)
를 제곱근으로 보기

gcd(a, p) = 1일때,
A = a^((p-1)/2)라 한다면,
A^2 ≡ a^(p-1) ≡ 1 (mod p)이다.
즉, p | A^2 - 1 = (A+1)(A-1)이다.
by 소수의 가약성, p|(A-1) 또는 p|(A+1)이다.
따라서 A ≡ 1 or -1 (mod p)

오일러 판정법

p가 홀수인 소수, gcd(a, p) = 1이라면
a^((p-1)/2) ≡ (a/p) (mod p)이다.

증명

• a = QR
  즉, a^((p-1)/2) ≡ 1 (mod p)임을 보이자.
  by 이차잉여의 정의, ∃b, b^2 ≡ a (mod p)
  이때, b, p가 서로소이므로,
  by 페르마의 소정리, a^((p-1)/2) ≡ b^(p-1) ≡ 1 (mod p) 이다.
  따라서 참
• a = NR
  a^((p-1)/2) ≡ -1 (mod p)임을 보이자.
  항등식 x^((p-1)/2) - 1 ≡ 0 (mod p) 이 있다 가정하자.
  위의 증명에 의해 모든 이차잉여는 해당 항등식의 해다.
  by 고차합동방정식의 성질, 차수가 d인 합동식은 최대 d개의 해를 가진다
  따라서 합동식은 최대 (p-1)/2개의 해를 가진다.
  그러나 QR의 개수가 (p-1)/2개 이므로 결국 NR은 하나도 해가 될 수 없다.
  즉, 페르마의 소정리
  $(a^{p-1}) \equiv(a^{\frac{p-1}{2}}+1) \times (a^{\frac{p-1}{2}}-1) \equiv 1 \space(mod \space p)$에서 앞의 식은 QR이, 뒤의 식은 NR이 만족시킨다.

가우스 μ함수

μ(a, p) = a, 2a, ..., Pa를 p로 나눈 나머지를 -P~P 범위 사이에서 선택할 때 음수인 것의 개수

보조정리

p = 홀수 소수, gcd(a, p) = 1일때 a, 2a, ..., Pa를 p로 나눈 나머지를 -P~P 범위 사이에서 선택하면
각각의 나머지의 절댓값은 겹치지 않는다.
증명
ka = qp+r이라 하고 r 중 서로 같거나 부호만 다른 쌍kai, kaj가 존재한다 가정하자
(즉, ri = ±rj)
ia - (±ja) = (qip+ri) - (qjp+rj) = p(qi-(±qj))
따라서 p|(qi-(±qj)) 즉, p|(ia - (±ja)) = p|a(i - (±j))
이때 gcd(a, p) = 1이므로 p|(i - (±j))
삼각부등식을 이용하면
|i - (±j)| <= |i| + |±j| = i+j <= P + P = P-1 ??????????
따라서 i = (±j)이다.
이때 i, j > 0이므로 i = j이므로 서로 같거나 부호만 다른 쌍은 존재하지 않는다.

가우스 판정법

p는 홀수 소수, gcd(a, p)=1 일 때 (a/p)=(-1)^μ(a, p) (mod p)이다.

• 증명
  (p-1)/2를 P라고 두겠다.
  집합 S = {a, 2a, …, ((p-1)/2)a}라고 하고
  S의 모든 원소의 곱 = $P!\times a^{\frac{p-1}{2}} (mod \space p)$ 이다.이제 두 식을 비교하면
  $P!\times a^{\frac{p-1}{2}} \equiv P!\times (-1)^{μ(a, p)} \space (mod \space p)$
  P!은 p와 서로소이므로 나눠주면
  $a^{\frac{p-1}{2}} \equiv (-1)^{μ(a, p)} \space (mod \space p)$
  오일러 판정법에 의해 (a/p) = (-1)^μ(a, p) (mod p)
• p가 소수이므로 S의 모든 원소는 mod p에서 서로 다른 절댓값을 가진다.
  각 원소가 -p/2~p/2에 들어오게 mod p에 대해 연산하면
  보조정리 1에 의해 정확히 절댓값의 겹침 없이
  R = {±1, ±2, ±3, ..., ±(p-1)/2} (mod p) 가 된다.
  이때 R의 원소를 다 곱하면,
  = $P!\times (-1)^{μ(a, p)} \space (mod \space p)$