정수문제 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)\ne v_p(y)$ 이면 $v_p(x\pm y)=\text{min}\left\{\begin{array}{c}{v}_p(x),v_p(y)\end{array}\right\}$ 이다. 

[Claim 증명] 

$x=p^{m}u,y=p^{n}v$라고 하자. 단, $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=\text{min}\left\{\begin{array}{c}{v}_p(x),v_p(y)\end{array}\right\}$ 가 되어 명제가 성립한다.

 

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

$v_p(b)$가 $n$의 배수가 아니라고 하자. 자명히 $v_p(b)\ne v_p(a_k^n)$이다.

따라서 $v_p(b-a_k^n)=\text{min}\left\{\begin{array}{c}{v}_p(b),n{v}_p(a_k)\end{array}\right\}$ 이다.

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

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

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

 

 

[문제 2]

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

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

(단, $x\le 2p$이다.)

[IMO 1999 P4]

 

 

sol)

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

[Claim의 증명]

$x$의 최소 소인수 $q$를 잡자.

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

$d=or{d}_q(p-1)$이라 하면, $d\nmid x$이고 $d|2x$이다. 

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

$d=2x$면 $q\ge 2x+1$ 이 되어 $q|x$에 모순이다. 

따라서 $d\le 2$이다.$d=1$이면 $p=2$가 되므로 pass

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

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

따라서 $p|x$이다. 증명 끝

 

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

$$v_p(x^{p-1})\le v_p((p-1{)}^x+1)\iff (p-1)v_p(x)\le v_p(p)+v_p(x)$$

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

따라서 $v_p(x)\le 1/p-2$이다. 한편 Claim에 의해 $v_p(x)\ge 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)$이다.