나머지로 불가능을 증명하다: 답을 찾지 않고도 답이 없음을 아는 방법
《나머지에서 시작하는 정수론》 · 7/8편 · 나머지로 불가능을 증명하다
0. 서론: 나머지는 정보를 버리지만, 모순은 남깁니다
정수 $x,y$가 다음 식을 만족할 수 있을까요?
$$x^2+y^2=3$$
작은 수를 넣어보면 답이 보이지 않습니다. 하지만 몇 개를 넣어 답이 나오지 않았다는 사실만으로는 모든 정수에서 불가능하다고 결론 내릴 수 없습니다. 음수까지 포함하면 확인해야 할 정수가 무한히 많기 때문입니다.
그렇다면 무한히 많은 정수를 하나하나 확인하지 않고도 답이 없다는 사실을 증명할 방법은 없을까요?
여기서 나머지를 이용해보겠습니다.
앞 편에서는 여러 나머지 조건을 합쳐 그 조건을 만족하는 수를 찾아냈습니다. 이번에는 반대로 답이 존재한다면 반드시 만족해야 할 나머지 조건을 찾아, 그 조건을 만족하는지 아닌지 살펴보겠습니다.
나머지를 이용하면 무한히 많은 정수를 몇 가지 경우로 나누어 생각할 수 있습니다.
예를 들어 모든 정수를 4로 나누면 나머지는 반드시 0, 1, 2, 3 중 하나입니다. 아무리 큰 수라도 이 네 가지 경우를 벗어나지 않습니다.
더욱 흥미로운 점은 어떤 수를 제곱한 뒤의 나머지는, 처음 나머지를 제곱해 구할 수 있다는 것입니다.
예를 들어 3과 7은 모두 4로 나누면 나머지가 3입니다. 두 수를 각각 제곱하면 9와 49가 되는데, 모두 4로 나누었을 때 나머지가 1입니다.
처음 나머지인 3을 제곱한 $3^2=9$를 4로 나누어도 나머지가 1입니다.
왜 그럴까요? 두 수의 차이인 $7-3=4$가 4의 배수인 것처럼, 제곱한 값의 차이인 $49-9=40$도 4의 배수이기 때문입니다. 일반적으로도 두 수의 차이가 어떤 수의 배수라면, 제곱한 값의 차이 역시 그 수의 배수가 됩니다.
즉, 처음에 나머지가 같은 수들은 제곱한 뒤에도 서로 나머지가 같습니다. 따라서 같은 나머지를 가진 무한히 많은 정수를 일일이 제곱하지 않고도, 가능한 나머지만 조사하면 제곱한 결과에서 나올 수 있는 나머지를 모두 확인할 수 있는 것이지요.
물론 어떤 수로 나누느냐에 따라 얻을 수 있는 정보는 달라집니다. 먼저 법 4의 제곱 나머지 표를 만든 뒤, 그 표로 원래 식을 검사하겠습니다. 법 2·3과도 비교하면서, 어떤 정보가 남고 어떤 정보가 부족한지 살펴보겠습니다.
그런데 여기서 먼저 확인해야 할 것이 있습니다.
나머지만 조사해서 답이 없다는 결론을 내린다면, 원래 정수 방정식에도 정말 해가 없다고 말할 수 있을까요?
나머지는 원래 정수의 정보를 일부만 남기는데, 어떻게 이것만으로 불가능하다는 사실을 증명할 수 있는지부터 확인해보겠습니다.
1. 정수해가 있으면 모든 나머지 검사도 통과해야 합니다
먼저 왜 나머지에서 모순을 찾으면 원래 식까지 배제할 수 있는지 확인하겠습니다.
정수 $x,y$에 대해 $x^2+y^2=3$이 성립한다고 가정해봅시다.
그렇다면 왼쪽의 계산 결과도 3이고, 오른쪽도 3입니다. 양쪽이 같은 수이므로 어떤 양의 정수 $m$으로 나누더라도 나머지가 같아야 합니다.
따라서 반드시
$$x^2+y^2\equiv3\pmod m$$
이 성립합니다.
이것은 합동식의 정의와도 일치합니다. 두 수의 차이가 0이므로, 어떤 양의 정수로 나누어도 나머지가 같기 때문입니다.
그런데 나머지가 맞는 수를 찾았으면 원래 식의 답도 찾은 걸까요? 그 방향은 일반적으로 성립하지 않습니다. 나머지가 같아도 두 수 자체가 같지는 않습니다. $1\equiv5\pmod4$이지만 $1=5$는 아닙니다.
그렇다면 나머지가 정보를 버리는데도 왜 해가 없다는 결론에는 쓸 수 있을까요?
실제 등식의 해는 반드시 나머지 검사도 통과해야 하기 때문입니다. 통과해야 할 검사에조차 통과할 수 없다면 실제 해일 가능성도 사라집니다. 따라서 논리의 방향을 다음과 같이 기억하면 됩니다.
따라서 한 법에서라도 가능한 나머지가 없으면 원래 정수해도 없습니다.
우리가 확인하는 것은 ‘몇 개의 수를 넣어도 안 되더라’가 아닙니다. 어느 정수를 넣든 들어가야 할 나머지 칸을 모두 살펴도 자리가 없다는 것입니다. 이 차이가 뒤의 작은 표를 증명으로 쓸 수 있게 해줍니다.
이를 필요조건이라고 합니다. 원래 문제의 해가 되려면 반드시 충족해야 하는 조건입니다. 필요조건을 어겼을 때에는 탈락을 확정할 수 있지만, 필요조건 하나를 통과했다고 최종 합격을 선언할 수는 없습니다.
예를 들어 후보 $(x,y)=(1,0)$은 $x^2+y^2\equiv3\pmod2$를 만족합니다. 양쪽이 모두 홀수이기 때문입니다. 하지만 원래 등식에 넣으면 $1^2+0^2=1$이어서 3이 아닙니다. 같은 후보가 나머지 검사에는 합격하면서 원래 등식에는 탈락할 수 있습니다. 검사가 원래 수의 차이에서 법의 배수만큼을 구별하지 않기 때문입니다.
이 방향을 불가능 증명에 쓰면 다음과 같습니다.
3편에서 $6x-9q=1$이 불가능하다고 할 때에도 같은 생각을 사용했습니다. 왼쪽은 법 3에서 항상 0인데 오른쪽은 1입니다. 이번에는 제곱이 어떤 나머지들만 가질 수 있는지를 조사합니다.
2. 제곱수의 나머지 표를 만드는 법
법 4에서 정수 $x$는 다음 네 형태 중 하나입니다.
여기서 $q$는 정수 몫이고 $r$은 0·1·2·3 중 하나인 나머지입니다. 예를 들어 $x=14$이면 $q=3,r=2$이고, $x=-1$이면 $q=-1,r=3$입니다.
14의 경우 $14^2=196$을 직접 4로 나누면 0이 남습니다. 이 값은 나머지 $r=2$만 제곱한 $2^2=4$의 나머지와 같습니다. 일반 전개는 이 일치가 모든 정수에서 성립하는 이유를 확인합니다.
시계 눈금만 읽으면 몇 바퀴를 돌았는지는 남지 않았지요. 여기서도 196과 4라는 실제 제곱의 크기는 다르지만, 법 4의 마지막 눈금은 둘 다 0입니다. 앞으로 만드는 표의 마지막 열은 그 눈금만 기록합니다. 그 열에서 0을 보았다고 원래 제곱수가 0이었다는 뜻은 아닙니다.
몫이 바뀌어도 제곱의 나머지가 같다는 말을 직접 확인해볼까요? 몫이 들어 있는 부분과 나머지만 있는 부분을 구별하려고, 앞의 식을 제곱해 전개하겠습니다. 제곱하면
앞의 두 항은 모두 4의 배수이므로 $x^2\equiv r^2\pmod4$입니다. 따라서 무한히 많은 $x$를 직접 제곱할 필요 없이 0·1·2·3만 제곱하면 됩니다.
$q$가 아무리 커도, 음수여도 이 배수 관계는 바뀌지 않습니다.
| $x$의 법 4 나머지 | 대표값의 제곱 | $x^2$의 법 4 나머지 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 4 | 0 |
| 3 | 9 | 1 |
표의 마지막 열만 읽어보세요. 입력 나머지는 네 가지였지만, 제곱한 뒤에는 0과 1 두 가지밖에 남지 않았습니다. 우리가 찾던 제약이 바로 이것입니다.
뒤에서 바로 사용할 수 있도록 결론을 묶어두겠습니다.
표의 0·2행은 짝수 전체를, 1·3행은 홀수 전체를 담당합니다. 이 두 묶음만으로 뒤의 제곱합을 검사할 수 있습니다.
이 표에는 음수도 포함됩니다. 예를 들어 $-1\equiv3\pmod4$이므로 제곱의 나머지는 마지막 행에서 1입니다. 더 일반적으로 모든 정수가 어떤 나머지 행에 들어가므로, 표는 양수만 시험한 경험칙이 아닙니다.
어떤 법에서 제곱으로 나타날 수 있는 나머지를 그 법의 제곱잉여라고 부르기도 합니다. 여기서는 이름을 몰라도 표를 만들고 읽을 수 있으면 충분합니다. 중요한 것은 “법 4에서 제곱은 0 또는 1”이라는 제한입니다.
같은 작업을 법 3에서 하면
| $x$의 법 3 나머지 | 0 | 1 | 2 |
|---|---|---|---|
| $x^2$의 법 3 나머지 | 0 | 1 | 1 |
입니다. 법 3과 법 4에서는 제곱의 가능한 나머지가 모두 0과 1이고, 두 나머지를 더해 얻는 값도 0·1·2로 같습니다. 하지만 비교할 오른쪽 3의 나머지는 다릅니다. 따라서 제곱 나머지 목록이 같다는 이유만으로 모순 여부까지 같다고 말할 수는 없습니다.
법 3 표의 중간 계산도 적으면 $0^2=0=3\times0+0$, $1^2=1=3\times0+1$, $2^2=4=3\times1+1$입니다. 제곱하기 전에는 세 나머지지만 제곱한 뒤에는 0 또는 1로 줄어듭니다. 두 표가 모두 0·1을 준다고 해도 오른쪽 3의 나머지는 법 3에서 0, 법 4에서 3입니다. 비교할 상대의 나머지까지 함께 확인해야 합니다.
법 2에서는 $0^2\equiv0$, $1^2\equiv1\pmod2$이므로 가능한 제곱 나머지가 0·1입니다. 아래 그림은 지금 확인한 법 2·3·4의 표만 나란히 놓은 것입니다. 각 행은 그 법의 나머지 대표들을 모두 제곱해 얻습니다.
그림을 만든 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', 'Choose a modulus that sharply restricts squares': '제곱수의 나머지를 강하게 제한하는 법을 고른다'}
_bfOriginalPixels = [1129, 565]
import matplotlib.pyplot as plt
mods=[2,3,4]
fig,ax=plt.subplots(figsize=(11.8,5.8),facecolor="#0d1117"); ax.axis("off")
rows=[]
for m in mods:
residues=sorted({x*x%m for x in range(m)})
rows.append([m,", ".join(map(str,residues)),", ".join(str((x*x)%m) for x in range(m))])
table=ax.table(cellText=rows,colLabels=["Modulus", "Possible square residues", "Squares of 0, 1, ... , m-1"],loc="center",cellLoc="center",colWidths=[.12,.35,.53])
table.auto_set_font_size(False); table.set_fontsize(13); table.scale(1,2.4)
for (r,c),cell in table.get_celld().items():
cell.set_facecolor("#173f50" if r==0 else "#1c2534"); cell.set_edgecolor("#526276"); cell.set_text_props(color="#e6edf3")
fig.suptitle("Choose a modulus that sharply restricts squares",color="#e6edf3",fontsize=18)
fig.subplots_adjust(left=.03,right=.97,top=.84,bottom=.04)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
assert {x*x%4 for x in range(4)}=={0,1}
3. 왜 법 2에서는 부족하고 법 4에서는 될까요
먼저 $x^2+y^2=3$을 법 2에서 보겠습니다. 제곱의 나머지는 0 또는 1입니다. 오른쪽 3은 1과 합동이므로, 왼쪽에서도 1을 만들 수 있는지 봅니다.
가능합니다. 법 2 검사는 $x,y$ 중 하나가 짝수이고 다른 하나가 홀수여야 한다는 조건만 줍니다. 이 조건은 중요하지만 아직 모순이 아닙니다.
홀짝으로는 아직 결론이 나지 않았습니다. 그렇다면 짝수를 법 4의 나머지 0과 2로, 홀수를 나머지 1과 3으로 더 나누어보면 어떨까요? 앞의 표에서 4로 나눈 나머지가 네 가지였지요.
이번에는 같은 방정식을 법 4로 검사하겠습니다. 비교 대상인 오른쪽 3은 나머지가 3입니다. 왼쪽에서 그 나머지를 만들 수 있는지만 보면 됩니다. 법 4에서는 제곱의 나머지가 0 또는 1이므로 첫 제곱에서 하나, 둘째 제곱에서 하나를 골라 더해봅시다. 가능한 선택을 빠짐없이 적으면
가능한 나머지는 0·1·2뿐입니다. 오른쪽 3은 법 4에서 3이므로 어떤 경우에도 같아질 수 없습니다.
이 네 계산은 $x,y$ 자체를 0이나 1로 제한한 것이 아닙니다. $x^2,y^2$ 각각의 나머지가 두 종류뿐이라는 뜻입니다. 예를 들어 $x=100$, $y=-37$이어도 제곱의 법 4 나머지는 각각 0과 1이므로 $0+1$ 경우에 들어갑니다. 입력의 크기와 부호가 사라져도, 해가 있다면 만족해야 할 제약은 남습니다.
따라서 정수해는 없습니다. $x,y$를 얼마나 크게 잡든, 음수로 잡든, 네 나머지 경우 중 하나에 들어가므로 이 결론을 피할 수 없습니다.
법 2에서는 가능한 제곱합 1과 오른쪽 3이 모두 홀수여서 구별되지 않습니다. 법 4에서는 둘이 다른 나머지가 됩니다. 홀수의 제곱이 반드시 1이라는 정보 덕분에 제곱합이 도달하지 못하는 3을 골라낼 수 있습니다.
그림에서 두 법이 나누는 칸을 비교해봅시다.
그림을 만든 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', 'Residue of x': 'x의 나머지', 'Residue of y': 'y의 나머지', 'mod 2: target 3 becomes 1': '법 2: 목표 3의 나머지는 1', 'mod 4: target 3 becomes 3': '법 4: 목표 3의 나머지는 3', 'Modulo 4 distinguishes square sums that parity cannot separate': '법 4는 홀짝만으로 구별하지 못한 제곱합을 구별한다', 'Cells contain (x^2 + y^2) mod m. Green cells pass the target test; modulo 4 there are none.': '칸의 값은 (x^2 + y^2)를 m으로 나눈 나머지이다.\n초록 칸은 통과하며, 법 4에는 통과하는 칸이 없다.'}
_bfOriginalPixels = [1304, 707]
from math import gcd, isqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib.patches import Rectangle, Circle, FancyBboxPatch, FancyArrowPatch
BG = "#101827"
PANEL = "#1d2b40"
INK = "#edf3fc"
MUTED = "#c0cede"
BLUE = "#8fdcff"
GREEN = "#91e0b2"
GOLD = "#ffd18c"
RED = "#ffaaaa"
LINE = "#667a96"
def canvas(rows=1, cols=1, size=(13.6, 6.8), title=""):
fig, axes = plt.subplots(rows, cols, figsize=size, facecolor=BG,
squeeze=False)
axes = axes.ravel().tolist()
for ax in axes:
ax.set_facecolor(BG)
ax.tick_params(colors=INK, labelsize=12)
for spine in ax.spines.values():
spine.set_color(LINE)
fig.suptitle(title, fontsize=18, color=INK, y=.98)
fig.subplots_adjust(left=.07, right=.97, top=.86, bottom=.13,
wspace=.34, hspace=.48)
return fig, axes
def off(ax):
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.axis("off")
def text(ax, x, y, value, color=INK, size=12, **kwargs):
defaults = dict(ha="center", va="center", fontsize=size, color=color,
transform=ax.transAxes, linespacing=1.35)
defaults.update(kwargs)
return ax.text(x, y, value, **defaults)
def card(ax, x, y, width, height, value, edge=LINE, color=INK, size=14):
ax.add_patch(FancyBboxPatch((x, y), width, height,
boxstyle="round,pad=0.012", transform=ax.transAxes,
facecolor=PANEL, edgecolor=edge, linewidth=1.4))
text(ax, x+width/2, y+height/2, value, color=color, size=size)
def arrow(ax, start, end, color=BLUE):
ax.add_patch(FancyArrowPatch(start, end, transform=ax.transAxes,
arrowstyle="-|>", mutation_scale=18,
color=color, linewidth=1.7))
def caption(fig, value):
fig.text(.5, .035, value, ha="center", va="center",
color=MUTED, fontsize=12)
fig,axes=canvas(1,2,size=(13.8,7.2),title="Modulo 4 distinguishes square sums that parity cannot separate")
for ax,m in zip(axes,[2,4]):
data=np.array([[(x*x+y*y)%m for x in range(m)] for y in range(m)])
hit=data==(3%m)
ax.imshow(hit,cmap=ListedColormap([PANEL,"#285a48"]),vmin=0,vmax=1)
for i in range(m):
for j in range(m):
ax.text(j,i,str(data[i,j]),ha="center",va="center",color=GREEN if hit[i,j] else INK,fontsize=20)
ax.set_xticks(range(m));ax.set_yticks(range(m))
ax.set_xlabel("Residue of x",color=INK,fontsize=12)
ax.set_ylabel("Residue of y",color=INK,fontsize=12)
ax.set_title(f"mod {m}: target 3 becomes {3%m}",color=INK,fontsize=16,pad=16)
ax.tick_params(length=0,pad=12)
assert bool(hit.any())==(m==2)
caption(fig,"Cells contain (x^2 + y^2) mod m. Green cells pass the target test; modulo 4 there are none.")
fig.subplots_adjust(bottom=.19)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
이번에는 법 4의 네 경우로 이미 모순을 얻었으므로 더 큰 법을 조사할 필요가 없습니다.
이 증명은 3이라는 수에만 해당하지 않습니다. $x^2+y^2$는 법 4에서 3이 될 수 없으므로, $4k+3$ 형태의 정수는 두 정수의 제곱합으로 표현할 수 없습니다. 7·11·15·19에도 같은 결론을 적용할 수 있습니다. 여기서 $k$는 정수이며, 양수로 표현할 경우 적절한 0 이상의 값을 택하면 됩니다.
오른쪽에 놓인 정수를 $N$이라고 쓰겠습니다. 실제로 쓸 수 있는 불가능 판정을 한 줄로 적으면 다음과 같습니다.
역으로 $N\not\equiv3\pmod4$라는 이유만으로 해가 있다고 말할 수는 없습니다. 이 규칙은 불가능한 한 종류를 통째로 제외한 것이지, 남은 모든 종류에 해를 만들어준 것은 아닙니다. 다음의 6이 바로 그 차이를 보여줍니다.
같은 법 4가 모든 제곱합을 판정해주지는 않습니다. $x^2+y^2=6$은 법 4에서 오른쪽이 2이고, $1+1=2$가 가능하므로 통과합니다.
법 4에서 통과한 문제에 왜 법 9를 더 시도할까요? 지금 오른쪽 6에는 3이 들어 있으니, 3의 배수들을 한층 더 구별하는 9로 나누어볼 수 있습니다. 이 선택이 성공하는지는 계산해봐야 합니다. 먼저 법 9의 표를 직접 만들어 빠진 입력이 없는지 확인하고, 그다음 두 출력을 더해 6을 만들 수 있는지 살펴보겠습니다.
법 9에서는 0부터 8까지를 제곱한 나머지가 차례로 $0,1,4,0,7,7,0,4,1$입니다. 따라서 가능한 제곱 나머지는 $0,1,4,7$입니다. 이 네 가지 중 두 개를 더해 법 9에서 6을 만들 수 있을까요? 아래 표에서 각 입력의 제곱 나머지를 먼저 확인한 뒤, 필요한 짝이 있는지 찾아보겠습니다.
| $r$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| $r^2$ | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 |
| 법 9 나머지 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 |
예를 들어 $16=9+7$, $25=18+7$, $49=45+4$, $64=63+1$로 각 칸을 구합니다. 여러 입력에서 같은 결과가 나오므로, 가능한 제곱 나머지를 0·1·4·7 네 가지로 묶을 수 있습니다. 이제 이 네 가지가 두 제곱의 합에 어떤 제한을 주는지 보겠습니다.
제곱합의 모든 조합을 더하는 대신, 하나를 정한 뒤 짝이 될 값이 있는지 찾아보겠습니다. 법 9에서 첫 번째 제곱의 나머지가 $0,1,4,7$이면, 합을 6으로 만들기 위해 필요한 두 번째 제곱의 나머지는 각각 $6,5,2,8$입니다. 예를 들어 첫 값이 1이면 둘째가 5여야 합이 6이고, 첫 값이 4이면 둘째가 2여야 합니다. 어느 값도 가능한 제곱 나머지 목록에 없습니다.
필요한 짝을 표의 같은 행에서 비교해봅시다. 오른쪽 후보가 제곱 나머지 0·1·4·7 중에 없으므로 네 행이 모두 막힙니다.
| 첫 제곱의 나머지 | 합이 6이 되려면 필요한 나머지 | 제곱으로 가능한가? |
|---|---|---|
| 0 | 6 | 불가능 |
| 1 | 5 | 불가능 |
| 4 | 2 | 불가능 |
| 7 | 8 | 불가능 |
마지막 경우는 $6-7=-1\equiv8\pmod9$이므로 8입니다. 이 네 경우가 전부인 이유는 첫 번째 제곱의 가능한 나머지가 네 종류뿐이기 때문입니다. 첫 번째 값을 하나 고르면 둘째에 필요한 값이 하나씩 정해지고, 그 값이 제곱 나머지 목록에 없는지 검사했습니다. 무한히 많은 정수쌍을 네 갈래로 나누어 전부 배제한 것입니다.
그림을 만든 Python 코드
from pathlib import Path as _bfPath
from matplotlib.font_manager import FontProperties as _bfFontProperties
from matplotlib.text import Text as _bfText
from matplotlib.ticker import Formatter as _bfFormatter
from io import BytesIO as _bfBytesIO
from IPython.display import display as _bfDisplay, Image as _bfImage
class _BilingualFormatter(_bfFormatter):
def __init__(self, base, labels):
self.base, self.labels = base, labels
def set_axis(self, axis):
super().set_axis(axis)
self.base.set_axis(axis)
def set_locs(self, locs):
super().set_locs(locs)
self.base.set_locs(locs)
def __call__(self, value, pos=None):
raw=self.base(value,pos)
translated=self.labels.get(raw)
return translated+'\n'+raw if translated else raw
def get_offset(self):
return self.base.get_offset()
def _apply_bilingual_figure(_bfFigure, _bfLabels, _bfOriginalPixels):
if getattr(_bfFigure, '_bilingual_complete', False):
return
_bfFont = _bfPath('C:/Windows/Fonts/malgun.ttf')
if not _bfFont.is_file():
raise RuntimeError('Korean/English figures require the Malgun Gothic font.')
_bfFamily = _bfFontProperties(fname=str(_bfFont)).get_name()
# Keep the delivered original's aspect ratio. A bilingual label must not
# stretch the chart, its grid cells, cards or geometry vertically.
_bfFigure.set_size_inches(_bfOriginalPixels[0] / 80,
_bfOriginalPixels[1] / 80, forward=True)
_bfFigure._bilingual_original_pixels = tuple(_bfOriginalPixels)
_bfFigure.canvas.draw()
for _bfAxes in _bfFigure.axes:
for _bfAxis in (_bfAxes.xaxis,_bfAxes.yaxis):
if any(_bfTick.get_text() in _bfLabels for _bfTick in _bfAxis.get_majorticklabels()):
_bfAxis.set_major_formatter(_BilingualFormatter(_bfAxis.get_major_formatter(),_bfLabels))
_bfTexts = list(_bfFigure.findobj(_bfText))
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
_bfTexts.extend(_bfCell.get_text() for _bfCell in _bfTable.get_celld().values())
_bfSeen = set()
_bfChanged = []
for _bfItem in _bfTexts:
if id(_bfItem) in _bfSeen:
continue
_bfSeen.add(id(_bfItem))
_bfOriginal = _bfItem.get_text()
_bfKorean = _bfLabels.get(_bfOriginal)
if _bfKorean:
_bfItem.set_text(_bfKorean + '\n' + _bfOriginal)
_bfItem.set_linespacing(1.05)
_bfChanged.append((_bfKorean, _bfOriginal))
_bfProperties = _bfItem.get_fontproperties().copy()
_bfProperties.set_file(None)
_bfProperties.set_family([_bfFamily, 'DejaVu Sans'])
_bfItem.set_fontproperties(_bfProperties)
assert _bfChanged, 'Every figure must contain meaningful Korean/English labels.'
# Bilingual column headers must stay inside their original table cells.
_bfFigure.canvas.draw()
_bfRenderer = _bfFigure.canvas.get_renderer()
for _bfAxes in _bfFigure.axes:
for _bfTable in _bfAxes.tables:
for _bfCell in _bfTable.get_celld().values():
_bfCellText = _bfCell.get_text()
_bfBox = _bfCellText.get_window_extent(_bfRenderer)
_bfCellBox = _bfCell.get_window_extent(_bfRenderer)
if _bfBox.width and _bfBox.height:
_bfFit = min(1, .92*_bfCellBox.width/_bfBox.width,
.88*_bfCellBox.height/_bfBox.height)
_bfCellText.set_fontsize(_bfCellText.get_fontsize()*_bfFit)
if _bfAxes.get_title():
_bfAxes.set_title(_bfAxes.get_title(), pad=6)
_bfFigure.canvas.draw()
# Keep subplot headings clear of the shared two-line title, moving the
# subplot boundary only as much as the actual rendered text requires.
if _bfFigure._suptitle is not None:
_bfTopTitle = _bfFigure._suptitle.get_window_extent(_bfRenderer)
for _bfAxes in _bfFigure.axes:
if not _bfAxes.get_title():
continue
_bfHeading = _bfAxes.title.get_window_extent(_bfRenderer)
_bfGap = _bfHeading.y1 - (_bfTopTitle.y0 - 9)
if _bfGap > 0:
_bfPosition = _bfAxes.get_position(original=True)
_bfAxes.set_position([_bfPosition.x0, _bfPosition.y0,
_bfPosition.width, _bfPosition.height - _bfGap/_bfFigure.bbox.height])
_bfFigure._bilingual_labels = _bfChanged
_bfFigure._bilingual_complete = True
def _display_bilingual_figure(_bfFigure):
# A fixed full canvas avoids notebook's automatic tight crop changing the
# aspect ratio after titles and labels become bilingual. This is a fresh
# Matplotlib rendering, at exactly twice the original pixel dimensions.
global _bfDisplayedFigure
_bfDisplayedFigure = _bfFigure
_bfBuffer = _bfBytesIO()
_bfFigure.savefig(_bfBuffer, format='png', dpi=160, bbox_inches=None,
pad_inches=0, facecolor=_bfFigure.get_facecolor())
_bfDisplay(_bfImage(data=_bfBuffer.getvalue()))
plt.close(_bfFigure)
_bfLabels = {'Dividend': '피제수', 'Divisor': '제수', 'Quotient': '몫', 'Remainder': '나머지', '3r mod 7': '3r의 법 7 나머지', 'then x5': '그다음 5를 곱하기', 'k, gcd(k,12)=1': '12와 서로소인 k', '5k mod 12': '5k의 법 12 나머지', 'Modulus': '법', 'Other factors': '나머지 법들의 곱', 'Inverse': '역원', 'Unit part': '단위 부품', 'Target': '목표 나머지', 'Contribution': '기여값', 'Possible square residues': '가능한 제곱 나머지', 'Squares of 0, 1, ... , m-1': '0·1·…·(m−1)의 제곱 나머지', 'PASS': '통과', 'IMPOSSIBLE': '불가능', 'mod 2': '법 2', 'mod 3': '법 3', 'mod 4': '법 4', 'mod 5': '법 5', 'mod 7': '법 7', 'mod 8': '법 8', 'mod 9': '법 9', 'mod 11': '법 11', 'mod 12': '법 12', 'mod 105': '법 105', 'mod 4: 6 leaves remainder 2': '법 4: 6의 나머지는 2', '1 + 1 = 2 is a possible square sum.': '1 + 1 = 2는 가능한 제곱합이다.', 'This test passes; existence is not proved.': '이 검사는 통과한다. 해의 존재는 아직 증명되지 않았다.', 'Second square residue': '두 번째 제곱 나머지', 'First square residue': '첫 번째 제곱 나머지', 'mod 9: none of the 16 cells contains 6': '법 9: 16개 칸 어디에도 6이 없다', 'For a sum of 6, modulo 9 removes the candidates left by modulo 4': '제곱합 6: 법 4를 통과한 후보도 법 9에서 탈락한다', 'Every cell is a possible sum of two square residues modulo 9. All combinations have been covered.': '각 칸은 법 9에서 가능한 두 제곱 나머지의 합이다.\n모든 조합을 확인했다.'}
_bfOriginalPixels = [1273, 707]
from math import gcd, isqrt
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib.patches import Rectangle, Circle, FancyBboxPatch, FancyArrowPatch
BG = "#101827"
PANEL = "#1d2b40"
INK = "#edf3fc"
MUTED = "#c0cede"
BLUE = "#8fdcff"
GREEN = "#91e0b2"
GOLD = "#ffd18c"
RED = "#ffaaaa"
LINE = "#667a96"
def canvas(rows=1, cols=1, size=(13.6, 6.8), title=""):
fig, axes = plt.subplots(rows, cols, figsize=size, facecolor=BG,
squeeze=False)
axes = axes.ravel().tolist()
for ax in axes:
ax.set_facecolor(BG)
ax.tick_params(colors=INK, labelsize=12)
for spine in ax.spines.values():
spine.set_color(LINE)
fig.suptitle(title, fontsize=18, color=INK, y=.98)
fig.subplots_adjust(left=.07, right=.97, top=.86, bottom=.13,
wspace=.34, hspace=.48)
return fig, axes
def off(ax):
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.axis("off")
def text(ax, x, y, value, color=INK, size=12, **kwargs):
defaults = dict(ha="center", va="center", fontsize=size, color=color,
transform=ax.transAxes, linespacing=1.35)
defaults.update(kwargs)
return ax.text(x, y, value, **defaults)
def card(ax, x, y, width, height, value, edge=LINE, color=INK, size=14):
ax.add_patch(FancyBboxPatch((x, y), width, height,
boxstyle="round,pad=0.012", transform=ax.transAxes,
facecolor=PANEL, edgecolor=edge, linewidth=1.4))
text(ax, x+width/2, y+height/2, value, color=color, size=size)
def arrow(ax, start, end, color=BLUE):
ax.add_patch(FancyArrowPatch(start, end, transform=ax.transAxes,
arrowstyle="-|>", mutation_scale=18,
color=color, linewidth=1.7))
def caption(fig, value):
fig.text(.5, .035, value, ha="center", va="center",
color=MUTED, fontsize=12)
fig,axes=canvas(1,2,size=(14.0,7.2),title="For a sum of 6, modulo 9 removes the candidates left by modulo 4")
ax=axes[0]
off(ax)
card(ax,.06,.69,.88,.16,"mod 4: 6 leaves remainder 2",edge=BLUE,size=16)
for x,value in zip([.22,.50,.78],["1","+","1"]):text(ax,x,.47,value,color=GREEN,size=26)
text(ax,.5,.28,"1 + 1 = 2 is a possible square sum.",color=GREEN,size=15)
text(ax,.5,.10,"This test passes; existence is not proved.",color=GOLD,size=13)
ax=axes[1]
squares=[0,1,4,7]
needed=[(6-q)%9 for q in squares]
data=np.array([[(a+b)%9 for b in squares] for a in squares])
ax.imshow(np.zeros_like(data),cmap=ListedColormap([PANEL]))
for i in range(4):
for j in range(4):
ax.text(j,i,str(data[i,j]),ha="center",va="center",color=INK,fontsize=20)
ax.set_xticks(range(4),[str(x) for x in squares]);ax.set_yticks(range(4),[str(x) for x in squares])
ax.set_xlabel("Second square residue",color=INK,fontsize=12)
ax.set_ylabel("First square residue",color=INK,fontsize=12)
ax.set_title("mod 9: none of the 16 cells contains 6",color=INK,fontsize=14,pad=16)
caption(fig,"Every cell is a possible sum of two square residues modulo 9. All combinations have been covered.")
assert needed==[6,5,2,8] and set(needed).isdisjoint(squares)
assert not np.any(data==6) and (1+1)%4==6%4
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
가능한 두 제곱 나머지를 모두 조합한 그림에서도 합의 나머지 6은 나타나지 않습니다. 법 4에서는 남았던 후보가 법 9에서는 사라지는 이유를 각 조합에서 확인할 수 있습니다.
4. 법 3으로 같은 문제를 보면 무엇이 남을까요
이번에는 $x^2+y^2=3$을 법 3으로 보겠습니다. 오른쪽은 0과 합동입니다. 제곱의 나머지는 0 또는 1이고,
인 경우가 있으므로 표만 보고 즉시 불가능하다고 말할 수는 없습니다. 법 4에서는 오른쪽의 나머지가 가능한 합 목록에서 빠졌지만, 법 3에서는 포함되어 있습니다.
여기서 “가능한 경우가 있네” 하고 멈출 필요는 없습니다. 어떤 경우만 살아남았는지 더 읽어보겠습니다. 0 또는 1 두 개를 더해서 법 3에서 0이 되려면 둘 다 0이어야 합니다. 따라서 $x^2,y^2$가 모두 3의 배수이고, 제곱 나머지 표에 의해 $x,y$ 자체도 3의 배수입니다.
합 네 가지는 $0+0=0$, $0+1=1$, $1+0=1$, $1+1=2$입니다. 법 3에서 이 중 0과 합동인 것은 첫 경우뿐입니다. 따라서 $x^2\equiv y^2\equiv0\pmod3$입니다. 앞의 법 3 제곱표에서 출력 0을 내는 입력 행은 0 하나뿐이므로 $x\equiv y\equiv0\pmod3$까지 얻습니다. “제곱이 3의 배수”에서 “원래 수가 3의 배수”로 옮길 때에도 그 표를 한 번 더 읽었습니다.
라고 쓸 수 있습니다. 여기서 두 새 문자는 각각 원래 변수를 3으로 나눈 정수 몫입니다. 이제 나머지만 보던 검사를 잠시 멈추고, 이 배수 형태를 원래 등식에 넣어보겠습니다. 3의 배수를 제곱하면 9의 배수가 된다는 더 강한 조건을 사용할 수 있습니다.
왼쪽은 9의 배수인데 오른쪽은 아닙니다. 여기서 모순을 얻을 수 있습니다.
즉 법 3의 첫 검사는 통과했지만, 거기서 얻은 나눗셈 정보를 원래 등식에 되돌려 넣으면 불가능을 증명할 수 있습니다.
법 4에서는 표만으로 끝났고, 법 3에서는 얻은 배수 조건을 원래 식에 한 번 더 넣었습니다. 표에 목표 나머지가 남아도, 그때 가능한 변수의 형태를 계속 사용할 수 있습니다.
여기까지의 결과를 여러 법의 검사 표에 함께 놓아보겠습니다. 같은 방정식도 어떤 법에서는 통과하고 다른 법에서는 모순이 드러나므로, 한 칸의 통과만으로 결론을 내리면 안 됩니다.
그림을 만든 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', 'PASS means only: this modulus has not ruled out a solution.': '통과의 뜻: 이 법으로는 아직 해를 배제하지 못했다.', 'A stronger modulus can expose an obstruction hidden by a weaker one': '더 강한 법은 앞선 법에서 보이지 않던 장애물을 드러낸다'}
_bfOriginalPixels = [1051, 461]
import matplotlib.pyplot as plt
mods=[2,3,4,5,8,9]; targets=[3,6]
data=[]
for target in targets:
data.append([any((x*x+y*y-target)%m==0 for x in range(m) for y in range(m)) for m in mods])
fig,ax=plt.subplots(figsize=(11.7,4.9),facecolor="#0d1117"); ax.axis("off")
table=ax.table(cellText=[["PASS" if ok else "IMPOSSIBLE" for ok in row] for row in data],rowLabels=["x^2 + y^2 = 3", "x^2 + y^2 = 6"],colLabels=[f"mod {m}" for m in mods],loc="center",cellLoc="center")
table.auto_set_font_size(False); table.set_fontsize(12); table.scale(1,3.1)
for (r,c),cell in table.get_celld().items():
cell.set_edgecolor("#526276"); cell.set_text_props(color="#e6edf3")
cell.set_facecolor("#173f50" if r==0 or c==-1 else "#214737" if data[r-1][c] else "#54333d")
ax.text(.5,.04,"PASS means only: this modulus has not ruled out a solution.",ha="center",color="#ffcf85",fontsize=13,transform=ax.transAxes)
fig.suptitle("A stronger modulus can expose an obstruction hidden by a weaker one",color="#e6edf3",fontsize=16)
fig.subplots_adjust(left=.23,right=.98,top=.84,bottom=.08)
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
assert data[0][0] and not data[0][2]
assert data[1][2] and not data[1][-1]
통과한 칸에서는 뒤의 추론을 계속해야 하고, 불가능한 칸에서는 증명을 끝낼 수 있습니다.
5. 3의 배수 항을 지우고 싶다면 법 3을 고릅니다
다음 식에는 3이 명시적으로 들어 있습니다.
정수 $x,y$가 존재할까요? 여기서는 무엇부터 없애면 계산이 편해질까요? 오른쪽의 $3y$를 지우고 싶습니다. 이번에는 법 3을 고를 이유가 선명합니다. 오른쪽의 $3y$가 0으로 사라지고 고정된 나머지 2만 남기 때문입니다.
하지만 법 3에서 제곱의 나머지는 0 또는 1뿐입니다. 따라서 이 식은 정수해를 갖지 않습니다. $y$가 음수여도 $3y$는 3의 배수이므로 결론은 같습니다.
법 2를 택하면 어떨까요? 오른쪽 $3y+2$의 홀짝은 $y$의 홀짝과 같습니다. 왼쪽 제곱도 0 또는 1의 나머지를 가질 수 있으므로 모순이 생기지 않습니다. 이번 문제에는 3을 택하는 것이 식의 구조를 직접 이용하는 방법입니다.
비슷한 식 $x^2=3y+1$은 법 3 검사를 통과합니다. 실제로 $x=2,y=1$을 넣으면 $4=3+1$이므로 해도 있습니다. 하지만 검사를 통과해서 자동으로 해가 생긴 것은 아닙니다. 이 경우에는 별도로 실제 값을 제시하여 존재를 확인했습니다.
계수를 없애는 선택 외에 제곱의 홀짝을 더 강하게 구분하려면 법 8도 유용합니다. 짝수 $x=2u$이면 $x^2=4u^2$의 나머지는 0 또는 4입니다. 홀수 $x=2u+1$이면
연속한 두 정수 $u,u+1$ 중 하나는 짝수이므로 $u(u+1)$은 짝수입니다. 따라서 홀수 제곱은 법 8에서 항상 1입니다.
이 사실은 마지막 편에서 무한강하의 새 변수가 정수인지 확인할 때도 쓰입니다. 지금 얻은 작은 나머지 표가 뒤의 긴 증명에서 특정 단계를 보장하게 됩니다.
6. 여러 검사를 통과해도 실제 정수해가 없을 수 있습니다
다음 식을 보겠습니다.
241은 240보다 1 크고, 240은 2·3·4·5·8의 배수입니다. 따라서 이 다섯 법에서는 모두 $241\equiv1$입니다. $x\equiv1$을 택하면 제곱도 1이므로 다섯 합동 검사를 전부 통과합니다.
| 법 | 2 | 3 | 4 | 5 | 8 |
|---|---|---|---|---|---|
| 241의 나머지 | 1 | 1 | 1 | 1 | 1 |
| $1^2$의 나머지 | 1 | 1 | 1 | 1 | 1 |
다섯 검사나 통과했는데도 아직 부족할까요? 네. 지금 확인한 것은 나머지가 맞는다는 사실까지입니다. 제곱하면 정확히 241이 되는 정수는 아직 찾지 못했습니다. 이번에는 두 연속한 제곱수의 크기를 비교해보겠습니다. 241이 어느 두 연속한 제곱수 사이에 있는지 찾으면, 정수의 제곱이 될 수 있는지를 판정할 수 있습니다.
0 이상의 정수는 커질수록 그 제곱도 커지므로 241은 두 연속한 제곱 사이에 있습니다. 음수의 제곱도 절댓값의 제곱과 같으므로 음수 해 역시 없습니다.
여기서 반례가 겨냥하는 주장은 “여러 작은 법을 통과했으니 실제 해도 있을 것이다”입니다. 선택한 검사들이 제공한 필요조건만으로 존재가 증명되지는 않는다는 뜻입니다. 앞에서는 연속한 두 제곱 사이의 크기로 불가능성을 확인했지만, 나머지만으로도 막을 수 있는 법이 있습니다. 실제로 이 문제는 법 7에서 바로 걸립니다.
법 7의 제곱 나머지는 0·1·2·4입니다. 0부터 6까지 제곱해 나누면 $0,1,4,2,2,4,1$이 됩니다. 반면 $241=7\times34+3$이므로 오른쪽 나머지는 3입니다. 따라서 법 7에서도 정수해의 불가능성을 증명할 수 있습니다.
각 경우를 표로 확인하겠습니다.
| $r$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| $r^2$ | 0 | 1 | 4 | 9 | 16 | 25 | 36 |
| 법 7 나머지 | 0 | 1 | 4 | 2 | 2 | 4 | 1 |
앞의 다섯 검사에 없던 구분이 법 7에서 생겼습니다. 241의 나머지 3은 이 표에 없으므로, 이 검사만으로도 불가능성을 확정할 수 있습니다.
앞의 다섯 검사에서 같은 후보 $x=1$이 모두 통과했으므로, 여러 법마다 서로 다른 후보를 임의로 고른 탓도 아닙니다. $1^2$과 241의 차이 240이 검사한 모든 법의 배수라는 사실은 둘의 차이가 0이라는 뜻이 아닙니다.
6편에서 법 3과 법 5의 조건을 합쳤던 계산을 떠올려볼까요? 지금 같은 후보 1이 통과한 두 조건에서 $x\equiv1\pmod3$, $x\equiv1\pmod5$라는 가지를 고르면, 그 두 조건을 만족하는 수는 $x=1+15t$입니다. 여기서 $t$는 정수입니다. 하지만 이 수를 원래 등식에 대입하면
차이가 15의 배수라는 것은 확인해도, 그 차이가 0인지는 아직 모릅니다. CRT는 선택한 나머지 조건을 정확히 합쳐주지만, ‘어떤 법의 배수’라는 조건을 ‘정확히 0’이라는 등식으로 바꾸어주지는 않습니다. 여기서 고른 가지가 두 제곱 합동식의 모든 해라는 뜻도 아닙니다.
$x=1$이라는 같은 후보는 $x^2\equiv241$을 법 2·3·4·5·8에서 모두 만족합니다. 그러나 실제 정수의 제곱이 241이 되는지는 별도로 따져야 합니다.
그림을 만든 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', 'An integer solution passes every modulus.': '정수해는 모든 법의 검사를 통과한다.', 'x^2 = 241 passes the tests\nmod 2, 3, 4, 5, and 8 at x = 1.': 'x^2 = 241은 x = 1에서\n법 2·3·4·5·8의 검사를 통과한다.', 'The reverse implication is not valid.': '역은 성립하지 않는다.', '241 - 1 = 240 is divisible by all five moduli.\nIt is still not zero.': '241 − 1 = 240은 다섯 법의 배수이다.\n그래도 0은 아니다.', 'target 241': '목표 241', 'Nonnegative integer |x|': '0 이상인 정수 |x|', 'Passing several remainder tests does not construct an integer square root': '여러 나머지 검사를 통과해도 정수 제곱근이 만들어지는 것은 아니다', '|x| <= 15 gives x^2 <= 225; |x| >= 16 gives x^2 >= 256. Thus no integer square equals 241.': '|x| ≤ 15이면 x^2 ≤ 225, |x| ≥ 16이면 x^2 ≥ 256.\n따라서 제곱이 241인 정수는 없다.'}
_bfOriginalPixels = [1280, 736]
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=(14.0,7.5),title="Passing several remainder tests does not construct an integer square root")
ax=axes[0]
off(ax)
card(ax,.05,.76,.90,.15,"An integer solution passes every modulus.",edge=BLUE,size=15)
arrow(ax,(.5,.73),(.5,.63))
card(ax,.05,.43,.90,.17,"x^2 = 241 passes the tests\nmod 2, 3, 4, 5, and 8 at x = 1.",edge=GREEN,size=15)
text(ax,.5,.26,"The reverse implication is not valid.",color=RED,size=15)
text(ax,.5,.09,"241 - 1 = 240 is divisible by all five moduli.\nIt is still not zero.",color=GOLD,size=13)
ax=axes[1]
xs=np.arange(0,17)
ax.plot(xs,xs*xs,"o-",color=BLUE,markersize=5)
ax.axhline(241,color=GOLD,linestyle="--",linewidth=1.8)
ax.scatter([15,16],[225,256],color=GREEN,s=85,zorder=4)
ax.annotate("15^2 = 225",(15,225),xytext=(7,180),color=GREEN,fontsize=13,
arrowprops=dict(arrowstyle="->",color=GREEN))
ax.annotate("16^2 = 256",(16,256),xytext=(8,288),color=GREEN,fontsize=13,
arrowprops=dict(arrowstyle="->",color=GREEN))
ax.text(1,250,"target 241",color=GOLD,fontsize=13)
ax.set_xlim(-.5,17);ax.set_ylim(-5,315)
ax.set_xticks([0,4,8,12,16])
ax.set_xlabel("Nonnegative integer |x|",color=INK,fontsize=12)
ax.set_ylabel("x^2",color=INK,fontsize=12)
ax.grid(alpha=.2,color=LINE)
caption(fig,"|x| <= 15 gives x^2 <= 225; |x| >= 16 gives x^2 >= 256. Thus no integer square equals 241.")
assert all(241%m==1%m for m in (2,3,4,5,8))
assert 15**2<241<16**2
_apply_bilingual_figure(plt.gcf(), _bfLabels, _bfOriginalPixels)
_display_bilingual_figure(plt.gcf())
$15^2<241<16^2$이므로 241은 정수의 제곱이 아닙니다. 그림의 화살표는 정수해가 합동 검사를 통과한다는 방향을 나타내며, 유한한 검사 통과가 원래 등식의 해를 보장한다는 역방향은 성립하지 않습니다.
7. 법을 고르는 순서와 결론을 쓰는 순서
처음 보는 정수 방정식에서 법을 어떻게 골라야 할까요? 모든 문제에 통하는 한 가지 법칙은 없지만, 식의 형태에서 출발할 수 있습니다.
- 짝수·홀수가 핵심이면 먼저 법 2를 봅니다.
- 제곱의 홀짝만으로 모순이 안 나면 법 4나 8이 더 세밀한 제곱 정보를 줍니다.
- $3y$처럼 계수가 보이면 법 3에서 그 항을 지워봅니다.
- 특정 소인수가 모든 변수에 강제로 들어가는 상황이라면, 그 인수의 제곱이나 더 높은 거듭제곱이 원래 식과 충돌하는지도 살펴볼 수 있습니다.
먼저 없애고 싶은 항이나 더 구별하고 싶은 나머지를 정하면, 어떤 법을 시도하는지 설명할 수 있습니다. 그 선택으로 모순이 나오는지는 실제 표를 만든 뒤 확인합니다.
증명을 쓸 때에는 다음 순서가 안전합니다.
- 정수해가 있다고 가정합니다.
- 선택한 법에서 각 항의 가능한 나머지를 구합니다.
- 왼쪽과 오른쪽의 가능한 나머지가 겹치지 않음을 보입니다.
- 마지막에 가정이 모순이므로 정수해가 없다고 결론 냅니다.
실험과 증명을 구분하는 표현도 중요합니다. “$|x|,|y|\le100$에서 해를 찾지 못했다”는 유한한 검색 결과입니다. “모든 정수의 제곱은 법 4에서 0 또는 1이므로 두 제곱의 합은 3이 될 수 없다”는 모든 정수를 포함하는 증명입니다.
'나머지 표'가 유한한데도 증명이 되는 이유는, 표의 각 행이 단순한 수 하나가 아니라 같은 나머지를 가진 모든 정수를 대표하기 때문입니다. $x=mq+r$라는 표현으로 모든 정수가 빠짐없이 어느 행에 들어감을 설명했기에 유한한 검사가 전체를 다룹니다.
또한 모순을 얻지 못했을 때에는 결론을 멈추어야 합니다. “이 법으로는 아직 불가능성을 증명하지 못했다”가 정확한 상태입니다. 여기서 실제 해를 구성하거나 다른 논증을 해야 존재 또는 부재를 확정할 수 있습니다.
이번에는 $x^2+y^2=77$을 보겠습니다. 법 2·3·4·8·9·16의 검사는 모두 통과하지만, 실제 해가 있는지는 원래 등식에서 따로 확인해야 합니다.
여러 법의 제곱합 검사
여섯 법에서 필요한 나머지 검사를 비교하고, 제한된 범위 안의 실제 정수해도 따로 찾습니다.
이번에는 ‘얼마나 멀리 찾아야 충분할까?’라는 질문이 남습니다. 그 범위를 적으려고 기호 두 개를 쓰겠습니다.
이제 오른쪽 수를 0 이상의 정수 $N$이라고 쓰겠습니다.
- $\sqrt N$은 제곱하면 $N$이 되는 0 이상의 수입니다.
- $\lfloor\sqrt N\rfloor$는 그 수를 넘지 않는 가장 큰 정수입니다.
예를 들어 $8^2=64\le77<81=9^2$이므로 $\lfloor\sqrt{77}\rfloor=8$입니다.
앞에서는 몇 개의 정수만 넣어 안 나왔다고 증명이 되지는 않는다고 했습니다.
그런데 이번에는 유한한 탐색으로 전체를 판정할 수 있습니다.
차이는 어디에 있을까요?
먼저 해가 있다면 들어가야 할 범위를 등식 자체에서 구할 수 있기 때문입니다.
제곱은 음수가 아니므로 $x^2\le x^2+y^2=N$이고 $y^2\le N$입니다.
따라서 각 절댓값이 $\sqrt N$을 넘을 수 없습니다.
$x,y$는 정수이므로 두 절댓값은 $\lfloor\sqrt N\rfloor$ 이하입니다. 77에서는 둘 다 8 이하입니다.
$x^2+y^2=N$이고 $N\ge0$이면 $|x|,|y|\le\lfloor\sqrt N\rfloor$이므로 이 범위를 전부 조사하면 완전한 판정이 됩니다.
77에서는 절댓값이 8 이하인 경우를 모두 확인해도 해가 없으며, 비음수인 두 값의 순서를 고정해 검색한 뒤 부호와 순서 대칭을 반영하면 정수 전체를 다룰 수 있습니다.
임의로 “100까지 보았다”는 탐색과 달리, 이번에는 그 밖에 해가 있을 수 없다는 상한을 먼저 증명했습니다.
0·1·2·3·4·5·6·7·8의 제곱은 $0,1,4,9,16,25,36,49,64$입니다. 77에서 이들을 빼면 $77,76,73,68,61,52,41,28,13$인데 어느 값도 제곱 목록에 없습니다. 그래서 이 유한한 목록을 전부 확인한 것으로 정수해의 부재를 확정할 수 있습니다.
8. 작은 법으로 시작한 제약이 큰 증명의 일부가 됩니다
지금 다룬 예에서는 나머지 하나로 불가능성을 끝내거나, 나누어떨어진다는 결론을 한 번 더 대입해서 끝낼 수 있었습니다. 그러나 모든 정수 방정식이 그렇게 간단하지는 않습니다.
예를 들어 양의 정수 세 개가 $a^2+b^2=c^2$를 만족하면, 그 세 수의 묶음을 피타고라스 삼조(Pythagorean triple) 혹은 피타고라스 삼중항이라고 합니다.(어느 곳에서는 삼쌍이라고도 한다네요..) 직각삼각형의 두 직각변이 $a,b$이고 빗변이 $c$인 경우이지요. 이 식을 법 4에서 검사하면 한 가지 제약을 얻습니다. 세 수의 최대공약수가 1인 경우를 원시 삼조라고 하겠습니다. 두 직각변이 모두 홀수라면 왼쪽은 법 4에서 2이지만 오른쪽 제곱은 0 또는 1이라 불가능합니다. 두 직각변이 모두 짝수이면 빗변의 제곱도 4의 배수여서 빗변 역시 짝수입니다. 세 변에 공약수 2가 생기므로 원시 삼조에서는 이 경우도 제외됩니다. 따라서 한 직각변은 짝수이고 다른 하나는 홀수여야 합니다.
홀짝 조건만으로 모든 피타고라스 삼조를 찾은 것은 아닙니다. 하지만 다음 편에서 전체 형태를 구할 때 출발점이 되는 제약입니다. 나머지 계산은 단독으로 문제를 끝내는 도구이기도 하고, 더 긴 증명에서 특정 가능성을 제거하는 도구이기도 합니다.
다음 편의 무한강하에서는 더 특이한 일이 일어납니다. 어떤 양의 정수해가 존재한다고 가정하고, 오늘처럼 홀짝과 서로소 조건을 분석한 뒤, 그 해로부터 같은 성질을 가진 더 작은 양의 정수해를 만듭니다. 양의 정수가 끝없이 작아질 수 없다는 사실이 최종 모순이 됩니다.
나머지 검사를 통과한 뒤에는 아무것도 할 수 없다는 뜻이 아닙니다. 나머지에서 얻은 구조를 정수의 크기와 결합하면, 한 번의 나머지 모순보다 긴 경로로 불가능성을 증명할 수 있습니다.
이 연결은 페르마의 마지막 정리로 이어집니다. 다음 편에서는 홀짝과 서로소성으로 피타고라스 삼조의 형태를 구한 뒤, 무한강하로 ‘넓이가 양의 정수의 제곱인 정수변 직각삼각형은 없다’는 사실을 증명합니다. 그 결과를 이용해 마지막 정리의 지수 4인 경우까지 직접 증명하겠습니다. 4편의 페르마 소정리와는 다른 정리이며, 모든 지수에 대한 일반 정리는 8편에서 따로 소개하겠습니다.
9. 직접 바꾸어 확인해보기
오른쪽을 3으로 두고 법 2와 4를 비교한 뒤, 오른쪽을 6으로 바꾸어 법 4와 9를 비교해보세요. 통과했다는 표시는 그 법에서 모순을 찾지 못했다는 뜻입니다. 실제 정수해가 있음을 확인하는 판정으로 읽으면 안 됩니다.
이번에는 오른쪽을 5로 바꾸어보세요. 법 4에서 5의 나머지는 1이고, 두 제곱의 나머지 0과 1을 더해 만들 수 있으니 통과합니다. 그렇다면 이번에는 정말 해가 있을까요? $1^2+2^2=5$를 원래 등식에 넣어 확인하면 있습니다. 나머지 검사를 통과한 뒤 실제 해를 하나 제시하는 일이 무엇인지 구분해보는 연습입니다. 앞의 6처럼 다른 법에서 끝내 탈락할 수도 있으므로, 통과 표시 자체를 존재의 근거로 쓰지는 않습니다.
불가능을 가려내는 법
x²+y²=N이 선택한 법에서 통과하는지 검사합니다.
10. 마무리
$x^2+y^2=3$에서 법 2는 홀짝 조건만 남겼고, 법 4는 가능한 제곱합 나머지에서 3을 제외하여 즉시 모순을 만들었습니다. $x^2=3y+2$에서는 법 3이 오른쪽의 변수 항을 지워서 불가능성을 드러냈습니다.
반면 $x^2=241$은 여러 작은 법을 통과해도 실제 정수해가 없었습니다. 나머지 조건은 반드시 만족해야 하는 조건이고, 통과했다는 사실만으로 원래 등식을 만족하는 정수가 생기지는 않습니다.
이제 우리는 답을 구성하는 방법과 불가능을 확인하는 방법을 둘 다 보았습니다. 마지막 편에서는 둘을 정수 방정식 안에서 합치겠습니다. 일차식의 모든 해를 찾고, $a^2+b^2=c^2$를 만족하는 피타고라스 삼조의 공식을 검증하는 데서 한 걸음 더 나아가 모든 원시 삼조가 왜 그 형태인지 증명하겠습니다. 그리고 같은 조건의 더 작은 해를 실제로 만드는 무한강하를 거쳐, 페르마의 마지막 정리의 지수 4인 경우에 도달하겠습니다.
'Study > Mathematics' 카테고리의 다른 글
| 나머지에서 시작하는 정수론 6편: 중국인의 나머지 정리(CRT) (0) | 2026.10.31 |
|---|---|
| 나머지에서 시작하는 정수론 5편: 오일러 또또또 당신이에요? (0) | 2026.10.30 |
| 나머지에서 시작하는 정수론 4편: 페르마의 소정리 (0) | 2026.10.29 |
| 나머지에서 시작하는 정수론 3편: 최대공약수의 비밀 (0) | 2026.10.28 |
| 나머지에서 시작하는 정수론 2편: 배수 판정법의 원리 (0) | 2026.10.27 |