소수의 나눗셈 성질 p | ab이면 p | a 혹은 p | b 이다.

p | ab이면 p | a 혹은 p | b 이다.

$gcd(a,b) = xa + yb$

먼저 $gcd(a,b) = xa + yb$를 전제로 해야 한다.

증명은 이렇게 된다.

p | ab이면 p | a 혹은 p | b 이다.

어찌보면 당연한 소리인데, 증명을 할 수 있다.

아래와 같은 케이스로 나눠보자.

1. p | a가 맞음 -> 증명 완료
2. p | a가 아님 -> p는 소수이니 gcd(p, a) = 1 or p 이다.
   1. gcd(p, a) = p -> a = kp이니 p | a가 맞다. -> 불가능.
   2. gcd(p, a) = 1 -> 위의 증명을 이용하면 gcd(p, a) = xp + ya = 1
      양변에 b를 곱하면 xpb + yab = b 이고,
      p | xpb + yab 이다. (p | xpb는 자명하고, p | yab는 p | ab라고 했으니 맞다.)
      따라서 p | b.