베주 항등식의 목적은 x, y가 정해졌을 때, 정수 p, q를 구하는 방법을 이야기 합니다.
$$ px + qy = 1 (mod (xy)) $$
예를 들어서, 7과 5에 대하여 항등식을 찾으면 다음과 같습니다.
여기서 음수는 크게 고려하지 않아도 됩니다.
-2는 mod 3에서 1과 같고, mod 7에서 -2는 5와 같습니다. 위 식에서 양변에 mod 7을 하면 : $$-2 × 3 = 1 (mod 7)$$
즉 \(\displaystyle -2 \equiv \frac13 (mod 7) \)
1 × \( 7 = 1 (mod 3) \)
즉, \( \displaystyle \frac17 \equiv 1 (mod 3) \)입니다.
$$(1 × 8) + (-1 × 6) = 2$$
예시는 6, 8의 경우 GCD(6, 8) = 2이므로, 아래의 경우 사용할 수 없는데, 양변을 2로 나누면,
$$(1 × 4) + (-1 × 3) = 1$$
댓글