정수론 | 페르마의 작은 정리

페르마의 작은 정리(Fermat's Little Theorem)

정리: $p$가 소수이고, $p\nmid a$이면 $a^{p-1}\equiv1\pmod{p}$이다.

[증명] 정수 $a$에 대하여 $p-1$개의 $a$의 배수들이 존재한다고 하면 $a,\ 2a,\ \cdots,\ (p-1)a$이고 각 수들은 소수 $p$에 대해 서로 합동관계가 성립하지 않는다. 만약 이 가정을 무시하고 $ra\equiv sa\pmod{p},~ 1\le r<s\le p-1$이라고 하면 $\gcd(a,p)=1$이므로 $r\equiv s\pmod{p}$가 되어 성립하지 않는다. 따라서 집합 $\{a,\ 2a,\ 3a.\cdots,\ (p-1)a\}$는 $\{1,2,3,\cdots,\ p-1\}$의 원소들과 서로 대응관계를 갖는다. 그러므로 $a\cdot2a\cdots(p-1)a\equiv 1\cdot2\cdots(p-1)\pmod{p}$가 성립하며 정리하면 $a^{p-1}(p-1)!\equiv(p-1)! \pmod{p}$이다. 따라서 $a^{p-1}\equiv 1\pmod{p}$가 성립한다.

정리: $p$가 소수이면, 임의의 정수 $a\in Z$에 대하여 $a^p\equiv a\pmod{p}$이다.

[증명] 만약 $a\equiv0\pmod{p}$이면 당연히 주어진 조건은 성립한다. $a\nmid p$일 때, 페르마의 작은 정리에 의해 성립함을 알 수 있다.

정리: $a^n\equiv a\pmod{n}$이면 정수 $n$은 소수가 아니고 합성수이다.

위 정리의 대우명제이므로 증명은 생략한다.

예제: $14^{193}\cdot15^{193}\cdot16^{193}\cdots22^{193}\cdot23^{193}\pmod{13}$을 구하여라.

주어진 식을 $A$라고 하자. 피제수들을 13으로 나눈 나머지를 보면 $A\equiv1^{193}\cdots10^{193}$과 같다. 그리고 윌슨의 정리에 따라 $12!\equiv -1\pmod{13}$이므로 $11!\equiv1=1+65\pmod{13}$이다. 양변을 약분하면 $10!\equiv 6\pmod{13}$이 되어 나머지는 6이다.

예제: 주어진 양의 정수 $m$에 대하여, $m^{343}$은 $77$로 나눈 나머지가 $53$이라고 한다. 정수 $m$을 $77$로 나눈 나머지를 구하여라.

$m^{343}\equiv 53 \pmod{77}$이므로 $\gcd(7,m)=\gcd(11,m)=1$이다. 그러므로 페르마의 작은 정리에 의해 $m^6\equiv1\pmod{7},\ m^{10}\equiv 1\pmod{10}$이고 각각의 최소공배수를 고려하면 $m^{30}\equiv 1\pmod{77}$이다. 정리하면 $m^{13}\equiv 53 \pmod{77}$이 된다. $m^6\equiv1\pmod{7}$이므로 $m^{12}\cdot m\equiv 4\pmod{7}$이 되어 $m\equiv 4\pmod{7}$이다. 동일하게 $m^{10}\equiv1 \pmod{11}$이므로 $m^3\equiv9\equiv-2\pmod{11}$이다. $(m^3)^3\equiv -8\equiv 3 \pmod{11}$이므로 $3m\equiv1\pmod{11}$이 되어 $m\equiv4 \pmod{11}$이다. 따라서 $7,\ 11$로 나눈 나머지가 모두 4이므로 $77$로 나눈 나머지도 4이다.

예제: $n=3\cdot7^7$일 때, $\gcd(7^n-1,7^n+4949)$를 구하여라.

유클리드 호제법에 의해 $\gcd(7^n-1,7^n+4949)=\gcd(7^n-1,4950)$이다. $4950=2\cdot3^2\cdot5^2\cdot11$이므로 $7^n-1$이 $4950$의 인수를 얼마나 갖는지 확인하면 된다.

1. $2|7^n-1$은 $7^n-1=(7-1)(7^{n-1}+\cdots+1)$이므로 $6|7^n-1$성립
2. $5|7^n-1$은 $7^4\equiv1\pmod{5}$이므로 $7^k-1$은 4를 주기로 $5$의 배수가 된다. $n\equiv 3\cdot7^3\equiv1\pmod{4}$이므로 $5\nmid n$이다.
3. $9|7^n-1$은 $7\equiv-2\pmod{9}$이므로 $7^3\equiv-8\equiv1\pmod{9}$이다. 그러므로 $n$이 $3$의 배수이면 $9|7^n-1$이고 $3|3\cdot7^7$이므로 $9|7^n-1$이다.
4. $11|7^n-1$은 $7^{10}\equiv1\pmod{11}$이므로 $10\nmid n$이므로 $11$인수로 갖지 않는다.

따라서 $\gcd(7^n-1,7^n+4949)=18$이다.

예제: $p^4+119$의 약수의 개수가 20개 이하가 되도록 하는 모든 소수 $p$의 합을 구하여라.

우선 계산이 쉬운 $2,\ 3,\ 5$에 대해 직접 계산 후 소인수 분해를 하면 $2^4+119=3^3\cdot5$, $3^4+119=2^3\cdot5^2$, $5^4+119=2^3\cdot3\cdot31$이 되어 모두 성립한다.

$p\ge 7$에 대해 $p^4$는 무조건 홀수이므로 제곱수를 $8$로 나눈 나머지가 $0,\ 1,\ 4$임을 참고하여 $8$을 인수로 가짐을 알 수 있다. $p^2\equiv1\pmod{3}$이므로 $p^4\equiv1\pmod{3}$이 되어 주어진 식은 $3$을 인수로 갖는다. $p^4\equiv1\pmod{5}$이므로 $5$도 인수로 갖게 되어 $2^3\cdot3\cdot5=120$의 배수임을 알 수 있다. $120$의 배수 중 약수의 개수가 $20$개 이하가 되려면 $120,\ 240$만 가능하다. 그런데 이 조건을 만족하는 $7$이상의 소수는 존재할 수 없으므로 $2+3+5=10$이다.

예제: 수열 ${a_n}$은 $a_1=1$이고 모든 양의 정수 $n$에 대하여 $a_{n+1}=3^{a_n}+1$을 만족한다. 수열 $a_n$을 $100$으로 나눈 나머지를 $b_n$이라 할 때, $b_{2011}+\cdots+b_{2020}$의 값을 구하여라.

1. $n=1$이면 $a_1=1,\ b_1=1$
2. $n=2$이면 $a_2=4,\ b_2=4$
3. $n=3$이면 $a_3=3^4+1,\ b_3=82$
4. $n=4$이면 $a_4=3^{3^4+1}+1$이다.

$n=4$부터는 차수가 너무 높기 때문에 연산이 불가능하다. 즉, 차수를 낮추기 위해 $3^k\equiv1\pmod{100}$인 $k$를 구해야 한다. $3^5=243=43\pmod{100}$이고 $43^2=(40+3)^2=1600+6\cdot40+9\equiv49\pmod{100}$이며 $49^2=(40+9)^2\equiv1600+18\cdot40+8\equiv1\pmod{100}$이다. 즉, $3^{10}\equiv49\pmod{100}$, $3^{20}\equiv1\pmod{100}$이다. 다시 $3^{82}+1$을 계산하면 $3^{20\cdot4+2}+1\equiv10\pmod{100}$이므로 $100t+10$으로 표현할 수 있다.

5. $n=5$이면 $a_5=3^{a_4}+1$이므로 $b_5=3^{20\cdot5t+10}+1\equiv 50\pmod{100}$이다.
6. $n=6$이면 $a_6=3^{a_5}+1$이므로 $b_6=3^{20\cdot5s+50}+1\equiv3^10+1\equiv50\pmod{100}$이다.

즉, $5$번째 항부터 계속 $b_n$의 값은 $50$으로 고정됨을 알 수 있으므로 $50\cdot10=500$이다.

예제: 수열 ${a_n}$은 $a_1=1$이고 모든 양의 정수 $n$에 대하여 $a_{n+1}=2004^{a_n}$을 만족한다. 수열 $a_n$을 $11$로 나눈 나머지들로 이루어진 집합을 $S$에 속한 모든 원소의 합을 구하여라.

1. $n=1$이면 $a_1=1\pmod{11}$
2. $n=2$이면 $a_2=2004\equiv2\pmod{11}$
3. $n=3$이면 $a_3=2004^{2004}\equiv2^{2004}\pmod{11}$인데 차수가 너무 높으므로 계산이 불가능하다.

차수를 낮추기 위해 $2^k\equiv1\pmod{11}$인 $k$를 찾으면 $2^5\equiv-1$, $2^{10}\equiv1\pmod{11}$임을 알 수 있다. 그러므로 $2^{2004}\equiv5\pmod{11}$이다. 그리고 차수가 $10$의 배수로 낮출 수 있기 때문에 각 항에 대해 $10$을 법으로 한 나머지 연산을 해야 한다. $a_3\equiv 6\pmod{10}$이다.

4. $n=4$이면 $a_4=2004^{a_3}\equiv2004^{10k+6}\equiv2^6\equiv9\pmod{11}$, $a_4\equiv6\pmod{10}$

즉, 이후로 모든 수열의 항은 $10$을 법으로 항상 나머지가 6이기 때문에 값도 일정하게 됨을 알 수 있다. 따라서 $1+2+5+9=17$이다.

예제: 양의 정수 $n$과 홀수인 소수 $p$에 대하여 $n^2-n$이 $p$의 배수가 아니라고 하자. $a_1=pn+1,\ a_{k+1}=na_k+1\ (k\ge1)$이라 하면 $a_{p-1}$이 소수가 아님을 증명하여라.

$a_k=pn^k+n^{k-1}+\cdots+n+1$이고 $a_{p-1}=pn^{p-1}+n^{p-2}+\cdots+n+1$이다. $n^{p-1}\equiv1\pmod{p}$이므로 $n^{p-1}-1\equiv0\pmod{p}$이다. $(n-1)(n^{p-2}+n^{p-3}+\cdots+n+1)$에 대해 $p\nmid n-1$이므로 $p|n^{p-2}+\cdots+n+1$이다. 그러므로 $p|a_{p-1}$이므로 소수가 아니다.

정리: $a\equiv 0\ or\ 2\pmod{3}$이면 $\gcd(a-1,a^2+a+1)=1$이다.

해당 정리는 반드시 암기할 필요는 없어 보인다. 다만, 아래 문제를 해결하기위해 위 정리를 도출하거나 사용해야 해서 첨부하였다.

[증명] $a^2+a+1=(a-1)(a+2)+3$이므로 $\gcd(a-1,a^2+a+1)$은 $1,\ 2,\ 3$중의 값을 가질 수 있다.

1. $a=3k$이라면 $\gcd(3k-1,3k(3k+1)+3)=1$이다.
2. $a=3k+1$이라면 $\gcd(3k,3k(3k+3)+3)=3$이다.
3. $a=3k+2$이라면 $\gcd(3k+1,(3k+1)(3k+4)+3)=1$이다.

정리: 소수 $p$가 $3$이 아니고 $p|a^2+a+1$이면 $p\nmid a-1$, $p\nmid a^2-1$이고 $p|a^3-1$이다.

해당 정리를 반드시 암기할 필요는 없어 보인다. 다만, 아래 문제를 해결하기 위해 위 정리를 사용해야 해서 첨부하였다.

[증명] 위 정리에 따라 $a-1$에 대해서는 $p$가 3이 아니라면 최대공약수가 1이며 서로소 관계임을 알 수 있다. $a^2-1=(a-1)(a+1)$에 대해서 $\gcd(a^2-1,a^2-1+a+2)$가 $1$이 되지 않으려면 $a^2-1$이 $a+2$를 인수로 가져야 하는데 모순이므로 서로소 관계이다. $a^3-1$에 대해서는 인수분해 결과 $a^2+a+1$을 인수로 가짐을 알 수 있다.

예제: $2^n-1$이 소수 $p$의 배수가 되는 양의 정수 $n$ 중 가장 작은 것은 $3^{2013}$인 소수 $p$가 존재함을 증명하여라.

문제에서 만족하는 가장 작은 수가 $3^{2013}$이라고 하였으므로 $n=3^{2012}$라고 해보자. 그리고 표기의 편의성을 위해 $2^{3^{2012}}=A$라고 하면 $A\equiv(-1)^{3^{2012}}=-1\equiv2\pmod{3}$이다. 그러므로 $\gcd(A-1,A^2+a+1)=1$이 성립한다. 그리고 특정 소수 $p$가 존재하여 $p|A^2+A+1$이라면 $p|A^3-1$을 만족한다. 즉, 문제에서 제시된 방정식과 유사한 형태이지만 $p\nmid A-1,\ p\nmid A^2-1$이기 때문에 $A^3=2^{3^{2012}\cdot3}=2^{3^{2013}}$이 되어 특정한 소수 $p$에 대해 조건을 만족하는 가장 작은 수 $n=3^{2013}$임을 확인할 수 있다. 문제에서 볼 수 있듯이 특정 소수 $p$에 대해 위 두 정리를 만족한다면 $p\nmid A-1,\ p\nmid A^2-1,\ p|A^3-1$이 성립함을 이용하였다. 그러므로 사실 차수는 별 의미가 없다. 어떠한 차수를 넣어도 $A\equiv 2\pmod{3}$이기 때문이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저