2차 잉여

문서의 이전 버전(r24)을 보고 있습니다.

역사 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)로 나타낸다.