배수 판정법의 원리: 20과 21의 차이 하나가 만드는 규칙
《나머지에서 시작하는 정수론》 · 2/8편 · 배수 판정법의 원리
0. 서론: 잘 쓰이는 규칙을 직접 만들 수 있을까요
앞 편에서 203을 7의 규칙으로 바꾸면 $20-2\times3=14$가 되었습니다. 286을 13의 규칙으로 바꾸면 $28+4\times6=52$가 되었습니다. 둘 다 작은 수를 보고 큰 수의 배수 여부를 판단했습니다.
그런데 숫자를 바꾸었는데도 어떻게 같은 답을 얻을까요?
이번 편에서 다룰 정보는 나머지입니다. 나누는 수를 정하고 나면, 어떤 수들은 크기가 달라도 같은 나머지를 가집니다. 이 관계를 이용하면 큰 자릿값을 1이나 $-1$처럼 간단한 값으로 바꿀 수 있습니다. 7·13·17·19의 서로 다른 계수도 같은 원리에서 얻습니다.
새 표기가 몇 개 등장하지만, 먼저 숫자로 뜻을 읽고 기호를 붙이겠습니다. 규칙의 존재를 보장하는 일반적인 방법은 다음 편으로 남겨두고, 이번에는 찾은 규칙이 왜 옳은지를 끝까지 확인합니다.
1. ‘법’은 나누는 수, ‘합동’은 같은 나머지
시계에서 먼저 출발해볼까요? 익숙한 시계의 12 자리에 0을 적고, 눈금을 0부터 11까지 두겠습니다. 여기서는 정수 하나를 나타낼 때마다 0에서 출발합니다. 양수만큼 움직이면 시계 방향, 음수만큼 움직이면 반대 방향으로 갑니다. 시계가 가리키는 위치와 우리가 움직인 칸 수는 구분해주세요.
0에서 2칸 가면 눈금 2입니다. 26칸 가도 두 바퀴를 돌고 2칸이 남아서 같은 눈금입니다. 이번에는 반대로 10칸 가봅시다. 이 이동량을 $-10$이라고 적으면, 역시 눈금 2에 닿습니다. 뒤로 한 바퀴 간 다음 앞으로 2칸 온 것과 같은 자리니까요. 세 수를 나눗셈의 식으로 쓰면 그 차이가 보입니다.
$$ 2=12\times0+2,\qquad 26=12\times2+2,\qquad -10=12\times(-1)+2. $$몫은 각각 0, 2, $-1$이지만 나머지는 모두 2입니다. 마지막 식의 음수 몫도 낯설 것 없습니다. 12의 $-1$배인 $-12$에 2를 더하면 원래 수 $-10$이 됩니다. 26과 2의 차이는 24이고, $-10$과 2의 차이는 $-12$입니다. 이렇게 차이가 12의 정수배이면 끝나는 눈금이 같습니다.
그림을 만든 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))
values = [2, 26, -10]
assert [divmod(x,12) for x in values] == [(0,2),(2,2),(-1,2)]
fig = plt.figure(figsize=(11.67, 8.75), dpi=120, facecolor=BG)
title(fig, '다른 정수, 같은 시계 눈금', 'Different integers, the same residue modulo 12')
ax = fig.add_axes([.02,.18,.57,.65])
clock(ax,12,active=(0,2))
arc_arrow(ax,0,2,12)
p=point(2,12)
ax.add_patch(Circle(p,.10,fill=False,ec=ORANGE,lw=3))
label(ax,0,.14,'출발 0',size=22,color=GREEN)
label(ax,0,-.14,'같은 도착 눈금 2',size=20,color=ORANGE)
label(ax,0,-.40,'Start at 0; finish at 2',size=13,color=MUTED)
cards=fig.add_axes([.60,.20,.37,.61]);cards.set_xlim(0,1);cards.set_ylim(0,1);cards.axis('off')
for y,x,q in zip([.83,.50,.17],values,[0,2,-1]):
cards.add_patch(FancyBboxPatch((.01,y-.13),.98,.26,boxstyle='round,pad=.01',
facecolor='#1d2b40',edgecolor=LINE,lw=1.2))
label(cards,.5,y+.055,str(x),size=28,color=BLUE)
label(cards,.5,y-.045,f'{x} = 12 × ({q}) + 2',size=17)
ftext(fig,.5,.105,'12시 자리는 0으로 씁니다. 눈금은 같아도 정수와 몫은 다릅니다.',size=18)
ftext(fig,.5,.055,'The top mark is 0. The clock forgets the number of full turns.',size=14,color=MUTED)
plt.show()
0부터 11까지의 시계에서 2·26·음의 10이 모두 눈금 2에 놓인다. 세 정수의 몫은 각각 0·2·음의 1이며, 같은 눈금과 같은 정수는 다르다.
그렇다고 2, 26, −10이 같은 정수라는 뜻은 아닙니다. 같은 것은 마지막 눈금이지, 움직인 양이 아닙니다. 이제 눈금 수를 열두 개에서 일곱 개로 바꾸어 같은 일을 해보겠습니다. 이때 한 바퀴에 해당하는 수는 12가 아니라 7입니다.
23을 7로 나누면 $23=7\times3+2$입니다. 9도 $9=7\times1+2$이므로 나머지가 2입니다. 두 수는 크기가 다르지만 7로 나눈 나머지가 같습니다. 이를
이라고 적습니다. $\equiv$는 합동이라는 관계를 나타내고, $\pmod{7}$은 7을 기준으로 나머지를 비교한다는 뜻입니다. 이때 나누는 수 7을 법이라고 부릅니다. “법 7에서 합동”은 “7로 나눈 나머지가 같다”는 문장입니다.
여기서 말하는 합동은 나머지의 동등성을 말합니다. 한편 우리가 이 단어를 처음 접한 기하학에서의 합동은 도형을 옮기거나 돌리거나 뒤집어 완전히 포갤 수 있음을 뜻합니다. 두 개념 모두 특정 기준에서 두 대상이 동등하다는 공통점이 있습니다.
$23=9$라고 쓰면 틀립니다. 등호는 두 수 자체가 같다는 뜻이기 때문입니다. 하지만 $23\equiv9\pmod{7}$은 맞습니다. 두 수의 차이 $23-9=14$가 7의 배수라서 나머지가 같기 때문입니다.
이 차이에 관한 설명을 정의로 삼으면 음수까지 자연스럽게 다룰 수 있습니다. 양의 정수 $n$에 대하여
가운데의 $\Longleftrightarrow$는 양쪽 방향으로 성립한다는 뜻입니다. 왼쪽이 참이면 오른쪽도 참이고, 오른쪽이 참이면 왼쪽도 참입니다. 배수라는 말을 짧게 $n\mid(x-y)$라고도 적습니다. 세로줄은 나머지 없이 나누어떨어진다는 뜻입니다.
예를 들어 $10-(-1)=11$이므로 $10\equiv-1\pmod{11}$입니다. $-1$을 보통의 나머지처럼 0부터 10 사이로 쓰면 10이지만, 계산을 간단하게 하려고 같은 나머지를 나타내는 $-1$을 사용할 수 있습니다. “음수인 나머지를 허용한다”는 말보다 “나머지가 같은 음수로 바꾸어 쓴다”라고 이해하면 정확합니다.
이번에는 눈금이 0부터 10까지인 열한 칸짜리 시계를 떠올리면 됩니다. 0에서 앞으로 10칸 간 자리와 뒤로 1칸 간 자리가 같지요. 앞의 열두 칸짜리 시계에서는 뒤로 1칸 간 자리가 11이었지만, 지금은 10입니다. 같은 음수를 사용해도 어느 법에서 읽는지가 함께 정해져야 합니다.
법을 바꾸면 관계도 바뀝니다. $23\equiv9\pmod{7}$이지만 법 5에서는 둘의 나머지가 3과 4라서 합동이 아닙니다. 따라서 긴 계산에서도 어느 법을 쓰는지 반드시 붙여두어야 합니다.
2. 더하고 곱할 수 있지만 마음대로 약분할 수는 없습니다
법 7에서 23과 9가 합동이면 양쪽에 5를 더해도 합동입니다. 두 수의 차이는 여전히 14입니다. 양쪽에 3을 곱하면 차이가 $3\times14$가 되어 역시 7의 배수입니다.
일반적으로 $x-y=nu$라면
따라서 같은 수를 더하거나 곱해도 합동 관계가 유지됩니다.
두 합동식을 서로 더하거나 곱하는 것도 가능합니다.
1. 곱셈에서도 합동이 유지되는 이유
다음 두 합동식이 있다고 가정하겠습니다.
이는 다음을 의미합니다.
-
$x-y$는 $n$의 배수
-
$u-v$도 $n$의 배수
우리가 증명하려는 것은 다음입니다.
즉, $xu-yv$ 역시 $n$의 배수임을 보이면 됩니다.
그런데 $xu-yv$는 바로 인수분해하기 어렵습니다. 그래서 중간에 $uy$를 더하고 빼는 방법을 사용합니다.
여기서 중요한 부분은 다음과 같습니다.
① $x-y$가 $n$의 배수이므로 $u(x-y)$도 $n$의 배수입니다.
② $u-v$가 $n$의 배수이므로 $y(u-v)$도 $n$의 배수입니다.
따라서 이 둘의 합인 $xu-yv$ 역시 $n$의 배수입니다.
결국
가 성립합니다.
그래서 계산 도중 큰 수를 그와 합동인 작은 수로 바꾸어 곱할 수 있습니다.
2. 실제 숫자로 확인하기
다음 두 합동식을 생각해 보겠습니다.
17과 5는 차이가 12이고, 14와 2 역시 차이가 12입니다.
이제 두 수를 각각 곱해 보겠습니다.
원래 수끼리 곱하기
작은 수로 바꿔 곱하기
곱한 결과는 238과 10으로 서로 다르지만, 12로 나눈 나머지는 같습니다.
바로 이것이 합동식에서 큰 수를 작은 수로 대체해도 되는 이유입니다.
3. 거듭제곱에도 적용되는 이유
거듭제곱은 같은 수를 반복해서 곱하는 연산입니다.
시계로 읽을 때도 이 연산의 차이는 지켜야 합니다. 5를 더한다면 지금 눈금에서 다섯 칸 앞으로 가지만, 5를 곱한다면 지금 눈금의 수를 다섯 배 한 뒤 도착 눈금을 읽습니다. 예를 들어 법 12의 눈금 5에서 5를 더하면 10이고, 5를 곱하면 25의 나머지인 1입니다. 아래에서 거듭제곱을 계산할 때 반복하는 것은 두 번째 작업입니다.
따라서
이면
이고, 같은 논리를 반복하면 모든 양의 정수 $k$에 대해
가 성립합니다.
예를 들어 $17^4$를 12로 나눈 나머지를 구한다면,
여기서 한 번 더 간소화할 수도 있습니다.
따라서
큰 수를 직접 계산하지 않고도 나머지를 구할 수 있습니다. 정리하면, 합동식의 곱셈 법칙은 두 곱의 차이도 $n$의 배수라는 사실에서 나오며, 이 성질 덕분에 거듭제곱에서도 계산 도중 수를 계속 작은 나머지로 바꿀 수 있습니다.
4. 반대로 곱해진 수를 지우는 약분에는 조건이 있습니다.
법 6에서
은 맞습니다. 2와 8의 차이가 6이기 때문입니다. 그러나 양쪽의 2를 지운 $1\equiv4\pmod{6}$은 틀립니다. 곱하기가 허용된다고 해서 그 반대가 언제나 허용되는 것은 아닙니다.
법을 그대로 유지하며 양쪽에서 공통인수 $c$를 안전하게 지울 수 있는 대표적인 조건은 $c$와 법 $n$이 서로소라는 것입니다. 최대공약수 기호로는 $\gcd(c,n)=1$이라고 씁니다. 서로소는 공통된 양의 약수가 1뿐이라는 뜻입니다. 이 약분 조건의 일반적인 증명은 다음 편에서 하겠습니다.
법 6에서 곱할 수를 2로 두고, 서로 다른 입력이 같은 출력으로 가는지 살펴보세요. 이어 곱할 수를 5로 바꾸면, 같은 법에서도 결과가 달라집니다.
약분이 가능한 조건
법 n에서 cx와 cy가 합동일 때 x와 y까지 합동이라고 결론 내려도 되는 조건을 확인합니다.
법 6에서 서로 다른 입력 $x=1$, $y=4$는 서로 합동이 아닙니다. 그런데 $c=2$를 곱한 $2\times1=2$와 $2\times4=8$은 둘 다 나머지가 2이므로 합동입니다. 따라서 곱한 결과가 합동이라는 사실만으로 원래 입력도 합동이라고 되돌릴 수 없습니다. 이 차이가 서로소 조건과 어떻게 연결되는지는 다음 편에서 증명합니다.
이번 편의 배수 판정에서는 실제로 찾은 관계식이 되돌아가는 길도 제공하므로, 약분을 ‘그냥 그렇다더라’ 라고 단순히 받아들이고 넘어갈 필요가 없습니다.
먼저 자릿값에서 출발해보겠습니다.
3. 3·9의 합과 11의 교대합은 자릿값에서 나옵니다
5724를 자릿값으로 펼치면
법 9에서 $10\equiv1\pmod{9}$입니다. 거듭제곱에도 같은 관계를 적용하면 $10^2,10^3$도 모두 1과 합동입니다. 따라서
자리 숫자의 합은 갑자기 등장한 요령이 아닙니다. 각 자리 숫자 앞에 붙었던 $10^j$가 전부 1로 바뀌면서 남은 식입니다. 법 3에서도 $10\equiv1\pmod{3}$이므로 같은 설명이 통합니다.
5724와 자리합 18의 차이는 $5724-18=5706$입니다. 이를 $5(1000-1)+7(100-1)+2(10-1)$로 나누면, 버린 부분이 왜 모두 9의 배수인지 자리마다 확인할 수 있습니다.
그림을 만든 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', 'Place-value terms': '자릿값에 따른 항', 'Digits': '자리 숫자', 'Removed': '버린 양', 'Thousands': '천의 자리', 'Hundreds': '백의 자리', 'Tens': '십의 자리', 'Units': '일의 자리', 'Amount removed': '버린 양', 'Every removed amount is divisible by 9': '버린 양은 모두 9로 나누어떨어진다', 'A digit sum removes exact multiples of 9': '자리 합으로 바꾸며 버린 양은 모두 9의 배수', '5724 - 18 = 5706 = 9 x 634. The digit sum has the same remainder modulo 9.': '5724 − 18 = 5706 = 9 × 634. 자리 합의 법 9 나머지는 같다.'}
_bfOriginalPixels = [1244, 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(1, 2, title="A digit sum removes exact multiples of 9")
ax = axes[0]
off(ax)
digits = [5, 7, 2, 4]
places = [1000, 100, 10, 1]
values = [d*p for d,p in zip(digits, places)]
removed = [d*(p-1) for d,p in zip(digits, places)]
for j, (digit, place, value, gone) in enumerate(zip(digits, places, values, removed)):
y = .78-j*.19
card(ax, .01, y, .31, .12, f"{digit} x {place} = {value}", size=13)
arrow(ax, (.34, y+.06), (.56, y+.06))
card(ax, .58, y, .16, .12, str(digit), edge=GREEN, color=GREEN)
text(ax, .87, y+.06, f"-{gone}", color=GOLD, size=13)
text(ax, .17, .98, "Place-value terms", size=14)
text(ax, .66, .98, "Digits", size=14)
text(ax, .87, .98, "Removed", size=14)
ax = axes[1]
ax.bar(range(4), removed, color=[BLUE, GREEN, GOLD, MUTED], width=.65)
for j, value in enumerate(removed):
ax.text(j, value+100, f"{value} = 9 x {value//9}",
ha="center", va="bottom", color=INK, fontsize=12)
ax.set_xticks(range(4), ["Thousands", "Hundreds", "Tens", "Units"])
ax.set_ylim(0, 6200)
ax.set_ylabel("Amount removed", color=INK, fontsize=12)
ax.set_title("Every removed amount is divisible by 9", color=INK, fontsize=14, pad=14)
ax.grid(axis="y", alpha=.2, color=LINE)
caption(fig, "5724 - 18 = 5706 = 9 x 634. The digit sum has the same remainder modulo 9.")
assert sum(values)==5724 and sum(digits)==18 and sum(removed)==5706
assert all(value % 9 == 0 for value in removed)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
5724에서 자릿수 합 18을 남길 때 버리는 양을 자리별로 분해한 그림. 4995·693·18·0은 모두 9의 배수이고 합은 5706이다.
그림에서 각 자리의 큰 묶음을 덜어내고 남은 숫자가 $5+7+2+4$입니다. 두 수가 같아진 것은 아니지만, 덜어낸 합이 9의 배수이므로 법 9의 나머지는 같습니다.
법 11에서는 $10\equiv-1\pmod{11}$입니다. 그러면
그래서 일의 자리부터 가중치가 $+1,-1,+1,-1$로 바뀝니다. 2728에서는
3과 9에서는 모든 자릿값이 같은 부호로 바뀌고, 11에서는 부호가 번갈아 바뀝니다. 두 규칙의 차이는 10이 각각의 법에서 무엇과 합동인지의 차이입니다.
그림을 만든 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', 'Same remainder as the place value; negative weights mean subtraction.': '자릿값과 나머지가 같다. 음의 가중치는 빼기를 뜻한다.', 'Decimal place values, seen through remainders': '십진법의 자릿값을 나머지로 살펴보기'}
_bfOriginalPixels = [1089, 599]
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch
divisors = [3, 9, 11, 7, 13]
weights = []
for n in divisors:
row = []
for position in range(6):
remainder = pow(10, position, n)
row.append(remainder if remainder <= n // 2 else remainder - n)
weights.append(row)
fig, ax = plt.subplots(figsize=(11.5, 6.3), facecolor="#0d1117")
ax.set_facecolor("#0d1117")
ax.set_xlim(-1.35, 5.9)
ax.set_ylim(-1.25, 5.25)
ax.axis("off")
for j in range(6):
ax.text(j, 4.75, f"$10^{j}$", ha="center", color="#e6edf3", fontsize=15)
for i, (n, row) in enumerate(zip(divisors, weights)):
y = 4 - i
ax.text(-.85, y, f"n = {n}", ha="center", va="center", color="#e6edf3", fontsize=13)
for j, value in enumerate(row):
color = "#173f50" if value > 0 else "#54333d"
ax.add_patch(FancyBboxPatch((j-.38, y-.34), .76, .68,
boxstyle="round,pad=0.04", facecolor=color, edgecolor="#526276"))
ax.text(j, y, f"{value:+d}", ha="center", va="center", fontsize=19,
color="#93e5ff" if value > 0 else "#ffb3b3")
ax.text(2.3, -0.85, "Same remainder as the place value; negative weights mean subtraction.",
ha="center", color="#bdc7d5", fontsize=11)
fig.suptitle("Decimal place values, seen through remainders", color="#e6edf3", fontsize=18, y=.97)
fig.subplots_adjust(left=.05, right=.98, top=.89, bottom=.05)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
십진법 자릿값의 나머지 표. 3과 9에서는 모두 1, 11에서는 1과 음의 1이 번갈아 나오며 7과 13에서는 다른 가중치가 나타난다.
4와 8의 끝자리 규칙도 같은 언어로 볼 수 있습니다.
$100=4\times25$이므로 법 4에서는 $100\equiv0$입니다. $N=100A+C$에서 $C$를 끝 두 자리라고 하면
앞부분 $100A$가 0으로 바뀌므로 끝 두 자리만 남습니다. 마찬가지로 $1000=8\times125$이므로 법 8에서는 끝 세 자리만 남고, $10000=16\times625$이므로 법 16에서는 끝 네 자리만 남습니다.
3·9·11은 큰 자릿값을 $\pm1$로 바꾸고, 4·8·16은 일정 위치 이상의 자릿값을 0으로 바꾼 것입니다.
4. 7의 규칙은 20이 21보다 1 작다는 사실에서
0 이상의 정수를 $N=10a+b$라고 쓰겠습니다. $a$는 앞부분 전체, $b$는 일의 자리 숫자이므로 $0\le b\le9$입니다. 7에서는 $10\equiv3\pmod{7}$이어서 바로 $\pm1$이 되지 않습니다. 대신 10에 2를 곱하면 7의 배수 21 바로 앞에 도착합니다.
20과 21은 같은 수가 아닙니다. 정확히 1 차이가 나며, 그 차이를 남겨야 규칙이 나옵니다.
$21a$는 7의 배수이므로 $2N$이 7의 배수인지와 $a-2b$가 7의 배수인지는 같습니다. 다만 우리가 알고 싶은 것은 $2N$이 아니라 $N$의 배수 여부입니다.
이번에는 그 연결을 직접 확인할 수 있습니다.
$N$이 7의 배수이면 $2N$도 당연히 7의 배수입니다.
반대로 $2N$이 7의 배수라면
의 오른쪽 두 항이 모두 7의 배수이므로 $N$도 7의 배수입니다.
따라서 양쪽 방향이 성립합니다.
203에서는 $a-2b=14$이므로 통과하고, 204에서는 12가 되어 통과하지 않습니다. 이때 $204$를 7로 나눈 나머지는 1이고, 12의 나머지는 5입니다. 나머지 값은 달라졌습니다. 이번 변환은 배수인지 아닌지를 보존하며, 나머지 값 자체를 그대로 보존하지는 않습니다.
203과 204를 나란히 바꾸면 무엇을 보존하는지가 더 분명해집니다. 203과 변환값 14는 모두 7의 배수이고, 204와 변환값 12는 모두 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', 'Same remainder modulo 9': '법 9에서 나머지 값이 같다', '5724\nremainder 0': '5724\n나머지 0', '18\nremainder 0': '18\n나머지 0', '5724 - 18 is a multiple of 9': '5724 − 18은 9의 배수', 'Each place value becomes 1.\nThe remainder itself is unchanged.': '각 자릿값이 1이 된다.\n나머지 값 자체가 유지된다.', 'Same yes/no answer modulo 7': '법 7에서 배수 여부만 같다', '203: remainder 0': '203: 나머지 0', '14: remainder 0': '14: 나머지 0', 'both divisible': '둘 다 배수', '204: remainder 1': '204: 나머지 1', '12: remainder 5': '12: 나머지 5', 'both not divisible': '둘 다 배수가 아님', 'T = a - 2b keeps divisibility;\nthe remainder may change.': 'T = a − 2b는 배수 여부를 보존한다.\n나머지 값은 달라질 수 있다.', 'Preserving a remainder and preserving divisibility are different': '나머지 값의 보존과 배수 여부의 보존은 다르다', 'The second rule uses multiplication and sign changes, rather than an equal-remainder replacement.': '두 번째 규칙은 같은 나머지로 바꾸는 대신 곱셈과 부호 전환을 사용한다.'}
_bfOriginalPixels = [1244, 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(1, 2, title="Preserving a remainder and preserving divisibility are different")
ax = axes[0]
off(ax)
text(ax, .5, .94, "Same remainder modulo 9", color=BLUE, size=15)
card(ax, .06, .67, .34, .17, "5724\nremainder 0")
card(ax, .60, .67, .34, .17, "18\nremainder 0")
arrow(ax, (.42,.75), (.57,.75))
card(ax, .12, .32, .76, .19, "5724 - 18 is a multiple of 9", edge=GREEN)
text(ax, .5, .12, "Each place value becomes 1.\nThe remainder itself is unchanged.", size=13)
ax = axes[1]
off(ax)
text(ax, .5, .94, "Same yes/no answer modulo 7", color=GOLD, size=15)
rows = [(203,14), (204,12)]
for i, (number, reduced) in enumerate(rows):
y=.65-i*.32
ok=number%7==0
card(ax, .03,y,.35,.19,f"{number}: remainder {number%7}",size=13)
card(ax, .61,y,.35,.19,f"{reduced}: remainder {reduced%7}",size=13)
arrow(ax,(.40,y+.095),(.58,y+.095),color=GREEN if ok else GOLD)
text(ax,.5,y-.055,"both divisible" if ok else "both not divisible",color=GREEN if ok else GOLD,size=12)
text(ax,.5,.10,"T = a - 2b keeps divisibility;\nthe remainder may change.",size=13)
caption(fig,"The second rule uses multiplication and sign changes, rather than an equal-remainder replacement.")
assert (204%7,12%7)==(1,5)
assert all((n%7==0)==(t%7==0) for n,t in rows)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
법 9의 자릿수 합은 나머지 자체를 보존하지만, 법 7의 끝자리 변환은 배수 여부를 보존한다. 204의 나머지 1과 변환값 12의 나머지 5가 달라지는 예로 구별한다.
두 번째 쌍의 나머지는 1과 5로 다릅니다. 그림의 배수 여부 열이 일치한다고 해서 나머지 숫자 열까지 같아야 하는 것은 아닙니다.
5. 13과 17의 계수와 부호를 만들어봅시다
법 13에서 $10\equiv-3\pmod{13}$이라는 관찰은 맞습니다. 곧바로 사용하면
이므로 $b-3a$로 13의 배수 여부를 검사할 수 있습니다. 286에서는 $6-3\times28=-78$이고, $-78$은 13의 배수입니다.
다만 이 식은 큰 앞부분 전체에 3을 곱합니다. 끝자리 숫자에만 작은 수를 곱하고 싶다면 10의 배수를 더 살펴보면 됩니다. 10, 20, 30 다음의 40은 13의 배수 39보다 1 큽니다.
따라서
이번에는 $a+4b$가 남습니다. 7에서와 달리 부호가 더하기인 것은 40이 39보다 1 크기 때문입니다. 286은 $28+24=52$로 검사할 수 있습니다. $b-3a$와 $a+4b$는 둘 다 옳은 규칙이며, 두 번째 형태가 큰 수에서 계산하기 편합니다.
같은 모양이 보이기 시작했다면 17은 직접 만들어볼 차례입니다. “앞부분에서 일의 자리의 다섯 배를 빼면 되지 않을까?”라는 예상은 맞습니다. 그 예상을 식으로 확인해봅시다. 50은 17의 배수 51보다 1 작으므로
따라서 $a-5b$를 검사합니다. 221에서는 $22-5=17$입니다. 19에서는 $20=19+1$이므로 $2N=19a+(a+2b)$가 되고, $a+2b$를 검사합니다.
여기까지의 계산을 나란히 놓으면 끝자리의 계수를 고르는 방법이 보입니다.
1. 10에 얼마를 곱해야 검사할 수의 배수 바로 옆에 올까요? 그 곱하는 수가 b의 계수가 됩니다.
2. 그때 10에 얼마를 곱한 수가 검사할 수의 배수보다 크면 더하기 기호, 작으면 빼기 기호를 씁니다.
예시를 볼까요?
1. 10에 2를 곱하면 7의 배수인 21 바로 옆(1 차이)에 옵니다. 이 2가 b의 계수가 됩니다.
2. 그때 20은 21보다 작으므로 빼기 기호를 씁니다.
결론적으로 a-2b가 완성되었습니다!
참 쉽죠?
그러면 이제 좀 더 어렵게, 이것을 ‘일반적인 문자’를 이용해서 ‘증명’해보도록 하겠습니다.
6. 최소 양의 계수와 양방향 정당화
1. 일반식 도입
배수 여부를 검사하려는 정수를 $N=10a+b$라고 합시다. 여기서 $a$는 일의 자리를 제외한 정수 부분, $b$는 일의 자리 숫자입니다. 그리고 $N$이 배수인지 판정할 기준 수를 $n$이라고 하겠습니다. 이 절에서 $n$은 2 이상의 정수로 두고, 우선 관계식을 찾을 수 있는 경우를 살펴보겠습니다. 어떤 $n$에서 가능한지는 뒤에서 따로 확인합니다. 어떤 정수 $m$에 대해
이 되는 가장 작은 양의 정수 $k$를 찾습니다. 여기서 $k$는 10에 곱해 움직이는 계수이며, $m$은 비교 대상으로 삼은 $n$의 배수가 몇 배인지를 나타냅니다. $k$를 작은 양의 정수부터 시험하면서, 어떤 정수 $m$에 대해 차이가 정확히 1이 되는 첫 경우를 찾는 것입니다. $|\;|$는 절댓값이므로, 두 수의 차이가 부호를 제외하고 정확히 1이라는 뜻입니다. 부호는 다음과 같이 결정합니다.
23에서는 $70=69+1$이므로 $k=7$과 $a+7b$를 얻습니다. 10, 20, 30, 40, 50, 60은 어느 23의 배수와도 차이가 1이 아니므로 이 계수는 최소입니다. $160=161-1$에서 $a-16b$도 나오지만 최소 양의 계수는 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', 'First hit: 70 = 69 + 1\nRule: a + 7b': '첫 도달: 70 = 69 + 1\n판정식: a + 7b', 'Positive multiplier k': '양의 승수 k', 'Distance to the nearest multiple of 23': '23의 가장 가까운 배수까지의 거리', 'The first distance of 1 gives the smallest coefficient': '거리가 처음 1이 되는 곳에서 최소 계수를 얻는다'}
_bfOriginalPixels = [1033, 559]
from math import gcd
import matplotlib.pyplot as plt
def smallest_rule(n):
if n < 3 or gcd(n, 10) != 1:
raise ValueError("This rule requires n >= 3 and gcd(n, 10) = 1.")
for k in range(1, n):
for sign in (1, -1):
if (10*k - sign) % n == 0:
return k, sign, (10*k - sign) // n
raise AssertionError("An inverse must exist.")
n = 23
ks = list(range(1,8))
nearest = [(10*k + n//2)//n for k in ks]
distances = [abs(10*k - m*n) for k,m in zip(ks,nearest)]
assert distances == [10,3,7,6,4,9,1]
fig, ax = plt.subplots(figsize=(11.1, 5.9), facecolor="#0d1117")
ax.set_facecolor("#0d1117")
ax.bar(ks,distances,color=["#526276"]*6+["#91e0b2"],width=.62)
ax.axhline(1,color="#ffcf85",linestyle="--",linewidth=1.5)
for k,distance in zip(ks,distances):
ax.text(k,distance+.18,str(distance),ha="center",color="#e6edf3",fontsize=13)
ax.annotate("First hit: 70 = 69 + 1\nRule: a + 7b",xy=(7,1),xytext=(4.8,8.6),
arrowprops={"arrowstyle":"->","color":"#91e0b2","linewidth":1.5},
ha="center",color="#91e0b2",fontsize=14)
ax.set_xticks(ks)
ax.set_ylim(0,11.7)
ax.set_xlabel("Positive multiplier k",color="#e6edf3",fontsize=12)
ax.set_ylabel("Distance to the nearest multiple of 23",color="#e6edf3",fontsize=12)
ax.tick_params(colors="#e6edf3")
for spine in ax.spines.values():
spine.set_color("#738399")
ax.grid(axis="y",color="#526276",alpha=.25)
ax.set_axisbelow(True)
fig.suptitle("The first distance of 1 gives the smallest coefficient",color="#e6edf3",fontsize=17,y=.97)
fig.subplots_adjust(left=.10,right=.97,top=.89,bottom=.13)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
print(" n k relation test")
for n in [7,11,13,17,19,23,29,31]:
k, sign, m = smallest_rule(n)
symbol = "+" if sign == 1 else "-"
print(f"{n:2d} {k:2d} {10*k:2d} = {m*n:2d} {symbol} 1 a {symbol} {k}b")
tested = 0
rules = [n for n in range(3, 200) if gcd(n, 10) == 1]
for n in rules:
k, sign, m = smallest_rule(n)
assert 10*k == m*n + sign and gcd(k,n) == 1
assert all((10*j) % n not in (1,n-1) for j in range(1,k))
for number in range(10000):
a, b = divmod(number, 10)
assert (number % n == 0) == ((a + sign*k*b) % n == 0)
tested += 1
print(f"{len(rules)} rules x 10,000 integers = {tested:,} comparisons; mismatches: 0")
23의 최소 계수를 찾는 막대그래프. k가 1부터 7까지 증가할 때 10k와 가장 가까운 23의 배수의 거리는 10·3·7·6·4·9·1이며, 처음 거리가 1이 되는 k는 7이다.
n k relation test
7 2 20 = 21 - 1 a - 2b
11 1 10 = 11 - 1 a - 1b
13 4 40 = 39 + 1 a + 4b
17 5 50 = 51 - 1 a - 5b
19 2 20 = 19 + 1 a + 2b
23 7 70 = 69 + 1 a + 7b
29 3 30 = 29 + 1 a + 3b
31 3 30 = 31 - 1 a - 3b
79 rules x 10,000 integers = 790,000 comparisons; mismatches: 0
지금까지는 수의 자릿수를 이용하여 배수 판정식을 만드는 방법을 살펴보았습니다. 그러나 새로운 판정식이 원래 수의 배수 여부를 정확히 판단하려면 양방향의 관계가 성립해야 합니다.
2. 판정의 양방향 증명
이를 위해 두 가지를 확인하겠습니다.
첫째, 원래 수 $N$과 $kN$의 배수 여부가 일치하는지
둘째, $kN$과 새로운 판정식 $T$의 배수 여부가 일치하는지
입니다.
왜냐하면 우리는 원래 수$N$에다가 $k$배를 한(1) 뒤에 이 $kN$으로 새로운 판정식 $T$를 만들고 이 식을 기반으로 배수 여부를 판정(2)하고 있기 때문에, 1번과 2번이 증명이 되어야 하기 때문입니다.
두 관계가 모두 성립하면 $N$과 $T$의 배수 여부도 일치하므로, 새로운 배수 판정법이 정확하다는 사실을 증명할 수 있습니다.
먼저 원래 수 $N$과 $kN$의 배수 여부가 일치하는지를 증명해 보겠습니다.
$10k-mn=\varepsilon$라 쓰되, $\varepsilon$는 1 또는 $-1$입니다. 양쪽에 $N$을 곱하면
$kN$이 $n$의 배수이면 왼쪽 두 항은 모두 $n$의 배수입니다. 따라서 $N$ 또는 $-N$도 $n$의 배수입니다. 반대 방향, 즉 $N$이 배수이면 $kN$도 배수라는 것은 곱셈의 정의에서 바로 따릅니다. 결국
이번엔 $kN$과 새로운 판정식 $T$의 배수 여부가 일치하는지를 살펴보겠습니다.
처음 두 식을 가지고 정리를 해보면
첫 번째 식의 양변에 $k$를 곱합니다.
여기서 새로운 판정식을
로 정의했으므로,
가 나옵니다.
더하기의 경우에는 $kN=mna+T$, 빼기 경우에는 $kN=mna-T$입니다. $mna$는 $n$의 배수이므로
를 얻습니다.
따라서 결론적으로
즉, 원래 수 $N$이 $n$의 배수인지 판정식 $T$로 확인할 수 있음을 증명했습니다. 여기서 보존하는 것은 배수 여부입니다. $N$과 $T$의 나머지가 항상 같다는 뜻은 아닙니다. 두 수가 모두 $n$의 배수라면 나머지가 0으로 같고, 배수가 아닌 경우에는 나머지가 서로 다를 수 있습니다.
7·13·17·19에서 사용했던 판정이 모두 이 증명의 예입니다.
3. 서로소 조건 두 가지
찾은 $k$와 $n$은 자동으로 서로소입니다.
위에서 우리는 식 하나를 다음과 같이 놨습니다.
여기서 $k$와 $n$이 서로소가 아니라고 가정해 보겠습니다.
그렇다면 두 수를 모두 나누는 1보다 큰 양의 정수 $d$가 존재합니다.
이 경우 다음 두 관계도 반드시 성립합니다.
왜냐하면 어떤 수가 $d$의 배수라면, 거기에 정수를 곱한 결과 역시 $d$의 배수이기 때문입니다.
또한 두 수가 모두 $d$의 배수라면 그 차이도 $d$의 배수입니다.
따라서
그런데 처음 조건에 따르면
이므로
이 되어야 합니다.
하지만 1을 나누는 양의 정수는 1뿐입니다. 따라서
입니다.
즉, $k$와 $n$이 서로소라는 건 처음 관계식 자체가 보장합니다.
즉, 이 관계식을 만족하는 $k$는 반드시 $n$과 서로소입니다. 다만 $k$와 $n$이 서로소라는 조건만으로, 정해진 $k$에 대해 관계식이 성립하는 것은 아닙니다. 예를 들어 $k=1$, $n=7$은 서로소이지만 $10-7m=\pm1$을 만족하는 정수 $m$은 없습니다.
또한 10과 $n$도 서로소여야 합니다.
논리는 동일합니다.
이번에는 10과 $n$에 공약수 $d$가 있다고 가정하겠습니다.
그러면 역시
이므로
이 되어야 합니다.
따라서
이어야 합니다.
실제로 14를 예로 들어 보겠습니다.
그런데 10과 14는 모두 짝수입니다.
따라서 $10k$와 $14m$도 짝수이며, 짝수끼리의 차이는 반드시 짝수입니다.
아무리 $k$와 $m$을 바꾸어도 그 차이가 1이나 -1이 될 수 없습니다.
반면 23은 10과 서로소이므로
이라는 관계를 만들 수 있습니다.
다만 이 두 조건의 역할은 다릅니다.
| 조건 | 의미와 역할 |
|---|---|
| $\gcd(10,n)=1$ | $10k-mn=\pm1$ 형태의 관계식을 만들 수 있는 조건 |
| $\gcd(k,n)=1$ | $n\mid kN\iff n\mid N$이 성립하도록 보장하는 조건 |
여기서 중요한 사실이 하나 더 있습니다.
10과 $n$이 서로소이면, 반드시 $10k-mn=1$을 만족하는 정수 $k,m$이 존재합니다.
이는 베주 항등식에 따른 것으로, 단순한 필요조건이 아니라 충분조건이기도 합니다. $k$도 양의 정수로 선택할 수 있습니다.(베주 항등식은 이후에 나옵니다!)
따라서 다음과 같이 정리할 수 있습니다.
그리고 이런 $k$를 찾았다면 자동으로 $\gcd(k,n)=1$이므로, 앞서 증명한 배수 판정의 양방향 관계도 성립합니다.
7. 0·음수·고정점이 증명과 충돌하지 않는 이유
위 증명에는 결과 $T$가 양수여야 한다는 조건이 없습니다. $0=n\times0$이고 음의 배수도 정수 배수이므로, 21이 7의 규칙에서 0으로 바뀌거나 49가 $-14$로 바뀌어도 문제가 없습니다.
또한 증명은 $N$과 $T$의 크기를 비교하지 않습니다. 그래서 13의 규칙에서 $26\to26$이 되는 고정점도 가능하며, 이것은 규칙의 실패가 아닙니다. 판정하려는 성질을 유지하는 변환이지, 반드시 0으로 내려가는 절차가 아닙니다.
큰 수에서 대체로 줄어드는 이유는 따로 설명할 수 있습니다. $a\le N/10$, $b\le9$이므로
따라서 $N>10k$이면 새 수의 절댓값은 원래 수보다 작습니다. 반면 작은 수에 도착한 뒤에는 더 이상 줄어든다고 보장하지 않습니다. 그래서 작은 배수나 비배수를 알아보는 순간 멈추면 됩니다.
프로그램으로 여러 입력을 시험하면 부호를 반대로 옮기거나 자릿수를 잘못 나눈 구현을 찾을 수 있습니다. 그러나 유한한 범위에서 모두 맞았다는 사실은 모든 정수에 대한 증명이 아닙니다. 위의 항등식은 모든 입력을 포괄하고, 실험은 그 식을 옮긴 계산이 맞는지 점검합니다.
8. 세 자리씩 묶으면 7·11·13이 만납니다
한 자리씩 나누는 대신 세 자리씩 묶어보겠습니다. 핵심 수는
입니다. 따라서 법이 7, 11, 13 중 어느 것이든 $1000\equiv-1$입니다. 11의 교대합에서 10을 $-1$로 바꾸었듯이, 이번에는 1000을 $-1$로 바꿉니다.
오른쪽부터 세 자리 묶음을 $B_0,B_1,B_2,\ldots$라 하면
각 $B_i$는 0부터 999 사이의 정수입니다. 그러므로
123456333을 $123\,|\,456\,|\,333$으로 끊으면
0은 세 법 모두의 배수이므로 원래 수도 7·11·13의 배수입니다. 실제로 $123456333=1001\times123333$입니다. 반면 123456340에서는 교대합이 7이므로 7의 배수이지만 11·13의 배수는 아닙니다.
그림을 만든 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', 'weight +1': '가중치 +1', 'weight -1': '가중치 −1', 'Three-digit blocks: one rule for 7, 11, and 13': '세 자리 묶음: 7·11·13에 쓰는 하나의 규칙'}
_bfOriginalPixels = [1123, 523]
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch
number = 123456333
blocks = [123, 456, 333]
signed_sum = blocks[0] - blocks[1] + blocks[2]
assert signed_sum == 0
assert 1001 == 7*11*13
assert all(number % n == 0 for n in (7,11,13))
fig, ax = plt.subplots(figsize=(11.5, 5.3), facecolor="#0d1117")
ax.set_facecolor("#0d1117")
ax.set_xlim(-.1,11.5)
ax.set_ylim(-.5,4.9)
ax.axis("off")
for x, block, weight in zip([1.8,5.7,9.6],blocks,["+1","-1","+1"]):
ax.add_patch(FancyBboxPatch((x-1.1,2.3),2.2,1.0,boxstyle="round,pad=0.08",
facecolor="#173f50" if weight=="+1" else "#54333d",edgecolor="#738399"))
ax.text(x,2.8,f"{block:03d}",ha="center",va="center",color="#e6edf3",fontsize=28)
ax.text(x,3.75,f"weight {weight}",ha="center",color="#bdc7d5",fontsize=13)
ax.text(5.7,1.45,"333 - 456 + 123 = 0",ha="center",color="#91e0b2",fontsize=23)
ax.text(5.7,.4,"1000 = 1001 - 1 | 1001 = 7 x 11 x 13",ha="center",color="#e6edf3",fontsize=16)
fig.suptitle("Three-digit blocks: one rule for 7, 11, and 13",color="#e6edf3",fontsize=18,y=.97)
fig.subplots_adjust(left=.02,right=.98,top=.90,bottom=.02)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
for n in (7,11,13):
print(f"{number} = {n} x {number//n}")
123456333을 123·456·333으로 끊어 교대합을 구하면 0. 1001이 7·11·13의 곱이므로 세 수의 배수라는 결론을 얻는다.
123456333 = 7 x 17636619
123456333 = 11 x 11223303
123456333 = 13 x 9496641
교대합의 시작점을 왼쪽으로 바꾸면 묶음의 개수에 따라 전체 부호가 바뀔 수 있습니다. 배수 여부는 같지만, 나머지 값까지 비교할 때는 오른쪽 묶음부터 더하는 약속을 유지해야 합니다. 무엇이 보존되는지를 구분하는 습관이 여기서도 필요합니다.
9. 직접 바꾸어 확인해보기
법을 7·13·17·19·23으로 바꾸며 최소 계수와 부호를 비교해보세요. 13에서는 26을 입력하면 변환값이 그대로 돌아옵니다. 작은 수에 도착한 뒤에도 반드시 줄어드는 절차는 아니라는 점을 확인할 수 있습니다. 실험 결과의 일반적인 근거는 앞에서 증명한 항등식입니다.
이번에는 소수가 아닌 21을 법으로 넣어보세요. $20=21-1$이므로 7에서처럼 끝자리의 두 배를 빼는 규칙이 나옵니다. 875를 넣으면 $87-2\times5=77$입니다. 77은 7의 배수지만 21의 배수는 아니므로, 이번 판정은 탈락입니다. 같은 규칙을 썼다고 검사하는 법까지 7로 바뀐 것은 아닙니다. 규칙이 존재하는 조건과 마지막 답을 읽는 기준을 나누어 확인해보세요.
규칙을 직접 만드는 실험
10k가 법의 배수와 정확히 1 차이 나는 첫 k를 찾습니다.
10. 마무리
배수 판정은 자릿값을 나머지가 같은 간단한 수로 바꾸는 일에서 출발합니다. 3·9에서는 $10$이 1, 11에서는 $-1$과 합동입니다. 4·8에서는 100이나 1000이 0과 합동이어서 앞부분이 사라집니다.
7·13·17에서는 한 번 더 움직여 10의 배수를 검사할 수의 배수 바로 옆에 놓았습니다. 그 관계식이 계수와 부호를 정하고, 원래 수와 바뀐 수 사이의 양방향 판정을 증명해주었습니다.
이제 남은 질문은 규칙을 찾는 체계적인 방법입니다. 23에서는 70까지 적어 찾았지만 큰 법에서도 같은 일을 효율적으로 할 수 있을까요? 서로소이면 계수가 존재한다는 약속은 왜 맞을까요? 다음 편에서는 최대공약수를 구하는 익숙한 나눗셈을 끝까지 따라가며 그 답을 찾겠습니다.
더 읽기: NRICH의 시계와 합동식 설명.