최대공약수
$n$와 $m$의 최대공약수 $\gcd(n, m)$의 정의는 다음과 같습니다.
소수 집합 $p \in \mathbb{P}$에 대하여, $n$, $m$이 각각
$$
n = \prod_{p} p^{n_{p}} \left( n_{p} \geq 0 \right)
$$
$$
m = \prod_{p} p^{m_{p}} \left( m_{p} \geq 0 \right)
$$
일 때, 최대공약수 $\gcd(n, m)$는
$$
\gcd(n, m) = \prod_{p} p^{\min(n_{p}, m_{p})}
$$
로 정의한다.
$\gcd(a, b)$에서 GCD는 Greatest Common Divisor 의 약자입니다.
소인수분해 대신 유클리드 호제법 으로도 구할 수 있습니다.
비슷한 관계로 최소공배수 가 있습니다.
$\gcd(n, m) = 1$이면 $n$과 $m$을 서로소 라고 합니다. (상대적인 소수 라는 뜻)
임의의 두 수 $n$, $m$이 서로소일 확률은 $\frac{6}{\pi^{2}}$임이 알려져있습니다. ( 바젤 문제 )
$\gcd(n, m) = d$일 확률은 $\frac{6}{\pi^{2}} \frac{1}{d^{2}}$임이 알려져있습니다. $n$이 $d$의 배수이며 ($n$이 $d$의 배수일 확률 $\frac{1}{d}$) $m$이 $d$의 배수이며 동시에 $\gcd\left(\frac{n}{d}, \frac{m}{d}\right) = 1$이어야 하므로 ($N = \frac{n}{d}$, $M = \frac{m}{d}$라 하면 $\gcd\left(N, M\right) = 1$ 일 확률은 $\frac{6}{\pi^{2}}$) 모든 확률을 곱한 $\frac{1}{d} \times \frac{1}{d} \times \frac{6}{\pi^{2}}$가 확률이기 때문입니다.