[Number Theory with Code] 5. Wilson's Theorem

주인공인 Wilson 정리를 소개한다.

Wilson

$p$를 소수라 하면 다음이 성립한다. $$ (p-1)! \equiv -1 \; (mod\; p) $$

다음의 계산을 효과적으로 할 수 있다면 Wilson 정리의 증명을 이해한 것이다! $$ 4 \cdot \frac1{3} \cdot \frac1{4} \cdot 5 \cdot 6 \cdot 2 \cdot 3 \cdot \frac1{2} \cdot \frac1{5} $$

다음 문제들은 모두 같은 문제이다.

1. 다음 식의 값을 간단히 하라. $$ \sum_{n=-100}^{100} \frac1{2^i+1}$$
   등차 수열을 합을 구하는 것과 다를 게 무엇인가? $$ \frac1{2^{-i}+1} + \frac1{2^{i}+1} = 1$$ 를 이용하면 된다.
2. 수열 $\{a_n\}$ 은 초항이 1이고 공차가 3인 등차수열이다. 다음 값을 구하라. $$ a_{11} \cdot {}_{10} C_0 + a_{10} \cdot {}_{10} C_1 + \cdots + a_1 \cdot {}_{10} C_{10} $$
3. 자연수 $N$의 모든 양의 약수가 크기순으로 $d_1, d_2, \cdots, d_100$ 일 때, $$ d_1 \times d_2 \times \cdots \times d_{100} $$ 의 값은?
   ㄱ. $ \left( \frac{N}2 \right)^{50}$

   ㄴ. $\left(\frac{N}2\right)^{100}$

   ㄷ. $N^{50}$

   ㄹ. $N^{100}$
4. 다음 식의 값을 간단히 하시오. $$ \cos^2 1^\circ + \cos^2 2^\circ + \cos^2 89^\circ + \cos^2 90^\circ $$
5. [수능 기출]
   
6. 반지름의 길이가 1인 반원의 호를 2022 등분한 점을 $p_0, p_1, \cdots p_{2022}$라 하고, $p_0$와 $p_i$ 를 잇는 선분의 길이를 $\overline{p_0 p_1}$ 를 $l_i$로 정의한다. $$ l_1^2 +l_2^2 + \cdots + l_{2022}^2 $$ 의 값을 구하라.
7. 함수 $f(x)=\frac{4^x}{4^x+2} $ 에 대하여 옳은 것을 보기에서 모두 고르시오.

   ㄱ. $f\left(\frac12\right)=\frac12$

   ㄴ. $f(x)+f(1-x)=1$

   ㄷ. $\sum_{k=1}^{100} f\left( \frac{k}{101} \right)=50 $

8. 두 수 $50^{99}$ 와 $99!$의 대소를 비교하라.
9. $x^{2023}=1$의 한 허근을 $\omega$라 할 때, $$ \frac1{1+\omega} + \frac1{1+\omega^2} + \cdots + \frac1{1+\omega^{2022}} $$ 의 값을 계산하라.
10. 밑면과 윗면이 정팔각형인 팔각기둥이 있다. $\overline{A_1A_3} = 3\sqrt{2}$ 이고,
    점 $P$가 모서리 $A_1B_1$ 의 중점일 때, 벡터 $$ \sum_{i=1}^8 \left( \overrightarrow{PA_i} + \overrightarrow{PB_i} \right) $$ 의 크기를 구하시오.
    
    
    


11. 자연수 $n$의 모든 양의 약수의 합이 $2n$일 때, $n$의 모든 양의 약수들의 역수들의 합은?
12. 공집합이 아닌 집합의 원소를 큰 수부터 나열한 뒤 - 와 + 를 교대로 넣어 계산한 값을 '교대합'이라 한다. 예를 들어 집합 $\left\{ 1,2,4,6,9 \right\} $ 의 교대합은 $$ 9 - 6 + 4 - 2 +1 $$ 이고 집합 $\left\{ 5 \right\} $ 의 교대합은 5이다. 집합 $$\mathit{A}=\left\{ 1,2,3,4,5 \right\}$$ 의 모든 부분 집합의 교대합의 합을 구하시오. (단, 공집합의 교대합은 0으로 정의한다.)

위 문제들을 같은 문제라 했는데 어떤 의미였을까?
정수론에서도 같은 사고 방식이 적용된다.

1. 다음 식의 11 로 나눈 나머지를 구하시오. $$ 1^{11}+2^{11}+\cdots + 10^{11} $$
2. 자연수 $n$에 대하여 $n+1$이 3의 배수이면 $n$의 양의 약수의 합도 3의 배수임을 보여라.
3. $k \ge 1 $이고 홀수인 자연수 $k$와 임의의 자연수 $n$에 대해 $$1^k +2^k + \cdots + n^k $$ 이 $n+2$의 배수가 아님을 보여라.
   $ S = 1^k +2^k + \cdots + n^k$라 하자. $$ \begin{matrix} S &= & 1^k & + & 2^k & + & 3^k & + &\cdots & + & n^k & & \\ S &= & & & n^k & + & (n-1)^k & + &\cdots & + & 2^k & + &1^k \end{matrix} $$ 위 식을 $k$가 홀수이므로 $ i^k + (n+2 - i)^k$ 는 $n+2$로 나누어진다. 그리고 남는 것은 2인데...
