[Java] 37. 서로소

Feb 11, 2025

💡

두 개의 자연수 a와 b가 있을 때,

공통된 약수가 1밖에 없는 경우 이 둘을 서로소(Coprime)라고 합니다. 다시 말해, 최대 공약수(GCD, Greatest Common Divisor)가 1인 두 수를 서로소라고 합니다.

예를 들어,

✔ 연속된 두 자연수는 항상 서로소이다.

✔ 소수(prime number)는 1을 제외한 모든 수와 서로소이다.

✔ 서로소인 두 수의 곱은 어떤 수로 나누어도 동시에 나누어지지 않는다.

✔ 오일러 피 함수(𝜑 함수)와 관련이 깊다.

서로소 개념은 암호학, 정수론, 확률론 등 다양한 분야에서 활용되며, 특히 RSA 암호 알고리즘에서 중요한 역할을 합니다.

More articles