주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대17. p-적합수

2018.04.30

같이 풀어볼까?

네이버밴드 구글플러스

이번 대한수학회 문제는 오병권 서울대 수리과학부 교수님께서 내주셨습니다. 어떤 문제인지 바로 확인해 볼게요!

 

양의 정수 \large n에 대해 \large S_n =\left \{ (a, b, c) \in \mathbb{Z}^3 : a^2 + b^2 + c^2 = n \right \} 이라 정의하자. 단, \large \mathbb{Z}는 정수 전체의 집합이다.

양의 정수 \large n\large 4^\alpha (8\beta + 7)(단, \large \alpha , \beta는 음이 아닌 정수)꼴이 아니면 집합 \large S_n이 공집합이 아님이 잘 알려져 있다.

이제 \large T_n =\left \{(a, b, c) \in S_n : a + b + c 는 3의 배수 \right \}는 3의 배수}, \large t_n =\left \{ \frac{a+b+c}{3} : (a, b, c) \in T_n \right \}이라 정의하자.

양의 정수 \large n\large 4^\alpha (8\beta + 7)꼴이 아니고 3으로 나눈 나머지가 1이 아니면 \large t_n\neq \varnothing이 성립한다.

앞으로 양의 정수 \large n은 항상 이 조건을 만족한다고 가정하자.

5 이상의 소수 \large p에 대해, 집합 \large t_n\large p와 서로소인 정수를 포함하고 있으면 \large n \large p-적합수라 정의한다. 

예를 들어, \large t_5_0= {0, 2, −2, 4, −4}이므로 임의의 소수 \large p ≥ 5에 대해 \large p-적합수이지만, \large t_4_2= {0}이므로 42는 모든 소수 \large p ≥ 5에 대해 \large p-적합수가 아니다.

 

 

문제1. 양의 정수 \LARGE n이, 9의 배수이고 \LARGE p^2의 배수가 아니면 \LARGE n은 임의의 소수 \LARGE p ≥ 5에 대해 \LARGE p-적합수임을 보여라.

 

 

문제2. 양의 정수 \LARGE n이, 3으로 나누면 나머지가 2이고 \LARGE p^2의 배수가 아니면 \LARGE n은 임의의 소수 \LARGE p ≥ 5에 대해 \LARGE p-적합수임을 보여라.

 

 

문제3.  문제 1과 2에서 양의 정수 \LARGE n\LARGE p^2의 배수이어도 주장이 역시 성립함을 보여라.