4. Let $m$ and $n$ be positive integers such that $$ \frac{m}{n} = 1-\frac12 + \frac13 -\frac14 + \cdots - \frac1{1318} + \frac1{1319}. $$ Prove that $m$ is divisible by 1979.

앞 문제를 조금 더 일반화해보자.

5. Let $p$ be a prime greater than 3, $q= \lfloor \frac{2p}{3} \rfloor$ and let $m$ and $n$ be positive integers such that $$ \frac{m}{n} = 1-\frac12 + \frac13 -\frac14 + \cdots + (-1)^{q-1}\frac1{q}. $$ Then $m$ is divisible by $p$.
   (1) $p=3k+1$ 인 경우 :
   $ \lfloor \frac{2p}{3} \rfloor= 2k$ 이므로 Catalan's Identity 를 적용하면 $$ \frac{m}{n} = \frac1{k+1}+\frac1{k+2}+ \cdots + \frac1{2k} $$ 이 성립한다. $$ 2 \frac{m}{n} = \left(\frac1{k+1}+\frac1{2k}\right) + \left( \frac1{k+2}+ \frac1{2k-1}\right)+ \cdots + \left( \frac1{2k}+ \frac1{k+1}\right) $$ 짝이어진 것들을 통분하면 $$ \frac{m}{n} = \frac12 \left\{ \left(\frac{3k+1}{(k+1)(2k)}\right) +\left( \frac{3k+1}{(k+2)(2k-1)} \right) + \cdots + \left( \frac{3k+1}{(2k)(k+1)}\right) \right\} $$ 원래의 $p=3k+1$ 임을 떠올리면 우변의 분자가 $p$의 배수임을 안다.
   (2) $p=3k+2$ 인 경우 :
   $ \lfloor \frac{2p}{3} \rfloor= 2k+1$ 이다. 마지막 분모가 짝수가 아니지만 상관없다. 직전항까지 Catalan's Identity 를 적용하자. $$ \frac{m}{n} = \frac1{k+1}+\frac1{k+2}+ \cdots + \frac1{2k} + \frac1{2k+1} $$ 나머지 과정은 위와 같다.
6. 홀수인 소수 $p$에 대하여 $$ \sum_{k=1}^{p-1} k^{2p-1} \equiv \frac{p(p+1)}2 \; (\mathnormal{mod}\; p^2) $$ 임을 증명하라.
   짝을 지을 것이다. $$ k^{2p-1} + (p-k)^{2p-1}$$ $n=2p-1$으로 두고 두번째 항을 이항전개하자. $$ p^{n} - {n \choose n-1} p^{n}k^1 + {n \choose n-2} p^{n-2}k^2 + \cdots - {n \choose 2} p^2 k^{n-2} + {n \choose 1} p k^{n-1} - k^n $$

   마지막 두 항을 제외하면 $p^2$의 배수이므로 제거해도 관계없다.(관심사가 $p^2$의 나머지임을 기억하자.)

   처음에 짝 지은 것을 다시 쓰자. $(p-k)^{2p-1}$을 이항 전개한 것의 마지막 두 항을 이용하면 $$ \begin{matrix} k^{2p-1} + (p-k)^{2p-1} &\equiv & k^{2p-1} + {2p-1 \choose 1} p k^{2p-2} - k^{2p-1} \\ & \equiv & (2p-1) p k^{2p-2} \; (mod\; p^2) \end{matrix}$$

   페르마의 소정리를 이용하여 $k^{p-1} \equiv 1 \; (mod \; p)$ 에서 $k^{p-1}=pQ+1$ 로 쓸 수 있다.

   $$ k^{2p-2} = \left(k^{p-1}\right)^2 = p^2Q^2 + 2pQ+1 $$ 이므로 다음과 같이 위 식의 일부분을 바꿀 수 있다. $$ p k^{2p-2} =p^3Q^2 + 2p^2Q+p \equiv p \; (mod \; p^2) $$ 이로부터 다음을 얻는다. $$ k^{2p-1} + (p-k)^{2p-1} \equiv (2p-1)p \equiv -p \; (mod \; p^2) $$ 문제의 합은 방금 얻은 결과로부터 $$ \sum_{k=1}^{p-1} k^{2p-1} \equiv \sum_{k=1}^{\frac{p-1}2} -p \equiv \frac{-p^2+p}2 \; (mod \; p^2) $$ 을 얻고 $p^2$ 을 더해서 최종 형태를 만든다. $$ \frac{-p^2+p}2 \equiv \frac{-p^2+p}2 +p^2 \equiv \frac{-p^2+p}2 \; (mod \; p^2) $$