Develop

[js] 2차 잉여.. (Quadratic reciprocity) 계산..

by hooni posted Apr 23, 2013
?

단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

Quadratic reciprocity

The Jacobi symbol, (m/n), is defined whenever n is an odd number. It has the following properties that enable it to be easily computed.
  • (a/n) = (b/n) if a = b mod n.
  • (1/n) = 1 and (0/n) = 0.
  • (2m/n) = (m/n) if n = ±1 mod 8. Otherwise (2m/n) = ¯(m/n).
  • (Quadratic reciprocity) If m and n are both odd, then (m/n) = (n/m) unless both m and n are congruent to 3 mod 4, in which case (m/n) = ¯(n/m).
If n is a prime, then (m/n) = 1 exactly when m is a nonzero square mod n (a quadratic residue).