Skip to content

태그: 정수론

총 2개의 글이 있습니다.

베주 항등식

ax + by = gcd(a, b)를 성립하는 x, y는 항상 존재한다. 집합 S = {ax + by 0 | x, y는 정수}를 가정했을 때 S는 공집합이 아니므로, y=0, x=1이면: a×1 + b×0 = a a가 양수면 그대로, 음수면 |a| (x=-1로 조정) 따라서 S는 최소한 하나의 원소를 가짐 S에 있는 가장 작은 원소를 d라고 불러볼 수 있다. a를 d로 나누면 몫 q와 나머지 r로 표현할 수 있을 것이다. a = dq + r (0 ≤ r &x3C; d) 여기서 만약 r이 0보다 크다면 r = a dq= a (as + bt)q= a(1-sq) + b(-tq) 이므로 r도 S의 원소라는 뜻인데, r &x3C; d이므로 d가 최소원소라는 것에 모순된다. 따라서 r = 0이어야

페르마 소정리

소수 m, 임의의 수 a에 대해 아래 식이 성립한다. a^(m-1) = 1 (mod m) 이 식을 활용해 역원을 구할 수 있다. a^(m-1) = a*a^(m-2) = 1 (mod m)즉, a^(m-2)가 a의 역원 증명 a와 서로소인 소수 p에 대해 a, 2a, 3a, …, (p−1)a인 p−1개의 수를 p로 나눴을 때 나오는 나머지는 모두 다르다. 귀류법으로 증명된다. 0&x3C;i&x3C;j&x3C;p인 정수에서 ia와 ja의 나머지가 같다고 하면 ia != ja (mod p)ja ia = 0 (mod p) 위 식이 성립하기 위해선, (j-i)a가 p로 나눠떨어져야 한다. a는 p와 서로소이므로 j-i가 p로 나눠떨어져야 한다. 하지만 조건에 따라 i-j가 p보다 클 수 없다 (i-j &x3C;