2차 잉여

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 정의2. 성질
2.1. 오일러 판정법2.2. 가우스 판정법2.3. 가우스의 상호법칙
3. 관련 문서


二次剩餘
Quadratic residue.

1. 정의[편집]

mm이 1보다 큰 자연수이고, gcd⁡(a,m)=1\gcd\left(a,m\right)=1일 때, 합동식 x2≡a(mod m)x^2\equiv a\left(\text{mod}\,m\right)이 해를 가지면 aa를 법 mm에 관한 2차 잉여(quadratic residue)라 하고, 이 합동식이 해를 갖지 않으면 aa를 법 mm에 관한 2차 비잉여(non-quadratic residue)라 한다. pp가 임의의 홀수인 소수이고, gcd⁡(a,p)=1\gcd\left(a,p\right)=1일 때 aa가 법 pp에 관한 2차 잉여이면 (ap)=1\left(\frac{a}{p}\right)=1로 표시하고, 그렇지 않으면 (ap)=−1\left(\frac{a}{p}\right)=-1로 표시한다. 이 때, (ap)\left(\frac{a}{p}\right)를 르장드르 기호(Legendre symbol)라 한다.

이것을 일반화한 것으로 야코비 기호가 있다. 1보다 큰 홀수 PP에 대하여 P=p1p2⋯pmP=p_1 p_2 \cdots p_m이 성립한다고하자. 단, p1,p2,⋯ ,pmp_1,p_2,\cdots,p_m는 홀수인 소수이며, 이 중에는 같은 것이 있을 수 있다. 이때, gcd⁡(b,P)=1\gcd\left(b,P\right)=1인 수 bb에 대하여 야코비 기호 (bP)=(bp1)(bp2)⋯(bpm)\left(\frac{b}{P}\right)=\left(\frac{b}{p_1}\right)\left(\frac{b}{p_2}\right)\cdots\left(\frac{b}{p_m}\right)로 정의한다. 야코비 기호에 대해서도 아래의 르장드르 기호의 성질들은 성립하나, (bP)=1\left(\frac{b}{P}\right)=1이라 해서 bb가 법 PP에 대한 이차 잉여인 것은 아니다.

2. 성질[편집]

pp가 홀수인 소수이고, a,ba,b가 pp와 서로소일 때, 다음이 성립한다.
  1. a≡b(mod p)a\equiv b \left(\text{mod}\,p\right)이면, (ap)=(bp)\displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).
  2. (abp)=(ap)(bp)\displaystyle \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
  3. (a2p)=1\displaystyle \left(\frac{a^2}{p}\right)=1.
  4. (a2bp)=(bp)\displaystyle \left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right).
  5. (1p)=1\displaystyle \left(\frac{1}{p}\right)=1.
  6. pp가 홀수인 소수일 때, (−1p)=(−1)p−12\displaystyle \left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}.
  7. pp가 홀수인 소수일 때, p의 완전 잉여계 중에는 p−12\frac{p-1}{2}개의 2차 잉여와 p−12\frac{p-1}{2}개의 2차 비잉여가 존재한다.


1~5의 증명:
어려운 증명 없이 르장드르 기호의 정의로 충분히 해결할 수 있다.

6번의 증명:
윌슨의 정리를 이용하면, −1≡(p−1)!≡1×2×⋯×p−12×(p−p−12)×⋯×(p−2)×(p−1)≡(1×2×⋯×p−12)2(−1)p−12(mod p)\displaystyle -1\equiv \left(p-1\right)! \equiv 1\times 2\times \cdots \times \frac{p-1}{2} \times \left(p-\frac{p-1}{2}\right) \times \cdots \times \left(p-2\right) \times \left(p-1\right) \equiv \left(1\times 2\times \cdots \times \frac{p-1}{2}\right)^2 (-1)^{\frac{p-1}{2}} \left(\text{mod}\,p\right)이므로 (−1)p−12=1\displaystyle \left(-1\right)^{\frac{p-1}{2}}=1이면 -1은 p의 2차잉여가 된다. 한편 (−1)p−12=−1\displaystyle \left(-1\right)^{\frac{p-1}{2}}=-1이면, x2≡−1(mod p)x^2\equiv -1 \left(\text{mod}\,p\right)이라고 할 때 xp−1≡(−1)p−12≡−1(mod p)x^{p-1}\equiv (-1)^{\frac{p-1}{2}}\equiv -1 \left(\text{mod}\,p\right)이므로 페르마 소정리에 모순이다. 따라서 이 경우 -1이 p의 2차잉여가 아니다.

7번의 증명:
임의의 완전잉여계 중에서, pp와 서로소이고, 2차 잉여가 되기 위해서는 12,22,⋯ ,(p−1)21^2,2^2,\cdots,\left(p-1\right)^2중 어떤 한 원소와 법 pp에 의해 같아야 한다. 그런데, (p−n)2≡(−n)2≡n2(mod p)\left(p-n\right)^2\equiv \left(-n\right)^2\equiv n^2 \left(\text{mod}\,p\right)이므로 그 원소는 12,22,⋯ ,(p−12)21^2,2^2,\cdots,\left(\frac{p-1}{2}\right)^2 중 한 원소와 법 pp에 의해 같아야 한다. 한편, 12,22,⋯ ,(p−12)21^2,2^2,\cdots,\left(\frac{p-1}{2}\right)^2은 법 pp에 의해 각기 다르므로, 2차 잉여는 p−12\frac{p-1}{2}개이다. 따라서, 2차 비잉여도 p−1−p−12=p−12p-1-\frac{p-1}{2}=\frac{p-1}{2}개이다.

2.1. 오일러 판정법[편집]

