페리 수열(farey sequence) 조금 더 깊게2 - 페리 수열의 대칭성과 페리 수열의 합 -

1. 페리 수열의 대칭성(symmetry) n번째 페리 수열의 분수 $\frac{a}{b}$에 대해 생각해보자. 먼저 기약분수이므로 a,b가 서로소이고 0과 1 사이에 있으므로 a < b이다. https://deepdata.tistory.com/1104 페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 - 1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. deepdata.tistory.com 이전에 관찰했던 것처럼 n번째 페리 수열에는 분모가 n 이하인 정수 b에 대하여 b보다 작은 서로소인 모든 정수 a에 대해 $\..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms

페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 -

1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. 이때, 0과 1 사이에 존재하는 기약분수이므로 a < b이다. 그러므로 n번째 페리수열에 존재하는 기약분수들은 다음과 같이 만들수도 있다. "양 끝에는 $\frac{0}{1}, \frac{1}{1}$이 있고, 분모가 b = 2,3,4,5,..,n에 대하여 분자는 k보다 작으면서 서로소인 모든 정수 a에 대해 $\frac{a}{b}$를 나열한 것이다." 예를 들어, 5번째 페리 수열을 보자. 분모가 2이면 2와 서로소인 1에 대해 $\frac{1}{2}$ 분모가 3이면 3과 서로소인 1,2에 대해..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• 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

오일러의 phi 함수 직접 구현해보면서 개념 익히기

1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데... 하나하나 파고들면 끝도 없으니까 문제 풀면서 익히기로 하자 2. 구현 예시1 - 가장 간단한 구현 가장 간단한 방법은 1이상 n이하의 자연수 중에서, n과 서로소인 것의 개수를 세보면 된다. 그러니까 1이상 n이하의 자연수 중에서 n과 최대공약수가 1인 자연수의 개수가 n이하에서 몇개인지 세보면 된다. 유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 만들고, def gcd(a,b): while b != 0: a,b = b,a%b return a 2부터 ..

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