댓글 19

  • 여백 패르마 2018.05.04 16:56:35

    이 문제는 꽤 어렵군요. 정수론의 한 부분의 정리 (Lemma (1),(2),(3))를 꼭 알고 있어야 합니다.  (구머님의 >< 표시에 all rights reserved 가 없었기 때문에 사용합니다.laugh)

     Lemma (1)) 양의 정수인 n,m이 존재하고, nm은 두 제곱수의 합으로 나타낼 수 있다면, n\cdot m도 두 제곱수의 합으로 나타낼 수 있다.

    pf(1)) n=a^{2}+b^{2},m=c^{2}+d^{2}이라고 하자. 그러면 n\cdot ma^{2}c^{2}+a^{2}d^{2}+b^{2}c^{2}+b^{2}d^{2}=(ac+bd)^{2}+(ad-bc)^{2}이므로 두 제곱수의 합으로 나타내어진다. ><

    Lemma (2)) 소수 p가 두 제곱수의 합으로 나타내어지기 위한 필요충분조건은 p\equiv 1(mod 4)인 것이다.(예외로 p=2가 있지만, 그것은 제외한다.)

    pf(2)) p\not\equiv 0(mod 4)인 것은 자명하다. 그리고 p\equiv 2(mod 4)이면,  p는 소수가 되지 않기 때문에 p\not\equiv 2(mod 4)이다. 다음으로 p\equiv 1(mod 4)이라고 하자. 이때 (\frac{-1}{p})=(-1)^{\frac{p-1}{2}}=1이므로 이차합동식 x^{2}\equiv -1(mod p)의 해가 존재한다. 즉, a^{2}\equiv -1(mod p), 1\leq a\leq p-1인 정수 a가 존재하고 또 a^{2}+1^{2}=kp인 정수  k가 존재한다. 그런데 1\leq kp=a^{2}+1\leq (p-1)^{2}+1<p^{2}이므로 1\leq k\leq p-1이다. 그러므로  1\leq k\leq p-1인 적당한 정수 k에 대하여 x=a,y=1은 방정식 x^2+y^2=kp의 정수해이다. 이제 정수해를 가지는 방정식 x^2+y^2=kp,  1\leq k\leq p-1중에서  k의 값이 가장 작은 것을 m이라고 하고 m=1이라는 것을 증명하자. 이와 반대로 1\leq m\leq p-1이라고 가정하고 x=a,y=b를 방정식 x^2+y^2=mp의 정수해라고 하자. 이 때 a^2+b^2=mp이므로a_1\equiv a(mod (m)), -\frac{m}{2}\leq a_1\leq \frac{m}{2}         b_1\equiv b(mod (m)), -\frac{m}{2}\leq b_1\leq \frac{m}{2}인 정수 a_1,b_1을 택하면  a_1^2+b_1^2\equiv a^2+b^2\equiv mp\equiv 0이므로 a_1^2+b_1^2=k_1m인 정수 k_1가 존재하고 이때 k_1m=a_1^2+b_1^2\leq \frac{m^2}{2}=\frac{m}{2}m이므로 0\leq k_1<\frac{m}{2}<m이다. 그런데, k_1=0이라고 가정하면, 분명히 a_1=b_1=0이므로 a\equiv b\equiv 0(mod(m))이고 또 a^2+ b^2=mp이므로 m^2\mid mp 즉 m\mid p로 되어 1<m\leq p-1이라는 사실에 모순된다. 그리고, k_1m^2p=(a_1^2+b_1^2)(a^2+b^2)=(a_1a+b_1b)^2+(a_1b-b_1a)^2, a_1a+b_1b\equiv a^2+b^2\equiv 0(mod(m)), a_1b-b_1a\equiv ab-ba\equiv 0(mod (m))이므로, \frac{a_1a+b_1b}{m}\frac{a_1b-b_1a}{m}는 모두 정수이고 또 다음이 성립한다: (\frac{a_1a+b_1b}{m})^2+(\frac{a_1b-b_1a}{m})^2=k_1p 이것의 뜻은 1\leq k_1<m인 정수  k_1에 대해 방정식 x^2+y^2=k_1p가 정수해를 가진다는 것이고, 이것은  m의 최소성에 모순된다. 그러므로 m=1이고, 방정식 x^2+y^2=p는 정수해 x=a, y=b를 가진다. ><

    Lemma (3)) 양의 정수 n이 두 제곱수의 합으로 나타내어지기 위한 필요충분조건은 다음 조건을 만족해야 한다.   

    (i) n=t^{2} (t\geq 1)   (ii)  n=p_1^{e_1}\cdot p_2^{e_2}\cdot \cdot \cdot p_r^{e_r}t^2(e_1\geq 1,...,e_r\geq 1,t\geq 1)

    pf(3)) 양의 정수 n에 대해서 (i),(ii) 또는 다음이 성립한다: (iii) p^{2e+1}\parallel n(e\geq 0) 이고 p\equiv 3(mod 4) 인 소수 p가 존재한다. 

    먼저, (i)의 경우에 n=0^{2}+t^{2}이므로 두 제곱수의 합으로 나타내어 진다. 

    그리고 (ii)의 경우에 Lemma (2)에 의해 각 p_i는 두 제곱수의 합으로 나타내어 지고 또 t^{2}은 두 제곱수의 합으로 나타내어지므로 Lemma (1)에 의해 n도 두 제곱수의 합으로 나타내어진다. 

    마지막으로, (iii)의 경우에 대해 생각해보자. 여기에서 gcd(a,b)는 a,b의 최대공약수이다. 

    두 정수 a,b에 대해 n=a^{2}+b^{2}이라고 가정하자. 또, d=gcd(a,b)이라고 하자. 이때, d^{2}\mid n이므로 a_1=\frac{a}{d},b_1=\frac{b}{d}, m=\frac{n}{d^2}이라고 놓으면 a_1^{2}+b_1^{2}=m이고 gcd(a,b)=1이다. 이제 정수 k에 대해 p^{k}\parallel d라고 하자. 이때, p^{2k}\parallel d^{2}d^{2}\mid n이므로 p^{2k}\mid n이고, 또 가정에 의해 p^{2e+1}\parallel n이므로 2k\leq 2e+1이다. 그런데 n=d^{2}m이므로 p^{2e+1-2k}\mid m이고, 또 2e+1-2k는 홀수이기 때문에 2e+1-2k\geq 1이고 따라서 p\mid m이다. 

    한편, p\mid a_1이라고 가정하면 b_1^{2}=m-a_1^2이므로 p \mid b_1^{2}이고 따라서 p \mid b_1으로 되어 gcd(a_1,b_1)=1이라는 사실과 모순이다. 

    그래서 gcd(a_1,p)=1이므로 일차합동식 a_1x\equiv b_1(mod p)의 해 x가 단 하나 존재한다. 이 해를 x\equiv c(mod p)라고 하면, a_1^{2}+b_1^{2}\equiv a_1^{2}+(a_1c)^{2}\equiv a_1^{2}(1+c^{2}) (mod p)이고 , 1+c^{2}\equiv 0(mod p), 즉 c^{2}\equiv -1(mod p) 그러므로 이차합동식 x^{2}\equiv -1(mod p)의 해가 존재한다. 한편, p\equiv 3(mod 4)으므로 (\frac{-1}{p})=(-1)^{\frac{p-1}{2}}=-1이고, 따라서 모순이 생긴다. 그러므로 (iii)의 경우는 모순이다. ><

    본 증명) 이 문제의 대우명제를 증명하자. 1번과 3번의 반절을 증명하자. 1번과 3번의 반절은 다음과 같다: 'n이 9의 배수이면 n은 p-적합수임을 증명해라.' 이의 대우 명제는 다음과 같다: 'n이 p-적합수가 아니면 n은 9의 배수가 아니다.' 이 명제를 증명해야 한다. 

     a^{2}+b^{2}+c^{2}=n이다. 즉, a^{2}+b^{2}=n-c^{2}a^{2}+c^{2}=n-b^{2}b^{2}+c^{2}=n-a^{2}이다. Lemma (3)에 의해 a^{2}+b^{2}a^{2}+c^{2}b^{2}+c^{2} 모두 제곱수의 배수이다. 즉, n-a^{2}=\alpha t^{2}n-b^{2}=\beta m^{2}n-c^{2}=\gamma k^{2}이다. 즉, a=\sqrt{n-\alpha t^2}, b=\sqrt{n-\beta m^2}, c=\sqrt{n-\gamma k^{2}}이다. 당연히 이 식들의 값은 모두 정수이여야 한다. a,b,c\in t_n이라면 \sqrt{n-\alpha t^{2}}+\sqrt{n-\beta m^{2}}+\sqrt{n-\gamma k^{2}}\equiv 0(mod 3)이다. 그리고 n이 p-적합수 가 아니기 때문에 \sqrt{n-\alpha t^{2}}+\sqrt{n-\beta m^{2}}+\sqrt{n-\gamma k^{2}}\equiv 0(mod p)이다. \sqrt{n-\alpha t^{2}}+\sqrt{n-\beta m^{2}}+\sqrt{n-\gamma k^{2}}를 x라고 치환하면 \left\{\begin{matrix}x\equiv 0(mod 3)) \\ x\equiv 0(mod p) \end{matrix}\right.이라는 연립일차합동식이 나온다. 

    Lemma (4)) 두 양의 정수 m_1,m_2가 서로소일때, 다음이 성립한다: 임의의 두 정수 c_1,c_2에 대해 연립일차합동식 \left\{\begin{matrix}x\equiv c_1(mod m_1) \\ x\equiv c_2(mod m_2) \end{matrix}\right.는 법 m_1m_2에 관해 단 한개의 해 x\equiv u(mod m_1m_2)를 가진다. 증명은 귀찮다. 중국인의 나머지 정리이기 때문에 쉽게 증명을 알아낼 수 있을 것이다. 

    본 증명)  즉, \left\{\begin{matrix} x\equiv 0(mod3)\\x\equiv 0(mod p) \end{matrix}\right.의 일차연립합동식의 해는 x\equiv 0(mod 3p)이다.  즉,  \sqrt{n-\alpha t^{2}}+\sqrt{n-\beta m^{2}}+\sqrt{n-\gamma k^{2}}은 3p의 배수이다. 즉, 다음 명제를 증명해야 한다: \sqrt{n-\alpha t^{2}}+\sqrt{n-\beta m^{2}}+\sqrt{n-\gamma k^{2}}이  3p의 배수이면 n은 9의 배수가 아님을 증명해야 한다. 수학적 귀납법을 쓰자. n=9일 때는 자명하다. \sqrt{n-\alpha t^{2}}이 정수가 되는 경우가 없기 때문이다. 이제 9r\rightarrow 9r+9일떄 성립함을 보이자. 그러면 \sqrt{9r-\alpha t^{2}}\rightarrow \sqrt{9r+9-\alpha t^{2}}\sqrt{9r-\beta m^{2}}\rightarrow \sqrt{9r+9-\beta m^{2}}\sqrt{9r-\gamma k^{2}}\rightarrow \sqrt{9r+9-\gamma k^{2}}이다. \sqrt{x+a}-\sqrt{x}=\frac{\sqrt{x+a}+\sqrt{x}}{a}이라는 것을 응용하자. \sqrt{9r+9-\alpha t^{2}} -\sqrt{9r-\alpha t^{2}}=\frac{\sqrt{9r+9-\alpha t^{2}} +\sqrt{9r-\alpha t^{2}}}{9}\sqrt{9r+9-\beta m^{2}} -\sqrt{9r-\beta m^{2}}=\frac{\sqrt{9r+9-\beta m^{2}} +\sqrt{9r-\beta m^{2}}}{9}\sqrt{9r+9-\gamma k^{2}} -\sqrt{9r-\gamma k^{2}}=\frac{\sqrt{9r+9-\gamma k^{2}} +\sqrt{9r-\gamma k^{2}}}{9}이다. 즉, 9r\rightarrow 9r+9일때 문제의 a+b+c=\sqrt{9r+9-\alpha t^{2}}+\sqrt{9r+9-\beta m^{2}}+\sqrt{9r+9-\gamma k^{2}}이다. 9r일때의  a+b+c는 \sqrt{9r-\alpha t^{2}}+\sqrt{9r-\beta m^{2}}+\sqrt{9r-\gamma k^{2}}이다. 두 둘의  a+b+c의 차는 \frac{\sqrt{9r-\alpha t^{2}}+\sqrt{9r-\beta m^{2}}+\sqrt{9r-\gamma k^{2}} +\sqrt{9r+9-\alpha t^{2}}+\sqrt{9r+9-\beta m^{2}}+\sqrt{9r+9-\gamma k^{2}} }{9}이다. \sqrt{9r+9-\alpha t^{2}}+\sqrt{9r+9-\beta m^{2}}+\sqrt{9r+9-\gamma k^{2}}=x\sqrt{9r-\alpha t^{2}}+\sqrt{9r-\beta m^{2}}+\sqrt{9r-\gamma k^{2}}=y라고 치환하면 x-y=\frac{x+y}{9}\rightarrow x=\frac{5}{4}y이다. 즉, y가 9의 배수가 아니면 x도 9의 배수가 아니다. 수학적 귀나법으로 증명 끝.

                                          Q.E.D

     

    좋아요0 댓글수6
    • 여백 패르마 2018.05.04 16:58:02

      정말정말 죄송합니다. 이것이 뭔 말을 숨기고 있는지 궁금하시겠지요... 아직 미완성인 풀이를 담고 있습니다. 양해부탁드립니다. ㅠㅠ

      좋아요0
    • 여백 패르마 2018.05.13 18:36:55

      이제 나왔습니다!! 1번과 3번의 반절입니다. 따끈따끈하네요...

      좋아요0
    • 구머 2018.05.13 23:08:28

      초등학생이 르장드르 기호를 다루다니..진짜 수준 쩌는데욥ㅎㅎ

      좋아요0
    • 구머 2018.05.14 00:41:45

      Lemma (3)에 의해 a^{2}+b^{2}a^{2}+c^{2}b^{2}+c^{2} 모두 제곱수의 배수이다.  의 반례 4^2+5^2=41

      \sqrt{9r+9-\alpha t^{2}} -\sqrt{9r-\alpha t^{2}}=\frac{\sqrt{9r+9-\alpha t^{2}} +\sqrt{9r-\alpha t^{2}}}{9}\sqrt{9r+9-\beta m^{2}} -\sqrt{9r-\beta m^{2}}=\frac{\sqrt{9r+9-\beta m^{2}} +\sqrt{9r-\beta m^{2}}}{9},식의 전개에서 우변의 분모분자가 바뀌었습니다.

      좋아요0
    • 수학장 2018.05.14 22:58:36

      중국 나머지 정리의 증명입니다 (출처: 인천대학교 과학영재교육원)

      여백 패르마님 초등학생 아니죠? 설마...

      좋아요1
    • 여백 패르마 2018.05.15 08:38:13

      초등학생 맞는데요...^^

      좋아요0
  • 일곱바늘 2018.05.14 10:46:31

    여백페르마님~ 말씀하신것처럼 그렇게 복잡한 정리가 필요하지는 않습니다. 물론 그러한 것들을 이용하면 좀 쉬운 풀이가 있을 수는 있겠네요.

    1번은 무척 쉽고요, 2번이 하이라이트입니다~ 

    3번은 아마 고등학교 교과과정으로는 풀이가 없을 거라고 생각됩니다. 찾으시면 저 좀 가르쳐 주세요~

    출제자드림

     

     

     

     

    좋아요0 댓글수3
    • 수학장 2018.05.14 22:51:49

      진짜 출제자님인가? 아니면 그냥 낚신가? 이번에는 출제자님이 원래 내던 분이랑 달라서 모르겠네요.. 그런데 1번이 무척 쉽다는 건 뭐죠

      좋아요0
    • 일곱바늘 2018.05.14 23:35:57

      출제자인 서울대 오병권교수 맞답니다. 그리고 저 계속 문제 내고 있습니다. 1번은 정말 쉬워요~~

      좋아요0
    • 수학장 2018.05.14 23:54:29

      아... 이번 문제에 오병권 교수님이 출제해주셨다고 따로 써져 있어서 평소에는 다른 사람이 내주시나 착각했네요.ㅎㅎ

      좋아요0
  • 수학장 2018.05.15 23:05:12

    댓글이 너무 적은데요;; 수학동아 기자님들 이거 기사로 쓰실 때 난감하시겠어요 *-*

    좋아요0 댓글수1
    • 김우현 기자 2018.05.16 09:02:10

      cryingcryingcrying

      좋아요0
  • Simon 2018.05.22 16:26:26

    교수님은 이 풀이를 기대하고 계셨었나요? 훨씬 쉽긴 한데

    좋아요0 댓글수5
    • 수학장 2018.05.22 16:46:18

      아... 저도 거의 다 풀었는데 4^{\alpha }(8\beta +7)을 이용할 생각을 미처 못했네요

      좋아요0
    • 일곱바늘 2018.05.22 21:27:52

      잘 하셨습니다!

      여기에서 질문 하나 더~

      t_n이 공집합이 아니라는 조건만 써서 증명할 수 있을까요? 즉,

       

      n이 9의 배수이고, 세 정수의 제곱의 합으로 쓰여지면 항상

      3의 배수인 세 정수의 제곱의 합으로도 쓰여진다.

       

      를 주어진 '알려진 사실'을 사용하지 않고 증명할 수 있을까요?  예를들어, n=99인 경우, 1^2+7^2+7^2=99이므로 9^2+3^2+3^2=99인 해도 존재한다.

      이렇게 문제를 내려고 했는데요, 처음부터 너무 어려워 보여서 '알려진 사실'을 힌트로 주었답니다~   

       

      좋아요0
    • 수학장 2018.05.22 23:19:30

      "t_n이 공집합이 아니라는 조건"이 무슨 뜻인가요?

      양의 정수 \large n\large 4^\alpha (8\beta + 7)꼴이 아니고 3으로 나눈 나머지가 1이 아니면 \large t_n\neq \varnothing이 성립한다.

      이걸 말하시는 건가요?

      좋아요0
    • Simon 2018.05.23 23:39:04

      이 방식을 언급하셨던게 맞나요???

      좋아요1
    • 일곱바늘 2018.05.24 15:42:48

      예, 맞습니다. 잘하셨습니다~

      이제 2번을 도전해 보시기 바랍니다~

      일곱바늘

       

       

      좋아요0