최대공약수의 비밀: 나눗셈의 끝에서 시작되는 역주행
《나머지에서 시작하는 정수론》 · 3/8편 · 최대공약수의 비밀
0. 서론: 학교에서 배운 최대공약수부터
최대공약수라고 하면 어떤 계산이 먼저 떠오르시나요? 두 수를 나란히 적고, 공통으로 나누어떨어지는 수를 왼쪽에 쓰며 아래로 내려가던 풀이가 익숙할 겁니다. 왼쪽에 적은 수만 직선으로 곱하면 최대공약수, 마지막 줄의 두 수까지 ㄴ자로 곱하면 최소공배수가 되던 그 계산입니다. 이번 편은 그 풀이에서 출발하겠습니다. 그리고 교육과정에서도 바로 뒤에 나오는 소인수분해로 같은 답을 얻는 이유를 짚은 뒤, 두 수의 소인수를 모두 찾지 않고 최대공약수를 구하는 유클리드 호제법으로 넘어가겠습니다.
0.1. 왼쪽만 곱하면 최대공약수, ㄴ자로 곱하면 최소공배수
12와 18을 나란히 적어봅시다. 두 수를 모두 나누어떨어지게 하는 수를 공약수, 그중 가장 큰 수를 최대공약수라고 합니다. 두 수의 양의 배수에 공통으로 들어 있는 수는 공배수, 그중 가장 작은 수는 최소공배수입니다. 먼저 12와 18을 공통 약수 2로 나누면 6과 9가 됩니다. 다시 두 수를 공통 약수 3으로 나누면 2와 3이 됩니다.
| 2 | 12 | 18 |
| 3 | 6 | 9 |
| 2 | 3 |
마지막의 2와 3에는 1보다 큰 공약수가 없으므로 여기서 멈춥니다. 이처럼 최대공약수가 1인 두 수를 서로소라고 부릅니다. 여기서는 작은 소수 2, 3을 차례로 썼습니다. 매번 왼쪽에 적는 수는 그 줄의 두 수를 모두 나누어떨어지게 하는 1보다 큰 공약수여야 합니다. 더 이상 그런 공약수가 없으면 멈추며, 마지막 두 수가 각각 소수가 될 때까지 나눌 필요는 없습니다. 왼쪽에 모은 2와 3은 두 수에서 함께 꺼낸 곱셈 재료입니다. 그래서 왼쪽만 곱한 $2\times3=6$이 최대공약수입니다. 최소공배수는 그 공통 부분에 마지막 줄의 2와 3까지 이어 곱합니다.
ㄴ자로 곱하는 이유를 원래 두 수에서 확인해보겠습니다. 12는 공통 부분 6에 2를 곱한 수이고, 18은 같은 6에 3을 곱한 수입니다. 두 수의 배수가 되려면 공통 부분 6에 남은 재료 2와 3을 모두 갖추어야 합니다. 남은 2와 3은 서로소이므로 두 재료를 더 겹쳐 줄일 수 없습니다. 따라서 공통 부분은 한 번만 쓰고, 남은 두 몫을 곱한 $6\times2\times3=36$이 가장 작은 공배수입니다.
0.2. 소인수분해는 그 곱셈 재료를 펼쳐놓는 방법입니다
이번에는 12와 18을 각각 소수의 곱으로 써봅시다. 소수는 1보다 크고 양의 약수가 1과 자기 자신뿐인 자연수입니다. 자연수를 이런 소수들의 곱으로 나타내는 것이 소인수분해입니다.
12에는 2가 두 개, 3이 한 개 들어 있습니다. 18에는 2가 한 개, 3이 두 개 들어 있습니다. 최대공약수를 만들 때는 양쪽에 공통으로 들어 있는 만큼만 가져갑니다. 2는 한 개, 3도 한 개를 쓸 수 있으므로 $2\times3=6$입니다. 최소공배수는 12와 18 어느 쪽도 빠짐없이 만들 수 있어야 합니다. 따라서 2는 두 개, 3도 두 개를 갖추어 $2^2\times3^2=36$으로 만듭니다. 같은 소인수를 양쪽에서 중복해 전부 곱하는 것이 아니라, 소인수마다 더 많이 들어 있는 쪽의 개수를 택합니다.
| 소인수 | 12에 든 개수 | 18에 든 개수 | 최대공약수에 쓰는 개수 | 최소공배수에 쓰는 개수 |
|---|---|---|---|---|
| 2 | 2개 | 1개 | 적은 쪽인 1개 | 많은 쪽인 2개 |
| 3 | 1개 | 2개 | 적은 쪽인 1개 | 많은 쪽인 2개 |
앞의 나눗셈에서 왼쪽에 모았던 $2\times3$이 바로 공통 소인수 부분입니다. 마지막 줄에 남았던 2와 3은 공통 부분을 꺼내고 남은 재료입니다. 두 풀이는 같은 곱셈 재료를 나눗셈 표로 모아 보느냐, 소수의 곱으로 펼쳐 보느냐의 차이입니다.
0.3. 공통 약수가 바로 보이지 않으면 어떻게 할까요?
이제 같은 질문을 252와 105에 해봅시다. 소인수분해를 하면 다음과 같습니다.
공통으로 쓸 수 있는 소인수는 3 한 개와 7 한 개이므로 최대공약수는 $3\times7=21$입니다. 하지만 수가 커져서 공통 약수나 소인수가 바로 보이지 않는다면 어떻게 할까요?
유클리드 호제법은 이때 쓸 수 있는 방법입니다. 두 수를 공통 약수로 함께 나누던 계산에서, 큰 수를 작은 수로 나누어 나머지를 구하는 계산으로 바꿉니다. 105가 252를 나누어떨어지게 할 필요는 없습니다. 나머지가 생기면 그 나머지를 다음 계산에 사용합니다.
이 세 줄로 얻는 최대공약수도 같은 21입니다. 새로운 계산에서 왜 몫 2가 나오는지, 앞 식의 105와 42가 왜 뒷 식의 앞자리를 맡는지 차례로 확인하겠습니다. 이 방법은 학교에서 배운 풀이와 같은 답을 구하면서도, 매번 찾아야 하는 것은 공통 소인수가 아니라 보통 나눗셈의 몫과 나머지입니다. 각 숫자의 역할을 고정해 나눗셈을 따라가고, 무엇이 보존되는지 양쪽 방향으로 확인하겠습니다. 그런 다음 계산을 거꾸로 올라가면 최대공약수가 원래 두 수의 정수 배를 더한 식으로 나타납니다. 이 식은 앞 편에서 남겨둔 질문, “10과 서로소인 수에서는 왜 배수 판정 계수를 찾을 수 있을까?”에 답합니다.
나눗셈 하나가 최대공약수, 합동식의 약분, 역원의 존재를 이어줍니다.
1. 몫 2는 252 안에 105가 몇 번 들어가는가에서 정해집니다
252와 105의 공약수를 찾으려 합니다. 다시 한 번 말해보자면, 공약수는 두 수를 모두 나머지 없이 나누는 양의 정수이며, 그중 가장 큰 것이 최대공약수입니다. 기호로 $\gcd(252,105)$라고 씁니다. 먼저 252를 105로 나눕니다. 105를 두 번 더하면 210이고 세 번 더하면 315입니다.
따라서 105는 252 안에 최대 두 번 들어갑니다. 이 2가 몫이고, 남은 $252-210=42$가 나머지입니다.
2는 최대공약수를 짐작해서 고른 특별한 수가 아닙니다. 보통의 정수 나눗셈이 정한 몫입니다. 나머지를 0 이상이고 제수(나누는 수)보다 작게 만들도록 고른 것입니다. 물론 $252=105\times1+147$도 등식으로는 맞습니다. 하지만 147에는 105가 한 번 더 들어가므로 보통의 나머지 조건을 만족하지 않습니다. 두 번 뺄 것을 한 번의 나눗셈으로 묶어 계산을 줄인다고 이해하면 됩니다.
| 역할 | 값 | 뜻 |
|---|---|---|
| 나누어지는 수, 피제수 | 252 | 처음에 가진 수 |
| 나누는 수, 제수 | 105 | 몇 번 들어가는지 검사하는 수 |
| 몫 | 2 | 완전히 들어간 횟수 |
| 나머지 | 42 | 빼고 남은 수 |
이 네 역할을 분명히 해두면 다음 줄로 이동할 때 어떤 값이 무엇을 맡는지 읽을 수 있습니다. 만약 105를 20으로 나누는 줄이라면 $20\times5=100\le105<120=20\times6$이므로 몫은 5이고 나머지는 5입니다. 매 줄마다 지금의 피제수 안에 지금의 제수가 최대 몇 번 들어가는지를 다시 정합니다. 이제 숫자 대신 글자를 붙이면 $A$는 지금 나누어지는 수, $B$는 지금 나누는 양의 수, $q$는 몫, $r$은 나머지입니다. 나눗셈 한 줄에는 다음 두 정보가 함께 들어 있습니다.
첫 등식은 수량이 맞는다는 정보이고, 뒤의 부등식은 더 이상 $B$를 한 번 빼낼 수 없다는 정보입니다. 호제법이 끝나는 이유에는 이 두 번째 정보가 꼭 필요합니다.
2. 공약수 목록이 양쪽 방향으로 보존됩니다
이제 왜 252와 105 대신 105와 42를 보아도 되는지 증명하겠습니다.
공약수 7에서 $252=7\times36$, $105=7\times15$이므로 $42=7(36-2\times15)=7\times6$입니다. 7을 묶어낼 수 있기 때문에 뺀 결과에도 7이 남습니다.
따라서 원래 두 수의 공약수는 105와 42의 공약수입니다.
일반적인 문자로 다시 한 번 증명해 보겠습니다.
먼저 어떤 양의 정수 $d$가 252와 105를 모두 나눈다고 합시다. 그러면 105의 두 배도 나누므로
$$ d\mid252,\qquad d\mid105,\qquad d\mid2\times105 $$
로 쓸 수 있습니다. 이는 252와 105를 각각 $d$로 나누었을 때 나머지가 0이라는 뜻입니다.
따라서 어떤 정수 $u,v$가 존재할 때, 위 관계는 등식으로
라고 표현할 수 있습니다.
이제 우리가 처음 작성 했던 식
$$ 252=105\times2+42 $$
에서, 이항을 조금 해주면
이 됩니다.
이 식에서 위의 등식 관계를 대입해주면,
$$ 252-2\times105=du-2dv=d(u-2v). $$
이렇게 정리가 됩니다. $u-2v$는 정수이므로 오른쪽은 $d$의 정수 배입니다.
즉, 계산 결과가 무조건 $d$로 나누어 떨어지게 되는 것이죠. 같은 수의 배수끼리는 더해도, 빼도 그 수의 배수입니다.
따라서
$$ 252-2\times105=42 $$
이 식에서 양변은 $d$로 나누어 떨어지고, 그렇기 때문에 원래 두 수의 모든 공약수가 105와 42도 나눈다는 것을 확인했습니다.
그러나 항상 증명에서는 양방향이 중요했었죠.
지금까지는 앞 두 수로 다음 수가 나오는 것을 확인해 보았습니다.
이번엔 반대로 새로 등장한 공약수가 원래 수에서는 공약수가 아닐 가능성도 배제해야 합니다.
다시 말해 뒷 두 수로 앞 수가 나오는 것을 확인해 보겠습니다.
이쪽도 같은 방식으로 확인할 수 있습니다.
$105=dv$, $42=dw$라고 쓰면 $252=2dv+dw=d(2v+w)$입니다.
여기서 $252=d(2v+w)$이고, $2v+w$는 정수이므로, 252는 $d$로 나누어 떨어집니다.
앞에서는 $252$에서 $105$의 두 배를 빼서 42를 얻었고, 이번에는 $105$의 두 배와 42를 더해서 252를 복원했습니다. 두 계산은 반대 방향의 주장에 각각 쓰입니다.
그런데 한 방향만으로 최대공약수가 같다고 하면 왜 위험할까요?
예를 들어 6과 10의 공약수는 1·2인데, 둘 다 30의 약수이기도 합니다. 그렇다고 30의 모든 약수가 6과 10의 공약수는 아닙니다.
원래 공약수를 잃지 않았다는 확인과, 새로운 공약수가 끼어들지 않았다는 확인이 함께 있어야 목록이 같아집니다.
결국 두 쌍은 공약수의 전체 목록이 같습니다. 큰 공약수 하나를 우연히 공유하는 정도가 아닙니다. 전체 목록이 같으니 그중 가장 큰 수도 같습니다.
이것이 두번째 식에서 105가 앞에 오고 42가 제수가 되는 이유입니다. 더 작은 두 수로 같은 문제를 다시 풀게 된 것입니다. 두 쌍의 공약수를 실제로 적으면 모두 $1,3,7,21$입니다. 아래 그림의 두 방향은 각각 $42=252-2\times105$와 $252=2\times105+42$를 사용합니다.
그림을 만든 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', '252 and 105': '252와 105', '105 and 42': '105와 42', 'Old': '변환 전', 'New': '변환 후', 'Common divisors in both rows: 1, 3, 7, 21. The largest is 21.': '두 행의 공약수: 1·3·7·21. 가장 큰 수는 21이다.', 'Both directions preserve the entire common-divisor list': '양방향으로 공약수 전체가 보존된다', 'The reverse arrow matters: the new pair cannot introduce an extra common divisor.': '역방향도 필요하다. 새 수의 쌍에서 공약수가 추가되어서는 안 된다.'}
_bfOriginalPixels = [1334, 670]
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(size=(14.6,6.8), title="Both directions preserve the entire common-divisor list")
ax=axes[0]
off(ax)
card(ax,.08,.71,.32,.15,"252 and 105",edge=BLUE,size=18)
card(ax,.60,.71,.32,.15,"105 and 42",edge=GREEN,size=18)
arrow(ax,(.42,.81),(.57,.81),color=BLUE)
arrow(ax,(.58,.74),(.43,.74),color=GREEN)
text(ax,.5,.95,"42 = 252 - 2 x 105",color=BLUE,size=14)
text(ax,.5,.62,"252 = 2 x 105 + 42",color=GREEN,size=14)
for i,d in enumerate(range(1,22)):
x=.08+i*.042
text(ax,x,.48,str(d),size=12)
first=(252%d==0 and 105%d==0)
second=(105%d==0 and 42%d==0)
for y,yes in [(.36,first),(.24,second)]:
ax.add_patch(Circle((x,y),.015,transform=ax.transAxes,
color=GREEN if yes else "#35445b"))
assert first==second
text(ax,.035,.36,"Old",ha="right",size=12)
text(ax,.035,.24,"New",ha="right",size=12)
text(ax,.5,.08,"Common divisors in both rows: 1, 3, 7, 21. The largest is 21.",color=GREEN,size=15)
caption(fig,"The reverse arrow matters: the new pair cannot introduce an extra common divisor.")
assert gcd(252,105)==gcd(105,42)==21
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
252·105와 105·42의 공약수 목록이 양방향으로 같은 이유를 뺄셈과 복원 덧셈으로 연결한다. 두 행에서 공약수 1·3·7·21이 정확히 일치한다.
화살표 하나만 있으면 한쪽 목록이 다른 쪽에 포함된다는 것만 알 수 있습니다. 두 방향을 모두 확인했기 때문에 목록 자체와 최대공약수가 함께 보존됩니다. 일반식도 같은 구조입니다. $A=Bq+r$이면
이므로 $(A,B)$의 공약수와 $(B,r)$의 공약수가 같습니다. 따라서
앞 편의 배수 판정에서는 배수 여부를 보존했습니다. 여기서는 두 수의 공약수 목록을 보존합니다. 매번 무엇이 남는지를 명확히 알 때 수를 바꾸어도 되는지가 판명됩니다.
3. 제수가 다음 피제수가 되고, 나머지가 다음 제수가 됩니다
이제 105와 42의 최대공약수를 구하면 됩니다. 105를 42로 나누면 42가 두 번 들어가고 21이 남습니다.
이번 줄의 피제수는 105이고 제수는 42입니다. 첫 줄의 제수 105가 피제수로, 첫 줄의 나머지 42가 제수로 역할을 바꾸었습니다. 같은 원리에 따라 이제 $(42,21)$을 검사합니다.
전체 이동을 표로 보면 다음과 같습니다.
| 단계 | 피제수 | 제수 | 몫 | 나머지 | 다음에 검사할 쌍 |
|---|---|---|---|---|---|
| 1 | 252 | 105 | 2 | 42 | $(105,42)$ |
| 2 | 105 | 42 | 2 | 21 | $(42,21)$ |
| 3 | 42 | 21 | 2 | 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', 'Next row: old divisor -> dividend; old remainder -> divisor': '다음 행: 이전 제수 → 피제수, 이전 나머지 → 제수', 'Euclid changes the roles of the numbers, not their common divisors': '유클리드 알고리즘은 수의 역할을 바꾸고 공약수는 보존한다'}
_bfOriginalPixels = [1055, 574]
from math import gcd
import matplotlib.pyplot as plt
steps=[]
a,b=252,105
while b:
q,r=divmod(a,b); steps.append((a,b,q,r)); a,b=b,r
assert steps==[(252,105,2,42),(105,42,2,21),(42,21,2,0)]
fig,ax=plt.subplots(figsize=(11.5,5.9),facecolor="#0d1117"); ax.axis("off")
cols=["Dividend", "Divisor", "Quotient", "Remainder"]
table=ax.table(cellText=steps,colLabels=cols,loc="center",cellLoc="center",colColours=["#173f50"]*4)
table.auto_set_font_size(False); table.set_fontsize(20); table.scale(1,2.8)
for (row,col),cell in table.get_celld().items():
cell.set_edgecolor("#526276"); cell.set_text_props(color="#e6edf3")
if row: cell.set_facecolor("#1c2534" if col in (0,2) else "#214737")
ax.text(.5,.08,"Next row: old divisor -> dividend; old remainder -> divisor",ha="center",color="#91e0b2",fontsize=13,transform=ax.transAxes)
ax.text(.5,.94,"252 = 105 x 2 + 42",ha="center",color="#ffcf85",fontsize=20,transform=ax.transAxes)
fig.suptitle("Euclid changes the roles of the numbers, not their common divisors",color="#e6edf3",fontsize=16)
fig.subplots_adjust(left=.05,right=.95,top=.88,bottom=.04)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
assert gcd(252,105)==gcd(105,42)==gcd(42,21)==21
print("Final nonzero remainder: 21. The final zero is the stopping signal.")
252와 105의 호제법 표. 다음 줄의 피제수는 이전 제수, 다음 제수는 이전 나머지가 된다. 마지막 0이 아닌 나머지는 21이다.
Final nonzero remainder: 21. The final zero is the stopping signal.
마지막 나머지가 0이면 계산을 끝냅니다. 0으로 나누는 다음 줄을 만들지는 않습니다. 42가 21의 배수라는 사실을 얻었으므로 42와 21의 최대공약수는 21입니다. 공약수 목록을 보존하며 내려왔으므로 원래 쌍의 최대공약수도 21입니다.
왜 0이 아니라 마지막으로 0이 아니었던 21일까요? 0은 양의 공약수 후보가 아니며, 마지막 줄은 “이제 21로 정확히 나누어진다”는 신호입니다. 어떤 공약수든 21을 나누어야 하고, 21 자체가 두 수를 나누므로 21이 가장 큽니다. 마지막 쌍 $(42,21)$에서 공약수가 될 수 있는 수는 반드시 21의 양의 약수입니다. 따라서 21보다 클 수 없습니다. 한편 21은 21 자체를 나누고, $42=2\times21$도 나눕니다. 즉 “21 이하밖에 없다”는 상한과 “21이 실제로 된다”는 확인이 함께 있으므로 최대값이 21입니다. 이를 $(21,0)$이라는 쌍으로 표현하기도 합니다. 모든 양의 정수는 0을 나눕니다. $0=d\times0$이기 때문입니다. 그래서 21과 0의 공약수는 21의 양의 약수 전체이고, 최대공약수는 역시 21입니다. 다만 이 표현은 공약수에 관한 설명이지 0으로 나눗셈을 하라는 지시는 아닙니다. 이 절차는 반드시 끝납니다. 나머지는 항상 직전 제수보다 작은 0 이상의 정수입니다. 105, 42, 21처럼 양의 제수가 계속 엄격히 작아지면서 끝없이 이어질 수는 없습니다. 결국 나머지 0이 나옵니다. 이 방법을 유클리드 호제법이라고 부릅니다.
이제 드디어 요상한 이름인 ‘호제법’이라는 이름을 완전히 깨달을 수 있습니다. 유클리드 호제법의 ‘호제법’은 互除法(서로 호·나눌 제·법 법)입니다.
互(호): 서로
-
除(제): 나누다
-
法(법): 방법
즉, ‘서로 나누는 방법’이라는 뜻입니다. 감이 오시죠? 앞 단계의 제수(나누는 수)가 다음 단계의 피제수(나누어지는 수)가 되면서 나눗셈을 반복하기 때문에 호제법이라고 부른답니다. 그렇다면 영어로는 뭐라고 부를까요? Ho-Ge-Beob은 아닐테죠? 그냥 단순히 Euclidean algorithm이라고 불러요. 뜻을 알고보면 동양식 이름이 좀 더 ‘근본원리’를 담고있다는 느낌도 듭니다.
4. 계산을 거꾸로 올라가면 베주 항등식이 됩니다
21을 찾은 뒤 계산을 버리지 말고 거꾸로 읽어봅시다. 둘째 줄에서
입니다. 그런데 첫 줄에서 $42=252-2\times105$였습니다. 이 42를 위 식에 그대로 넣습니다.
괄호를 풀 때 $-2$가 $-2\times105$에도 곱해져 $+4\times105$가 된다는 점을 확인해보세요. 원래 두 수 105와 252의 정수 배를 더하여 최대공약수 21을 만들었습니다.
여기서 계수 $-2$와 5는 앞의 나눗셈을 거꾸로 대입하면서 구한 값입니다. 최대공약수만 알아냈을 때에는 보이지 않던 추가 정보입니다. 역대입의 목적은 42처럼 계산 중에 새로 생긴 수를 없애고, 출발했던 252와 105만 남기는 것입니다. 첫째 줄의 $105-2(252-2\times105)$에서 바깥의 $-2$를 괄호 안 두 항에 모두 곱하면 $-2\times252+4\times105$입니다. 원래 앞에 있던 $105$는 $1\times105$이므로, 마지막에 $1\times105+4\times105=5\times105$로 모입니다. 수치 검산도 해두겠습니다. $(-2)\times252+5\times105=-504+525=21$입니다. 음수 계수를 허용한 이유는 양의 배수를 더하는 것만으로 만들기 어려운 작은 수를, 두 배수의 차이로 만들기 위해서입니다. 이때 결과인 최대공약수는 양수여도 계수까지 양수일 필요는 없습니다.
일반적으로 양의 정수 $a,b$의 최대공약수가 $d$이면, 어떤 정수 $u,v$를 찾아
라고 쓸 수 있습니다. 이를 베주 항등식(Bézout identity)이라고 합니다. 이름보다 만드는 과정이 중요합니다. 호제법의 마지막 0 아닌 나머지부터 시작해서, 중간 나머지들을 이전 줄의 식으로 차례로 바꾸면 결국 처음의 $a,b$만 남습니다. 각 단계에서 정수 계수로 더하고 빼므로 마지막 계수도 정수입니다. 이 식에서 $a,b$는 처음 넣은 두 양의 정수이고, $d$는 그 최대공약수입니다. $u,v$는 계산으로 찾아낼 정수 계수입니다. 252와 105의 예에 맞추면 $a=252$, $b=105$, $d=21$, $u=-2$, $v=5$입니다. 글자가 다섯 개 나와도 서로 독립된 새 문제 다섯 개가 생긴 것은 아닙니다. 같은 계산에서 입력·결과·만드는 계수를 구분한 것입니다. 왜 이 되짚기가 처음 두 수까지 반드시 도달할까요? 바로 앞에서 구한 나머지 하나에는, 그 나머지를 만든 나눗셈 줄이 하나씩 있습니다. 예를 들어 21의 식에 있던 42를 첫 줄로 바꾸면 42라는 중간 수가 사라졌습니다. 더 긴 호제법에서도 가장 뒤에서 생긴 중간 수부터 없애면, 남아 있는 나머지들은 점점 앞줄에서 생긴 것들뿐이 됩니다. 나눗셈 줄이 유한하므로 이 과정도 끝납니다. 반대로 $a,b$의 정수 배를 더하면 언제나 $d$의 배수입니다. $d$가 $a$와 $b$를 모두 나누기 때문입니다. 베주 항등식은 가능한 값들 중 최대공약수 자체도 실제로 만들 수 있음을 보장합니다. 계수는 하나로 정해지지 않습니다. 위 식에서 $u=-2$, $v=5$가 답이지만, $u=3$, $v=-7$도 $252\times3+105\times(-7)=21$을 만족합니다. 지금 필요한 것은 모든 계수를 찾는 일이 아니라 하나를 확실하게 만드는 일입니다. 모든 정수해의 형태는 마지막 편에서 다루겠습니다. 이번에는 나머지의 크기뿐 아니라, 그 나머지가 처음 두 수의 몇 배씩으로 이루어졌는지도 따라가보겠습니다. 252와 105를 넣고 각 줄의 계수를 읽으면 마지막에 $21=-2\times252+5\times105$가 남습니다.
베주 계수 되짚기
각 나머지가 원래 두 수의 정수배 합인 계수를 한 단계씩 확인합니다.
중간 나머지의 이름이 없어져도 처음 두 수에 대한 계수는 계산 내내 이어집니다. 이 계수 기록이 다음 절에서 나머지 1을 만드는 수를 찾는 데 쓰입니다.
5. 7에 무엇을 곱해야 법 11에서 1이 될까요
이제 다음 합동식을 풀어봅시다.
뜻을 등식으로 풀면 “$7x$를 11로 나누었을 때 1이 남는다”입니다. 따라서 어떤 정수 $q$에 대해
갑자기 뺄셈 문제가 생긴 것이 아닙니다. 합동 관계를 “차이가 법의 배수”라는 정의로 다시 적고, $11q$를 왼쪽으로 옮긴 것입니다. 필요한 것은 7과 11의 정수 배를 더하거나 빼서 1을 만드는 방법입니다. 7과 11의 정수배를 더하거나 빼서 최대공약수를 찾는 것을 우리는 위에서 베주 항등식이라고 배웠습니다. 그리고 베주 항등식은 유클리드 호제법으로 부터 나오지요.
그렇다면 일단 유클리드 호제법을 실행해 보겠습니다.
최대공약수는 1입니다. 이제 역대입합니다. 이번에는 필요한 수가 1이므로 마지막으로 0이 아닌 줄 $4=3+1$에서 출발합니다. 먼저 양쪽에서 3을 빼서 $1=4-3$을 얻습니다. 이 식에는 중간 수 4와 3이 있으므로, 3을 $7-4$로, 그다음 4를 $11-7$로 바꾸어 7과 11만 남기겠습니다. 대입할 때는 바꾸어 넣은 식 전체를 괄호로 감싸야 앞의 뺄셈 부호가 빠지지 않습니다.
셋째 줄에서 $4-(7-4)=4-7+4=2\times4-7$입니다. 괄호 앞이 뺄셈이므로 괄호 안의 두 부호가 바뀝니다.
넷째 줄은 첫 나눗셈에서 얻은 $4=11-7$을 대입했습니다.
마지막 줄은 $2(11-7)-7=2\times11-2\times7-1\times7$에서 7의 계수 $-2-1=-3$을 모았습니다.
각 줄은 같은 수 1을 다른 모양으로 썼고, 마지막에는 출발했던 11과 7만 남았습니다.
다시 써보면
$$ -3\times7-(-2)\times11=1 $$
처음의 등식 $7x-11q=1$과 비교하면 $x=-3$, $q=-2$가 한 해입니다. 여기서 $x$와 $q$는 정수이므로 음수여도 괜찮습니다.
다만, 여기서 한 가지 걸리는 부분이 있습니다.
현재 위 식은 “$7x$를 11로 나누었을 때 1이 남는다”라는 것을 유클리드 호제법과 베주 항등식을 통해서 특정한 정수 계수를 찾아낸 형태입니다.
근데 여기서 x가 $-3$이면 음수 피제수를 나누는 상황이 됩니다. 못 할 것도 없긴 하지만, 그래도 느낌이 이상하죠.
그래서 우리는 이 $-3$을 양수로 바꿔볼 겁니다.
힌트는 '11로 나누었을 때' 입니다.
그렇다면 7을 11로 나누었을 때 나머지가 0이 되게 만드는 한 방법은 11을 곱해주는 걸 겁니다.
$ 7\times11 \equiv 0 \pmod {11} $ 이라고 쓸 수 있을 겁니다.
그리고 이 11은 분해해보면 $ 8+3 = 11 \Leftrightarrow 8 - (-3) = 11 $ 이죠?
다시 써보면
$ 7\times8-7\times(-3)=7\times11 $이고
현재 $ 7\times11 $은 나머지가 0임을 알 수 있으므로,
뺄셈으로 연결된 $7\times8 $과 $ 7\times(-3) $의 나머지는 무조건 같아야 함을 알 수 있습니다.
즉, $x$는 $-3$도 되고, 나누는 수인 11을 더해서 8도 됩니다. 일반적으로 써보면 $ x = -3 + 11t $죠. $t$는 임의의 정수입니다.
따라서 보기 좋게 $x$는 보기 편한 8로 정하도록 하겠습니다.
(여기서 일반적으로 확장해서 $x$는 두 수를 뺐을 때 '나누는 수'와 같다면 나머지는 항상 같습니다)
그렇다면 식을 정리했을때,
$$ 7 \times 8 - 11 \times 5 = 1 $$
이 되고, 이것을 “$7x$를 11로 나누었을 때 1이 남는다”로 다시 바꿔보면
$$ 7 \times 8 \equiv1\pmod {11}. $$
가 되겠네요.
여기서 어떤 수와 곱해 법 $n$에서 1이 되는 수를 모듈러 역원(나머지 연산에서 곱셈의 역원)이라고 합니다.
따라서 8은 법 11에서 7의 모듈러 역원입니다.
그림을 만든 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', 'Each substitution uses an earlier remainder equation.': '매 역대입은 앞서 얻은 나머지 식을 사용한다.', 'Inverse of 7 modulo 11: -3 ≡ 8 (mod 11)': '법 11에서 7의 역원: −3 ≡ 8 (mod 11)', 'Back substitution turns a gcd of 1 into an inverse': '역대입으로 최대공약수 1에서 역원을 얻는다'}
_bfOriginalPixels = [1101, 609]
from math import gcd
import matplotlib.pyplot as plt
rows=[("42", "1 x 252 - 2 x 105",1,-2), ("21", "105 - 2 x 42",-2,5), ("1", "-3 x 7 + 2 x 11",-3,2)]
fig,axes=plt.subplots(2,1,figsize=(11.5,6.4),facecolor="#0d1117")
for ax in axes: ax.axis("off")
axes[0].text(.5,.86,"21 = 105 - 2 x (252 - 2 x 105)",ha="center",color="#ffcf85",fontsize=20)
axes[0].text(.5,.42,"= -2 x 252 + 5 x 105",ha="center",color="#91e0b2",fontsize=24)
axes[0].text(.5,.04,"Each substitution uses an earlier remainder equation.",ha="center",color="#bdc7d5",fontsize=12)
axes[1].text(.5,.80,"1 = -3 x 7 + 2 x 11",ha="center",color="#93e5ff",fontsize=23)
axes[1].text(.5,.40,"7 x (-3) = 1 - 2 x 11",ha="center",color="#e6edf3",fontsize=20)
axes[1].text(.5,.02,"Inverse of 7 modulo 11: -3 ≡ 8 (mod 11)",ha="center",color="#91e0b2",fontsize=18)
fig.suptitle("Back substitution turns a gcd of 1 into an inverse",color="#e6edf3",fontsize=18)
fig.subplots_adjust(left=.03,right=.97,top=.88,bottom=.06,hspace=.30)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
assert -2*252+5*105==21
assert -3*7+2*11==1 and 7*8%11==1
베주 역대입으로 21을 원래 수 252와 105의 정수배 합으로 표현하고, 7과 11의 경우 역원 8을 얻는 흐름
다른 방법으로도 계산해 볼 수 있습니다.
호제법에서 나온 $7×(-3)−11×(−2)=1$에 $7×11−11×7=0$을 식끼리 더해 묶으면 $7×(−3+11)−11×(−2+7)=1 \rightarrow 7×8−11×5=1$
해 x가 −3에서 8로 바뀐 것을 알 수 있습니다.(여기서는 q가 -2에서 5로 바뀌는 것까지 한번에 알 수 있습니다)
이제 찾아낸 8이 곱셈을 정말 되돌리는지도 확인해볼까요? 법 11에서 입력 눈금을 2로 두고 7을 곱하면 $7\times2=14\equiv3\pmod{11}$입니다. 이 출력 3에 다시 8을 곱하면 $8\times3=24\equiv2\pmod{11}$로 처음 눈금을 되찾습니다. 7을 곱하기 전 정수가 2였는지 13이었는지까지 알아낸 것은 아닙니다. 두 수는 처음부터 법 11에서 같은 눈금이었으니까요. 역원이 복구하는 것은 원래의 나머지입니다.
6. 역원이 존재하는 조건은 정확히 서로소입니다
이번에는 법 9에서 6의 모듈러 역원을 찾는다고 합시다. 필요한 식은
하지만 왼쪽은 어떤 정수 $x,q$를 넣어도 3의 배수입니다. 오른쪽 1은 3의 배수가 아닙니다. 따라서 이 식은 불가능합니다. 후보를 더 많이 찾아보아도 답이 나오지 않는 이유가 있습니다. $6x-9q=3(2x-3q)$에서 괄호 안은 언제나 정수입니다. 따라서 어떤 계수를 골라도 결과는 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', 'Integer x': '정수 x', 'Integer q': '정수 q', '6x - 9q: every entry is a multiple of 3': '6x − 9q: 모든 값이 3의 배수', 'gcd(6, 9) = 3\n6x - 9q = 3(2x - 3q)': '최대공약수는 3\n6x − 9q = 3(2x − 3q)', 'The number 1 is outside this lattice.\nMore searching cannot produce an inverse.': '1은 이 격자 밖에 있다.\n더 찾아도 역원을 만들 수 없다.', 'A gcd is a barrier for every integer combination': '최대공약수는 모든 정수 결합의 경계', 'The displayed grid illustrates the algebraic divisibility argument; it is not the proof by finite search.': '격자는 대수적인 배수 논증의 예시이며, 유한 탐색 자체가 증명인 것은 아니다.'}
_bfOriginalPixels = [1302, 698]
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.1),title="A gcd is a barrier for every integer combination")
xs=np.arange(-3,4)
qs=np.arange(-3,4)
values=np.array([[6*x-9*q for x in xs] for q in qs])
ax=axes[0]
ax.imshow(np.ones_like(values),cmap=ListedColormap([PANEL]))
for i in range(7):
for j in range(7):
ax.text(j,i,str(values[i,j]),ha="center",va="center",color=INK,fontsize=12)
ax.set_xticks(range(7),xs)
ax.set_yticks(range(7),qs)
ax.set_xlabel("Integer x",color=INK,fontsize=12)
ax.set_ylabel("Integer q",color=INK,fontsize=12)
ax.set_title("6x - 9q: every entry is a multiple of 3",color=INK,fontsize=14,pad=14)
ax=axes[1]
off(ax)
for i,value in enumerate(range(-6,7)):
x=.05+i*.075
ax.add_patch(Circle((x,.66),.022,transform=ax.transAxes,
color=GREEN if value%3==0 else "#35445b"))
text(ax,x,.54,str(value),size=12)
if value==1:
text(ax,x,.80,"1",color=RED,size=18)
arrow(ax,(x,.75),(x,.70),color=RED)
text(ax,.5,.36,"gcd(6, 9) = 3\n6x - 9q = 3(2x - 3q)",color=BLUE,size=17)
text(ax,.5,.12,"The number 1 is outside this lattice.\nMore searching cannot produce an inverse.",color=GOLD,size=14)
caption(fig,"The displayed grid illustrates the algebraic divisibility argument; it is not the proof by finite search.")
assert np.all(values%3==0)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
6x−9q의 정수 조합은 모두 3의 배수 격자에 머무른다. 작은 계산 표와 수직선에서 1이 그 격자 밖에 있음을 보여 역원이 불가능한 이유를 설명한다.
작은 범위에서 1을 찾지 못했다는 실험 결과보다 강한 결론입니다. 모든 정수 계수에서 공약수 3이 남는다는 식이 불가능성을 보장합니다. 일반적인 두 방향을 분리해봅시다. 먼저 법 $n>1$에서 $a$의 역원 $x$가 존재한다면
입니다. $a,n$의 공약수는 왼쪽도 나누므로 1을 나누어야 합니다. 따라서 공약수는 1뿐이며 $\gcd(a,n)=1$입니다. 이것이 필요조건입니다. $a$가 음수이면 양수 $|a|$에 베주 항등식을 적용한 뒤 $a$에 곱할 계수의 부호를 바꾸면 됩니다. $a=0$은 $n>1$에서 서로소가 아니므로 역원이 존재하는 경우에 들어가지 않습니다. 반대로 $\gcd(a,n)=1$이면 베주 항등식에 의해 어떤 정수 $u,v$가 존재해서
입니다. 법 $n$에서 $nv$는 나머지가 0이므로 $au\equiv1\pmod n$입니다. 따라서 $u$가 역원입니다. 이것이 충분조건입니다.
필요조건은 공약수로 불가능성을 보였고, 충분조건은 호제법과 역대입으로 실제 값을 만들었습니다. “서로소여야 한다”와 “서로소이면 된다”는 다른 주장이고, 이제 둘 다 증명했습니다. “역원이 있으면 서로소”만 알았다면, 서로소인 수에 대해서도 역원이 정말 있는지는 아직 모릅니다. 반대로 “서로소이면 역원이 있다”만 알았다면, 서로소가 아닌 수에 숨어 있는 역원까지 제외한 것은 아닙니다. 앞쪽 방향이 불가능한 경우를 모두 제외하고, 뒤쪽 방향이 남은 경우에 답을 실제로 제공합니다. 양방향 화살표는 이 두 증명을 한 줄로 묶은 표기입니다. 역원은 법 $n$에서 하나의 나머지로 정해집니다. $ax\equiv1$, $ay\equiv1$이라면 $a(x-y)\equiv0$입니다. 여기에 이미 존재를 확인한 $a$의 역원을 곱하면 $x-y\equiv0$이므로 $x\equiv y\pmod n$입니다. 정수로는 여러 개여도 나머지로는 하나라는 뜻입니다.
7. 합동식의 약분을 정당화하고 적용 범위를 구분하기
법 $n$에서 $ca\equiv cb$이고 $c$와 $n$이 서로소라고 합시다. $c$의 역원을 $u$라 하면 $uc\equiv1$입니다. 양변에 $u$를 곱하면
이것이 앞 편에서 약속한 약분의 이유입니다. 기호를 무작정 지우는 것이 아니라, 곱해서 1이 되는 수를 양변에 곱합니다. 숫자로는 법 11에서 $7a\equiv7b$에 8을 곱하는 계산입니다. $56a\equiv56b$이고 $56\equiv1\pmod{11}$이므로 $a\equiv b$가 됩니다. (56을 1로 바꿀 때 버린 $55a$, $55b$는 각각 11의 배수입니다.) 양쪽에 같은 수를 곱하는 것은 허용되며, 곱해진 $uc$를 1로 바꾸는 것도 허용됩니다. 이 두 허용된 계산을 이어 한 것이 약분입니다. 법 6에서 $2\times1\equiv2\times4$인데 2를 지울 수 없었던 이유도 설명됩니다. 2와 6은 서로소가 아니므로 2의 역원이 없습니다. 이 경우에는 법을 그대로 둔 약분이 안전하지 않습니다.
좀 더 정확히는 $d=\gcd(c,n)$일 때 $ca\equiv cb\pmod n$이면
까지는 얻습니다. $c=dc'$, $n=dn'$라 두면 $n\mid c(a-b)$는 $n'\mid c'(a-b)$와 같고, $c',n'$이 서로소여서 약분할 수 있기 때문입니다. 앞의 예에서는 법 6이 법 3으로 줄어들어 $1\equiv4\pmod3$이라는 올바른 결론을 얻습니다.
법이 줄어드는 과정을 등식으로 쓰면 더 분명합니다. $ca\equiv cb\pmod n$이라는 말은 $c(a-b)=nk$인 정수 $k$가 있다는 뜻입니다. $c=dc'$, $n=dn'$를 넣으면 $dc'(a-b)=dn'k$입니다. 이것은 정수의 등식이므로 양쪽을 0이 아닌 정수 $d$로 나누어 $c'(a-b)=n'k$를 얻습니다.
$c',n'$이 서로소인 이유도 최대공약수라는 말 안에 들어 있습니다. 만약 둘에게 공약수 $e>1$이 남아 있으면, 원래 $c,n$에는 $de>d$라는 공약수가 있었다는 뜻이 됩니다. $d$를 최대공약수라고 고른 것과 충돌하므로 그런 $e$는 없습니다.
$n'>1$이면 이렇게 서로소임을 확인한 $c'$의 법 $n'$ 역원을 곱해 약분합니다. 등식의 나눗셈과 합동식의 약분을 같은 단계로 섞지 않은 것입니다.
여기서 $n'=1$이면 역원을 따로 사용할 필요가 없습니다. 모든 정수는 1의 배수이므로 $1\mid(a-b)$는 언제나 참입니다. 예를 들어 법 6에서 공통 계수가 6이면 $d=6$, $n/d=1$이고, 약분 후 얻는 것은 두 정수가 법 1에서 합동이라는 항상 참인 사실입니다. 법을 줄여서 얻은 결론의 범위까지 확인한 것입니다.
법 6에서 2를 지우는 계산은 결론의 법도 3으로 바꾸어야 합니다. $2\cdot1\equiv2\cdot4\pmod6$에서 얻는 것은 $1\equiv4\pmod3$이지, 법 6에서의 합동이 아닙니다.
그림을 만든 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', 'Multiply by 2 modulo 7': '법 7에서 2를 곱하기', 'Input': '입력', 'Output': '출력', 'gcd(2,7)=1: every output has one input.\nAn inverse restores the original residue.': 'gcd(2,7)=1: 각 출력의 입력은 하나뿐이다.\n역원으로 원래 나머지를 되찾는다.', 'Multiply by 2 modulo 6': '법 6에서 2를 곱하기', '1 and 4 both reach 2.\nEqual products do not imply equal inputs.': '1과 4가 모두 2로 간다.\n곱이 같아도 입력이 같다는 뜻은 아니다.', 'Cancellation works when multiplication can be reversed': '곱셈을 되돌릴 수 있을 때 약분할 수 있다', 'In modulo 6, dividing 2x and 2y by 2 requires changing the modulus to 3.': '법 6에서 2x와 2y를 2로 나누려면 법도 3으로 바꿔야 한다.'}
_bfOriginalPixels = [1262, 717]
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.3),title="Cancellation works when multiplication can be reversed")
for ax,n in zip(axes,[7,6]):
off(ax)
inputs=list(range(n))
outputs=[2*x%n for x in inputs]
text(ax,.5,.96,f"Multiply by 2 modulo {n}",color=BLUE,size=16)
for x in inputs:
y=.82-x*.095
text(ax,.13,y,str(x),size=15)
text(ax,.86,y,str(x),size=15)
for x,value in zip(inputs,outputs):
arrow(ax,(.20,.82-x*.095),(.79,.82-value*.095),
color=GREEN if n==7 else GOLD)
text(ax,.13,.91,"Input",size=12)
text(ax,.86,.91,"Output",size=12)
if n==7:
text(ax,.5,.08,"gcd(2,7)=1: every output has one input.\nAn inverse restores the original residue.",color=GREEN,size=13)
assert len(set(outputs))==n
else:
text(ax,.5,.08,"1 and 4 both reach 2.\nEqual products do not imply equal inputs.",color=GOLD,size=13)
assert outputs[1]==outputs[4] and 1%6!=4%6
caption(fig,"In modulo 6, dividing 2x and 2y by 2 requires changing the modulus to 3.")
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
2를 곱한 나머지 대응을 법 7과 법 6에서 비교한다. 법 7에서는 입력을 되돌릴 수 있지만 법 6에서는 입력 1과 4가 같은 출력 2로 합쳐져 약분할 수 없다.
반면 법과 서로소인 수는 역원을 곱해 없애도 법을 유지할 수 있습니다. 그림을 읽을 때 지워진 계수와 함께 오른쪽에 적힌 법이 바뀌었는지를 확인해보세요. 이 설명은 첫 편의 조건 조합도 뒷받침합니다. 서로소인 $u,v$가 각각 $N$을 나눈다고 합시다. $N=ut$라고 쓰면 $v\mid ut$이고, $u$와 $v$가 서로소이므로 $v\mid t$입니다. 따라서 $N$은 $uv$의 배수입니다. 공통인수가 있는 4와 6에서는 같은 약분을 할 수 없어서 24의 배수라고 단정하지 못했었습니다.
8. 배수 판정의 최소 계수로 돌아가기
8.1. 계수의 존재증명
이 절의 배수 판정에서는 다시 $n>1$인 법만 생각하겠습니다. 법 1에서는 모든 정수가 배수이므로 따로 판정 계수를 만들 필요가 없습니다. 법 $n$에서 10과 $n$이 서로소이면, 이제 베주 항등식으로 $10u+nv=1$을 만들 수 있습니다. 따라서 10의 역원이 존재합니다. 그 역원을 1 이상 $n$ 미만의 수 $r$로 나타내면
동시에
이므로 더하기 계수 $r$와 빼기 계수 $n-r$를 모두 얻습니다. 그리고 여기서 합동의 정의에 따르면 이것은
이라는 뜻입니다. 즉, $10r-1$이 $n$의 배수이므로 어떤 정수 $m$이 존재하여
이라고 쓸 수 있습니다. 정리하면
입니다.
이번엔 또다른 배수 판정법을 만들 수 있는 $-1$을 구하기 위해 앞서 구한 등식
에서, $10(n-r)$을 전개하면($\because 10(-r) \equiv -1 \pmod n \Leftrightarrow 10(n-r) \equiv -1 \pmod n$)
따라서
여기서 $k=n-r$, 새로운 정수 $m'=10-m$으로 놓으면
을 얻습니다.
(아까 위에서 얼핏 지나간
$$ 7 \times -3 - 11\times(-2) = 1 $$
$$ 7 \times 8 - 11 \times 5 = 1 $$
를 기억하시나요?
여기서는 나머지를 -1로 바꾸진 않았지만, 7에 곱해지는 k를 바꾸는 순간 m도 따라 바뀌는 걸 볼 수 있답니다. 정확히는 k가 11만큼 바뀔 때 m은 7만큼 바뀌었습니다.)
즉, 두 경우 모두
를 만족합니다.(여기서 $M$은 $m, m'$을 모두 포함합니다)
그리고 이를 통해 앞 편의 $|10k-mn|=1$을 만족하는 계수가 반드시 존재한다는 증명이 완성되었습니다.
8.2. 최소 계수 증명
최소 양의 계수는 왜 이 둘 중 작은 것일까요? $+1$을 만드는 모든 계수는 역원의 유일성에 따라 $r$와 법 $n$에서 합동이고, $-1$을 만드는 모든 계수는 $n-r$와 합동입니다. 따라서 각각의 가장 작은 양의 대표가 $r$와 $n-r$이며
입니다. 아무 후보 두 개만 비교한 것이 아니라 가능한 두 나머지 종류를 모두 비교한 것입니다. 예를 들어 $n=23$에서 $r=7$이면 $+1$을 만드는 양의 계수는 $7,30,53,\ldots$이고, $-1$을 만드는 양의 계수는 $16,39,62,\ldots$입니다. 각각 23씩 차이 나는 한 나머지 종류입니다. 음의 정수배를 더하면 그 종류의 다른 대표도 생기지만, 1 이상 22 이하에 있는 대표보다 작은 양의 대표는 생기지 않습니다. 그래서 두 목록의 첫 양수인 7과 16만 비교하면 전체 양의 후보의 최소가 결정됩니다. 23에서 직접 구해보겠습니다.
역대입하면
따라서 $r=7$, $n-r=16$이며, 최소는 7입니다. $70=69+1$이므로 끝자리의 7배를 더하는 $a+7b$를 선택합니다. 숫자를 하나씩 시험해서 얻었던 답을 이제 체계적인 나눗셈으로 얻었습니다.
이 증명을 딱 한 줄로 정리하자면, 10과 $n$이 서로소이면 $10k-mn=1$을 만족하는 양의 정수 $k$와 정수 $m$이 반드시 존재하며, 가장 작은 양의 계수 $k$를 찾기 위해 $10k-mn=-1$인 경우까지 함께 고려해 본다. 입니다.
9. 직접 바꾸어 확인해보기
먼저 252와 105를 그대로 계산하고, 7과 11로 바꾸어보세요. 각 줄의 제수와 나머지가 다음 줄에서 어떤 역할을 맡는지 비교합니다. 6과 9에서는 마지막 식의 오른쪽이 1이 되지 않는 이유를 최대공약수와 연결해보세요.
호제법의 역할 이동
각 나눗셈의 몫과 나머지, 마지막 역대입 결과를 함께 확인합니다.
10. 마무리
252와 105에서 105와 42로 이동한 이유는 두 쌍의 공약수 목록이 같기 때문입니다. 제수보다 작은 나머지로 이동하므로 계산이 끝나고, 마지막 0 아닌 값이 최대공약수입니다. 계산을 거꾸로 올라가면 그 최대공약수를 원래 두 수의 정수 배의 합으로 만들 수 있습니다. 그 베주 항등식에서 최대공약수가 1이면 모듈러 역원을 얻습니다. 역원은 합동식에서 약분을 허용하고, 앞 편의 배수 판정 계수도 만들어줍니다. 오늘 구한 것은 최대공약수 하나를 넘어, 나머지 계산에서 무엇을 되돌릴 수 있는지에 관한 기준입니다. 다음 편에서는 이 기준으로 나머지 전체에 곱셈을 해보겠습니다. 서로소인 수를 곱했는데 나머지가 중복되지 않는다면, 그 목록 전체는 어떻게 바뀔까요? 그 질문에서 페르마의 소정리가 나옵니다.
더 읽기: 확장 유클리드 호제법과 역원의 활용.