정수 #2.소인수분해 관점과 최대공약수 설정

수형도

#2.소인수분해 관점과 최대공약수 설정

a,b 는 서로소인 정수라 하자. 임의의 자연수 c에 대하여, a+bx와 c가 서로소가 되도록 하는 정수 x가 존재함을 보여라.

 

b,c의 모든 공통소인수를 p1,p2,....pt라 하자. 이제

b=p₁^e1...p_t^et×b'   c=p₁^f1...p_t^et×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)

b₁,b₂...,b_n이 주어진 정수이고, m₁,m₂,...,m_n이 쌍으로 서로소 (즉,∀i≠j, gcd(m_i,m_j)=1)인 자연수이면,

x≡b₁(mod m₁), x≡b₂(mod m₂), ...... , x≡b_n(mod m_n)

을 동시에 만족시키는 정수 x가 mod m₁m₂...m_n에 대하여 유일하게 존재한다.