수학동아 - 폴리매스

폴리매스 문제

아직 아무도 답을 모르는 문제에 도전하세요!

[대한수학회] 대17. [문제 수정 및 추가!] p-적합수

수학동아 2018.04.30 21:35 조회 2376

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

대한수학회 17번

P-적합수

문제 출제자 : 오병권 서울대학교 수리과학부 교수

6월 14일 오전 11시 문제를 수정합니다. Simon님이 지적대로 문제에 오류가 있어 고칩니다.

오병권 교수님께서 문제를 다시 검토한 결과 문제 2번에서 조건이 하나 빠졌다고 합니다. 이참에 문제도 더 다듬고, 문제 4번을 추가로 내주셨습니다.

대한수학회 폴리매스 17번 문제를 다시 즐겁게 풀어주세요~!

양의 정수 $\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 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 \}$ 이라 정의하자.

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_9_3$ = $\left \{\pm 5 \right \}$ 이므로 93은 5-적합수가 아니고, $\large t_2_7_3$ = $\left \{\pm 7 \right \}$ 이므로 273 역시 7-적합수가 아니다.

양의 정수 $n$ 은 $t_n\neq \varnothing$ 이 성립한다고 가정하고, $p$ 는 5 이상의 소수라 하자.

문제1. 양의 정수 $\LARGE n$ 이, 9의 배수고 $\LARGE p^2$ 의 배수가 아니면 $\LARGE p$ -적합수임을 보여라.

문제2. 양의 정수 $\LARGE n$ 이, 3으로 나누면 나머지가 2이고 $\LARGE p^2$ 의 배수가 아니면서 $\LARGE t_n\neq \left \{ 0\right \}$ 이면 $\LARGE p$ -적합수임을 보여라.

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

문제4. 3의 배수이면서 5-적합수인 정수 $\LARGE n$ 을 모두 구하여라.

※알립니다

Simon 친구가 소문제 (1), (2)번 문제를 해결했어요!

이전글 대16. 정보의 양 측정하기

다음글 대18. '색'다른 축구공

문제 찜하기 목록보기

댓글 작성하기

여백 패르마 Lv.5 2018.05.04 16:56

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

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

