728x90 반응형 스터디/정수론4 [정수론] 디오판토스 방정식 (Diophantine equation) 디오판토스 방정식 (ax+by=c)정수를 계수로 갖는 방정식의 정수해를 구하는 문제를 디오판토스 방정식 (또는 부정방정식)이라 한다.요즘에도 그런지 모르겠는데, 필자가 고등학생일때 수학의 정석에 간단한 경우(상황이 특수한 경우)에 소개되어있다.정수론에서 보다 일반적인 방법으로 이 방정식을 푸는 방법을 소개한다.a,b,c∈Z이고 (적어도 하나는 0이 아니다.) d=gcd(a,b)라 하자. 이 때,(1) 방정식 ax+by=c의 해가 존재하기 위한 필요충분조건은 d∣c 이다.(2) x0,y0가 ax+by=c의 특수해(particular solution)일 때, 일반해는 다음과 같다.\[ x = x_0 + \bigg(.. 2024. 8. 19. [정수론] 소수와 관련된 알고리즘 (소수 판정, 에라토스테네스의 체, 오일러 피 함수) 소수, 에라토스테네스의 체, 표준분해, 오일러 피 함수소수와 합성수 (primes and composites)소수: 1과 자기 자신만을 약수로 가지는 수이다. 영어로 prime number라 하기 때문에 보통 p로 표기한다.합성수: 1보다 큰 자연수 중에서 소수가 아닌 수. 약수의 개수가 3개 이상이다.※ 1은 소수도 아니고 합성수도 아닌 수이다. 1을 소수로 분류하면 소인수분해가 유일하지 않기 때문인 것으로 보인다.※ 소수(prime number)의 발음은 '소쑤'이고, 소수(decimal notation)의 발음은 '소:수'이다. p≤n인 모든 소수 p에 대하여 p의 배수가 되는 합성수들을 모두 제거한 나머지는 모두 소수이다.따라서 n=46의 소수.. 2024. 8. 11. [정수론] 약수, 배수, 최대공약수, 최소공배수와 관련된 알고리즘 공약수와 최대공약수(GCD), 공배수와 최소공배수(LCM), 유클리드의 호제법 (Euclidean Algorithm)나눗셈 정리 (Division Algorithm)임의의 정수 a,b (b≠0)에 대하여 a=bq+r, 파이썬코드에서는간단히구할수있다0≤r파이썬코드에서는간단히구할수있다.q=a//br=aa, b \ (b \neq 0)에대하여에대하여b=ac를만족하는정수를만족하는정수c가존재할때가존재할때,b를를a의배수라하고의배수(multiple)라하고a를를b의약수또는인수라한다이때의약수(divisor)또는인수(factor)라한다.이때"a는는b를나눈다또는를나눈다"또는"b는는a$에 의하여 나누어떨어진다" 라고 하고, .. 2024. 8. 10. [정수론] 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리 정수론 4대 정리: 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리 정수론 4대정리에 대해 간단히 정리한다. 자세한 내용이나 증명은 이후 포스팅 할 예정이다.여기서는 정리의 내용과 간단한 활용방법에 대해 알아본다.페르마의 소정리 (Fermat's little theorem)정수 a, 소수 p에 대하여 다음이 성립한다.ap≡p(modp)a가 p로 나누어지지 않는 경우에(즉 p∤a, gcd(p,a)=1) 다음이 성립한다.ap−1≡1(modp) 역은 성립하지 않는다. 즉, 소수가 아닌 합성수 p인 경우에도 ap−1≡1(modp)인 경우가 존재한다.이런 p.. 2024. 8. 6. 이전 1 다음 728x90 반응형
