수학시간

수와 연산 · 자연수의 성질

최대공약수와 최소공배수

두 수가 공유하는 약수와 공배수의 구조를 이해하고, 소인수분해와 유클리드 알고리즘으로 최대공약수를 구해 봅시다. 계산 결과가 왜 맞는지도 직접 확인할 수 있습니다.

  • 서로소의 뜻을 예로 설명할 수 있다.
  • 최대공약수와 최소공배수를 구할 수 있다.
  • 유클리드 알고리즘의 나눗셈 단계를 해석할 수 있다.
01

서로소

공약수가 1뿐인 두 자연수를 살펴봅니다.

서로소의 뜻

두 자연수의 최대공약수가 \(1\)이면 두 수는 서로소입니다. 예를 들어 \(8\)과 \(15\)의 공약수는 \(1\)뿐이므로 서로소입니다.

둘 다 소수일 필요는 없습니다

\(8\)과 \(15\)는 모두 합성수이지만 서로소입니다. 반대로 \(6\)과 \(9\)는 공약수 \(3\)을 가지므로 서로소가 아닙니다.

핵심 정리 서로소는 한 수의 성질이 아니라 두 수 사이의 관계입니다. \(1\)은 모든 자연수와 서로소입니다.
02

최대공약수와 최소공배수의 계산 원리

소인수의 지수를 비교하면 두 값을 함께 구할 수 있습니다.

최대공약수: 작은 지수 선택

\(12=2^2\times3\), \(18=2\times3^2\)입니다.

공통 소인수 \(2,3\)에서 작은 지수를 고르면

\[\operatorname{GCD}(12,18)=2^1\times3^1=6\]

최소공배수: 큰 지수 선택

두 수의 모든 소인수가 충분히 들어가야 합니다.

각 소인수에서 큰 지수를 고르면

\[\operatorname{LCM}(12,18)=2^2\times3^2=36\]

곱의 관계 두 자연수 \(a,b\)에 대해 \[\operatorname{GCD}(a,b)\times\operatorname{LCM}(a,b)=a\times b\] 가 성립합니다.
03

최대공약수·최소공배수 계산기

두 자연수를 입력하면 소인수분해와 곱의 관계를 함께 확인합니다.

04

유클리드 알고리즘 시뮬레이션

나머지가 \(0\)이 될 때까지 나누며 최대공약수를 찾습니다.

\(a=bq+r\)일 때 \(\operatorname{GCD}(a,b)=\operatorname{GCD}(b,r)\)입니다. 따라서 큰 수를 작은 수로 나눈 뒤, 나누는 수와 나머지를 다음 쌍으로 바꿉니다.

05

빠른 배수 판정법

소인수분해를 시작하기 전에 나누어떨어지는지 빠르게 확인해 봅시다.

2

끝자리가 짝수

일의 자리 숫자가 \(0,2,4,6,8\)입니다.

3

각 자리의 합

각 자리 숫자의 합이 \(3\)의 배수입니다.

4

끝 두 자리

끝 두 자리 수가 \(4\)의 배수입니다.

5

끝자리 0 또는 5

일의 자리 숫자가 \(0\) 또는 \(5\)입니다.

6

2와 3을 동시에

\(2\)와 \(3\)의 배수 조건을 모두 만족합니다.

8

끝 세 자리

끝 세 자리 수가 \(8\)의 배수입니다.

9

각 자리의 합

각 자리 숫자의 합이 \(9\)의 배수입니다.

10

끝자리 0

일의 자리 숫자가 \(0\)입니다.

06

수학이 암호가 될 때

최대공약수와 서로소는 공개 키 암호의 핵심 아이디어와 연결됩니다.

RSA에서는 어떤 수가 \(\varphi(n)\)과 서로소인지 확인하고, 곱셈의 역원을 찾는 데 유클리드 알고리즘을 확장한 방법을 사용합니다. 아래는 원리만 보이기 위한 아주 작은 예입니다.

1. 두 소수 선택 \(p=3\), \(q=11\)이면 \(n=pq=33\), \(\varphi(n)=(p-1)(q-1)=20\)입니다.
2. 서로소인 수 선택 \(e=3\)은 \(20\)과 서로소입니다. \(3\times7\equiv1\pmod{20}\)이므로 \(d=7\)입니다.
3. 암호화와 복호화 메시지 \(5\)를 암호화하면 \(5^3\equiv26\pmod{33}\), 복호화하면 \(26^7\equiv5\pmod{33}\)입니다.
주의 이 작은 수들은 학습용 예시일 뿐입니다. 실제 보안에서는 매우 큰 수와 검증된 암호 라이브러리를 사용합니다.

더 읽어 보기

EBSMath · 소인수분해와 암호

중학교 수학의 소인수분해가 RSA 암호와 어떻게 이어지는지 한국어로 살펴봅니다.

읽으러 가기 →

CrypTool · RSA Step by Step

RSA의 키 만들기, 암호화, 복호화 흐름을 단계별 도구로 탐색할 수 있습니다.

도구 열기 →

위키백과 · 공개 키 암호 방식

공개 키와 개인 키의 역할, RSA 같은 암호 방식에 쓰이는 수학적 원리를 한국어로 살펴봅니다.

개념 읽기 →