정수론/정수론 문제풀이 26

[정수론](-)[r(i+2) < 1/2 r(i) ?]

유클리드 호제법을 a, b에 적용할 때 나오는 나머지 b=r0, r1, r2...에서 모든 i에 대해 r(i+2) 먼저 유클리드 호제법에서 r(i) = r(i+1)q(i+1) + r(i+2) 다.유클리드 호제법에선 모든 r >= 0이고, q>0이므로0 그리고 q(i+1)를 기준으로 경우를 나눠 살펴보자.if q(i+1) = 1?r(i) = r(i+1)q(i+1) + r(i+2) = r(i+1) + r(i+2)이다.여기서 r(i+1) > r(i+2) 이므로2r(i+2) 따라서 q=1이면 r(i+2)if q(i+1) >= 2?r(i+2) = r(i) - r(i+1)q(i+1)에서 q(i+1) >= 2 이므로r(i+1)q(i+1) >= 2r(i+1)즉, r(i) = r(i+2) + r(i+1)q(i+1) >=..

[정수론](-)[카마이클 수 판별]

561이 카마이클 수인지 판별하시오카마이클 수란, gcd(a, m) = 1일때, a^(m-1) ≡ 1 (mod m)를 만족하지만 소수가 아닌 m을 말한다.따라서m이 합성수이고gcd(a, m) = 1인 모든 a에 대해 a^(m-1) ≡ 1 (mod m)를 만족하는지 보이면 된다.1.561이 합성수?561 = 3 * 11 * 17이므로 합성수gcd(a, 561) = 1인 모든 a에 대해 a^(560) ≡ 1 (mod 561)?gcd(a, 561) = 1 이고 561의 인수가 각각 서로소이고 소수이므로,    gcd(a, 3) = 1    gcd(a, 11) = 1    gcd(a, 17) = 1 만족한다.따라서 3, 11, 17에 대해서 페르마의 소정리를 사용할 수 있다.    a^2 ≡ 1 (mod 3) ..

[정수론](-)[연립 합동방정식의 해 구하기]

나머지가 같은 경우조건 단순화 하기x ≡ b (mod m1), x ≡ b (mod m2), x ≡ b (mod m3)... 처럼 나머지 b가 같을 때는조건을 병합할 수 있다.x ≡ b (mod LCM(m1m2m3...))로 병합하고 풀자증명m1|x-b, m2|x-b, m3|x-b .... 이므로m1, m2, m3의 최소공배수로도 x-b는 나눠진다.이후 남은 식들이 단순하다면 그냥 한 식에 대해 x = m1k + b 꼴의 식을 구하고이걸 다른 식에 대입하며 푼다. 나머지가 다른 경우한 합동식에 대해 풀고 대입하기먼저 나머지가 가장 간단한 합동식에 대해 풀어 x=a1k1+b1를 구하고다음 식에 x대신 대입해서 k1 을 구한다.구한 k1으로 새로운 식 k1 = a2k2+k1을 만든다.이후 반복해서 모든 k를 ..

[정수론](-)[LCM = ab/gcd(a, b)]

두 정수 a, b에 대해 최소공배수 lcm(a, b) = ab/gcd(a, b)임을 보이시오.a, b의 어떤 공배수 d가 있다고 한다면a|d, b|d여야 하고최소공배수 lcm은 가장 작은 공배수이므로모든 d에 대해 lcm(a, b)|d이어야 한다. lcm(a, b) = ab/g라 하자. (g = gcd(a, b))ab/g | d -> ab | dg선형방정식의 정리에 의해 g = ax+by의 x, y를 항상 구할 수 있다. 따라서 해당 등식으로 바꾸면ab | d(ax+by)d는 a, b의 공배수이므로 d = am = bn (m, n은 정수)ab | bnax + amby = ab | ab(nx + my) 이므로따라서 모든 d를 ab/g가 나누므로 lcm(a, b) = ab/g다.

[정수론](-)[(p-1)! = p-1 (mod p)]

모든 소수 p에 대해 (p-1)! = p-1 (mod p)인가?p = 2에서 증명1 = 1 (mod 2) 이므로 참p = 3에서 증명2 = 2 (mod 3) 이므로 참p > 3에서 증명선형합동방정식의 정리에 의해 ax ≡ b (mod m), gcd(a, m) = 1일때유일한 해를 가진다. (x=bu/g, au+mv=1)(p-1)! (mod p)에서도 p-1, p-2, ... 1은 모두 p와 서로소 관계이다.따라서 aa' ≡ 1 (mod p)인 a'도 0~p-1 범위 내에 유일하게 가진다.이때 특수한 경우인 x^2 ≡ 1 (mod p)를 만족하는 x = 1, p-1 말고 나머지는 2~p-2가 짝수개이므로서로 짝지을 수 있다.a ≡ b (mod m1), a ≡ b (mod m2)⇒ a1a2 ≡ b1b2 (m..

[정수론](-)[ax+by+cz=1]

정수론 과제 중...문제: 1. 방정식 ax+by+cz = 1이 정수해를 가지는 조건은 무엇인가?         2. 해가 존재한다면 일반해를 찾는 방법은 무엇인가?         3. 예시로 155x+341y+385z=1의 정수해를 찾아라 1. 방정식 ax+by+cz = 1이 정수해를 가지는 조건은 무엇인가?a, b, c의 순서는 고려하지 않아도 된다.추측: gcd(a, b, c) = 1 이라면 ax+by+cz = 1이 정수해를 가진다.by 선형방정식 정리,    ax+by=gcd(a, b)를 만족하는 해인(x1, y1) (단, x1, y1은 정수)를 구할 수 있다    따라서 정수 p에 대해 p(ax+by) = pgcd(a, b)를 통해 gcd의 p배를 만드는 해도 찾을 수 있다.따라서 ax+by+c..

728x90
반응형