pf(1)) $n=a^{2}+b^{2},m=c^{2}+d^{2}$ 이라고 하자. 그러면 $n\cdot m$ 은 $a^{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$

댓글 작성하기 좋아요1 댓글수8
- 여백 패르마 Lv.5 2018.05.04 16:58
  
  정말정말 죄송합니다. 이것이 뭔 말을 숨기고 있는지 궁금하시겠지요... 아직 미완성인 풀이를 담고 있습니다. 양해부탁드립니다. ㅠㅠ
  
  좋아요0
- 여백 패르마 Lv.5 2018.05.13 18:36
  
  이제 나왔습니다!! 1번과 3번의 반절입니다. 따끈따끈하네요...
  
  좋아요0
- 구머 Lv.5 2018.05.13 23:08
  
  초등학생이 르장드르 기호를 다루다니..진짜 수준 쩌는데욥ㅎㅎ
  
  좋아요0
- 구머 Lv.5 2018.05.14 00:41
  
  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
- 베네딕트0724 Lv.6 2018.05.14 22:58
  
  중국 나머지 정리의 증명입니다 (출처: 인천대학교 과학영재교육원)
  
  여백 패르마님 초등학생 아니죠? 설마...
  
  좋아요1
- 여백 패르마 Lv.5 2018.05.15 08:38
  
  초등학생 맞는데요...^^
  
  좋아요0
- Simon Lv.2 2018.05.30 22:11
  
  이 풀이가 맞는 풀인가요?? 중간에 이해하지 못하는 부분이 있어서....
  
  이런 내용을 초등학생분이 다루신다니.... ㄷㄷ
  
  좋아요0
- ha-lin Lv.1 2019.06.18 20:40
  
  같은 초등학생인데 왜 나는 그게 이해 안되는걸까.. 대단하시네요.
  
  좋아요0
일곱바늘 Lv.1 2018.05.14 10:46

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

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

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

출제자드림

댓글 작성하기 좋아요0 댓글수3
- 베네딕트0724 Lv.6 2018.05.14 22:51
  
  진짜 출제자님인가? 아니면 그냥 낚신가? 이번에는 출제자님이 원래 내던 분이랑 달라서 모르겠네요.. 그런데 1번이 무척 쉽다는 건 뭐죠
  
  좋아요0
- 일곱바늘 Lv.1 2018.05.14 23:35
  
  출제자인 서울대 오병권교수 맞답니다. 그리고 저 계속 문제 내고 있습니다. 1번은 정말 쉬워요~~
  
  좋아요0
- 베네딕트0724 Lv.6 2018.05.14 23:54
  
  아... 이번 문제에 오병권 교수님이 출제해주셨다고 따로 써져 있어서 평소에는 다른 사람이 내주시나 착각했네요.ㅎㅎ
  
  좋아요0
베네딕트0724 Lv.6 2018.05.15 23:05

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

댓글 작성하기 좋아요0 댓글수1
- 김우현 기자 Lv.5 2018.05.16 09:02
  
  좋아요0
Simon Lv.2 2018.05.22 16:26

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

댓글 작성하기 좋아요0 댓글수7
- 베네딕트0724 Lv.6 2018.05.22 16:46
  
  아... 저도 거의 다 풀었는데 $4^{\alpha }(8\beta +7)$ 을 이용할 생각을 미처 못했네요
  
  좋아요0
- 일곱바늘 Lv.1 2018.05.22 21:27
  
  잘 하셨습니다!
  
  여기에서 질문 하나 더~
  
  t_n이 공집합이 아니라는 조건만 써서 증명할 수 있을까요? 즉,
  
  n이 9의 배수이고, 세 정수의 제곱의 합으로 쓰여지면 항상
  
  3의 배수인 세 정수의 제곱의 합으로도 쓰여진다.
  
  를 주어진 '알려진 사실'을 사용하지 않고 증명할 수 있을까요? 예를들어, n=99인 경우, 1^2+7^2+7^2=99이므로 9^2+3^2+3^2=99인 해도 존재한다.
  
  이렇게 문제를 내려고 했는데요, 처음부터 너무 어려워 보여서 '알려진 사실'을 힌트로 주었답니다~
  
  좋아요0
- 베네딕트0724 Lv.6 2018.05.22 23:19
  
  "t_n이 공집합이 아니라는 조건"이 무슨 뜻인가요?
  
  양의 정수 $\large n$ 이 $\large 4^\alpha (8\beta + 7)$ 꼴이 아니고 3으로 나눈 나머지가 1이 아니면 $\large t_n\neq \varnothing$ 이 성립한다.
  
  이걸 말하시는 건가요?
  
  좋아요0
- Simon Lv.2 2018.05.23 23:39
  
  이 방식을 언급하셨던게 맞나요???
  
  좋아요1
- 일곱바늘 Lv.1 2018.05.24 15:42
  
  예, 맞습니다. 잘하셨습니다~
  
  이제 2번을 도전해 보시기 바랍니다~
  
  일곱바늘
  
  좋아요0
- 여백 패르마 Lv.5 2018.05.28 15:50
  
  딱 하나 궁금한데, 왜 p-적합수가 아니면 $p\mid \frac{a+b-c}{3}$ 이죠?
  
  좋아요0
- Simon Lv.2 2018.05.29 08:02
  
  $n = a^{2}+b^2+(-c)^2$ 이기 때문입니다
  
  좋아요0
베네딕트0724 Lv.6 2018.05.25 00:10

2번 문제 simon님 1번 풀이랑 비슷하게 가봤는데 마지막 단계에서는 simon님 논리를 적용할 수가 없더라고요.

let $n=3k+2, p^{2}\nmid n$ $a^2+b^2+c^2=3k+2$ 이 때, a, b, c는 3의 배수 하나와 3의 배수가 아닌 정수 2개로만 나타난다. $(3k+1)^2\equiv (3k+2)^2 \equiv 1(\mod 3)$ 이기 때문이다. 3의 배수인 것을 c라고 놓으면,

$\begin {Bmatrix} a+b \equiv 0(a \not\equiv b)\\ a-b\equiv 0(a \equiv b)\end{matrix}$ 이다. 여기까지는 했습니다만, 1번과는 다른 풀이 방법으로 풀어야 할 수도 있습니다.

댓글 작성하기 좋아요0 댓글수5
- 여백 패르마 Lv.5 2018.05.25 15:23
  
  a는 3으로 나누면 나머지가 0, b는 3으로 나누면 나머지가 1, c를 3으로 나누면 나머지가 2입니다. 뭐, 순서는 바뀔 수 있지만.. 그리고 3의 배수 하나와 3의 배수가 아닌 정수 2개로만 나타난다가 아니라 3의 배수 1개, 3k+1 한개, 3k+2 한개입니다. 즉, 증명해야 하는 것은 If $a+b+c\equiv 0(\mod p)$ , $p^2\mid n$ 입니다.
  
  좋아요0
- 베네딕트0724 Lv.6 2018.05.25 21:38
  
  아하 -1이랑 2랑 합동이니까 그렇네요
  
  좋아요0
- 낙하운동중인 사과 Lv.1 2018.05.30 22:48
  
  오랜만에 복귀합니다.
  
  죄송한데, 제 컴퓨터가 너무 느려서 사진 업로드가 안 되네요... 꽤 괜찮은 아이디어가 나왔다고 생각하는데.
  
  어떻게 사진을 올릴 수 있을까요??
  
  좋아요0
- 낙하운동중인 사과 Lv.1 2018.05.30 22:51
  
  제가 증명한 것은 a+b+c가 법 p에 대해 0과 합동일때, p의 제곱이 n을 나눈다는 여백 패르마님의 아이디어입니다....
  
  좋아요0
- 김우현 기자 Lv.5 2018.05.31 00:34
  
  낙하운동중인 사과 친구! 수학동아 이메일(mathdonga@naver.com)로 사진을 보내줄 수 있나요???
  
  좋아요0
여백 패르마 Lv.5 2018.06.02 20:48

3번도 풀 수 있다고 생각합니다.

3-(1) $n$ 이 9의 배수일때 $n$ 은 $p$ -적합수이다.

Simon님의 풀이에 의하면 $a\equiv 0(\mod 3), b\equiv 0(\mod 3), c\equiv 0(\mod 3)$ 입니다. 그리고, $n$ 이 $p$ -적합수가 아니라고 하자. 그런다면 Simon 님의 풀이에 의하면 $p\mid a, p\mid b, p\mid c$ 입니다. 그런데 $a$ $=9, b=27, c=81$ 이라고 하면 $p\mid a, p\mid b, p\mid c$ 일 수 가 없습니다.

댓글 작성하기 좋아요0 댓글수2
- 베네딕트0724 Lv.6 2018.06.02 21:49
  
  무슨 뜻인지 자세히 설명해주실 수 있나요? 잘 이해가 안 가서요.
  
  좋아요0
- Simon Lv.2 2018.06.03 11:33
  
  그런 방식으론 어려울 것 같습니다. 제가 모순점을 찾은 곳은 $p|a, p|b, p|c$ 이므로 $p^2|n$ 라는 논리인데, 사실 $p^2|n$ 이 가능해 진다면 여기서 모순이 나올 수는 없습니다. 이런 접근이 아닌 $a\equiv 0(\mod 3), b\equiv 0(\mod 3), c\equiv 0(\mod 3)$ 이 성립하지 않는 근을 일반적인 경우에 대하여 찾으면 모순이 나오지 않을까 조심스레 예상해 봅니다.
  
  좋아요0
Simon Lv.2 2018.06.06 17:16

이 문제와 OEIS A025172가 관련이 있을까요? 문제를 풀던 도중에 이 수열의 절댓값과 같은 수열이 나오던데 왜 그런지 증명은 못하겠어요ㅠㅠ

link: https://oeis.org/A025172

댓글 작성하기 좋아요0 댓글수0
Simon Lv.2 2018.06.06 21:06

문제가 제가 원하던 데로 수정되었으니 그에 맞추어 마무리를 하도록 하겠습니다.

n은 존재 불가하다를 이야기 하기 전에 밑에서 얘기하는 부분을 봐주셨으면 해요

위 과정을 반복하다 보면 $x_a + y_a \equiv b(mod\3^\infty)\ where \; a, b\in\mathbb{Z}$ 와

$z_a \equiv c(mod\3^\infty)\ where \; a, c\in\mathbb{Z}$ 를 얻어 $x_a = y_a=z_a=0$ 이라는 것을 알 수 있습니다.

이를 위 식에 대입해 보면 $n = (3l+1)^2+(3l+1)^2+0^2$ 가 되며, 이 상황에서 $t_n = \{0\}$ 이 됨은

어렵지 않게 알 수 있습니다.

$Quod\;Eart\;Demonstrandum$

댓글 작성하기 좋아요0 댓글수8
- 베네딕트0724 Lv.6 2018.06.16 22:12
  
  simon님의 식 변형 능력에 감탄할 뿐입니다.... 어떻게 인수분해(는 아니지만)를 저렇게 하셨는지 궁금합니다.
  
  좋아요0
- Simon Lv.2 2018.06.17 21:55
  
  인수분해를 목적으로 한 것이니까 인수분해 맞습니다 ^^(별로 인수분해같이 보이진 않지만요)
  
  저 식 변형 $3^k$ 을 인수분해 해 보다 보니까 굉장히 신기한 일이 일어나더라고요.
  
  그걸 OEIS에 검색해 봤더니 https://oeis.org/A025172 요놈이 나오더라고요
  
  이 수열을 이용해서 비에타의 공식과 같은 것과 점화식을 풀어 보니까 이렇게 되더라고요
  
  좋아요0
- 김우현 기자 Lv.5 2018.06.26 09:02
  
  주정훈 멘토가 '잘 풀었다'는 답변을 보내왔습니다. 교수님께서 최종 확인하면 소문제 (2)번도 해결!!
  
  좋아요0
- Simon Lv.2 2018.06.26 17:17
  
  감사합니다!
  
  좋아요0
- Simon Lv.2 2018.07.02 20:10
  
  혹시 언제쯤 답변해 주실지 알 수 있을까요ㅠㅠ
  
  좋아요0
- 김우현 기자 Lv.5 2018.07.05 09:59
  
  검토가 늦어져서 미안해요, Simon 친구! 불철주야 대기하다가 답변이 오는 즉시 알려줄게요!!!
  
  좋아요0
- 일곱바늘 Lv.1 2018.07.06 13:03
  
  Simon님~
  
  잘 하셨습니다. 정답입니다. 축하축하~
  
  시간이 꽤 걸리지 않을까 했는데 의외로 빨리 푸셨네요.
  
  그리고 연락이 늦어 미안해요... 어떤 때는 매일 들어오다가도
  
  바빠지면 또 자주 못 오고 그래요.
  
  좀 더 자주 들를게요.
  
  아무튼 이 싸이트에 들어오는 모든 젊은 친구들 Go! Go! 입니다.
  
  일곱바늘
  
  좋아요1
- Simon Lv.2 2018.07.07 11:19
  
  감사합니다~
  
  문제 4번에 먼저 도전해 보도록 하겠습니다!
  
  Simon
  
  좋아요0
Simon Lv.2 2018.06.07 01:13

잠시만요 $p|0$ 을 인정하게 된다면은 문제 2는 참이 아님을 $n=2$ 일때 알 수 있습니다. 위에서 0은 세지 않는다고 생각하고 풀었는데 곤란해 졌네요...

댓글 작성하기 좋아요0 댓글수4
- Simon Lv.2 2018.06.10 21:27
  
  다시말해 문제 (2)는 $n=2$ 일때 $t_n=\{0\}$ 이 된다는 반례를 가지고 있고, $n=8$ 일때 또한 같은 이유로 반례가 됩니다. 원소 '0'만 있는 집합을 $t_n$ 으로 가질 때 p-적합수가 아니라는 것은 $n=42$ 일때 p-적합수가 아니라는 것으로 예시를 주셔서 분명하다고 생각합니다.
  
  문제가 증명하라는 명제가 모순이 나오는 이상한 상황이 생겼네요(?)
  
  좋아요0
- 여백 패르마 Lv.5 2018.06.10 21:36
  
  헉 그러면 2번 명제가 틀린 것이라고 결론낼 수 밖에... 그러면 2번은 증명할 필요가 없네요.
  
  좋아요0
- Simon Lv.2 2018.06.11 18:36
  
  제 생각에는 문제가 수정될 것 같네요(그랬으면 좋겠다는 생각도 들고요)
  
  좋아요0
- 일곱바늘 Lv.1 2018.06.13 12:50
  
  문제에 조건을 하나 빠트렸네요. Simon님, 지적해 주어서 감사합니다.
  
  기자분게 수정본을 보내드렸으니 조만간 올리실 것으로 생각됩니다.
  
  Enjoy Math~
  
  일곱바늘
  
  좋아요0
Simon Lv.2 2018.06.14 19:39

위에 (2)번 풀이 공개댓글로 전환하였습니다~

확인 부탁드립니다

댓글 작성하기 좋아요0 댓글수1
- 김우현 기자 Lv.5 2018.06.19 22:35
  
  현재 주정훈 멘토의 답변을 기다리는 중입니다~!! 혹시 그 전에 교수님이 나타나실지도!!!
  
  좋아요0
Simon Lv.2 2018.06.26 18:11

문제 4에서 $t_n = \{0\}$ 일때도 포함하는 건가요?

댓글 작성하기 좋아요0 댓글수4
- 김우현 기자 Lv.5 2018.07.03 13:37
  
  그러면 n이 5-적합수가 되지 않기 때문에 $t_{n}=\left \{ 0 \right \}$ 인 경우는 포함되지 않습니다~.
  
  좋아요0
- Simon Lv.2 2018.07.03 14:04
  
  그럼 (2)에 풀이는 맞나요 아님 틀리나요?
  
  언제쯤 답을 받을 수 있을까요 ㅠㅠ
  
  좋아요0
- 조가현 편집장 Lv.15 2018.07.06 13:40
  
  일곱바늘님께서 답글을 달아주셨어요~^^ 문제 풀이 대댓글을 확인해 주세요!
  
  좋아요0
- Simon Lv.2 2018.07.07 11:18
  
  부분해결 딱지 붙여주세요~
  
  좋아요0

여백 패르마 Lv.5 2020.04.08 20:50

저만 이런 오래된 문제를 파고 있는 것 같은 느낌적인 느낌....

어쨌든간에 #3 풀이 도전 시작해보겠습니다. 참고로 이 도전에는 원시근에 대한 내용이 많이 나오므로 원시근에 대한 lemma를 많이 넣었습니당~

P.S)mod n 이 라텍스 수식에서 그냥 modn 으로 나오네요....글고 나누어 떨어지지 않는다 의 기호가 없네요...

