이항계수를 소수로 나눈 나머지 구하는 방법 - Lucas' Theorem 배우고 적용하기

https://en.wikipedia.org/wiki/Lucas%27s_theorem Lucas's theorem - Wikipedia From Wikipedia, the free encyclopedia In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} by a prime number p in terms of the base p expansions of the integers m and n. en.wikipedia.org 1. Lucas' Theorem 정수 m,n과 소수 p에 대하여 $$\binom{m}{n..

• format_list_bulleted 정수론
• · 2023. 7. 4.
• textsms

조합의 곱의 합을 구하는 Vandermonde's identity

https://en.wikipedia.org/wiki/Vandermonde%27s_identity Vandermonde's identity - Wikipedia From Wikipedia, the free encyclopedia Mathematical theorem on convolved binomial coefficients In combinatorics, Vandermonde's identity (or Vandermonde's convolution) is the following identity for binomial coefficients: ( m + n r ) = ∑ k = 0 r ( m k ) ( n en.wikipedia.org 1. Vandermonde's identity 음이 아닌 정수 m..

• format_list_bulleted 정수론
• · 2023. 7. 3.
• textsms

밀러 라빈 소수 판별법(Miller-Rabin primality test) 배우기

1. 밀러 라빈 소수 판별법(Miller-Rabin primality test) 어떤 홀수 n이 소수인지 확률적으로 판별해주는 알고리즘 확률적이라는 말은, 합성수를 소수로 잘못 판별할 수 있다는 뜻이다. 주어진 n이 "합성수이다" 또는 "아마도 소수일 것이다"라는 대답을 내놓는다는 의미 2. 핵심 아이디어 알고리즘의 아이디어는 페르마의 소정리에서 시작한다. https://deepdata.tistory.com/573 페르마의 소정리 문제 풀어보면서 익히기 1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$ 이다. 1-2) p가 소수이..

• format_list_bulleted 정수론
• · 2023. 5. 5.
• textsms

오일러의 정리를 배우고 거듭제곱의 나머지를 구하는 방법 익히기

1. 오일러의 정리(Euler's theorem) a와 n이 서로소인 양의 정수이면, 다음이 성립한다 $$a^{\varphi(n)} \equiv 1 (mod n)$$ 여기서 $\varphi(n)$은 n에 대한 오일러 phi 함수이다. 서로소가 아니라면 다음과 같이 쓸 수 있다. $$a^{\varphi(n) + 1} \equiv a (mod n)$$ n이 소수 p이면, $\varphi(p) = p-1$이므로, a,p가 서로소이면 $a^{p-1} \equiv 1 (mod p)$이다. 페르마의 소정리는 오일러의 정리의 특수한 케이스이다. 2. 거듭제곱을 어떤 정수로 나눈 나머지 $a^{n}$을 어떤 정수 p로 나눈 나머지는 어떻게 구할 수 있을까? $a^{n}$을 직접 계산한 다음에, p로 나눈 나머지를 구하..

• format_list_bulleted 정수론
• · 2022. 12. 18.
• textsms

모듈로 연산에서 나눗셈을 하는 방법(모듈로 곱셈의 역원 구하기)

1. 합동식에서 기본적으로 알아야하는 성질 1-1) 양변에 어떤 정수에 대한 덧셈이나 뺄셈을 하더라도 상관없다. $a \equiv b (mod p)$이고 $c \equiv d (mod p)$이면, $$a \pm c \equiv b \pm d (mod p)$$ 그러므로, c = d이면, 양변에 동일한 수를 더하거나 빼더라도 합동식은 변하지 않는다. $$a \pm c \equiv b \pm c (mod p)$$ 1-2) 양변에 어떤 정수에 대한 곱셈을 하더라도 상관없다 $a \equiv b (mod p)$이고 $c \equiv d (mod p)$이면, $$ac \equiv bd (mod p)$$ 그러므로, c=d이면, 양변에 동일한 수를 곱하더라도 합동식은 변하지 않는다. $$ac \equiv bc (mod..

• format_list_bulleted 정수론
• · 2022. 12. 16.
• textsms

페르마의 소정리 문제 풀어보면서 익히기

1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$ 이다. 1-2) p가 소수이면, 모든 정수 a에 대하여 $$a^{p} \equiv a (mod p)$$ 응용하는 방법은 여러가지가 있겠지만, 하나하나 다 나열할 수도 없고, 접한지 얼마 안되었으니 나도 다 모르고 증명도 굳이 할 필요없을 것 같고, 받아들이면서 문제를 풀면서 익혀보기로 하자 2. 응용 - 합성수 판정 페르마의 소정리 역은 성립하지 않는다. 즉, a와 p가 서로소일때, $$a^{p-1} \equiv 1 (mod p)$$ 가 성립한다면, p는 소수이다는 거짓이다. 즉, ..

• format_list_bulleted 정수론
• · 2022. 12. 15.
• textsms