[정수론](-)[(어떤 식)의 이차잉여인가?]

(a / (어떤식)) 꼴의 르장드르 기호에서
(어떤 식) ≡ ■ (mod 4)를 연산해서 뒤집어주고 계산해준다!

 

모든 n에 대해 4^n ≡ 4 (mod 12)임을 보이고, 이를 이용하여 3은 2^2n + 1 꼴의 모든 소수의 이차비잉여임을 증명하여라. 또한 3이 2^p − 1 꼴(p는 홀수인 소수)의 모든 소수의 이차비잉여임을 증명하여라

 

1. 4^n ≡ 4 (mod 12)

귀납법을 이용한 증명

• n = 1 ?
  4 ≡ 4 (mod 12) 참
• n = k에서 참이라고 가정할 때 n = k+1 ?
  4^k ≡ 4 (mod 12) 라고 가정하자.
  4^(k+1) ≡ 4 * 4^k
  ≡ 4 * 4 ≡ 16 ≡ 4 (mod 12)이므로 참

 

2. 3은 2^2n + 1 꼴의 모든 소수의 이차비잉여?

(3 / 2^2n+1) = -1 임을 보이면 된다.

 

2^2n+1 ≡ 4^n + 1 ≡ 1 (mod 4) 이므로,
이차상호법칙에 의해 (3 / 4^n + 1) = (4^n + 1 / 3)
앞에서 4^n ≡ 4 (mod 12)라고 했으므로, 4^n - 4 = 12k
즉, 4^n + 1 ≡ 12k + 4 + 1 ≡ 2 (mod 3)
(4^n + 1 / 3) = (2/ 3)이고, 2는 3의 NR이므로
3은 2^2n + 1꼴 소수의 이차비잉여다.

 

3. 3이 2^p − 1 꼴(p는 홀수인 소수)의 모든 소수의이차비잉여?

(3 / 2^p-1) = -1 를 보이자.

 

p = 홀수 이므로, p = 2k+1
2^p - 1 = 2^(2k + 1) - 1 ≡ 2*4^k -1 ≡ -1 ≡ 3 (mod 4) 이므로,
(3 / 2^p-1) = -(2^p-1 / 3)
앞에서 4^n ≡ 4 (mod 12)라고 했으므로, 4^n - 4 = 12t
2*4^k -1 ≡ 2*(12t + 4) - 1 ≡ 8 - 1 ≡ 1 (mod p)
-(2^p-1 / 3) = -(1 / 3) = -1
3은 p^2 - 1꼴 소수의 이차비잉여다.