이 증명의 요지: 읽어 보시는 분들이 혼란스러울 것 같아 요지부터 작성합니다.

Step 1. 주어진 조건을 만족하는데도 $p$ -적합수가 아닌 양의 정수 $n$ 이 존재한다고 가정하자,

Step 2. $p$ -적합수가 아니기 위해서는 $p\mid a, p\mid b, p\mid c$ 이여야 한다.

Step 3. 이떄 주어진 조건을 만족하는 $n$ 에 대한,일반적인 $gcd(a,b,c)\not\equiv 0(mod p)$ 인 해가 존재하면 성립!!!

일단 $9\mid n$ 인 경우부터 보겠습니다.

<귀류법> $n=a^2+b^2+c^2, gcd(a,b,c)\not\equiv 0 (mod p)$ 일때 $p\mid a+b+c$ 라고 하자.

이때 ${a,b,c}$ 중 $p$ 의 배수가 존재하지 말아야 한다.

만약 존재한다면:

$W.L.O.G p\mid a$ 라고 두면, $p\mid b^2+c^2, p\mid b+c\Rightarrow p\mid 2bc$ 이고, $(p,2)=1$ 이므로, $p\mid b$ 또는 $p\mid c$ 이다. 즉, $p\mid gcd(a,b,c)$ 이므로 <모순>

