이번 시간에는 몇가지의 부정방정식들의 풀이를 들며, 부정방정식의 다양한 팁들을 설명해보고자 한다. #1.(4x-y)(4y-x)=306을 만족하는 자연수의 순서쌍의 개수는? 식 치환 4x-y=a 4y-x=b 치환 4a+b≡0(mod 15) a+4b≡0(mod 15) 이 두 식을 서로 빼면 a≡b(mod 15)임을 알 수 있다. a/15 · b/15=26×34×54 순서쌍의 개수는 7×5×5=175개 부정방정식을 전개하기 어려울 때, 이러한 형식으로 치환을 하여 문제를 풀어나갈 수 있다. #2.(a+b+2)/c=ab-2c 을 만족하는 자연수의 순서쌍 (a,b,c) 의 개수를 구하여라. 대소비교 c가 최대라면 2c≤ab≤c2 c=1,2 c=1 (a-1)(b-1)=5 ->(2,6,1), (6,2,1) c=2 (..

인수분해 -크기비교 -홀짝성 및 나머지 관찰 대수적 접근법 -이차방정식 이론-D≥0, D=k2 -일차인 변수에 대해 정리 -a/b∈Z일 때, a와 b가 어떤 문자에 관한 다항식일 경우, a의 차수가 b보다 낮도록 만들어보고 a≠0이면 /a/≥/b/(/ /은 절댓값 기호) 부등식 -식의 대칭성 -정수의 이산성 -양수 조건을 보고 크기를 비교하여 문자를 치환(차이치환) mod 관찰 -지수함수, !이 등장하는 형태 등에서 적당한 mod로 관찰해본다. -mod에 관한 다양한 이론들을 적용해본다. 최대공약수와 서로소 관찰 -소인수분배 -a/bc, gcd(a,b)=1 → a/c -ab=ck (a,b∈N), gcd(a,b)=1 → a=xk, b=yk +) 1≡n(mod n-1)

위수란? 2 이상의 정수 m 에 대해서 m 과 서로소인 정수 a일때, an 이 m으로 나눈 나머지가 1이 되는 가장 작은 n 을 mod m에 대한 a의 위수 라고 한다. ordm(a)=r이다. 원시근이란? 원시근에 대해서 설명하기 전에, 오일러 함수에 대해서 알아야 한다. 자연수 n에 대한 오일러 함수 Φ(n) = (n보다 작거나 같은 자연수 중, n과 서로소인 수의 개수)로서 정의 되는데, aΦ(m) 을 m으로 나눈 나머지가 1이 되지만, Φ(m)보다 작은 n에 대해서는 an 을 m으로 나눈 나머지가 1이 되지 않도록 하는 a가 존재할 때, a를 법 m(mod m)에 대한 원시근이라고 한다.

#2.소인수분해 관점과 최대공약수 설정 a,b 는 서로소인 정수라 하자. 임의의 자연수 c에 대하여, a+bx와 c가 서로소가 되도록 하는 정수 x가 존재함을 보여라. b,c의 모든 공통소인수를 p1,p2,....pt라 하자. 이제 b=p1e1...ptet×b' c=p1f1...ptet×c' gcd(c',b')=1 gcd(b,c')=1 이므로, bx≡1-a(mod c')인 정수 x가 존재한다. 따라서 gcd(a+bx,c')=1이다. 한편, 만약 gcd(a+bx,pi)=pi면 (pi,a)=1인데 이는 조건 gcd(a,b)=1와 모순이다. 따라서 gcd(a+bx,p1p2...pt)=1 c=p1f1...ptft×c'이라 gcd(a+bx,c)=1 을 얻는다. 중국인의 나머지 정리(CRT) b1,b2...,bn이..

#1.수열에서의 m의 배수 찾기 x1=-2 x2=5이고 모든 자연수 n에 대해서 xn+2=xn-2xn+1와 같이 정의된 수열 {xn}을 생각하자. 주어진 자연수 m에 대하여 {xn,n은 모든 자연수}의 원소 중에는 m의 배수가 존재함을 보여라. xn을 m으로 나눈 나머지를 rn이라고 하면 (r1,r2).....(rm^2+1,rm^2+2)에는 같은 두 쌍이 있다. (ri,ri+1)=(ri+k,ri+k+1) ri-1=2ri+ri+1≡2ri+k+ri+k+1≡ri+k-1(mod m) ri+2=ri-2ri+1≡ri+k-2ri+k+1≡ri+k+2(mod m) 따라서 xn=xn+k(mod m) n≤0일때도 확장해서 생각시, x0=1 x-1=0 x2k-1≡xk-1≡x-1≡0(mod m) 다음 문제처럼 수열에서 m의 배..