페르마의 소정리: 나머지를 모두 곱하면 거듭제곱이 보입니다
《나머지에서 시작하는 정수론》 · 4/8편 · 페르마의 소정리
0. 서론: 큰 거듭제곱을 작은 계산으로 바꾸려면
$3^{100}$은 손으로 계산하기에도 큰 정수입니다. 하지만 만약 11로 나눈 나머지만 필요하다면 그 정수 전체를 만들 이유가 없습니다.
지금까지 따라오셨다면, 느낌이 오시죠? 배수판정법에서 사용했던 원리를 이번에는 거듭제곱에 적용하는 것입니다.
만약 $3^{10}$을 11로 나눈 나머지가 1이라는 사실을 알고 있다면 어떻게 될까요? 3을 백 번 곱하는 대신, 열 번씩 곱한 덩어리를 열 개 만들면 됩니다.
$$ 3^{100}=(3^{10})^{10}\equiv1^{10}=1\pmod{11}. $$
큰 계산이 아주 짧아집니다. 그러니 우리가 알아내고 싶은 것은 “같은 수를 몇 번 곱하면 나머지가 1이 되는가” 입니다.
그리고 한 발짝 더 나아가 보자면 “왜 그렇게 되는가”입니다.
직관적으로 보자면 얼핏 잘 맞는 것 같습니다. 나머지가 같은 애로 바꿔서 풀기.
그러나 수학은 엄밀성이죠! 이게 왜 성립하는지, 한 번 자세하게 살펴보겠습니다.
그리고 이 이야기를 따라가다보면 아주 재밌는 결론에 도달하게 됩니다.
먼저 표가 짧아서 확인하기 쉬운 법 7에서 시작해보겠습니다.
법 7이라고 놨기 때문에 이제부터 우리가 탐구할 부분은 바로 $3^{100}$을 7로 나눈 나머지가 뭘까요? 입니다.
이제부터 탐구해 들어가보도록 하겠습니다!
1. 1부터 6까지에 3을 곱하면 나머지는 어떻게 바뀔까요?
어떤 수를 7로 나눈 나머지는 0, 1, 2, 3, 4, 5, 6입니다. 이 가운데 0을 제외한 여섯 수를 놓겠습니다.
$$ 1,\quad2,\quad3,\quad4,\quad5,\quad6. $$
0을 제외하는 이유도 있습니다. 우리는 잠시 뒤 이 수들을 모두 곱할 텐데, 0이 끼면 전체 곱이 무조건 0이 됩니다. 그러면 곱해 넣은 3에 관한 정보를 읽어낼 수 없습니다.
이제 여섯 수에 각각 3을 한 번씩 곱해봅시다.
서론에서 우리는 3의 거듭제곱을 살펴보았기 때문에 굳이 3을 곱하는 겁니다.
$$ 3\times1,\quad 3\times 2,\quad 3\times 3,\quad 3\times 4,\quad 3\times 5,\quad 3\times 6. $$
$$ 3,\quad 6,\quad 9,\quad 12,\quad 15,\quad 18. $$
3을 곱한 뒤의 나머지들은 원래의 (1,2,3,4,5,6)과 어떤 관계가 있을까요?
| 원래 나머지 $r$ | $3r$ | 7로 나눈 나머지 |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 6 | 6 |
| 3 | 9 | 2 |
| 4 | 12 | 5 |
| 5 | 15 | 1 |
| 6 | 18 | 4 |
마지막 열은 $3,6,2,5,1,4$입니다. 순서는 달라졌지만 1부터 6까지가 빠짐없이 한 번씩 나타났습니다. 이렇게 같은 목록을 순서만 바꾸어 놓는 것을 순열, 또는 재배열이라고 합니다.
예를 들어 $r=3$인 줄에서는 $3r=9=7\times1+2$라서 출력이 2입니다. $r=5$인 줄에서는 $15=7\times2+1$이므로 출력이 1입니다. 표의 “원래 나머지”는 곱하기 전의 입력이고, 마지막 열은 곱한 뒤 다시 1부터 6 사이로 줄인 출력입니다.
마지막 열을 크기순으로 정렬하면 $1,2,3,4,5,6$입니다. 순열이라고 할 때 보존되는 것은 각 수의 등장 횟수입니다.
여기서 표를 읽는 순서를 한 번 짚고 가겠습니다. 각 행에서는 서로 다른 입력 1·2·3·4·5·6에 3을 한 번씩 곱했습니다. 앞 행의 답에 다시 3을 곱해서 다음 행을 만든 표가 아닙니다. 예를 들어 첫 행의 출력 3에 또 3을 곱하면 9의 나머지인 2가 되지만, 표의 둘째 행은 새 입력 2에 3을 곱한 결과 6이지요. 한 입력에서 계속 곱하는 거듭제곱의 경로는 뒤에서 따로 살펴보겠습니다.
이제 우리는 나머지의 등장 횟수가 3배를 해도 똑같다는 것을 알았습니다.
그렇다면 이것을 다시 수식으로 바꿔보면,
$$ (3\times1)(3\times2)\cdots(3\times6) = 3^6(1\times2\times3\times4\times5\times6). $$
이와 같이 정리할 수 있겠습니다.
갑자기 왜 모두 곱하냐고요? 나머지 목록이 그대로 유지된다는 성질은 남긴 채 3의 거듭제곱에 관한 식으로 바꾸기 위해 곱셈을 사용했습니다. 나머지 목록의 유지에 대한 성질에 대해서는 덧셈도 사용할 수 있겠지만, 그렇다면 거듭제곱에 관한 식으로 바꿀 수 없겠죠?
자, 이렇게 모두 곱해서 3을 모아보면, 각 항에 하나씩 넣어둔 3이 여섯 개 모여 $3^6$이 되었습니다.
그런데 2편에서 배웠듯이, 곱하는 수들을 각각 그 나머지로 바꾸어도 전체 곱의 나머지는 같습니다. 따라서 우항에 있는 식에서 왼쪽의 거듭제곱을 바로 계산하기 전에, 각 항을 7로 나눈 나머지부터 살펴볼 수 있습니다.
표를 보면 이번 예에서는 사실임을 알 수 있습니다. 하지만 표 하나만으로 모든 소수와 모든 곱하는 수에서 맞는다고 증명할 수는 없지요.
결국 알고 싶은 것은 단 하나입니다. ‘나머지 목록이 왜 유지가 되는가’.
그리고 이하의 세 가지 질문이 만족된다면 모든 소수와 그 소수의 배수가 아닌 수에서 맞는다고 증명할 수 있습니다.(함수 관계에서 1:1대응 조건을 찾아본다고 생각하시면 됩니다)
-
왜 곱한 결과의 나머지가 0이 되지 않을까요?
-
왜 서로 다른 두 입력이 같은 나머지로 합쳐지지 않을까요?
-
그 두 사실에서 왜 모든 나머지가 등장한다고 결론 내릴까요?
그림을 만든 Python 코드
from pathlib import Path as _bfPath
from matplotlib.font_manager import FontProperties as _bfFontProperties
from matplotlib.text import Text as _bfText
from matplotlib.ticker import Formatter as _bfFormatter
from io import BytesIO as _bfBytesIO
from IPython.display import display as _bfDisplay, Image as _bfImage
class _BilingualFormatter(_bfFormatter):
def __init__(self, base, labels):
self.base, self.labels = base, labels
def set_axis(self, axis):
super().set_axis(axis)
self.base.set_axis(axis)
def set_locs(self, locs):
super().set_locs(locs)
self.base.set_locs(locs)
def __call__(self, value, pos=None):
raw=self.base(value,pos)
translated=self.labels.get(raw)
return translated+'\n'+raw if translated else raw
def get_offset(self):
return self.base.get_offset()
def _apply_bilingual_figure(_bfFigure, _bfLabels, _bfOriginalPixels):
if getattr(_bfFigure, '_bilingual_complete', False):
return
_bfFont = _bfPath('C:/Windows/Fonts/malgun.ttf')
if not _bfFont.is_file():
raise RuntimeError('Korean/English figures require the Malgun Gothic font.')
_bfFamily = _bfFontProperties(fname=str(_bfFont)).get_name()
# Keep the delivered original's aspect ratio. A bilingual label must not
# stretch the chart, its grid cells, cards or geometry vertically.
_bfFigure.set_size_inches(_bfOriginalPixels[0] / 80,
_bfOriginalPixels[1] / 80, forward=True)
_bfFigure._bilingual_original_pixels = tuple(_bfOriginalPixels)
_bfFigure.canvas.draw()
for _bfAxes in _bfFigure.axes:
for _bfAxis in (_bfAxes.xaxis,_bfAxes.yaxis):
if any(_bfTick.get_text() in _bfLabels for _bfTick in _bfAxis.get_majorticklabels()):
_bfAxis.set_major_formatter(_BilingualFormatter(_bfAxis.get_major_formatter(),_bfLabels))
_bfTexts = list(_bfFigure.findobj(_bfText))
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
_bfTexts.extend(_bfCell.get_text() for _bfCell in _bfTable.get_celld().values())
_bfSeen = set()
_bfChanged = []
for _bfItem in _bfTexts:
if id(_bfItem) in _bfSeen:
continue
_bfSeen.add(id(_bfItem))
_bfOriginal = _bfItem.get_text()
_bfKorean = _bfLabels.get(_bfOriginal)
if _bfKorean:
_bfItem.set_text(_bfKorean + '\n' + _bfOriginal)
_bfItem.set_linespacing(1.05)
_bfChanged.append((_bfKorean, _bfOriginal))
_bfProperties = _bfItem.get_fontproperties().copy()
_bfProperties.set_file(None)
_bfProperties.set_family([_bfFamily, 'DejaVu Sans'])
_bfItem.set_fontproperties(_bfProperties)
assert _bfChanged, 'Every figure must contain meaningful Korean/English labels.'
# Bilingual column headers must stay inside their original table cells.
_bfFigure.canvas.draw()
_bfRenderer = _bfFigure.canvas.get_renderer()
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
for _bfCell in _bfTable.get_celld().values():
_bfCellText = _bfCell.get_text()
_bfBox = _bfCellText.get_window_extent(_bfRenderer)
_bfCellBox = _bfCell.get_window_extent(_bfRenderer)
if _bfBox.width and _bfBox.height:
_bfFit = min(1, .92*_bfCellBox.width/_bfBox.width,
.88*_bfCellBox.height/_bfBox.height)
_bfCellText.set_fontsize(_bfCellText.get_fontsize()*_bfFit)
if _bfAxes.get_title():
_bfAxes.set_title(_bfAxes.get_title(), pad=6)
_bfFigure.canvas.draw()
# Keep subplot headings clear of the shared two-line title, moving the
# subplot boundary only as much as the actual rendered text requires.
if _bfFigure._suptitle is not None:
_bfTopTitle = _bfFigure._suptitle.get_window_extent(_bfRenderer)
for _bfAxes in _bfFigure.axes:
if not _bfAxes.get_title():
continue
_bfHeading = _bfAxes.title.get_window_extent(_bfRenderer)
_bfGap = _bfHeading.y1 - (_bfTopTitle.y0 - 9)
if _bfGap > 0:
_bfPosition = _bfAxes.get_position(original=True)
_bfAxes.set_position([_bfPosition.x0, _bfPosition.y0,
_bfPosition.width, _bfPosition.height - _bfGap/_bfFigure.bbox.height])
_bfFigure._bilingual_labels = _bfChanged
_bfFigure._bilingual_complete = True
def _display_bilingual_figure(_bfFigure):
# A fixed full canvas avoids notebook's automatic tight crop changing the
# aspect ratio after titles and labels become bilingual. This is a fresh
# Matplotlib rendering, at exactly twice the original pixel dimensions.
global _bfDisplayedFigure
_bfDisplayedFigure = _bfFigure
_bfBuffer = _bfBytesIO()
_bfFigure.savefig(_bfBuffer, format='png', dpi=160, bbox_inches=None,
pad_inches=0, facecolor=_bfFigure.get_facecolor())
_bfDisplay(_bfImage(data=_bfBuffer.getvalue()))
plt.close(_bfFigure)
_bfLabels = {'Dividend': '피제수', 'Divisor': '제수', 'Quotient': '몫', 'Remainder': '나머지', '3r mod 7': '3r의 법 7 나머지', 'then x5': '그다음 5를 곱하기', 'k, gcd(k,12)=1': '12와 서로소인 k', '5k mod 12': '5k의 법 12 나머지', 'Modulus': '법', 'Other factors': '나머지 법들의 곱', 'Inverse': '역원', 'Unit part': '단위 부품', 'Target': '목표 나머지', 'Contribution': '기여값', 'Possible square residues': '가능한 제곱 나머지', 'Squares of 0, 1, ... , m-1': '0·1·…·(m−1)의 제곱 나머지', 'PASS': '통과', 'IMPOSSIBLE': '불가능', 'mod 2': '법 2', 'mod 3': '법 3', 'mod 4': '법 4', 'mod 5': '법 5', 'mod 7': '법 7', 'mod 8': '법 8', 'mod 9': '법 9', 'mod 11': '법 11', 'mod 12': '법 12', 'mod 105': '법 105', 'Original': '원래 나머지', 'No zero. No collisions. The same six destinations.': '출력 0 없음, 충돌 없음, 같은 여섯 목적지.', 'Multiplying by 3 permutes the nonzero residues modulo 7': '법 7에서 3을 곱하면 0이 아닌 나머지가 재배열된다'}
_bfOriginalPixels = [1114, 590]
import matplotlib.pyplot as plt
from matplotlib.patches import FancyArrowPatch
p,a=7,3
source=list(range(1,p)); target=[(a*k)%p for k in source]
assert sorted(target)==source and 0 not in target
fig,ax=plt.subplots(figsize=(11.4,6),facecolor="#0d1117"); ax.axis("off")
ax.set(xlim=(0,8),ylim=(0,7))
for k,t in zip(source,target):
ax.text(1,7-k,str(k),ha="center",va="center",color="#e6edf3",fontsize=24)
ax.text(7,7-k,str(k),ha="center",va="center",color="#e6edf3",fontsize=24)
ax.add_patch(FancyArrowPatch((1.35,7-k),(6.65,7-t),arrowstyle="-|>",mutation_scale=18,color=plt.cm.Set2(k/7),linewidth=2,alpha=.85))
ax.text(1,6.65,"Original",ha="center",color="#bdc7d5",fontsize=13)
ax.text(7,6.65,"Remainder",ha="center",color="#bdc7d5",fontsize=13)
ax.text(4,.05,"No zero. No collisions. The same six destinations.",ha="center",color="#91e0b2",fontsize=13)
fig.suptitle("Multiplying by 3 permutes the nonzero residues modulo 7",color="#e6edf3",fontsize=18)
fig.subplots_adjust(left=.02,right=.98,top=.88,bottom=.03)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
print("Input residues:",source)
print("3 x input mod 7:",target)
법 7에서 1부터 6에 3을 곱하면 3·6·2·5·1·4가 되어 영이 아닌 나머지가 한 번씩 나타나는 대응 그림.
Input residues: [1, 2, 3, 4, 5, 6]
3 x input mod 7: [3, 6, 2, 5, 1, 4]
2. 0이 없고, 충돌이 없고, 빈칸이 없습니다
먼저 법 7에서 3의 모듈러 역원은 5입니다. $3\times5=15\equiv1\pmod7$이기 때문입니다. 이 역원을 사용하면 곱셈을 되돌릴 수 있습니다.
2.1. 나오는 나머지에 0이 없다.
먼저 0이 나올 가능성부터 확인하겠습니다. 아래의 $\in$은 “뒤 목록에 속한다”는 뜻으로, $r$에는 1·2·3·4·5·6 중 하나를 넣습니다.
어떤 $r\in\{1,2,3,4,5,6\}$에서 $3r\equiv0\pmod7$이라고 가정해봅시다.
양변에 5를 곱하면
$5\times3r\equiv5\times0$에서 $15r\equiv0$, 이어 $15r=(14+1)r=14r+r\equiv r$입니다. $14r$는 7의 배수여서 사라집니다.
따라서 $r\equiv0\pmod7$입니다.
이 말의 뜻은 $r$을 7로 나누었을 때 나머지가 0이다~ 입니다. 다시 말해 $r$은 7의 배수다~ 라고 말하는 거지요.
그러나 1부터 6 사이의 수는 7의 배수가 아닙니다. 모순입니다. 따라서 0은 나올 수 없습니다.
2.2. 충돌이 없다(=결과가 합쳐지지 않는다)
다음으로 서로 다른 $r,s$에서 같은 나머지가 나왔다고 합시다.
위에서 정리해 본 대로, 양변에 5를 곱하면 $r\equiv s\pmod7$입니다.
그런데 우리가 고른 입력은 1부터 6까지입니다. 이 범위에서는 서로 다른 두 수가 7로 나눈 나머지가 같을 수 없습니다.
더 자세히 살펴보자면 둘 다 1부터 6 사이이므로 차이의 절댓값은 7보다 작습니다. 이 말은 서로 다른 두 수라면 차이가 7의 배수만큼 벌어질 수 없기 때문에 같은 나머지가 나올 수 없다는 뜻입니다.
구체적으로 $r-s$는 $-5$부터 5 사이의 정수입니다. 이 범위에서 7의 배수는 0 하나뿐입니다. 따라서 차이가 0입니다. 예를 들어 $r=1,s=8$이었다면 법 7에서 합동이어도 다른 정수였겠지만, 8은 지금의 입력 목록에 없습니다.
따라서 $r=s$여야 합니다.
어라? 처음에는 서로 다른 두 입력이라고 가정했는데, 계산해 보니 같은 수여야 한다는 결론이 나왔습니다.
즉, 서로 다른 입력이 같은 나머지로 합쳐지는 것은 불가능합니다.
앞의 두 단계는 서로 다른 일을 했습니다. 첫 단계가 없으면 여섯 출력 중 하나가 0으로 가서 원래 목록을 벗어날 수도 있습니다. 둘째 단계가 없으면 모두 1부터 6 안에 있어도 $1,1,1,1,1,1$처럼 겹칠 수 있습니다. 두 단계가 모두 끝나야 “여섯 개의 서로 다른 출력이 여섯 자리 안에 있다”는 문장을 사용할 수 있습니다.
2.3. 빈칸이 없다
마지막으로 개수를 셉니다.
입력은 여섯 개이고, 각 입력에서 나머지를 하나씩 얻습니다.
이 나머지는 모두 1부터 6 사이이며(2.1), 서로 다른 입력에서 얻은 나머지는 겹치지 않습니다(2.2).
따라서 여섯 나머지가 전부 한 번씩 나옵니다.
“곱하면 순열이 된다”는 짧은 문장 안에는 이렇게 범위를 벗어나지 않음, 중복되지 않음, 개수가 같음이라는 세 단계가 들어 있습니다.
그림을 만든 Python 코드
from pathlib import Path as _bfPath
from matplotlib.font_manager import FontProperties as _bfFontProperties
from matplotlib.text import Text as _bfText
from matplotlib.ticker import Formatter as _bfFormatter
from io import BytesIO as _bfBytesIO
from IPython.display import display as _bfDisplay, Image as _bfImage
class _BilingualFormatter(_bfFormatter):
def __init__(self, base, labels):
self.base, self.labels = base, labels
def set_axis(self, axis):
super().set_axis(axis)
self.base.set_axis(axis)
def set_locs(self, locs):
super().set_locs(locs)
self.base.set_locs(locs)
def __call__(self, value, pos=None):
raw=self.base(value,pos)
translated=self.labels.get(raw)
return translated+'\n'+raw if translated else raw
def get_offset(self):
return self.base.get_offset()
def _apply_bilingual_figure(_bfFigure, _bfLabels, _bfOriginalPixels):
if getattr(_bfFigure, '_bilingual_complete', False):
return
_bfFont = _bfPath('C:/Windows/Fonts/malgun.ttf')
if not _bfFont.is_file():
raise RuntimeError('Korean/English figures require the Malgun Gothic font.')
_bfFamily = _bfFontProperties(fname=str(_bfFont)).get_name()
# Keep the delivered original's aspect ratio. A bilingual label must not
# stretch the chart, its grid cells, cards or geometry vertically.
_bfFigure.set_size_inches(_bfOriginalPixels[0] / 80,
_bfOriginalPixels[1] / 80, forward=True)
_bfFigure._bilingual_original_pixels = tuple(_bfOriginalPixels)
_bfFigure.canvas.draw()
for _bfAxes in _bfFigure.axes:
for _bfAxis in (_bfAxes.xaxis,_bfAxes.yaxis):
if any(_bfTick.get_text() in _bfLabels for _bfTick in _bfAxis.get_majorticklabels()):
_bfAxis.set_major_formatter(_BilingualFormatter(_bfAxis.get_major_formatter(),_bfLabels))
_bfTexts = list(_bfFigure.findobj(_bfText))
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
_bfTexts.extend(_bfCell.get_text() for _bfCell in _bfTable.get_celld().values())
_bfSeen = set()
_bfChanged = []
for _bfItem in _bfTexts:
if id(_bfItem) in _bfSeen:
continue
_bfSeen.add(id(_bfItem))
_bfOriginal = _bfItem.get_text()
_bfKorean = _bfLabels.get(_bfOriginal)
if _bfKorean:
_bfItem.set_text(_bfKorean + '\n' + _bfOriginal)
_bfItem.set_linespacing(1.05)
_bfChanged.append((_bfKorean, _bfOriginal))
_bfProperties = _bfItem.get_fontproperties().copy()
_bfProperties.set_file(None)
_bfProperties.set_family([_bfFamily, 'DejaVu Sans'])
_bfItem.set_fontproperties(_bfProperties)
assert _bfChanged, 'Every figure must contain meaningful Korean/English labels.'
# Bilingual column headers must stay inside their original table cells.
_bfFigure.canvas.draw()
_bfRenderer = _bfFigure.canvas.get_renderer()
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
for _bfCell in _bfTable.get_celld().values():
_bfCellText = _bfCell.get_text()
_bfBox = _bfCellText.get_window_extent(_bfRenderer)
_bfCellBox = _bfCell.get_window_extent(_bfRenderer)
if _bfBox.width and _bfBox.height:
_bfFit = min(1, .92*_bfCellBox.width/_bfBox.width,
.88*_bfCellBox.height/_bfBox.height)
_bfCellText.set_fontsize(_bfCellText.get_fontsize()*_bfFit)
if _bfAxes.get_title():
_bfAxes.set_title(_bfAxes.get_title(), pad=6)
_bfFigure.canvas.draw()
# Keep subplot headings clear of the shared two-line title, moving the
# subplot boundary only as much as the actual rendered text requires.
if _bfFigure._suptitle is not None:
_bfTopTitle = _bfFigure._suptitle.get_window_extent(_bfRenderer)
for _bfAxes in _bfFigure.axes:
if not _bfAxes.get_title():
continue
_bfHeading = _bfAxes.title.get_window_extent(_bfRenderer)
_bfGap = _bfHeading.y1 - (_bfTopTitle.y0 - 9)
if _bfGap > 0:
_bfPosition = _bfAxes.get_position(original=True)
_bfAxes.set_position([_bfPosition.x0, _bfPosition.y0,
_bfPosition.width, _bfPosition.height - _bfGap/_bfFigure.bbox.height])
_bfFigure._bilingual_labels = _bfChanged
_bfFigure._bilingual_complete = True
def _display_bilingual_figure(_bfFigure):
# A fixed full canvas avoids notebook's automatic tight crop changing the
# aspect ratio after titles and labels become bilingual. This is a fresh
# Matplotlib rendering, at exactly twice the original pixel dimensions.
global _bfDisplayedFigure
_bfDisplayedFigure = _bfFigure
_bfBuffer = _bfBytesIO()
_bfFigure.savefig(_bfBuffer, format='png', dpi=160, bbox_inches=None,
pad_inches=0, facecolor=_bfFigure.get_facecolor())
_bfDisplay(_bfImage(data=_bfBuffer.getvalue()))
plt.close(_bfFigure)
_bfLabels = {'Dividend': '피제수', 'Divisor': '제수', 'Quotient': '몫', 'Remainder': '나머지', '3r mod 7': '3r의 나머지', 'then x5': '5를 곱하기', 'k, gcd(k,12)=1': '12와 서로소인 k', '5k mod 12': '5k의 법 12 나머지', 'Modulus': '법', 'Other factors': '나머지 법들의 곱', 'Inverse': '역원', 'Unit part': '단위 부품', 'Target': '목표 나머지', 'Contribution': '기여값', 'Possible square residues': '가능한 제곱 나머지', 'Squares of 0, 1, ... , m-1': '0·1·…·(m−1)의 제곱 나머지', 'PASS': '통과', 'IMPOSSIBLE': '불가능', 'mod 2': '법 2', 'mod 3': '법 3', 'mod 4': '법 4', 'mod 5': '법 5', 'mod 7': '법 7', 'mod 8': '법 8', 'mod 9': '법 9', 'mod 11': '법 11', 'mod 12': '법 12', 'mod 105': '법 105', '1. No zero output': '1. 출력 0이 없다', 'An inverse would send\na zero output back to zero.': '역원이 있다면\n출력 0은 입력 0으로 돌아간다.', 'Inputs are 1 through 6.\nNone is zero modulo 7.': '입력은 1부터 6까지.\n법 7에서 0인 수는 없다.', '2. No collisions': '2. 출력이 겹치지 않는다', 'The inverse 5 recovers every input.\nTwo inputs cannot merge.': '역원 5가 모든 입력을 되찾는다.\n서로 다른 입력이 겹칠 수 없다.', '3. Equal finite counts': '3. 유한한 개수가 같다', '6 different outputs\ninside 6 legal slots': '서로 다른 출력 6개\n허용된 자리도 6개', 'If one slot were empty,\nonly five slots would remain.': '한 자리가 비어 있다면\n남은 자리는 다섯 개뿐이다.', 'Why the multiplication table must be a permutation': '곱셈표가 순열이어야 하는 이유', 'No zero + no collisions + the same number of slots = every nonzero residue appears exactly once.': '출력 0 없음 + 충돌 없음 + 자리 수 동일\n= 0이 아닌 모든 나머지가 정확히 한 번씩 등장'}
_bfOriginalPixels = [1369, 707]
from math import gcd, isqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib.patches import Rectangle, Circle, FancyBboxPatch, FancyArrowPatch
BG = "#101827"
PANEL = "#1d2b40"
INK = "#edf3fc"
MUTED = "#c0cede"
BLUE = "#8fdcff"
GREEN = "#91e0b2"
GOLD = "#ffd18c"
RED = "#ffaaaa"
LINE = "#667a96"
def canvas(rows=1, cols=1, size=(13.6, 6.8), title=""):
fig, axes = plt.subplots(rows, cols, figsize=size, facecolor=BG,
squeeze=False)
axes = axes.ravel().tolist()
for ax in axes:
ax.set_facecolor(BG)
ax.tick_params(colors=INK, labelsize=12)
for spine in ax.spines.values():
spine.set_color(LINE)
fig.suptitle(title, fontsize=18, color=INK, y=.98)
fig.subplots_adjust(left=.07, right=.97, top=.86, bottom=.13,
wspace=.34, hspace=.48)
return fig, axes
def off(ax):
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.axis("off")
def text(ax, x, y, value, color=INK, size=12, **kwargs):
defaults = dict(ha="center", va="center", fontsize=size, color=color,
transform=ax.transAxes, linespacing=1.35)
defaults.update(kwargs)
return ax.text(x, y, value, **defaults)
def card(ax, x, y, width, height, value, edge=LINE, color=INK, size=14):
ax.add_patch(FancyBboxPatch((x, y), width, height,
boxstyle="round,pad=0.012", transform=ax.transAxes,
facecolor=PANEL, edgecolor=edge, linewidth=1.4))
text(ax, x+width/2, y+height/2, value, color=color, size=size)
def arrow(ax, start, end, color=BLUE):
ax.add_patch(FancyArrowPatch(start, end, transform=ax.transAxes,
arrowstyle="-|>", mutation_scale=18,
color=color, linewidth=1.7))
def caption(fig, value):
fig.text(.5, .035, value, ha="center", va="center",
color=MUTED, fontsize=12)
fig,axes=canvas(1,3,size=(15,7.2),title="Why the multiplication table must be a permutation")
for ax in axes:off(ax)
ax=axes[0]
text(ax,.5,.97,"1. No zero output",color=BLUE,size=16)
for j,r in enumerate(range(7)):
x=.09+j*.135
card(ax,x-.045,.65,.09,.13,str(r),edge=RED if r==0 else GREEN,size=14)
text(ax,.09,.56,"X",color=RED,size=18)
text(ax,.53,.41,"An inverse would send\na zero output back to zero.",size=14)
text(ax,.5,.17,"Inputs are 1 through 6.\nNone is zero modulo 7.",color=GOLD,size=13)
ax=axes[1]
text(ax,.5,.97,"2. No collisions",color=BLUE,size=16)
rows=[[r,3*r%7,5*(3*r%7)%7] for r in range(1,7)]
table=ax.table(cellText=rows,colLabels=["r","3r mod 7","then x5"],
cellLoc="center",bbox=[.01,.28,.98,.56])
table.auto_set_font_size(False);table.set_fontsize(12)
for (i,j),cell in table.get_celld().items():
cell.set_facecolor(PANEL);cell.set_edgecolor(LINE);cell.get_text().set_color(INK)
text(ax,.5,.12,"The inverse 5 recovers every input.\nTwo inputs cannot merge.",color=GREEN,size=13)
ax=axes[2]
text(ax,.5,.97,"3. Equal finite counts",color=BLUE,size=16)
for j in range(6):
x=.10+j*.16
ax.add_patch(Rectangle((x-.055,.64),.11,.14,
transform=ax.transAxes,facecolor=PANEL,edgecolor=GREEN))
ax.add_patch(Circle((x,.71),.025,transform=ax.transAxes,color=GREEN))
text(ax,.5,.46,"6 different outputs\ninside 6 legal slots",color=GREEN,size=16)
text(ax,.5,.17,"If one slot were empty,\nonly five slots would remain.",size=14)
caption(fig,"No zero + no collisions + the same number of slots = every nonzero residue appears exactly once.")
assert sorted(3*r%7 for r in range(1,7))==list(range(1,7))
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
페르마 순열 증명의 세 단계를 분리한다. 0 출력 배제, 역원 5로 입력을 복구하는 표, 서로 다른 여섯 결과와 여섯 자리의 개수 일치가 각각 어떤 역할인지 보여준다.
지금까지 진행한 것이 바로 ‘페르마의 순열 증명’이었습니다.
이제 이 계산을 다른 곱하는 수에도 쓸 수 있는지 보겠습니다.
3. 소수라는 조건 드디어 등장
방금 7과 3으로 확인한 과정은 사실 7이 ‘소수’, 그리고 7과 3이 ‘서로소’였기 때문에 가능한 것이었습니다.
따라서 다른 소수에서도 되는지 살펴보겠습니다.
소수는 1보다 큰 정수 중 양의 약수가 1과 자기 자신뿐인 수입니다. 7과 11은 소수이고, 8이나 9는 아닙니다.
이번 절은 위에서 살펴봤던 것을 소수 조건에서 문자로 다시 한번 풀어 보는 것입니다. 쉽게 읽으시면 됩니다.
이제 소수를 $p$라고 쓰겠습니다.
$p$의 배수가 아닌 정수 $a$를 고릅니다. 기호로 $p\nmid a$라고 씁니다. $p$가 소수이므로 이 조건은 $\gcd(a,p)=1$과 같습니다. 따라서 3편의 정리에 의해 $a$는 법 $p$에서 역원을 갖습니다.
소수 $p$의 양의 약수는 1과 $p$ 둘뿐이므로 $a,p$의 공약수가 1보다 크다면 반드시 $p$여야 합니다. 그런데 $p$는 $a$를 나누지 않는다고 했습니다. 그래서 남는 최대공약수는 1입니다. 법이 8이라면 “8의 배수가 아니다”만으로는 부족합니다. 2는 8의 배수가 아니지만 8과 공약수 2를 가져 역원이 없기 때문입니다.
0이 아닌 나머지 목록
에 각각 $a$를 곱합니다. $ar\equiv0\pmod p$이면 역원을 곱해 $r\equiv0$이 되어 불가능합니다.(나머지는 0이 될 수 없음)
$ar\equiv as\pmod p$이면 역원을 곱해 $r\equiv s$이고, 주어진 범위에서는 $r=s$입니다.(나머지가 겹치지 않음)
출력은 0을 제외한 $p-1$개의 자리 안에 들어가며 서로 다르고, 입력도 $p-1$개입니다. 따라서 출력은 $1,\ldots,p-1$을 정확히 한 번씩 차지합니다.
여기서 소수 조건이 하는 일은 모든 영이 아닌 나머지가 역원을 갖도록 보장하는 것입니다.
합성수인 법 8에서는 2, 4, 6이 8과 서로소가 아니어서 같은 보장이 없습니다.
이제 각 항의 나머지가 무엇인지를 일일이 계산할 필요는 없습니다. 어떤 순서인지는 몰라도, 결과가 원래 목록의 재배열이라는 것을 알았기 때문입니다. 바로 이 정보로 전체 곱을 비교할 수 있습니다.
4. 전체 곱을 비교하고, 약분할 수 있는 이유까지 확인하기
이 재배열에서 어떻게 거듭제곱을 얻을까요? 법 7의 예로 돌아가, 양쪽 목록을 각각 전부 곱해봅시다. $3,6,9,12,15,18$의 나머지는 $3,6,2,5,1,4$였습니다. 따라서
곱의 순서는 결과에 영향을 주지 않으므로 오른쪽을 크기순으로 다시 적었습니다. 왼쪽에는 3이 여섯 번 곱해져 있으므로
양변의 긴 곱을 지우면 $3^6\equiv1$처럼 보입니다. 하지만 합동식에서 약분하려면 곱과 법이 서로소인지 확인해야 합니다. 1부터 6까지 어느 수도 소수 7을 인수로 갖지 않으므로 그 곱도 7과 서로소입니다. 따라서 역원이 있고, 그 역원을 곱해 약분할 수 있습니다.
일반적으로 $1\cdot2\cdots(p-1)$을 $(p-1)!$이라고 씁니다. 느낌표는 팩토리얼이며, 1부터 해당 수까지 모두 곱한다는 뜻입니다. 재배열에서 얻은 식은
따라서 $\gcd((p-1)!,p)=1$이고 약분이 정당합니다.
긴 곱을 잠시 $P$라고 쓰고 그 역원을 $v$라고 하면 $Pv\equiv1\pmod p$입니다. 실제로 하는 계산은
입니다. 등식에서 같은 수를 나누는 모양과 닮았지만, 근거는 역원을 양쪽에 곱했다는 데 있습니다. 약분할 수가 법과 서로소인지 확인한 이유가 바로 이것입니다.
결론은
입니다. 이것이 페르마의 소정리입니다. 곱셈으로 나머지가 재배열된다는 사실을 전체 곱에 적용하고, 역원이 있는 인수를 취소해서 얻었습니다.
증명의 마지막 한 줄만 외우면 지수 $p-1$이 어디서 왔는지 놓치기 쉽습니다. 그 지수는 원래 목록에 0 아닌 나머지가 $p-1$개 있었기 때문에 나옵니다. 각 항에 $a$를 하나씩 곱했으므로 전체 곱에 $a$가 정확히 $p-1$번 들어 있습니다.
5. 두 가지 형태의 정리는 조건이 다릅니다
페르마의 소정리는 다음 형태로도 나타납니다.
앞의 형태에서는 $p\nmid a$라는 조건이 있었는데, 이번에는 모든 정수 $a$라고 적혀 있습니다. 왜 조건을 없앨 수 있을까요?
$p$가 $a$를 나누지 않으면 이미 증명한 $a^{p-1}\equiv1$의 양변에 $a$를 곱하면 됩니다.
한편 $p$가 $a$를 나누면 $a\equiv0\pmod p$이고 $a^p$도 0과 합동입니다. 이 경우에도 $a^p\equiv a$가 성립합니다.
두 경우를 합쳐 모든 정수에 대한 형태를 얻습니다.
반대로 두 번째 형태에서 $a$를 무조건 약분하여 첫 번째 형태를 얻으면 안 됩니다. $a$가 $p$의 배수일 때는 역원이 없기 때문입니다. 예를 들어 $a=7$, $p=7$이면 $7^7\equiv7\equiv0\pmod7$은 맞지만 $7^6\equiv1\pmod7$은 틀립니다.
| 형태 | 사용할 수 있는 $a$ | 법 7에서 $a=7$ |
|---|---|---|
| $a^{p-1}\equiv1\pmod p$ | $p$의 배수가 아닌 정수 | 사용할 수 없음 |
| $a^p\equiv a\pmod p$ | 모든 정수 | 양쪽 모두 0 |
둘은 이름이 같은 정리의 관련된 형태이지만, 조건이 같지는 않습니다. 계산하려는 식에 어떤 형태가 필요한지 먼저 확인해야 합니다.
6. 법 11에서 3의 100제곱, 법 7에서는 다른 답
11은 소수이고 3을 나누지 않으므로
왜 지수를 10으로 묶을까요? 법 11에서 1로 바꿀 수 있다고 보장받은 덩어리가 $3^{10}$이기 때문입니다. $3^{100}$에는 3이 백 번 곱해져 있습니다. 이를 열 개씩 묶으면 묶음 열 개가 되고, 각 묶음을 법 11에서 1로 바꿉니다. 이때 한 묶음 안에 있는 3 하나하나의 나머지를 1로 바꾸는 것이 아닙니다.
100은 10의 열 배이므로
중간의 등호는 거듭제곱 법칙에 따른 정확한 등식이고, 합동 기호부터는 법 11에서 나머지를 바꾼 것입니다. $3^{10}=1$이라는 등식을 주장하는 것은 아닙니다. 실제 값 $3^{10}=59049$는 1과 다르지만 $59049=11\times5368+1$입니다.
앞 식의 $3^{10}$을 더 짧게 확인하려면 $3^5=243=22\times11+1$에서 출발해 $3^{10}=(3^5)^2\equiv1\pmod{11}$이라고 해도 됩니다.
같은 $3^{100}$을 7로 나누면 답이 달라집니다. 법 7에서는 페르마의 소정리가 보장하는 지수가 6입니다.
이므로
법 11에서 얻은 나머지 1을 법 7 계산에 그대로 가져올 수 없습니다. 법은 수식 끝에 붙이는 장식이 아니라, 어떤 수를 같은 것으로 취급하는지 정하는 기준입니다.
같은 지수 100도 법 11에서는 $10\times10$, 법 7에서는 $6\times16+4$로 묶습니다. 그림에서 1로 바꾸는 대상은 밑 3이 아니라, 각 법에서 나머지가 1인 거듭제곱 묶음입니다.
그림을 만든 Python 코드
from pathlib import Path as _bfPath
from matplotlib.font_manager import FontProperties as _bfFontProperties
from matplotlib.text import Text as _bfText
from matplotlib.ticker import Formatter as _bfFormatter
from io import BytesIO as _bfBytesIO
from IPython.display import display as _bfDisplay, Image as _bfImage
class _BilingualFormatter(_bfFormatter):
def __init__(self, base, labels):
self.base, self.labels = base, labels
def set_axis(self, axis):
super().set_axis(axis)
self.base.set_axis(axis)
def set_locs(self, locs):
super().set_locs(locs)
self.base.set_locs(locs)
def __call__(self, value, pos=None):
raw=self.base(value,pos)
translated=self.labels.get(raw)
return translated+'\n'+raw if translated else raw
def get_offset(self):
return self.base.get_offset()
def _apply_bilingual_figure(_bfFigure, _bfLabels, _bfOriginalPixels):
if getattr(_bfFigure, '_bilingual_complete', False):
return
_bfFont = _bfPath('C:/Windows/Fonts/malgun.ttf')
if not _bfFont.is_file():
raise RuntimeError('Korean/English figures require the Malgun Gothic font.')
_bfFamily = _bfFontProperties(fname=str(_bfFont)).get_name()
# Keep the delivered original's aspect ratio. A bilingual label must not
# stretch the chart, its grid cells, cards or geometry vertically.
_bfFigure.set_size_inches(_bfOriginalPixels[0] / 80,
_bfOriginalPixels[1] / 80, forward=True)
_bfFigure._bilingual_original_pixels = tuple(_bfOriginalPixels)
_bfFigure.canvas.draw()
for _bfAxes in _bfFigure.axes:
for _bfAxis in (_bfAxes.xaxis,_bfAxes.yaxis):
if any(_bfTick.get_text() in _bfLabels for _bfTick in _bfAxis.get_majorticklabels()):
_bfAxis.set_major_formatter(_BilingualFormatter(_bfAxis.get_major_formatter(),_bfLabels))
_bfTexts = list(_bfFigure.findobj(_bfText))
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
_bfTexts.extend(_bfCell.get_text() for _bfCell in _bfTable.get_celld().values())
_bfSeen = set()
_bfChanged = []
for _bfItem in _bfTexts:
if id(_bfItem) in _bfSeen:
continue
_bfSeen.add(id(_bfItem))
_bfOriginal = _bfItem.get_text()
_bfKorean = _bfLabels.get(_bfOriginal)
if _bfKorean:
_bfItem.set_text(_bfKorean + '\n' + _bfOriginal)
_bfItem.set_linespacing(1.05)
_bfChanged.append((_bfKorean, _bfOriginal))
_bfProperties = _bfItem.get_fontproperties().copy()
_bfProperties.set_file(None)
_bfProperties.set_family([_bfFamily, 'DejaVu Sans'])
_bfItem.set_fontproperties(_bfProperties)
assert _bfChanged, 'Every figure must contain meaningful Korean/English labels.'
# Bilingual column headers must stay inside their original table cells.
_bfFigure.canvas.draw()
_bfRenderer = _bfFigure.canvas.get_renderer()
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
for _bfCell in _bfTable.get_celld().values():
_bfCellText = _bfCell.get_text()
_bfBox = _bfCellText.get_window_extent(_bfRenderer)
_bfCellBox = _bfCell.get_window_extent(_bfRenderer)
if _bfBox.width and _bfBox.height:
_bfFit = min(1, .92*_bfCellBox.width/_bfBox.width,
.88*_bfCellBox.height/_bfBox.height)
_bfCellText.set_fontsize(_bfCellText.get_fontsize()*_bfFit)
if _bfAxes.get_title():
_bfAxes.set_title(_bfAxes.get_title(), pad=6)
_bfFigure.canvas.draw()
# Keep subplot headings clear of the shared two-line title, moving the
# subplot boundary only as much as the actual rendered text requires.
if _bfFigure._suptitle is not None:
_bfTopTitle = _bfFigure._suptitle.get_window_extent(_bfRenderer)
for _bfAxes in _bfFigure.axes:
if not _bfAxes.get_title():
continue
_bfHeading = _bfAxes.title.get_window_extent(_bfRenderer)
_bfGap = _bfHeading.y1 - (_bfTopTitle.y0 - 9)
if _bfGap > 0:
_bfPosition = _bfAxes.get_position(original=True)
_bfAxes.set_position([_bfPosition.x0, _bfPosition.y0,
_bfPosition.width, _bfPosition.height - _bfGap/_bfFigure.bbox.height])
_bfFigure._bilingual_labels = _bfChanged
_bfFigure._bilingual_complete = True
def _display_bilingual_figure(_bfFigure):
# A fixed full canvas avoids notebook's automatic tight crop changing the
# aspect ratio after titles and labels become bilingual. This is a fresh
# Matplotlib rendering, at exactly twice the original pixel dimensions.
global _bfDisplayedFigure
_bfDisplayedFigure = _bfFigure
_bfBuffer = _bfBytesIO()
_bfFigure.savefig(_bfBuffer, format='png', dpi=160, bbox_inches=None,
pad_inches=0, facecolor=_bfFigure.get_facecolor())
_bfDisplay(_bfImage(data=_bfBuffer.getvalue()))
plt.close(_bfFigure)
_bfLabels = {'Dividend': '피제수', 'Divisor': '제수', 'Quotient': '몫', 'Remainder': '나머지', '3r mod 7': '3r의 법 7 나머지', 'then x5': '그다음 5를 곱하기', 'k, gcd(k,12)=1': '12와 서로소인 k', '5k mod 12': '5k의 법 12 나머지', 'Modulus': '법', 'Other factors': '나머지 법들의 곱', 'Inverse': '역원', 'Unit part': '단위 부품', 'Target': '목표 나머지', 'Contribution': '기여값', 'Possible square residues': '가능한 제곱 나머지', 'Squares of 0, 1, ... , m-1': '0·1·…·(m−1)의 제곱 나머지', 'PASS': '통과', 'IMPOSSIBLE': '불가능', 'mod 2': '법 2', 'mod 3': '법 3', 'mod 4': '법 4', 'mod 5': '법 5', 'mod 7': '법 7', 'mod 8': '법 8', 'mod 9': '법 9', 'mod 11': '법 11', 'mod 12': '법 12', 'mod 105': '법 105', '3^10 ≡ 1 (mod 11)': '법 11에서 3^10의 나머지는 1', 'mod 11: 10 blocks of 10, 0 left over': '법 11: 10개씩 10묶음, 남는 인수 0개', '3^6 ≡ 1 (mod 7)': '법 7에서 3^6의 나머지는 1', 'mod 7: 16 blocks of 6, 4 left over': '법 7: 6개씩 16묶음, 남는 인수 4개', 'The modulus determines how the same hundred factors are grouped': '같은 100개 인수라도 법에 따라 묶는 방식이 달라진다', 'mod 11: (3^10)^10 ≡ 1. mod 7: (3^6)^16 x 3^4 ≡ 4. Gold cells are the four leftover factors.': '법 11: (3^10)^10 ≡ 1. 법 7: (3^6)^16 × 3^4 ≡ 4.\n금색 칸은 묶이지 않고 남은 인수 네 개이다.'}
_bfOriginalPixels = [1253, 802]
from math import gcd, isqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib.patches import Rectangle, Circle, FancyBboxPatch, FancyArrowPatch
BG = "#101827"
PANEL = "#1d2b40"
INK = "#edf3fc"
MUTED = "#c0cede"
BLUE = "#8fdcff"
GREEN = "#91e0b2"
GOLD = "#ffd18c"
RED = "#ffaaaa"
LINE = "#667a96"
def canvas(rows=1, cols=1, size=(13.6, 6.8), title=""):
fig, axes = plt.subplots(rows, cols, figsize=size, facecolor=BG,
squeeze=False)
axes = axes.ravel().tolist()
for ax in axes:
ax.set_facecolor(BG)
ax.tick_params(colors=INK, labelsize=12)
for spine in ax.spines.values():
spine.set_color(LINE)
fig.suptitle(title, fontsize=18, color=INK, y=.98)
fig.subplots_adjust(left=.07, right=.97, top=.86, bottom=.13,
wspace=.34, hspace=.48)
return fig, axes
def off(ax):
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.axis("off")
def text(ax, x, y, value, color=INK, size=12, **kwargs):
defaults = dict(ha="center", va="center", fontsize=size, color=color,
transform=ax.transAxes, linespacing=1.35)
defaults.update(kwargs)
return ax.text(x, y, value, **defaults)
def card(ax, x, y, width, height, value, edge=LINE, color=INK, size=14):
ax.add_patch(FancyBboxPatch((x, y), width, height,
boxstyle="round,pad=0.012", transform=ax.transAxes,
facecolor=PANEL, edgecolor=edge, linewidth=1.4))
text(ax, x+width/2, y+height/2, value, color=color, size=size)
def arrow(ax, start, end, color=BLUE):
ax.add_patch(FancyArrowPatch(start, end, transform=ax.transAxes,
arrowstyle="-|>", mutation_scale=18,
color=color, linewidth=1.7))
def caption(fig, value):
fig.text(.5, .035, value, ha="center", va="center",
color=MUTED, fontsize=12)
fig,axes=canvas(1,2,size=(13.7,8.2),title="The modulus determines how the same hundred factors are grouped")
for ax,length,modulus in zip(axes,[10,6],[11,7]):
full=100//length
for index in range(100):
row,col=divmod(index,10)
leftover=index>=full*length
fill="#665033" if leftover else ("#285345" if (index//length)%2==0 else PANEL)
ax.add_patch(Rectangle((col-.46,row-.43),.92,.86,
facecolor=fill,edgecolor=LINE,linewidth=.6))
ax.text(col,row,"3",ha="center",va="center",color=GOLD if leftover else INK,fontsize=12)
ax.set(xlim=(-.65,9.65),ylim=(9.65,-.65))
ax.set_aspect("equal")
ax.set_xticks([]);ax.set_yticks([])
ax.set_title(f"mod {modulus}: {full} blocks of {length}, {100%length} left over",color=INK,fontsize=14,pad=16)
text(ax,.5,-.07,f"3^{length} ≡ 1 (mod {modulus})",color=GREEN,size=15)
caption(fig,"mod 11: (3^10)^10 ≡ 1. mod 7: (3^6)^16 x 3^4 ≡ 4. Gold cells are the four leftover factors.")
assert 100==10*10==6*16+4
assert pow(3,10,11)==pow(3,100,11)==1 and pow(3,6,7)==1 and pow(3,100,7)==4
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
같은 3의 백제곱을 법 11에서는 열 개씩 열 묶음, 법 7에서는 여섯 개씩 열여섯 묶음과 남은 네 개로 나눈다. 묶음의 나머지는 1이지만 최종 나머지는 각각 1과 4이며 밑을 바로 1로 바꾸는 계산이 아니다.
법 7의 마지막 지수 4는 묶음 밖에 남으므로 $3^4$를 따로 계산해야 합니다. 법을 바꾸면 사용할 묶음도 바뀐다는 점이 두 답의 차이를 설명합니다.
큰 지수가 꼭 보장 지수의 배수일 필요도 없습니다. 법 11에서 $3^{103}$이라면 $103=10\times10+3$으로 나누고
이라고 하면 됩니다. 보장 지수의 덩어리를 1로 바꾸고 남은 작은 지수만 계산합니다.
정리가 주는 지수를 사용하지 않고도 큰 거듭제곱의 나머지를 계산할 수 있습니다. $a,a^2,a^4,a^8,\ldots$를 제곱할 때마다 나머지로 줄이고, 필요한 지수들의 합에 해당하는 항만 곱하는 방법입니다.
거듭제곱을 나누어 계산하기
제곱-곱셈 표와 소수 법의 지수 묶기를 비교합니다.
예를 들어 $100=64+32+4$이면 세 항의 나머지를 곱합니다. 먼저 3의 100제곱을 법 11과 법 7에서 계산하여, 앞의 묶음 계산과 같은 답이 나오는지 확인해보세요.
지수 0을 입력하면 이 실험은 “곱할 항이 없는 곱”의 값을 1로 정하는 규약을 씁니다. 밑도 0인 $0^0$도 이 규약에 따라 1로 표시합니다. $0^1,0^2,\ldots$처럼 0을 한 번 이상 곱하면 0이라는 사실과는 구별해주세요.
7. 보장되는 지수와 처음 1이 되는 지수는 다릅니다
법 11에서 3의 거듭제곱을 직접 살펴봅시다. 한 단계마다 앞의 나머지에 3을 곱하고 다시 11로 나누면 됩니다.
| 지수 $j$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| $3^j$의 법 11 나머지 | 1 | 3 | 9 | 5 | 4 | 1 | 3 |
양의 지수 중 처음 1이 되는 것은 5입니다. 페르마의 소정리는 10에서 1이라고 했는데, 모순일까요? 아닙니다. 5에서 1이면 10에서도 $(3^5)^2\equiv1$입니다.
정리가 보장한 것은 $p-1$이라는 지수에서 1이 된다는 사실입니다. 그 지수가 가장 작다고 말하지 않았습니다. 처음 1이 되는 양의 지수를 위수라고 부릅니다. 법 11에서 3의 위수는 5입니다.
그림을 만든 Python 코드
from pathlib import Path as _bfPath
from matplotlib.font_manager import FontProperties as _bfFontProperties
from matplotlib.text import Text as _bfText
from matplotlib.ticker import Formatter as _bfFormatter
from io import BytesIO as _bfBytesIO
from IPython.display import display as _bfDisplay, Image as _bfImage
class _BilingualFormatter(_bfFormatter):
def __init__(self, base, labels):
self.base, self.labels = base, labels
def set_axis(self, axis):
super().set_axis(axis)
self.base.set_axis(axis)
def set_locs(self, locs):
super().set_locs(locs)
self.base.set_locs(locs)
def __call__(self, value, pos=None):
raw=self.base(value,pos)
translated=self.labels.get(raw)
return translated+'\n'+raw if translated else raw
def get_offset(self):
return self.base.get_offset()
def _apply_bilingual_figure(_bfFigure, _bfLabels, _bfOriginalPixels):
if getattr(_bfFigure, '_bilingual_complete', False):
return
_bfFont = _bfPath('C:/Windows/Fonts/malgun.ttf')
if not _bfFont.is_file():
raise RuntimeError('Korean/English figures require the Malgun Gothic font.')
_bfFamily = _bfFontProperties(fname=str(_bfFont)).get_name()
# Keep the delivered original's aspect ratio. A bilingual label must not
# stretch the chart, its grid cells, cards or geometry vertically.
_bfFigure.set_size_inches(_bfOriginalPixels[0] / 80,
_bfOriginalPixels[1] / 80, forward=True)
_bfFigure._bilingual_original_pixels = tuple(_bfOriginalPixels)
_bfFigure.canvas.draw()
for _bfAxes in _bfFigure.axes:
for _bfAxis in (_bfAxes.xaxis,_bfAxes.yaxis):
if any(_bfTick.get_text() in _bfLabels for _bfTick in _bfAxis.get_majorticklabels()):
_bfAxis.set_major_formatter(_BilingualFormatter(_bfAxis.get_major_formatter(),_bfLabels))
_bfTexts = list(_bfFigure.findobj(_bfText))
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
_bfTexts.extend(_bfCell.get_text() for _bfCell in _bfTable.get_celld().values())
_bfSeen = set()
_bfChanged = []
for _bfItem in _bfTexts:
if id(_bfItem) in _bfSeen:
continue
_bfSeen.add(id(_bfItem))
_bfOriginal = _bfItem.get_text()
_bfKorean = _bfLabels.get(_bfOriginal)
if _bfKorean:
_bfItem.set_text(_bfKorean + '\n' + _bfOriginal)
_bfItem.set_linespacing(1.05)
_bfChanged.append((_bfKorean, _bfOriginal))
_bfProperties = _bfItem.get_fontproperties().copy()
_bfProperties.set_file(None)
_bfProperties.set_family([_bfFamily, 'DejaVu Sans'])
_bfItem.set_fontproperties(_bfProperties)
assert _bfChanged, 'Every figure must contain meaningful Korean/English labels.'
# Bilingual column headers must stay inside their original table cells.
_bfFigure.canvas.draw()
_bfRenderer = _bfFigure.canvas.get_renderer()
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
for _bfCell in _bfTable.get_celld().values():
_bfCellText = _bfCell.get_text()
_bfBox = _bfCellText.get_window_extent(_bfRenderer)
_bfCellBox = _bfCell.get_window_extent(_bfRenderer)
if _bfBox.width and _bfBox.height:
_bfFit = min(1, .92*_bfCellBox.width/_bfBox.width,
.88*_bfCellBox.height/_bfBox.height)
_bfCellText.set_fontsize(_bfCellText.get_fontsize()*_bfFit)
if _bfAxes.get_title():
_bfAxes.set_title(_bfAxes.get_title(), pad=6)
_bfFigure.canvas.draw()
# Keep subplot headings clear of the shared two-line title, moving the
# subplot boundary only as much as the actual rendered text requires.
if _bfFigure._suptitle is not None:
_bfTopTitle = _bfFigure._suptitle.get_window_extent(_bfRenderer)
for _bfAxes in _bfFigure.axes:
if not _bfAxes.get_title():
continue
_bfHeading = _bfAxes.title.get_window_extent(_bfRenderer)
_bfGap = _bfHeading.y1 - (_bfTopTitle.y0 - 9)
if _bfGap > 0:
_bfPosition = _bfAxes.get_position(original=True)
_bfAxes.set_position([_bfPosition.x0, _bfPosition.y0,
_bfPosition.width, _bfPosition.height - _bfGap/_bfFigure.bbox.height])
_bfFigure._bilingual_labels = _bfChanged
_bfFigure._bilingual_complete = True
def _display_bilingual_figure(_bfFigure):
# A fixed full canvas avoids notebook's automatic tight crop changing the
# aspect ratio after titles and labels become bilingual. This is a fresh
# Matplotlib rendering, at exactly twice the original pixel dimensions.
global _bfDisplayedFigure
_bfDisplayedFigure = _bfFigure
_bfBuffer = _bfBytesIO()
_bfFigure.savefig(_bfBuffer, format='png', dpi=160, bbox_inches=None,
pad_inches=0, facecolor=_bfFigure.get_facecolor())
_bfDisplay(_bfImage(data=_bfBuffer.getvalue()))
plt.close(_bfFigure)
_bfLabels = {'Dividend': '피제수', 'Divisor': '제수', 'Quotient': '몫', 'Remainder': '나머지', '3r mod 7': '3r의 법 7 나머지', 'then x5': '그다음 5를 곱하기', 'k, gcd(k,12)=1': '12와 서로소인 k', '5k mod 12': '5k의 법 12 나머지', 'Modulus': '법', 'Other factors': '나머지 법들의 곱', 'Inverse': '역원', 'Unit part': '단위 부품', 'Target': '목표 나머지', 'Contribution': '기여값', 'Possible square residues': '가능한 제곱 나머지', 'Squares of 0, 1, ... , m-1': '0·1·…·(m−1)의 제곱 나머지', 'PASS': '통과', 'IMPOSSIBLE': '불가능', 'mod 2': '법 2', 'mod 3': '법 3', 'mod 4': '법 4', 'mod 5': '법 5', 'mod 7': '법 7', 'mod 8': '법 8', 'mod 9': '법 9', 'mod 11': '법 11', 'mod 12': '법 12', 'mod 105': '법 105', 'Actual period: 5\nFermat guarantees exponent 10': '실제 주기: 5\n페르마의 보장 지수: 10', 'Exponent k': '지수 k', '3^k mod 11': '3^k를 11로 나눈 나머지', 'A guaranteed exponent need not be the smallest period': '보장된 지수가 최소 주기일 필요는 없다'}
_bfOriginalPixels = [1111, 525]
import matplotlib.pyplot as plt
exponents=list(range(21)); residues=[pow(3,k,11) for k in exponents]
assert residues[:6]==[1,3,9,5,4,1] and pow(3,100,11)==1
fig,ax=plt.subplots(figsize=(11.6,5.5),facecolor="#0d1117"); ax.set_facecolor("#0d1117")
ax.plot(exponents,residues,"o-",color="#93e5ff",linewidth=1.6)
for k in [0,5,10,15,20]:
ax.scatter(k,1,s=110,color="#91e0b2",zorder=3)
ax.annotate(str(k),(k,1),xytext=(0,13),textcoords="offset points",color="#91e0b2",ha="center")
ax.set(xlabel="Exponent k",ylabel="3^k mod 11",xticks=range(0,21,2),ylim=(0,10))
ax.text(10,7.4,"Actual period: 5\nFermat guarantees exponent 10",ha="center",color="#ffcf85",fontsize=14)
ax.tick_params(colors="#e6edf3"); ax.xaxis.label.set_color("#e6edf3"); ax.yaxis.label.set_color("#e6edf3")
for spine in ax.spines.values(): spine.set_color("#738399")
ax.grid(color="#526276",alpha=.25)
fig.suptitle("A guaranteed exponent need not be the smallest period",color="#e6edf3",fontsize=18)
fig.subplots_adjust(left=.08,right=.98,top=.88,bottom=.14)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
법 11에서 3의 거듭제곱은 1·3·9·5·4를 반복한다. 실제 주기는 5이며 페르마가 보장하는 지수 10과 다르다.
그렇다면 곱하는 수가 달라도 법만 같으면 처음 돌아오는 횟수가 같을까요? 이번에는 법을 7로 고정하고, 곱하는 수만 2와 3으로 바꾸어봅시다. 둘 다 눈금 1에서 시작합니다. 아직 한 번도 곱하지 않은 출발값이 지수 0의 값 1이고, 화살표를 한 번 따라갈 때마다 지수가 1씩 늘어납니다.
$$ \begin{aligned} \text{법 7에서 2배 반복: }&1\to2\to4\to1,\\ \text{법 7에서 3배 반복: }&1\to3\to2\to6\to4\to5\to1. \end{aligned} $$2배 경로의 마지막 화살표는 4에 2를 곱해 얻은 8을 나머지 1로 바꾼 것입니다. 3배 경로에서는 3에 다시 3을 곱한 9를 나머지 2로 바꾸었지요. 매번 두 칸이나 세 칸 앞으로 가는 그림이 아니라, 현재 수를 두 배 또는 세 배 하는 그림입니다.
그림을 만든 Python 코드
import math
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyArrowPatch, FancyBboxPatch
from matplotlib.path import Path
from matplotlib.font_manager import FontProperties
BG = '#101827'
INK = '#edf3fc'
MUTED = '#a9bad0'
BLUE = '#8fdcff'
ORANGE = '#ffd18c'
GREEN = '#91e0b2'
LINE = '#60748d'
FONT = FontProperties(family=['Malgun Gothic', 'DejaVu Sans'])
def label(ax, x, y, text, size=20, color=INK, **kwargs):
return ax.text(x, y, text, fontproperties=FONT, fontsize=size,
color=color, ha='center', va='center', **kwargs)
def ftext(fig, x, y, text, size=20, color=INK, **kwargs):
return fig.text(x, y, text, fontproperties=FONT, fontsize=size,
color=color, ha='center', va='center', **kwargs)
def point(r, n, radius=1.0):
angle = math.pi / 2 - 2 * math.pi * r / n
return np.array([radius * math.cos(angle), radius * math.sin(angle)])
def clock(ax, n, active=()):
ax.set_facecolor(BG)
ax.set_aspect('equal')
ax.set_xlim(-1.45, 1.45)
ax.set_ylim(-1.45, 1.45)
ax.axis('off')
ax.add_patch(Circle((0, 0), 1, fill=False, ec=LINE, lw=2))
for r in range(n):
p = point(r, n)
q = point(r, n, 1.2)
ax.plot(*p, 'o', color=BLUE if r in active else LINE, ms=8)
label(ax, *q, str(r), size=23, color=INK if r in active else MUTED)
def title(fig, ko, en):
ftext(fig, .5, .945, ko, size=25, weight='bold')
ftext(fig, .5, .895, en, size=16, color=MUTED)
def arc_arrow(ax, start, end, n, color=BLUE, radius=.9):
angles = np.linspace(math.pi/2-2*math.pi*start/n,
math.pi/2-2*math.pi*end/n, 40)
xy = np.column_stack((radius*np.cos(angles),radius*np.sin(angles)))
path = Path(xy)
ax.add_patch(FancyArrowPatch(path=path, arrowstyle='-|>', mutation_scale=22,
color=color, lw=3))
def multiply_arrow(ax, a, b, n, color=BLUE):
ax.add_patch(FancyArrowPatch(point(a,n,.94),point(b,n,.94),
connectionstyle='arc3,rad=.13',arrowstyle='-|>',
mutation_scale=21,color=color,lw=2.4,shrinkA=3,shrinkB=3))
cycles = {2:[1,2,4,1],3:[1,3,2,6,4,5,1]}
for a,path in cycles.items():
assert all((a*x)%7==y for x,y in zip(path,path[1:]))
assert path[-1]==1
fig = plt.figure(figsize=(11.67,8.75),dpi=120,facecolor=BG)
title(fig,'같은 법 7에서도 첫 복귀는 다릅니다','Same modulus 7, different first returns to 1')
for x,a in [(.02,2),(.51,3)]:
ax=fig.add_axes([x,.22,.47,.58]);path=cycles[a]
clock(ax,7,active=path[:-1])
for u,v in zip(path,path[1:]):multiply_arrow(ax,u,v,7)
p=point(1,7)
ax.add_patch(Circle(p,.10,fill=False,ec=ORANGE,lw=3))
label(ax,0,.15,f'×{a}',size=25,color=ORANGE)
label(ax,0,-.15,f'주기 {len(path)-1}',size=19,color=ORANGE)
ftext(fig,x+.235,.805,f'화살표 한 번: 현재 눈금 × {a}',size=18)
ftext(fig,x+.235,.185,' → '.join(map(str,path)),size=17,color=BLUE)
ftext(fig,.5,.115,'출발 눈금 1은 지수 0입니다. 화살표는 덧셈이 아니라 곱셈입니다.',size=18)
ftext(fig,.5,.060,'Each arrow multiplies the current residue; it is not a fixed angular step.',size=13,color=MUTED)
plt.show()
법 7의 같은 눈금판에서 1부터 두 배를 반복하면 1·2·4의 세 자리 순환, 세 배를 반복하면 1·3·2·6·4·5의 여섯 자리 순환이다. 화살표는 현재 값의 곱셈이며 일정 칸 덧셈이 아니다.
2배는 세 번, 3배는 여섯 번 만에 처음 1로 돌아옵니다. 2배도 0 아닌 여섯 나머지 전체를 재배열하지만, 1에서 출발한 이 경로만 따라가면 1·2·4만 방문합니다. 전체 목록을 한 번 재배열한다는 사실이 한 출발점에서 모든 눈금을 방문한다는 뜻은 아닌 것이지요. 그래도 여섯 번 곱한 뒤에는 둘 다 1입니다. 2배의 세 번짜리 경로는 두 번 반복되기 때문입니다. 이제 이 예에서 보인 ‘처음 돌아오는 횟수’와 ‘1이 되는 다른 지수’의 관계를 일반적으로 확인하겠습니다.
최소 지수 $d$가 있으면 $a^{d+j}\equiv a^j$이므로 그 이후의 나머지가 반복됩니다. 또한 $a^h\equiv1$인 지수 $h$는 $d$의 배수입니다. $h=qd+r$, $0\le r 따라서 법 $p$에서의 위수는 $p-1$을 나눕니다. 이 결론은 보장 지수와 최소 지수가 아무 관계도 없다는 뜻이 아니라, 최소 지수가 보장 지수의 약수라는 뜻입니다. 나눗셈으로 남은 $r$이 0이면 $a^r=a^0=1$이므로 문제가 없습니다. 반면 $1\le r 계산에 바로 쓸 결과를 적으면 다음과 같습니다. 아래에서 $E$는 구하려는 0 이상의 지수이고, $q,r$는 이를 $p-1$로 나눈 몫과 나머지입니다. 계산에서는 굳이 최소 지수까지 찾지 않아도 됩니다. $3^{100}$을 구할 때 5를 써도 되고 10을 써도 됩니다. 페르마의 소정리의 장점은 밑마다 처음 반복되는 곳을 찾아보지 않아도 사용할 지수를 제공한다는 데 있습니다. 법이 소수가 아니면 $n-1$이라는 지수를 그대로 쓸 수 없습니다. 예를 들어 법 8에서 3은 8과 서로소이지만 $3^7$의 나머지가 1이 아니므로 “서로소이면 항상 $a^{n-1}\equiv1$”이라는 일반화는 틀립니다. 합성수에서는 0 아닌 나머지 전체에 역원이 있다는 보장도 사라집니다. 8에서는 2와 4를 곱해도 0이 됩니다. 앞의 증명을 법 8에서 그대로 따라가면 정확히 어디서 막힐까요? 뜻밖에도 1부터 7까지에 3을 곱한 나머지는 3·6·1·4·7·2·5입니다. 원래 목록이 빠짐없이 돌아옵니다. 3과 8은 서로소여서 3을 곱하는 일 자체는 되돌릴 수 있기 때문입니다. 하지만 그 목록을 전부 곱한 수는 어떨까요? 잠시 그 곱을 $P$라고 쓰면 입니다. 재배열에서 $3^7P\equiv P\pmod8$까지는 얻어도, 양쪽은 이미 0과 합동입니다. 곱 $P$에는 법 8에서 역원이 없으므로 이를 취소해 $3^7\equiv1$을 얻을 수 없습니다. 3의 역원이 있다는 사실과, 목록 전체를 곱한 수의 역원이 있다는 사실은 별개입니다. 앞의 소수 법 증명에서 긴 곱의 약분 조건을 따로 확인한 이유가 이 예에서 드러납니다. 반대로 어떤 $a,n$에 대해 $a^{n-1}\equiv1\pmod n$이 맞으면 $n$은 소수일까요? 이것도 아닙니다. 합성수 을 보겠습니다. $2^{10}=1024=3\times341+1$이므로 341은 합성수인데 밑 2에서는 소수일 때 기대한 관계를 통과합니다. 이처럼 특정 밑에서 검사를 통과하는 합성수를 그 밑에 대한 의사소수라고 부릅니다. 이 예는 직접 계산으로 검증했으므로 소수 목록을 믿어야 하는 반례도 아닙니다. 논리의 방향을 분명히 적으면 다음과 같습니다. $n$이 소수이고 $n\nmid a$이면 검사를 통과합니다. 따라서 적합한 $a$에서 검사를 실패하면 $n$은 소수가 아닙니다. 그러나 통과했다는 사실만으로 소수라고 결론 낼 수는 없습니다. 필요조건을 만족한 것과 충분조건을 확보한 것은 다릅니다. 341의 두 정보는 동시에 참입니다. $341=11\times31$이므로 합성수이고, $2^{10}=3\times341+1$이므로 밑 2의 페르마 검사는 통과합니다. 합성수 341에서 2의 거듭제곱 나머지가 열 번째에 1로 돌아오는 그래프와 341=11×31의 인수분해를 나란히 보여준다. 밑 2 검사를 통과해도 소수라는 결론은 안 나온다. 이제 소수 판정과는 별개로, 이미 소수임을 아는 법에서 이 정리를 역원 계산에 써보겠습니다. 페르마의 소정리는 역원 계산에도 사용할 수 있습니다. $a^{p-1}\equiv1$을 $a\cdot a^{p-2}\equiv1$로 읽으면 $a^{p-2}$가 역원입니다. 다만 실제 손계산에서는 앞 편의 호제법이 더 간단할 수 있습니다. 같은 대상을 찾는 방법이 둘이라고 해서 언제나 계산량도 같은 것은 아닙니다. 역원으로 나누기를 대신하는 작은 계산도 해보겠습니다. 서로 다른 물건 10개에서 순서를 구별하지 않고 3개를 고르는 방법의 수를 $X$라고 하겠습니다. 순서까지 구별하면 첫째 물건은 10가지, 둘째는 남은 9가지, 셋째는 남은 8가지입니다. 같은 세 물건도 놓는 순서가 $3\times2\times1=6$가지이므로 $6X=10\times9\times8=720$입니다. 법 7에서 오른쪽의 나머지는 6이니 $6X\equiv6\pmod7$입니다. 6의 역원은 6이므로 양쪽에 곱하면 $X\equiv36\equiv1\pmod7$을 얻습니다. 보통 나눗셈으로 구한 $X=120$의 나머지도 1이지요. 여기서 법을 3으로 바꾸면 6의 역원이 없어 같은 약분을 할 수 없습니다. 경우의 수 자체가 없어지는 것이 아니라, 그 법에서 이 곱셈을 되돌릴 수 없다는 뜻입니다. 곱할 수를 바꾸며 목적지가 겹치는지 살펴보세요. 소수인 법의 배수를 넣으면 모든 목적지가 0이 됩니다. 조건을 만족하는 경우에는 보장된 지수와 실제로 처음 1로 돌아오는 지수도 비교할 수 있습니다. 각 나머지에 같은 수를 곱했을 때 목적지가 겹치는지 확인합니다. 페르마의 소정리의 지수는 나머지의 개수에서 나왔습니다. 소수 법에서 0 아닌 나머지에 배수가 아닌 수를 곱하면, 0이 나오지 않고 충돌도 없으며 입력과 출력의 개수가 같아서 전체 목록이 재배열됩니다. 그 목록을 모두 곱하고 역원이 있는 곱을 약분하면 $a^{p-1}\equiv1$을 얻습니다. 정리는 최소 주기를 약속하지 않으며, 검사를 통과했다고 소수인 것도 아닙니다. 이 두 경계를 함께 기억하면 큰 거듭제곱을 계산할 때 정리가 말하는 범위만 정확하게 사용할 수 있습니다. 합성수에서는 어떻게 해야 할까요? 법 8의 나머지 중 1·3·5·7은 모두 역원이 있습니다. 역원이 없는 나머지를 빼고 이들만 놓으면, 오늘의 재배열 증명을 다시 사용할 수 있을 것 같습니다. 다음 편의 오일러 정리는 이 생각을 일반화합니다. 더 읽기: Gowers의 거듭제곱 주기에서 정리를 찾아가는 설명, Conrad의 나머지 목록과 곱을 이용한 증명, 역원을 이용한 계산 응용.8. 합성수에서 실패하는 곳과 역이 성립하지 않는 이유
그림을 만든 Python 코드
from pathlib import Path as _bfPath
from matplotlib.font_manager import FontProperties as _bfFontProperties
from matplotlib.text import Text as _bfText
from matplotlib.ticker import Formatter as _bfFormatter
from io import BytesIO as _bfBytesIO
from IPython.display import display as _bfDisplay, Image as _bfImage
class _BilingualFormatter(_bfFormatter):
def __init__(self, base, labels):
self.base, self.labels = base, labels
def set_axis(self, axis):
super().set_axis(axis)
self.base.set_axis(axis)
def set_locs(self, locs):
super().set_locs(locs)
self.base.set_locs(locs)
def __call__(self, value, pos=None):
raw=self.base(value,pos)
translated=self.labels.get(raw)
return translated+'\n'+raw if translated else raw
def get_offset(self):
return self.base.get_offset()
def _apply_bilingual_figure(_bfFigure, _bfLabels, _bfOriginalPixels):
if getattr(_bfFigure, '_bilingual_complete', False):
return
_bfFont = _bfPath('C:/Windows/Fonts/malgun.ttf')
if not _bfFont.is_file():
raise RuntimeError('Korean/English figures require the Malgun Gothic font.')
_bfFamily = _bfFontProperties(fname=str(_bfFont)).get_name()
# Keep the delivered original's aspect ratio. A bilingual label must not
# stretch the chart, its grid cells, cards or geometry vertically.
_bfFigure.set_size_inches(_bfOriginalPixels[0] / 80,
_bfOriginalPixels[1] / 80, forward=True)
_bfFigure._bilingual_original_pixels = tuple(_bfOriginalPixels)
_bfFigure.canvas.draw()
for _bfAxes in _bfFigure.axes:
for _bfAxis in (_bfAxes.xaxis,_bfAxes.yaxis):
if any(_bfTick.get_text() in _bfLabels for _bfTick in _bfAxis.get_majorticklabels()):
_bfAxis.set_major_formatter(_BilingualFormatter(_bfAxis.get_major_formatter(),_bfLabels))
_bfTexts = list(_bfFigure.findobj(_bfText))
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
_bfTexts.extend(_bfCell.get_text() for _bfCell in _bfTable.get_celld().values())
_bfSeen = set()
_bfChanged = []
for _bfItem in _bfTexts:
if id(_bfItem) in _bfSeen:
continue
_bfSeen.add(id(_bfItem))
_bfOriginal = _bfItem.get_text()
_bfKorean = _bfLabels.get(_bfOriginal)
if _bfKorean:
_bfItem.set_text(_bfKorean + '\n' + _bfOriginal)
_bfItem.set_linespacing(1.05)
_bfChanged.append((_bfKorean, _bfOriginal))
_bfProperties = _bfItem.get_fontproperties().copy()
_bfProperties.set_file(None)
_bfProperties.set_family([_bfFamily, 'DejaVu Sans'])
_bfItem.set_fontproperties(_bfProperties)
assert _bfChanged, 'Every figure must contain meaningful Korean/English labels.'
# Bilingual column headers must stay inside their original table cells.
_bfFigure.canvas.draw()
_bfRenderer = _bfFigure.canvas.get_renderer()
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
for _bfCell in _bfTable.get_celld().values():
_bfCellText = _bfCell.get_text()
_bfBox = _bfCellText.get_window_extent(_bfRenderer)
_bfCellBox = _bfCell.get_window_extent(_bfRenderer)
if _bfBox.width and _bfBox.height:
_bfFit = min(1, .92*_bfCellBox.width/_bfBox.width,
.88*_bfCellBox.height/_bfBox.height)
_bfCellText.set_fontsize(_bfCellText.get_fontsize()*_bfFit)
if _bfAxes.get_title():
_bfAxes.set_title(_bfAxes.get_title(), pad=6)
_bfFigure.canvas.draw()
# Keep subplot headings clear of the shared two-line title, moving the
# subplot boundary only as much as the actual rendered text requires.
if _bfFigure._suptitle is not None:
_bfTopTitle = _bfFigure._suptitle.get_window_extent(_bfRenderer)
for _bfAxes in _bfFigure.axes:
if not _bfAxes.get_title():
continue
_bfHeading = _bfAxes.title.get_window_extent(_bfRenderer)
_bfGap = _bfHeading.y1 - (_bfTopTitle.y0 - 9)
if _bfGap > 0:
_bfPosition = _bfAxes.get_position(original=True)
_bfAxes.set_position([_bfPosition.x0, _bfPosition.y0,
_bfPosition.width, _bfPosition.height - _bfGap/_bfFigure.bbox.height])
_bfFigure._bilingual_labels = _bfChanged
_bfFigure._bilingual_complete = True
def _display_bilingual_figure(_bfFigure):
# A fixed full canvas avoids notebook's automatic tight crop changing the
# aspect ratio after titles and labels become bilingual. This is a fresh
# Matplotlib rendering, at exactly twice the original pixel dimensions.
global _bfDisplayedFigure
_bfDisplayedFigure = _bfFigure
_bfBuffer = _bfBytesIO()
_bfFigure.savefig(_bfBuffer, format='png', dpi=160, bbox_inches=None,
pad_inches=0, facecolor=_bfFigure.get_facecolor())
_bfDisplay(_bfImage(data=_bfBuffer.getvalue()))
plt.close(_bfFigure)
_bfLabels = {'Dividend': '피제수', 'Divisor': '제수', 'Quotient': '몫', 'Remainder': '나머지', '3r mod 7': '3r의 법 7 나머지', 'then x5': '그다음 5를 곱하기', 'k, gcd(k,12)=1': '12와 서로소인 k', '5k mod 12': '5k의 법 12 나머지', 'Modulus': '법', 'Other factors': '나머지 법들의 곱', 'Inverse': '역원', 'Unit part': '단위 부품', 'Target': '목표 나머지', 'Contribution': '기여값', 'Possible square residues': '가능한 제곱 나머지', 'Squares of 0, 1, ... , m-1': '0·1·…·(m−1)의 제곱 나머지', 'PASS': '통과', 'IMPOSSIBLE': '불가능', 'mod 2': '법 2', 'mod 3': '법 3', 'mod 4': '법 4', 'mod 5': '법 5', 'mod 7': '법 7', 'mod 8': '법 8', 'mod 9': '법 9', 'mod 11': '법 11', 'mod 12': '법 12', 'mod 105': '법 105', '2^10 leaves 1': '2^10의 나머지는 1', 'Exponent k': '지수 k', '2^k mod 341': '2^k를 341로 나눈 나머지', 'The remainder returns to 1': '나머지가 1로 돌아온다', '341 = 11 x 31: composite': '341 = 11 × 31: 합성수', '2^340 = (2^10)^34\nThe test passes with remainder 1.': '2^340 = (2^10)^34\n나머지 1로 검사를 통과한다.', 'A passed Fermat test is not a proof of primality': '페르마 검사의 통과는 소수의 증명이 아니다', 'Primality implies the Fermat congruence for an allowed base; the reverse implication is false.': '소수이면 허용된 밑에서 페르마의 합동식이 성립하지만, 역은 성립하지 않는다.'}
_bfOriginalPixels = [1324, 689]
from math import gcd, isqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib.patches import Rectangle, Circle, FancyBboxPatch, FancyArrowPatch
BG = "#101827"
PANEL = "#1d2b40"
INK = "#edf3fc"
MUTED = "#c0cede"
BLUE = "#8fdcff"
GREEN = "#91e0b2"
GOLD = "#ffd18c"
RED = "#ffaaaa"
LINE = "#667a96"
def canvas(rows=1, cols=1, size=(13.6, 6.8), title=""):
fig, axes = plt.subplots(rows, cols, figsize=size, facecolor=BG,
squeeze=False)
axes = axes.ravel().tolist()
for ax in axes:
ax.set_facecolor(BG)
ax.tick_params(colors=INK, labelsize=12)
for spine in ax.spines.values():
spine.set_color(LINE)
fig.suptitle(title, fontsize=18, color=INK, y=.98)
fig.subplots_adjust(left=.07, right=.97, top=.86, bottom=.13,
wspace=.34, hspace=.48)
return fig, axes
def off(ax):
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.axis("off")
def text(ax, x, y, value, color=INK, size=12, **kwargs):
defaults = dict(ha="center", va="center", fontsize=size, color=color,
transform=ax.transAxes, linespacing=1.35)
defaults.update(kwargs)
return ax.text(x, y, value, **defaults)
def card(ax, x, y, width, height, value, edge=LINE, color=INK, size=14):
ax.add_patch(FancyBboxPatch((x, y), width, height,
boxstyle="round,pad=0.012", transform=ax.transAxes,
facecolor=PANEL, edgecolor=edge, linewidth=1.4))
text(ax, x+width/2, y+height/2, value, color=color, size=size)
def arrow(ax, start, end, color=BLUE):
ax.add_patch(FancyArrowPatch(start, end, transform=ax.transAxes,
arrowstyle="-|>", mutation_scale=18,
color=color, linewidth=1.7))
def caption(fig, value):
fig.text(.5, .035, value, ha="center", va="center",
color=MUTED, fontsize=12)
fig,axes=canvas(1,2,size=(13.8,7.0),title="A passed Fermat test is not a proof of primality")
ax=axes[0]
exponents=list(range(1,11))
residues=[pow(2,k,341) for k in exponents]
ax.plot(exponents,residues,"o-",color=BLUE,markersize=7)
ax.scatter([10],[1],color=GREEN,s=100,zorder=4)
ax.annotate("2^10 leaves 1",xy=(10,1),xytext=(5.0,80),
color=GREEN,fontsize=13,arrowprops=dict(arrowstyle="->",color=GREEN))
ax.set_xticks(exponents)
ax.set_ylim(-8,295)
ax.set_xlabel("Exponent k",color=INK,fontsize=12)
ax.set_ylabel("2^k mod 341",color=INK,fontsize=12)
ax.set_title("The remainder returns to 1",color=INK,fontsize=15,pad=15)
ax.grid(alpha=.2,color=LINE)
ax=axes[1]
off(ax)
card(ax,.04,.73,.92,.14,"341 = 11 x 31: composite",edge=RED,color=RED,size=18)
card(ax,.04,.46,.92,.16,"2^10 = 1024 = 3 x 341 + 1",edge=BLUE,size=16)
arrow(ax,(.5,.43),(.5,.33))
card(ax,.04,.12,.92,.17,"2^340 = (2^10)^34\nThe test passes with remainder 1.",edge=GREEN,size=16)
caption(fig,"Primality implies the Fermat congruence for an allowed base; the reverse implication is false.")
assert 341==11*31 and 2**10==3*341+1 and pow(2,340,341)==1
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
9. 직접 바꾸어 확인해보기
나머지 순열 실험
10. 마무리