그러므로, $a,b,c\not\equiv 0(mod p)$ 이다.

i) $p\equiv 2(mod 3)$ 인 경우

이떄 $(3, p-1)=1$ 이다.

$p\mid a+b+c\Leftrightarrow (-a)\equiv b+c (mod p)$ $\Leftrightarrow n\equiv (-a)^2+b^2+c^2\equiv 2(b^2+bc+c^2)\equiv 0(modp)$

그러므로, $b^3\equiv c^3(mod p), b^{(p-1)}\equiv c^{(p-1)}(mod p)\Rightarrow$ $ord_{p}(b\cdot \bar{c})\mid gcd (3,p-1)=1\Rightarrow b\equiv c(mod p)$

( $\bar{c}$ 는 $c$ 의 $modp$ 에 대한 잉여역수이다.)

그러므로, $p\mid b^2+bc+c^2\Rightarrow p\mid 3b^2\therefore p\mid b$ 이다. <모순>

ii) $p\equiv 1(mod 3)$ 인 경우

이떄 i)의 경우와 유사한 논리로 $a^3\equiv b^3\equiv c^3(mod p)$ 임을 알 수 있다.

Lemma (1). 모든 소수는 원시근을 가진다.

pf(1)) $mod p$ 에 대한 기약잉여계 $S=[1,2,3,...,p-1]$ 를 잡자.

