연분수(continued fraction)를 이용한 선형 디오판토스 방정식의 해를 구하는 방법

1. 연분수 표현에서 a,b의 최대공약수를 바로 구하는 방법 $\frac{A}{B}$의 연분수 표현을 구하고자 한다면, A/B가 기약분수 형태로 들어가줘야한다. 기약분수로 바꿀려면 A,B의 최대공약수가 g = gcd(A,B)일때, $p_{k} = A/g, q_{k} = B/g$이고 그래서 $\frac{A}{B} = \frac{p_{k}}{q_{k}}$이다. 따라서, A/B가 기약분수가 아닐때, 연분수 표현 p,q를 구한 다음 A를 p[-1]로 나눠주면 A,B의 최대공약수가 된다. #A/B가 기약분수가 아닐때, A,B의 최대공약수 구하기 def continued_fraction(p,q): f = [] while q != 0: f.append(p//q) p,q = q,p%q return f def conve..

• format_list_bulleted 정수론
• · 2023. 9. 29.
• textsms

디오판토스 분수방정식의 정수 해법 배우기(+팩토리얼 인수분해, 제곱수의 약수의 개수)

1. 문제1 7516번: 알렉산드리아의 디오판토스 (acmicpc.net) 7516번: 알렉산드리아의 디오판토스 알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오 www.acmicpc.net 2. 풀이 주어진 방정식 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 정리하면, $$\frac{y+x}{xy} = \frac{1}{n}$$ 이다. 그래서 $$n(y+x) = xy$$ 를 얻는다. 솔직히 여기서 넘어가기 어려운데, (억지라는 생각이 들 정도..) $n^{2} = pq$라 하자. p,q는 정수이다. 즉, p,q는 $n^{2}$의 약수이다. 그리고..

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

중국인의 나머지 정리(Chinese Remainder Theorem) 기본 이해하기

1. 중국인의 나머지 정리(Chinese Remainder Theorem) 정수 $m_{1}, m_{2}, ..., m_{n}$이 임의의 i,j = 1,2,...,n에 대하여 $i \neq j$일때, $m_{i}$와 $m_{j}$가 서로소라면, 즉 $$gcd(m_{i}, m_{j}) = 1, i \neq j$$ 라고 하자. 일차연립합동식 $$x \equiv a_{1} (mod m_{1})$$ , $$x \equiv a_{2} (mod m_{2})$$ , $$x \equiv a_{3} (mod m_{3})$$ , $$\vdots$$ , $$x \equiv a_{n} (mod m_{n})$$ 의 해는 mod $m_{1}, m_{2}, ..., m_{n}$에 대하여 유일하게 존재한다. 2. 보조정리 1 정수 a,b,k..

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