정말 재미있는 당신을 위한 구수략
어떤 곱셈을 검증하려 한다. 피연산자 A에 대한 A mod 9는 6, 연산자 B에 대한 B mod 9는 4이다. 이것이 정상적인지 검증하라.
- 첫 행에 6,4를 쓴다.
(6,4)
- 피연산자의 나머지 6에 9를 곱하고(구거법), 십의 자리와 일의 자리를 분리해 54를 5,4로 떼어 쓴다.
(5, 4)
- 2행의 두 수의 합은 9이다. 구거법의 상위 자리와 하위 자리 표기법에 따라 9,1로 표기한다. (10의 보수가 아니다. 만약 합이 8이었다면 8,1이다.)
(9, 1)
전통적인 구거법은 복잡하고 머리아픈 모듈러 연산이다. 이것을 배열로 치환하여 쉽고 연산 자체를 단순화해서 처리한다.
matrix = [[6, 4], [5, 4], [9, 1]]
if abs(matrix[0][0]-matrix[2][1]) == abs(matrix[0][1] - matrix[2][0]):
print("mod 9를 이용한 검산 결과 곱셈은 정상입니다.")
결과
Python 3.14.3 (main, Feb 4 2026, 00:00:00) [GCC 15.2.1 20260123 (Red Hat 15.2.1-7)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> matrix=[[6,4], [5,4], [9,1]]
>>> if abs(matrix[0][0]-matrix[2][1]) == abs(matrix[0][1] - matrix[2][0]):
... print("mod 9를 이용한 검산 결과 곱셈은 정상입니다.")
...
mod 9를 이용한 검산 결과 곱셈은 정상입니다.
>>>
원본 식이 무엇인지도 모르지만 mod 9만 가지고 연산이 정상인 것을 알 수 있다.
원본 식의 후보는 사실 너무 다양하다. 아래는 후보를 뽑아 주는 코드이다.
from typing import List, Tuple, Optional
def mod9(n: int) -> int:
"""
Return modulo-9 in the table notation.
Multiples of 9 are written as 9 instead of 0.
Range: 1..9
"""
r = n % 9
return 9 if r == 0 else r
def find_numbers_by_residue(target: int, start: int, end: int) -> List[int]:
"""
Find all integers in [start, end] such that mod9(n) == target.
"""
if not 1 <= target <= 9:
raise ValueError("target must be in 1..9")
result: List[int] = []
for n in range(start, end + 1):
if mod9(n) == target:
result.append(n)
return result
def reconstruct_pairs(
left_residue: int,
right_residue: int,
start: int,
end: int,
) -> List[Tuple[int, int]]:
"""
Reconstruct all candidate pairs (A, B) such that:
mod9(A) == left_residue
mod9(B) == right_residue
"""
left_candidates = find_numbers_by_residue(left_residue, start, end)
right_candidates = find_numbers_by_residue(right_residue, start, end)
pairs: List[Tuple[int, int]] = []
for a in left_candidates:
for b in right_candidates:
pairs.append((a, b))
return pairs
def reconstruct_triples(
left_residue: int,
right_residue: int,
product_residue: Optional[int],
start: int,
end: int,
) -> List[Tuple[int, int, int]]:
"""
Reconstruct candidate triples (A, B, C) where C = A * B.
Required:
mod9(A) == left_residue
mod9(B) == right_residue
Optional:
mod9(C) == product_residue
"""
left_candidates = find_numbers_by_residue(left_residue, start, end)
right_candidates = find_numbers_by_residue(right_residue, start, end)
triples: List[Tuple[int, int, int]] = []
for a in left_candidates:
for b in right_candidates:
c = a * b
if product_residue is not None and mod9(c) != product_residue:
continue
triples.append((a, b, c))
return triples
def verify_multiplication(a: int, b: int, c: int) -> bool:
"""
Verify A * B = C using mod 9 arithmetic.
"""
left = mod9(mod9(a) * mod9(b))
right = mod9(c)
return left == right
def diagonal_check(tl: int, tr: int, bl: int, br: int) -> bool:
"""
Check the relation:
tl - br == bl - tr
"""
return (tl - br) == (bl - tr)
if __name__ == "__main__":
# Example: residue pair (6, 4)
pairs = reconstruct_pairs(6, 4, 1, 40)
print("Pairs (A, B) with residues (6, 4):")
print(pairs[:20])
print()
# Product residue: 6 * 4 = 24 -> mod9 = 6
triples = reconstruct_triples(6, 4, 6, 1, 40)
print("Triples (A, B, A*B) with residue constraint:")
print(triples[:20])
print()
# Verification example
a, b, c = 15, 13, 195
print("Verify:", verify_multiplication(a, b, c))
print()
# Diagram check: (6,4) vs (9,1)
print("Diagonal check:", diagonal_check(6, 4, 9, 1))
Pairs (A, B) with residues (6, 4):
[(6, 4), (6, 13), (6, 22), (6, 31), (6, 40), (15, 4), (15, 13), (15, 22), (15, 31), (15, 40), (24, 4), (24, 13), (24, 22), (24, 31), (24, 40), (33, 4), (33, 13), (33, 22), (33, 31), (33, 40)]
Triples (A, B, A*B) with residue constraint:
[(6, 4, 24), (6, 13, 78), (6, 22, 132), (6, 31, 186), (6, 40, 240), (15, 4, 60), (15, 13, 195), (15, 22, 330), (15, 31, 465), (15, 40, 600), (24, 4, 96), (24, 13, 312), (24, 22, 528), (24, 31, 744), (24, 40, 960), (33, 4, 132), (33, 13, 429), (33, 22, 726), (33, 31, 1023), (33, 40, 1320)]
Verify: True
Diagonal check: True
원본 식이 뭔지 몰라도 2x3 격자만 그리면 그만이다. 수천억 단위의 숫자 폭탄에 시달리던 세금 집행인들에게도 이 책은 도움이 되었을 것으로 보인다. 그렇지 않다면 굳이 어렵게 어렵게 그 시절에 귀하던 인쇄용 먹(사실상 잉크같은 질감이었다고 하고 특히 귀하다고 하는)과 활자를 들고 인쇄소에서 출력할 까닭이 없었다.
만약 9가 아닌 2의 거듭제곱으로 모듈러를 바꾸면 비트 연산으로 모듈러 처리를 할 수 있을 것이다. 향후 CS에서 응용한다고 치면(이 정도로 컴퓨터 과학이라기엔 좀 거창하지만) 연산량을 줄일 수 있을 것으로 보이는데, 이후 코드를 짜서 벤치마크해 보도록 하겠다.
어라, 수포자인데 모듈러 연산을 했다
나같은 감각을 느낀 사람이 많을 것이다. 원래 어려운 수식으로 보면 뭐라는지도 모르겠는데, 이렇게 보면 눈에도 확 들어오고 모듈러 연산을 할 수가 있다.
그리고 무엇보다, 그냥 무작정 mod 9 어쩌구 하는거보다 눈이 시원하다, 오늘도 계산에 시달리는 공돌이들을 위해서 열심히 책을 써준(그리고 본인은 뼈문과였던) 최석정에게 감사를 전하는 바이다. 역시 우리는 뉴턴의 말대로 거인의 어깨 위에 있는 셈이다.