Let) $X_d=[a\in S\mid ord_{p}a=d]$ & $f(d)=\left | X_d \right |$

이떄 $f(d)=\left | X_d \right |\geq 0, \sum_{d\mid p-1}f(d)=p-1=\sum_{d\mid p-1}\phi (d)$ .

또한, $p-1$ 의 모든 양의 약수 $d$ 에 대해 $\phi (d)\geq 1$ 이므로, $p-1$ 의 양의 약수 중 에는 $f(d)\geq 1$ 인 양의 약수 $d$ 가 존재한다.

이때, $f(d)\geq 1$ 인 경우 임의의 $X_d$ 의 원소 $a$ 를 잡자.

그러면, $ord_{p}a=d$ 이므로, $x^d\equiv 1(mod p)$ 는 $x\equiv a^0, a^1,..,a^{d-1}(mod p)$ 의 해를 가진다.

또한, 임의의 $X_d$ 의 원소 $c$ 를 잡자. $ord_{p}c=d$ 이므로, $c^d\equiv 1(mod p)$ 이다. 그러므로, $c$ 는 $[a^0, a^1,..,a^{d-1}]$ 의 한 원소와 $(mod p)$ 로 합동이다.

또, $ord_ma^k=\frac{ord_ma}{(k,ord_ma)}$ 이므로, $[a^0, a^1,..,a^{d-1}]$ 중 위수가 $d$ 인 원소는 $\phi (d)$ 개이다.

