[정수론], 일차합동식

일차합동식은 일차방정식과 같은 형태지만 합동식이 들어가 있어 일차합동식이라 부른다.

식으로 표현하자면 ax+ b ≡ 0 (mod ⁡m)에 형태이다.

 

일차방정식이 있듯이 이차방정식이 있고 당연히 이차합동식 또한 존재한다.

 

x^2 + 1 ≡ 0 (mod 5)일 때  , f(x) = x^2 + 1 ≡ 0 (mod 5)

f(0) = 1 ≡ 1 (mod 5) ,  f(1) = 2 ≡ 2 (mod 5), f(2) = 5 ≡ 0 (mod 5)

f(3) = 10 ≡ 0 (mod 5), f(4) = 17 ≡ 2 (mod 5)

 

그로 인해 해가 존재하는건  x ≡ 2 (mod 5), x ≡ 3 (mod 5)가 이차합동식의 해이다.

답을 작성할 때 해가 존재하는 경우 위와 같이 적어주고 해가 존재하지 않을 경우 해가 존재하지 않다. 라 작성하면 된다.

 

위 식에서 계산은 덧셈으로 하였을 때 항등원은 0이며, m = 5 이므로 5 = {0 ,1, 2, 3, 4}로 f(x)의 x값안에 차례대로 대입하여 계산한다.

 

반대로 

 

만약 식이 곱셉이였을 때 항등원은 1이며, m 또는 p로 0을 제외한 수로 대입하며 계산해야한다.

 

일차 합동식 ax ≡ b (mod m)이 해를 가지기 위해 필요충분조건 d = (a, m)과 d | b일 때 성립된다. 

d = (a, m) = gcd (a, m) 즉 최대공약수 1이 되야하며, d | b의 수가 약수, 배수 관계가 되면 가능하다.

 

위 식의 경우 곱셈으로 되어있는 일차합동식인데 (a x s) + (b x t) = 1이 성립이 되어야 하며, 식을 풀어 나갈 때 "확장된 유클리드 알고리즘"으로 계산 해야한다. 

 

r = r_1 - (q × r_2 ), S = S1 - (q × S2 ), t = t1 (q x t2 )

r = 나머지