pp가 홀수인 소수이고, gcd⁡(a,p)=1\gcd\left(a,p\right)=1일 때,
(ap)≡a(p−1)/2(mod p)\displaystyle \left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \left(\text{mod}\,p\right)
이다. 또, aa가 법 pp에 관한 2차 잉여이면, 이차합동식 x2≡a(mod p)x^2\equiv a\left(\text{mod}\,p\right)는 꼭 두 개의 해 x≡±x0(mod p)x\equiv\pm x_0\left(\text{mod}\,p\right)를 갖는다.

증명 :
x2≡a(mod p)x^2\equiv a\left(\text{mod}\,p\right)의 해가 존재한다고 하자. 즉, (ap)=1\displaystyle \left(\frac{a}{p}\right)= 1이라고 하자. 이때 gcd⁡(a,p)=1\gcd\left(a,p\right)=1이므로 gcd⁡(x,p)=1\gcd\left(x,p\right)=1이다.

그러면 페르마의 소정리에 의해 xp−1≡1(mod p)x^{p-1}\equiv 1\left(\text{mod}\,p\right)이므로, a(p−1)/2≡xp−1≡1(mod p)\displaystyle a^{(p-1)/2}\equiv x^{p-1}\equiv 1 \left(\text{mod}\,p\right)이다. 즉, (ap)=1≡a(p−1)/2(mod p)\displaystyle \left(\frac{a}{p}\right)=1\equiv a^{(p-1)/2} \left(\text{mod}\,p\right)

반대로, a(p−1)/2≡1(mod p)\displaystyle a^{(p-1)/2}\equiv 1 \left(\text{mod}\,p\right)이라고 하자. 이때 rr를 p의 원시근[1] 이라 하면 rk≡a(mod p)r^k\equiv a\left(\text{mod}\,p\right)인 정수 k가 존재한다. 그러면 rk(p−1)/2≡a(p−1)/2≡1(mod p)r^{k(p-1)/2} \equiv a^{(p-1)/2} \equiv 1\left(\text{mod}\,p\right) 이다.

여기서 r이 p의 원시근이므로 (p−1)∣k(p−1)2\displaystyle (p-1)\mid\frac{k(p-1)}{2}이어야 하고, kk 는 짝수가 된다. 즉, k=2lk=2l로 쓸 수 있고, (rl)2≡a(mod p)\left(r^{l}\right)^2\equiv a\left(\text{mod}\,p\right) 이므로 x2≡a(mod p)x^2\equiv a\left(\text{mod}\,p\right)의 해가 존재한다. 따라서 (ap)=1≡a(p−1)/2(mod p)\displaystyle \left(\frac{a}{p}\right)= 1 \equiv a^{(p-1)/2} \left(\text{mod}\,p\right)

마찬가지로 x2≡a(mod p)x^2\equiv a\left(\text{mod}\,p\right)의 해가 없는 경우, 즉 (ap)=−1\displaystyle \left(\frac{a}{p}\right)=-1인 경우에 위와 같이 원시근 r를 생각하면 rk≡a(mod p)r^k\equiv a\left(\text{mod}\,p\right)인 k가 홀수여야 한다. 따라서 ap−1≡1(mod p)a^{p-1} \equiv 1 \left(\text{mod}\,p\right)이 성립하는데 a(p−1)/2≡1(mod p)a^{(p-1)/2} \equiv 1 \left(\text{mod}\,p\right)은 성립할 수 없으므로, a(p−1)/2≡−1(mod p)a^{(p-1)/2} \equiv -1 \left(\text{mod}\,p\right)이다.


2.2. 가우스 판정법[편집]

pp가 홀수인 소수일 때, 다음이 성립한다.
  • (2p)=(−1)p2−18\displaystyle \left(\frac{2}{p}\right)=\left(-1\right)^\frac{p^2-1}{8}
  • gcd(a,p)=1\mathrm{gcd}(a, p)=1일 때, (ap)=(−1)n\displaystyle \left(\frac{a}{p}\right)=\left(-1\right)^n. 여기서 n은 {a,2a,⋯ ,p−12a}\displaystyle \left\{a, 2a, \cdots, \frac{p-1}{2}a\right\}중에서 p로 나눈 나머지가 p2\displaystyle \frac{p}{2}보다 큰 것의 개수
  • gcd(a,2p)=1\mathrm{gcd}(a, 2p)=1일 때, (ap)=(−1)t\displaystyle \left(\frac{a}{p}\right)=\left(-1\right)^t. 여기서 t=∑j=1(p−1)/2⌊jap⌋\displaystyle t= \sum_{j=1}^{(p-1)/2} \left\lfloor\frac{ja}{p}\right\rfloor.
위 식에서 ⌊⋅⌋\lfloor\cdot\rfloor는 바닥함수를 뜻한다.

2.3. 가우스의 상호법칙[편집]

p,qp,q가 서로 다른 홀수인 소수일 때, (pq)(qp)=(−1)p−12⋅q−12\displaystyle \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}이다.

3. 관련 문서[편집]


[1] 원시근은 법 p에 대한 위수가 p−1p-1인 것을 말한다. r이 p의 원시근이면 {r,r2,⋯ ,rp−1}≡{1,2,⋯ ,p−1}(mod p) \left\{r, r^2, \cdots, r^{p-1} \right\} \equiv \left\{1, 2, \cdots, p-1 \right\} \left(\text{mod}\,p\right)이다. 참고로 법 p에 대한 b의 위수란 bx≡1(modp)b^x \equiv 1 \left(\mathrm{mod} p \right)인 최소의 정수 x로, ordp(b) \mathrm{ord}_p\left(b\right)로 나타낸다.