그러므로, 모든 소수는 원시근을 $\phi (p)$ 개 가지고 있다. ♦

이때 소수 $p$ 의 원시근을 $g$ 라고 하자.

이떄 $[g^1,g^2,...,g^{p-1}]$ 은 $(mod p)$ 에 대한 기약잉여계이다.

$a,b,c\not\equiv 0(mod p)$ 이므로, $a\equiv g^{a_{1}}, b\equiv g^{b_1},c\equiv g^{c_1}(mod p)$ 이라고 둘 수 있다.

$\therefore$ $g^{3a_1}\equiv g^{3b_1}\equiv g^{3c_1}(mod p)$ 이고, $ord_pg=p-1$ 이므로, $3a_1\equiv 3b_1\equiv 3c_1(mod (p-1))$ 이다. 이떄 $3\mid p-1$

이므로, $a_1\equiv b_1\equiv c_1(mod \frac{p-1}{3})$ 이다. $W.L.O.G a_1, b_1, c_1\in [1,2,...,p-1]$ ( $\because$ $ord_pg=p-1$ )

(1) $a_1=b_1/b_1=c_1/c_1=a_1$ 인 경우:

$W.L.O.G a_1=b_1$ . $\Leftrightarrow a\equiv b(mod p)$

이떄 $p\mid a^2+ab+b^2$ 을 만족해야 하므로, 자명히 모순이다.

