루카스의 정리

M을 m 원소로 세트로 하고, i의 다양한 값에 대해 길이 p의ⁱ m 사이클로_i 나눈다.그런 다음 이 사이클들은 각각 개별적으로 회전할 수 있어 주기 그룹 C의_pⁱ 데카르트 산물인 그룹 G가 M에 작용한다.따라서 N 크기의 부분 집합 N에도 작용한다.G에 있는 원소의 수는 p의 힘이기 때문에, 그 궤도의 어떤 것도 마찬가지다.따라서${\displaystyle }$(${\displaystyle m\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$) ${\$ modulo$$ p를 계산하려면 이 그룹 작업의 고정 지점만 고려하면 된다.고정 지점은 일부 사이클의 조합인 하위 집합 N이다.보다 정확하게는 k-i에 대한 유도를 통해 N이 정확히 n_i 사이클의 pⁱ 사이즈를 가져야 한다는 것을 보여줄 수 있다.따라서 N에 대한 선택 횟수는 ${\displaystyle \underset{}{\overset{}{정확히}}}$ $\prod {\displaystyle \underset{}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{\mathrm{k}}}}$( ${\displaystyle m\genfrac{}{}{0ex}{}{{}_{}}{}}$ ${\displaystyle i}$ ${\displaystyle \genfrac{}{}{0ex}{}{i_{}}{}}$ i$){\$이다.

이 증거는 네이쓴 파인 때문이다.^[2]

p가 prime이고 n이 1 ≤ n ≤ p - 1의 정수일 경우, 이항계수의 분자

${\displaystyle {\binom {p}{n}}={\frac {p\cdot(p-1)\cdots(p-n+1)}{n\cdot(n-1)\cdots:1}}}$

p로 나누어져 있지만 분모는 그렇지 않다.따라서 p는${\displaystyle }$(${\displaystyle p\genfrac{}{}{0ex}{}{}{}}$ $){\$을(를) 나눈다$.$ 일반적인 생성함수의 관점에서, 이는 다음을 의미한다.

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}.}$

유도에 의해 계속되면서, 우리는 음이 아닌 모든 정수 i를 가지고 있다.

${\displaystyle (1+X)^{p^{i}}^{p^{p^{p^}}{\pmod {p}}.}$

이제 나를 음이 아닌 정수로 하고, p를 프라임이 되게 하라.0 ${\displaystyle \underset{}{\overset{}{p}}}$ m m p-1의_i 일부 비음수 정수 k와 정수_i m에 $대해$ m${\displaystyle }$= ${\displaystyle \underset{}{\overset{}{}}}$i = 0 ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle m_{}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle p^{}}$ ${\displaystyle {}_{}{}^{}}${\$displaystyle$ m$=\sum$_{$i=0}^{k}m_{i}$p^{i}{i}p$^{i}}}}}:{$i}}}}}}}}}}}}에 쓰도록 한다.그러면

${\displaystyle {\begin{aigned}\sum _{n=0}^{m}{n}X^{n}{n}}=(1+X)^{m}=\i=0}^{k}\p^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\왼쪽(1+X^{p^{i}}\오른쪽)^{m_{i}}=\prod_{i}}{k}\좌(\sum_{n_{i}=0}^{m_{i}}}{n_}}}}}X^{n_{i}p^{i}\오른쪽)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}$

여기서, 최종 제품에서 n은_i n의 base p에 있는 ih 자릿수다.이것은 루카스의 정리를 증명한다.