정수문제 2개

최대지수와 LTE Lemma 관련 문제를 풀다가 좋은 문제들을 소개한다. 

 

 

 

[문제1]

양의 정수 \(b, n>1\)에 대해 다음 조건을 만족하면 \(b=A^n\)꼴임을 보여라. (단, \(A\)는 정수)

(조건): 2이상의 모든 양의 정수 \(k\)에 대해 \(b-a_{k}^n\)이 \(k\)의 배수가 되는 정수 \(a_k\)가 존재한다.   

[IMO SL 2007 N2]

 

 

최대지수에 대한 기본적인 성질들로 풀리는 멋진 문제이다. 

 

sol)

[Claim]  \( v_p(x)\neq v_p(y)\) 이면 \(v_p(x\pm y)=\textup{min}\begin{Bmatrix}
v_p(x), v_p(y) \\
\end{Bmatrix}\) 이다. 

[Claim 증명] 

\(x=p^mu , y=p^nv\)라고 하자. 단, \(u, v\)는 \(p\)와 서로소이다.

일반성을 잃지 않고 \(m>n\)이라 하자.

\(x \pm y=p^n(p^{m-n}u\pm v)\)가 되고, \(gcd(p^{m-n}u\pm v, p)=1\)이므로, 

\(v_p(x\pm y)= n = \textup{min}\begin{Bmatrix}
v_p(x), v_p(y) \\
\end{Bmatrix}\) 가 되어 명제가 성립한다.

 

본 문제로 돌아와 \(b=A^n\)꼴이 되는 걸 부정하여 \(b\)를 나누는 어떤 소수 \(p\)에 대해

\(v_p(b)\)가 \(n\)의 배수가 아니라고 하자. 자명히 \(v_p(b)\neq v_p(a_{k}^n)\)이다.

따라서 \(v_p(b-a_k^n)=\textup{min}\begin{Bmatrix}
v_p(b), nv_p(a_k)  \\
\end{Bmatrix}\    \) 이다.

\(k | b-a_k^n \)이므로 \(v_p(k)\leq v_p(b-a_k^n)\leq v_p(b)\) 가 성립한다. 

이는 고정된 \(b\)에 대해 무한한 양의 정수 \(k\)에 대해 식이 성립하므로 모순이다. 

따라서 \(b\)를 나누는 모든 소수의 최대지수는 \(n\)의 배수이다. 

 

 

[문제 2]

소수 \(p\)와 양의 정수 \(x\)에 대해 다음 조건을 만족하는 순서쌍 \((x, p)\)를 모두 찾아라.

         $$ x^{p-1} \;  | \; (p-1)^x+1 $$

(단, \(x\leq 2p\)이다.)

[IMO 1999 P4]

 

 

sol)

[Claim]  \(p\)가 홀수라면 \(p|x\) 이다. (단, \(x>1\))

[Claim의 증명]

\(x\)의 최소 소인수 \(q\)를 잡자.

\((p-1)^x\equiv -1 , (p-1)^{2x}\equiv 1 \;(\textup{mod}\; q)\) 이므로, 

\(d=ord_q(p-1)\)이라 하면, \(d\nmid x\)이고 \(d|2x\)이다. 

또한, 페르마 소정리에 의해 \(d|q-1\)이다. 

\(d=2x\)면 \(q\geq 2x+1\) 이 되어 \(q|x\)에 모순이다. 

따라서 \(d\leq 2\)이다.\(d=1\)이면 \(p=2\)가 되므로 pass

\(d=2\)인 경우 \((p-1)^2\equiv 1 \;(\textup{mod} \; q)\) 가 되고, 위수의 정의에 의해

\((p-1)\equiv -1 \;(\textup{mod} \; q) \) 즉, \(p=q\)를 얻는다. 

따라서 \(p|x\)이다. 증명 끝

 

본 문제로 돌아와 위 조건을 만족하는 홀수인 소수 \(p\)를 찾자.

$$  v_p(x^{p-1})\leq v_p((p-1)^x+1) \Leftrightarrow (p-1)v_p(x)\leq v_p(p)+v_p(x) $$

(by LTE Lemma 조건: \(x\)는 홀수인건 easy, \(p\nmid p-1, 1\)이고 \(p|(p-1)+1\))

따라서 \(v_p(x)\leq 1/p-2 \)이다. 한편 Claim에 의해 \(v_p(x)\geq 1\)이므로, 이를 만족하는

소수 \(p=3\)이다.  \(x^2|2^x+1\)인 수들을 찾아주면 된다. 이 때 \(v_3(x)=1\)이다.

이를 만족하는건 \(x=3\)뿐이다. 따라서 \((3,3)\)은 한 해가 된다.

 

\(p=2\)인 경우엔 \(x=1,2\)가 가능하다. 

\(x=1\)인 경우엔 모든 \(p\)가 가능하다. 

종합하면 모든 해는 \((1,p), (2,2), (3,3)\)이다.