(2) $W.L.O.G a_1>b_1>c_1$ 이라고 하자.

이떄 $a_1\equiv c_1+\frac{2(p-1)}{3}, b_1\equiv c_1+\frac{p-1}{3}, c_1\equiv c_1(mod p)$ 이다.

$\therefore a\equiv c\cdot g^{\frac{2(p-1)}{3}}, b\equiv c\cdot g^{\frac{(p-1)}{3}},c\equiv c(modp)$ 이다.

이제 주어진 조건을 다시 보자. $p\mid a+b+c$ 임은 자명하고, $p\mid n$ 임은 자명하다.

그러므로, 우리는 $3\mid a+b+c, 9\mid n, p^2\mid n$ 의 조건을 이용하면 된다.

Lemma (2)

홀수인 소수 $p$ 에 대해 $g$ 가 $p$ 의 원시근일 떄, $g$ 또는 $g+p$ 가 $p^2$ 의 원시근이다.

pf(2)) Let) $ord _{p^2}g=r$

$g^r\equiv 1(mod p^2)$ $\Rightarrow g^r\equiv 1(mod p)$ $\Rightarrow$ $p-1\mid r$

또한, $r\mid \phi (p^2)=p(p-1)$ 이므로, $r=p-1/p(p-1)$

i) $r=p(p-1)$ 인 경우: $g:p^2$ 의 원시근이다.

ii) $r=p-1$ 인 경우: Let) $h=p+g$

이때 $h\equiv g(mod p)$ 이므로, $h$ 는 $p$ 의 원시근이다.

또한, $h^{p-1}=(g+p)^{p-1}=g^{p-1}+(p-1)g^{p-2}p+...+(p-1)gp^{p-2}+p^{p-1}$ $\equiv g^{p-1}-pg^{p-2}\equiv 1-pg^{p-2}\not\equiv 1(mod p)$

이므로, $ord_{p^2}h=p(p-1)$ 이 성립한다. 즉, $h$ 는 $p^2$ 의 원시근이다.

Lemma (3)

정수 $m(\geq 3)$ 이 원시근을 가질 떄, $x^n\equiv a(mod m), (a,m)=1$ 에 대하여 $d=(n,\phi (m))$ 이라고 하면, 이 합동식은 $d$ 개의 해를 가진다.

pf(3)) $x^n\equiv a(mod m), (a,m)=1$ 과 다음 합동식은 동치이다. (By. 이산로그의 원리)

$n \cdot ind_{g}x\equiv ind_{g}a(mod \phi (m))$

이떄 다음 합동식은 $d\mid ind_{g}a$ 일떄만 $d$ 개의 해를 가진다.

$a\equiv c\cdot g^{\frac{2(p-1)}{3}}+a_2p, b\equiv c\cdot g^{\frac{p-1}{3}}+b_2\cdot p$ $,c\equiv c(mod p^2)$ 이라고 하자.

