![[Java] 37. 서로소](https://image.inblog.dev?url=https%3A%2F%2Fsource.inblog.dev%2Ffeatured_image%2F2025-02-11T07%3A36%3A37.505Z-6bdb888b-9978-429f-bba7-28b8d67d4044&w=3840&q=75)
서로소(Coprime)란?
두 개의 자연수 a와 b가 있을 때,
공통된 약수가 1밖에 없는 경우 이 둘을 서로소(Coprime)라고 합니다.
다시 말해, 최대 공약수(GCD, Greatest Common Divisor)가 1인 두 수를 서로소라고 합니다.
예를 들어,
- 8과 15의 약수:
- 8→ {1, 2, 4, 8}
- 15→ {1, 3, 5, 15}
- 공통 약수: {1} → 서로소 ✅
- 12와 18의 약수:
- 12→ {1, 2, 3, 4, 6, 12}
- 18→ {1, 2, 3, 6, 9, 18}
- 공통 약수: {1, 2, 3, 6} → 서로소 ❌
서로소의 특징
✔ 연속된 두 자연수는 항상 서로소이다.
✔ 소수(prime number)는 1을 제외한 모든 수와 서로소이다.
✔ 서로소인 두 수의 곱은 어떤 수로 나누어도 동시에 나누어지지 않는다.
✔ 오일러 피 함수(𝜑 함수)와 관련이 깊다.
서로소 개념은 암호학, 정수론, 확률론 등 다양한 분야에서 활용되며,
특히 RSA 암호 알고리즘에서 중요한 역할을 합니다.
Share article