정수 #1.mod의 기본 성질

모듈러 공법

#1.수열에서의 m의 배수 찾기

x₁=-2 x₂=5이고 모든 자연수 n에 대해서 x_n+2=x_n-2x_n+1와 같이 정의된 수열 {x_n}을 생각하자. 주어진 자연수 m에 대하여 {x_n,n은 모든 자연수}의 원소 중에는 m의 배수가 존재함을 보여라.

 

x_n을 m으로 나눈 나머지를 r_n이라고 하면 (r₁,r₂).....(r_m^2+1,r_m^2+2)에는 같은 두 쌍이 있다.

(r_i,r_i+1)=(r_i+k,r_i+k+1)

r_i-1=2r_i+r_i+1≡2r_i+k+r_i+k+1≡r_i+k-1(mod m)

ri+2=ri-2ri+1≡ri+k-2ri+k+1≡ri+k+2(mod m)

따라서 x_n=x_n+k(mod m)

n≤0일때도 확장해서 생각시,

x₀=1 x_-1=0

x_2k-1≡x_k-1≡x_-1≡0(mod m)

 

다음 문제처럼 수열에서 m의 배수를 찾으려면 주기를 찾는 것이 중요하다. 그 예시로 아래의 문제를 보도록 하자.

20ⁿ-13ⁿ-7ⁿ이 103의 배수가 되는 자연수 n을 모두 구하여라.

전체 합(또는 차)의 주기가 필요한 상황이다.

페르마 소 정리나 이항정리 등을 사용하려고 하면 풀리지 않는 문제다. 한땀한땀 열심히 노가다해야 한다.

열심히 노가다를 하다 보면

20⁶≡13⁶≡7⁶(mod 103)을 확인할 수 있다.

n=6k+r(0≤r<6, r은 자연수)꼴로 두고 대입시 r=±1일때만 가능하다는 것을 알 수 있다.

따라서 n=6k±1꼴인 모든 자연수

이 경우가 주기를 찾는 방법 중 노가다에 속하는 방법이다. 이제 아래의 방법은 노가다를 하지 않고 주기를 찾는 방법이다.

 

n≥1에 대하여 a_n=2ⁿ+3ⁿ+6ⁿ-1와 같이 정의된 수열을 생각하자. 모든 자연수 n에 대하여 a_n과 서로소가 되는 자연수를 모두 찾아라.

#1.수열에서의 m의 배수 찾기에서 배운 방법을 활용해보자.

페르마 소 정리에 의해 a_i≡a_i+p-1(mod p) (단, p≠2,3)

n≥1이라고는 했지만 n을 음수까지 확장하여 i에 -1을 대입시 a_-1=0이기 때문에 a_p-2≡0(mod p)임을 알 수 있다.

p=2,3일때는 mod 2,3에 대하여 살펴볼 경우, a_n이 2,3의 배수인 경우가 나온다는 것을 알 수 있다. (a_n은 항상 짝수,a_n은 n이 짝수일때 3의 배수) 따라서 모든 자연수 n에 대하여 an과 서로소가 되는 수는 1밖에 없다.

 

이와 같은 점화식의 주기를 찾는 방법이 있다.