이때 $a^2\equiv c^2\cdot g^{\frac{4(p-1)}{3}}+2\cdot a_2\cdot c\cdot g^{\frac{2(p-1)}{3}}\cdot p(mod p^2)$ , $b^2\equiv c^2\cdot g^{\frac{2(p-1)}{3}}+2\cdot b_2\cdot c\cdot g^{\frac{(p-1)}{3}}\cdot p(mod p^2)$ , $c^2\equiv c^2(mod p^2)$ 임을 쉽게 알 수 있다.

그러므로, $a^2+b^2+c^2\equiv c^2\cdot [g^{\frac{4(p-1)}{3}}+g^{\frac{2(p-1)}{3}}+1]+2\cdot c\cdot p\cdot [a_2g^{\frac{2(p-1)}{3}}+b_2g^{\frac{p-1}{3}}]\equiv 0(mod p^2)$ 이다.

Lemma (2)와 같은 분류기준을 사용하면,

(a) $ord_{p^2}g=p-1$ 인 경우: $g^{p-1}\equiv 1(mod p^2)$ 이므로, $g^{\frac{2(p-1)}{3}}, g^{\frac{p-1}{3}}, 1$ 은 모두 $x^3\equiv 1(mod p^2)$ 의 해이다.

또한, $3\mid \phi (p^2)=p(p-1), p^2$ 은 원시근을 가지므로, $x^3\equiv 1(mod p^2)$ 의 모든 해는 $x\equiv (g+p)^{\frac{p(p-1)}{3}\cdot i}(mod p^2)$ 이다. (By. Lemma(2): $p^2$ 의 원시근은 $p+g$ 이기 때문이다.)( $1\leq i\leq 3$ )

또, Lemma (3)에 의해, $x^3\equiv 1(mod p^2)$ 는 3개의 해를 가지므로, $[g^{\frac{2(p-1)}{3}}, g^{\frac{p-1}{3}}, 1]$ $\equiv [(g+p)^{\frac{p(p-1)}{3}\cdot i}\mid 1\leq i\leq 3](mod p^2)$ 이 성립함을 알 수 있다.

$(g+p)^{\frac{2p(p-1)}{3}}+(g+p)^{\frac{p(p-1)}{3}}+1=\frac{(g+p)^{p(p-1)}-1}{(g+p)^{\frac{p-1}{3}}-1}$ 이다. 이때, $ord_{p^2}(g+p)=p(p-1), ord _{p}(g+p)=p-1$ 이고, $p\neq 3\Rightarrow \frac{p(p-1)}{3}\not\equiv 0(mod (p-1))$ 이므로, $(g+p)^{\frac{p(p-1)}{3}}\not\equiv 1(mod p), p^2\mid (g+p)^{p(p-1)}-1$ 이므로,

$(g+p)^{\frac{2p(p-1)}{3}}+(g+p)^{\frac{p(p-1)}{3}}+1=\frac{(g+p)^{p(p-1)}-1}{(g+p)^{\frac{p-1}{3}}-1}\equiv 0(mod p^2)$ 이다. 그러므로, $g^{\frac{2(p-1)}{3}}+ g^{\frac{p-1}{3}}+ 1\equiv 0(mod p^2)$ 임을 알 수 있다.

그러므로, $p\mid a_2\cdot g^{\frac{2(p-1)}{3}}+b_2\cdot g^{\frac{p-1}{3}}$ 이다.

댓글 작성하기 좋아요0 댓글수3

여백 패르마 Lv.5 2020.04.08 20:56

이거 풀다가 아주 심각하게 막혀서 좀 도와주세요~~~

좋아요0
Simon Lv.2 2020.07.14 17:54

와 오래전부터 매달리던 문제인데 이제 봤네요 시험 끝나면 다시 한번 매달려 보겠습니다 조금만 기다려주세요!

좋아요0
리프 Lv.7 2020.07.14 21:40

라텍스에서는 띄어쓰기 기호가 따로 있습니다. 좌측 상단 보면 네모_네모 이런 표시가 있을텐데 그거 누르면 돼요

좋아요0