본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대63. 원분다항식의 성질
수학동아 2022.02.22 09:29 조회 1754

대한수학회 63번

 

 

원분다항식의 성질

 

문제 출제자 : 현윤석 인하대학교 수학과 교수

 

 

 

* 2022. 03. 07. 복소수 설명에 수정사항이 있습니다.

 

귀납법을 사용하면, z=r(cos   heta +isin   heta ) 일 때, z^{n}=r(cos(n   heta )+isin(n   heta )) 가 됨을 쉽게 보일 수 있다. 

-> 귀납법을 사용하면, z=r(cos   heta +isin   heta ) 일 때, z^{n}=r{\color{Red} ^{n}}(cos(n   heta )+isin(n   heta )) 가 됨을 쉽게 보일 수 있다. 

 

* 2022. 03. 15. 문제 제목에 수정사항이 있습니다.

 

복소수와 복소수의 극형식 -> 원분다항식의 성질

 

 

======================================================================================

현윤석 교수님의 피드백! (2022.04.22)

 

 1. 1번 문항에서 원분다항식이 정수계수임을 설명하는 것을 "원분다항식(q)는 x^q-1=0을 정수 계수에서 인수분해한 것이기 때문에 정수 계수 다항식입니다."  라고 한 줄로 설명하셨는데, 이는 설명이 조금 부족하다고 여겨집니다. 

  문제에서 주어진 원분다항식의 정의로만 보면,  이 다항식이  x^q-1=0을 정수 계수에서 인수분해한 결과물이라는 점은 자명하지 않은 사실입니다. 여기에 대해 약간의 보충이 필요하다고 느껴집니다.

    

2.  5번 문제의 경우, 충분조건을 하나 제대로 구하셨는데, 그 충분조건이 필요충분조건이 되지 않는다고 해서 "필요충분조건은 없습니다" 와 같이 단정지을 수는 없습니다. 

  무언가 q의 다른 조건들이 추가되거나, 다른 방식으로  필요충분조건을 찾을 여지는 있는거니까요. 

   즉, 마치 서울에서 부산으로 갔다가 오는 왕복 도로를 찾으려고 하는데, 서울에서 부산으로 가는 도로는 찾았는데, 내가 찾은 그 도로로 부산에서 서울로 오지는 못한다고 해서 "서울에서 부산으로 왕복하는 도로는 존재하지 않는다!" 라고 말할수는 없다는 뜻이죠. 전혀 다른 도로가 있을수도 있으니까요.

======================================================================================

 

문제를 시작하기 전에, 먼저 복소수의 개념을 가볍게 살펴보도록 하자.

 

임의의 실수 $a, b$에 대하여, $a+bi$ 꼴의 수를 복소수라고 한다.

 

(여기서 $i$는 $\sqrt{-1}$을 의미하며, 제곱하면 $-1$이 되는 허수이다.)

 

따라서 $(2+3i)(1+i) = 2 + 3i + 2i + 3 i^2 = 2+ 5i -3 = -1+ 5i$와 같이 계산할 수 있다.

 

 

 

복소수 $z = a+bi$는 좌표평면상의 점 $P = (a,b)$와 대응시킬 수 있는데,

 

이 때 원점과 $P$사이의 거리를 $r$, $x$축의 양의 방향과 \overline{OP}가 이루는 각을    heta라 할 때,

 

z=r(cos   heta +isin   heta ) 가 되고, 이를 z=r   imes e^{i   heta } 와 같이 쓰기도 한다.

 

이를 복소수 $z$의 극형식 이라고 한다.

 

(잘 알려진 오일러의 식 $e^{i \pi } + 1 = 0$ 도 여기로부터 바로 얻어진다.)

 

귀납법을 사용하면, z=r(cos   heta +isin   heta ) 일 때,

 

z^{n}=r{\color{Red} ^{n}}(cos(n   heta )+isin(n   heta )) 가 됨을 쉽게 보일 수 있다. 

 

 

 

양의 정수 $q$에 대하여 복소수 $z$가 $z^q = 1$을 만족할 때, ``1의 $q$-제곱근'' 이라고 말한다.

 

만약 이러한 $z$가 $q$보다 작은 임의의 양의 정수 $k$에 대해서 $z^k \neq 1$ 을 만족하면,

 

특별히 ``1의 $q$-원시근'' 이라고 말한다. 복소수의 극형식으로 나타내면,

 

$1$의 $q$-제곱근은  $e^{\left(2i \pi {\frac{t}{q}}\right)}$ ($t = 0, 1, \cdots, q-1$) 들이 되고,

 

이 중 $\gcd (t, q) = 1$ 인 복소수들이 $1$의 $q$-원시근이 된다. 

 

 

 

양의 정수 $q$에 대한 원분다항식 (cyclotomic polynomial) $\Phi _q (x)$는,

 

이러한 $q$-원시근들을 근으로 갖는 다항식으로, 다음과 같이 정의된다. 

 

 $$ \displaystyle \Phi _{q}(x)=\prod _{\stackrel {1\leq t\leq q}{\gcd(t,q)=1}}\left(x-e^{2i\pi {\frac {t}{q}}}\right) $$

 

 

 

이제 다음 문제들을 풀어보자.

 

문제 도중 등장하는 $\mu(q)$는 뫼비우스 함수로,

 

$\mu(q)$는 $\mu(1) = 1$, $q$가 서로 다른 소인수 $k$개의 곱 일 때

 

$\mu(q) = (-1)^k$, 그 이외의 모든 경우에 $\mu(q) = 0$으로 정의된다.

 

또한 $\phi(q)$는 오일러 피(phi) 함수로, $q$ 이하의 양의 정수 중에서 $q$와 서로소인 것들의 갯수를 의미한다. 

 

 

 

문제 1.  $\Phi _3 (x) $, $\Phi _4 (x) $, $\Phi _6 (x)$  를 각각 구해보자. 또한, $\Phi_q (x)$ 가 항상 차수가 $\phi( q)$인 정수 계수 다항식임을 보여보자. 

 

 

 

문제 2. $\Phi_q (x)$의 $\phi(q) - 1$차항의 계수는 $-\mu(q)$가 됨을 보여라. (즉, 항상 $0, -1, 1$중 하나가 된다.)  

 

 

 

문제 3. 양의 정수 $u$에 대해 집합 $M_u$를 다음과 같이 정의하자.  $$M_u = \left\{ v \in \{ 0, 1, \cdots , u-1 \} \mid \gcd (v, u) = 1 \right\} $$  $a,b, c$가 양의 정수이고 $a,b$가 서로소일때, 집합 $T = \left\{at \mid t \in M_{bc} \right\}$ 를 생각하자. $T$의 원소들을 $b$로 나눈 나머지가 같은 것 끼리 묶으면, 각 묶음의 원소들의 갯수가 같음을 보여라.  

 

 

 

문제 4. 양의 정수 $m, q$에 대해,  $q^{\prime} = \frac{q}{\gcd(m, q)}$라 하고, 모든 1의 $q$-원시근들을 $x_1 , x_2 , \cdots, x_n$ 이라 하자.  $x_1 ^m  , \cdots , x_n ^m$ 들 중 같은 값을 갖는 것 끼리 묶으면, 각 묶음은 정확히 $\frac{\phi(q)}{\phi(q^{\prime})}$개의 원소를 가짐을 보여라.  그리고 이를 이용하여, 다음 식이 성립함을 증명하여라.  $$ x_1 ^m + \cdots + x_n ^m = \frac{\phi(q)}{\phi(q^{\prime})} \mu \left( q^{\prime} \right)$$  

 

 

 

문제 5. 원분다항식 $\Phi _q (x)$의 모든 계수는 항상 $0, -1, 1$ 중 하나일까? 만약 반례가 있다면, 반례가 되는 최소의 $q$값은 무엇일까? $\Phi _q (x)$의 모든 계수가 $0, -1, 1$  이 되도록 하는 $q$의 필요충분조건을 구할 수 있을까? 

 

 

 

 

 

  •  
    부분해결
    pure math Lv.6 2022.03.02 08:59

    1. 

    파이3 = (x - e2i\pi * 1/2)  파이4 = (x - e2i\pi * 1/3), 파이6 = (x - e2i\pi * 1/5)

    저는 1과는 서로소가 아니라는 전제를 두고 하였습니다.

    그리고, 1은 q = 1일때를 제외한 나머지 자연수 q에 대하여 원시근이 아니기 때문에, 1을 제외하였습니다.

    파이(x)의 차수는, (x - e2i\pi * t/q)를 곱한 횟수와도 같습니다. 곱한 횟수는 gcd(t,q) = 1이며, t = 1이 아닌 모든 t의 개수입니다.

    이것은 phi함수의 정의 자체와 같으며, \phi(q)와 같은 수입니다. 고로, 파이(x)는 항상 차수가 phi(q)인 정수 계수 다항식이다.

    댓글 작성하기 좋아요0 댓글수6
    •  
      강지원 멘토 Lv.4 2022.03.03 11:32

      원분다항식의 정의에 의해 \Phi_{3}(x)=\prod_{1\leq t\leq 3, gcd(t,3)=1}\left(x-e^{2i\pi\frac{t}{3}} \right )\Phi_{4}(x)=\prod_{1\leq t\leq 4, gcd(t,4)=1}\left(x-e^{2i\pi\frac{t}{4}} \right )\Phi_{6}(x)=\prod_{1\leq t\leq 6, gcd(t,6)=1}\left(x-e^{2i\pi\frac{t}{6}} \right )이고, 문제 1은 이 곱셈을 직접 계산해서 우리가 잘 알고 있는 다항식의 형태로 나타내는 문제입니다. 예를 들어 \Phi_{5}(x)=\prod_{1\leq t\leq 5, gcd(t,5)=1}\left(x-e^{2i\pi\frac{t}{5}} \right )는 실제로 계산해보면 \Phi_{5}(x)=x^4+x^3+x^2+x+1로 표현할 수 있습니다. \Phi_{3}(x),\Phi_{4}(x),\Phi_{6}(x)는 어떻게 계산할 수 있을까요?

      차수를 구하는 문제에서는 \left(x-e^{2i\pi\frac{t}{q}}\right)를 곱한 횟수를 잘 살펴보았습니다. 다만 t=1일 때 e^{2i\pi\frac{t}{q}}=e^{2i\pi\frac{1}{q}}는 실제로 1의 q-원시근이 되기 때문에 곱에서 제외되지 않습니다. 결국 곱한 횟수는 1\leq t\leq q\gcd(t,q)=1인 t(1도 포함)의 개수와 같은데 이것은 \phi(q)와 같으므로 결과적으로 차수가 \phi(q)가 됩니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.03 12:59

      아아 제가 1을 잘못 썼네요;;; 그냥 단순히 실수인 1일때만 한 것입니다!

      또한, 궁금한 것이 하나 있어서 여쭙는데, 차수의 계수를 구할 때, 2번 문제에서는 모든 근들을 더한 것이 뫼비우스 함수인 것을 증명하는 것입니다.

      삼각함수, 정수론 등 많은 것을 이용해도 잘 되지 않더라구요. 혹시 re^i세타 꼴인 것에서 더한 것은 실수로 옮길 수 있는 방법이 있을까요?? 예를 들어, e^2i파이*1/5 + e^2i파이*2/5 = -1(예를 들어, 계산은 틀림)처럼 바꿀 수 있는 방법이 있나요??

      좋아요0
    •  
      RedoC Lv.5 2022.03.03 20:07

      @pure_math 혹시 pure math님의 증명에서 어떤 부분으로부터 \Phi_q(x)가 정수계수다항식임을 보이는 지 설명해주실 수 있으실까요?

      좋아요0
    •  
      pure math Lv.6 2022.03.03 21:31

      아아 그리고 잘못 썼는데

      파이3은 1/3, 2/3을 곱한 거고,

      4는 1/4, 3/4

      6은 1/6, 5/6을 곱한 것입니다.

      좋아요0
    •  
      RedoC Lv.5 2022.03.03 21:54

      @pure_math 혹시 pure math님의 증명에서 어떤 부분으로부터 \Phi_q(x)가 정수계수다항식임을 보이는 지 설명해주실 수 있으실까요?

      이 질문에 대해서 답변해주실 때에는 @RedoC으로 멘션 주시면 감사드리겠습니다 (원래 질문 댓글 단 뒤에 이 댓글을 달았어야 했는데 까먹고 못 올렸네요;;)

      좋아요0
    •  
      pure math Lv.6 2022.03.04 11:57

      @RedoC

      q번쨰 원분다항식은 x^q-1=0인 다항식을 정수 계수에서 인수분해하여 마지막에 남은 식이기에 정수 계수 다항식이기 때문입니다! 또한, x^q-1=0은 q의 약수들 번째 원분다항식들을 약수로 가지기 때문이죠!

      좋아요0
  •  
    pure math Lv.6 2022.03.03 18:47
    확인요청중

    3.

    at \equiv n (mod b)(앞으로는 모듈러 기호 생략함, 너무 많음;;) 이라고 하자. 또한, n은 b와 서로소여야 하며, b보다 작아야 하기에 n의 개수는 phi(b)와 같다.

    또한, 나머지가 될 수 없는 것들을 원소가 0개라고 하면 안되며, 애초부터 집합 T에 그 나머지를 갖는 얘들이 없기에, 고려해주지 않는다.

    위의 식을 만족하는 최초의 t를 t라 하자. 또한, 가장 큰 t를 tk라 하자. tk <= bc-1이기에, tk는 b(c-1) + t이다. 그렇기에 t 부터 tk 까지의 개수는 c개이다. 그런데, tp= b(c-p) + t = bc-bp+t인데, bp-t = c의 배수인 p가 1부터 c중에 1개가 있다. (1<=p<=c이기 때문) 고로, n이 정해져 있으면, 반드시 개수는 c-1개 이다.

    또한, b와 c가 동시에 짝수이면 위의 식이 성립하지 않을 수도 있는데, 그렇다는 것은, 어차피 n은 짝수일 경우에만 고려해주면 되며, t는 홀수고, 고로 p는 존재하지 않으므로 개수는 c개가 된다.

    또한, 전체 t의 개수는 0부터 bc-1 까지에서, bc와 서로소인 수의 개수인데, 반대로 b, c의 배수를 사용해도 포함배제로 할 수 있다. 하지만, b와 c의 소인수분해 꼴이 명확하지 않기에 앞의 식이 제일 정확하다. 또한, n의 개수도 정해져 있기에 phi(b) * (c-1) = 0부터 bc-1 까지에서, bc와 서로소인 수의 개수 이다.

    아무튼, 고로, 어떤 n에 대해서든, n에 대한 t의 개수는 c-1개며, t의 개수가 곧 나머지가 같은 묶음의 원소의 개수이므로, 모든 개수가 c-1로 같다.

    또한, b, c가 동시에 짝수이면 어떤 n에 대해서든 n에 대한 t의 개수는 c개다.

    댓글 작성하기 좋아요0 댓글수14
    •  
      강지원 멘토 Lv.4 2022.03.06 23:22

      M_{bc}의 원소는 b뿐만 아니라 c와도 서로소가 되어야 한다는 사실을 유의하면서 풀이를 진행해주세요! 예를 들어서 t\in M_{bc}, 0<t<b라 해서 반드시 b(c-1)+t\in M_{bc}가 될 필요는 없습니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:25

      제가 c까지 서로소인 경우를 해봤는데 모든 나머지에 대해서 c와 서로소가 아닌 것들을 빼면, 위의 증명과 똑같은 방법으로 몇개가 제외됩니다!

      혹시 수정사항이 있다면 말씀해주세요!

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.06 23:31

      문제에 a와 b가 서로소라는 조건은 있지만, b와 c가 서로소라는 조건은 없기 때문에 위 풀이의 방법대로 그대로 진행할 수는 없습니다. 0부터 bc-1 중 bc와 서로소인 수의 개수는 \phi(b)*(c-1)이 아니라 \phi(bc)가 됩니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:34

      당장 수정해서 올리겠습니다!

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:42

      @강지원 멘토

      그렇다면 짝수개일때만 풀이가 잘못된 건가요?

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.06 23:44

      짝수/홀수가 중요한 것이 아니라, b와 c가 공통 소인수를 가질 수 있다는 사실이 중요합니다. 그 공통 소인수가 2라면 짝수가 문제가 되는 것이겠지만, 2가 아니라 3,5,7,\cdots도 얼마든지 가질 수 있습니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.07 12:06

      그렇다면, tp=bc-bp+t인데, 모든 t에 대하여 t는 bc와 서로소가 되어야 합니다.

      만약 tp가 bc와 서로소가 아닌 p가 존재한다고 하면, bp-t도 bc와 서로소가 아니어야 합니다. 하지만, t는 bc와 서로소입니다. 고로, bp-t는 b와는 서로소입니다.

      b와 c의 최대공약수를 k라고 합시다. b = vk, c=uk라고 합시다. bp-t가 bc와 서로소가 아니게 되는 bp-t는 c/gcd(b, c)인 u와 서로소가 아닌 것이 됩니다.

      일단, t는 u와 서로소이며, v와 u는 서로소입니다. 1 <= p <= c이기에, 그리고,  bp-t\equivphi(u) mod(u)인 p들만이 묶음에 들어갈 것이고, b, u는 고정이기에 모든 묶음에서 p의 개수는 같다.

      고로, 전체 묶음의 개수는 같다!

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.07 22:41

      b와 u가 서로소라면 제시된 합동식으로 증명이 바로 완료되지만, b와 u는 서로소가 아닐 수도 있습니다(물론, v와 u는 서로소가 맞습니다).

      좋아요0
    •  
      pure math Lv.6 2022.03.08 00:00

      서로소가 아니어서 p의 개수가 줄어들지 몰라도 b, u등은 고정이니 모든 n에 대해서 개수가 같아집니다! b, u가 서로소가 아니어도, 특정 n에 대해서만 그런 것이 아니기 때문에, 저 합동식은 맞습니다!!

      제 풀이의 핵심은 b, u가 고정이라는 것입니다!

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.08 00:27

      bu가 고정이더라도 t는 각각의 묶음에 따라 달라지기 때문에 t+(u와 서로소인 \phi(u)개의 수)의 집합이 달라지고, 그러면 bp\equiv t+(u와 서로소인 \phi(u)개의 수)\pmod u를 만족하는 p의 개수가 달라질 수 있습니다. 만약 bu가 서로소라면 어차피 b,2b,\cdots,ub가 \mod u에 대해 완전잉여계를 이루고 c가 u의 배수이기 때문에 t+(u와 서로소인 \phi(u)개의 수)가 \mod u에 대해 무엇이 나오든 개수는 상관없지만, 그렇지 않은 경우라면 t+(u와 서로소인 \phi(u)개의 수) 중 \gcd(b,u)의 배수가 몇 개인지 따져봐야 하는 상황이 발생합니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.08 11:09

      수정했습니다!

      증명했습니다!

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.08 23:12

      이 풀이에서도 같은 문제점이 나타납니다. 각각의 n마다 그에 해당되는 t_1, 그 t_1에 해당되는 c'이 서로 다르기 때문에 bp\equiv b-c'\pmod c를 만족하는 p의 개수가 달라집니다. b와 c가 서로소라면 문제가 없지만, 서로소가 아닐 경우 이는 문제가 됩니다. 단순히 변수의 이름을 바꾸는 정도가 아니라 조금 더 근본적으로 이 풀이의 논리상 문제점이 무엇인지, 그 문제점을 어떻게 해결할 지 생각이 필요합니다.

       

      참고로 a와 c가 서로소가 아니라고 해서 b와 c가 서로소일 필요가 없습니다. 예를 들어 a=4b=9c=6 이런 식으로 수가 주어져 있으면 a와 b는 서로소이지만 a와 cb와 c는 각각 서로소가 아니게 됩니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.08 23:31

      으어...더 고민해봐야겠네요 그럼 다른 소문제는 완벽히 다 된 건가요??

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.12 16:12

      그렇습니다 다른 소문제는 모두 해결되었네요!

      좋아요0
  •  
    pure math Lv.6 2022.03.04 14:48
    확인요청중

    2.

    이것은 모든 원시근의 합이 뫼비우스(q)와 같다는 것을 증명하는 것과 동치입니다.

    일단, 자명하게도 모든 단위근의 합은 0입니다. (xq-1=0이기 때문에) 근데, 그 단위근에는 1이 섞여 있으니, 1을 제외한 다른 단위근의 합은 -1이 됩니다.

    여기서, 예외 하나가 생깁니다. q=1 일때지요. q=1일 때는 자연스레 이 명제가 성립합니다.

    또한, 하나의 원시근을 x라 한다면, 모든 단위근의 합(1 제외)이 x + x^2 + x^3 + ......... + x^(q-1)가 되고, 이것이 -1이 됩니다. 

    근데, q의 약수인 p(예시)들에 대해서도 p + p^2 + p^3 +........+ p^(q-1) = -1이 성립합니다. 모든 p에 대해서 성립하니,

    교집합의 성질로 인해 원시근들의 합은 -1 + q - qC2 ........+-qCq-1이 됩니다.

    q가 오로지 소수의 1제곱들만을 인수로 가지면, 위의 식은 뫼비우스(q)가 됩니다.

    그런데, q가 소수의 제곱수를 인수로 가지면, 인수가 홀수개든 짝수개든, 홀수개면 +1이 추가로 되고, 짝수개면 -1이 추가로 되서(제곱수로 인해 약수들의 개수와 더하고 빼야 할 식의 개수가 달라져서) 어떻게 하든 0이 됩니다.

    고로, 모든 q에 대하여 q-원시근의 합은 뫼비우스(q)가 되니, phi(q)-1차항의 계수는 -뫼비우스(q)가 됩니다.

    댓글 작성하기 좋아요0 댓글수4
    •  
      강지원 멘토 Lv.4 2022.03.06 23:17

      1을 제외한 모든 단위근의 합이 -1이 된다는 사실을 이용하는 아이디어 맞습니다. pure math님의 풀이에서는 포함-배제의 원리를 이용해 직접 계산하다 보니 풀이가 복잡해진 감이 있는데 수학적 귀납법을 이용한다면 이를 좀 더 편하게 서술할 수 있습니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:22

      아하 그렇군요! 혹시 더 수정할 부분이 있나요??

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.06 23:24

      서술이 어려워서 그렇지 풀이 자체는 문제없어 보입니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:25

      네! 감사합니다!

      좋아요0
  •  
    조희승 Lv.4 2022.03.04 15:29
    확인요청중

    시작하기에 앞서 오일러 파이 함수의 성질에 대해 알아보자. phi(ab)=phi(a)*phi(b) 이다. 단, a,b는 서로소.(증명생략)이를 성질 1이라하자.

    4.  먼저 수열 ak 를 정의하자. 수열 ak(1<=k<=phi(q))는 q의 기약잉여계다. 단, 이 수열은 증가한다. 그리고 xk=e2pi*i*ak/q 이다. 이때 xsm=xtm(1<=s<t<=phi(q))이라면 e2m*pi*i*as/q=e2m*pi*i*at/q이다. 양변을 좌변으로 나누면,  1=e2pi*i*m(at-as)/q 이다. 그리고 이건 복소평면 상에서 길이가 1인 단위 벡터를 2pi*i*m(at-as)/q 라디안 만큼 돌린거라 볼 수있다. 이때 이는 2pi*i의 배수여야 하므로 m(at-as)/q는 자연수이다.  즉, q는 m(at-as)를 나눈다.이때 gcd(q,m)은 둘다 나누므로 소거해주면 q/gcd(q,m) 은 m/gcd(q,m)*(at-as)를 나눈다. 이때 q/gcd(q,m)가 q'의 정의이므로 q'은 m/gcd(q,m)*(at-as)을 나눈다. 이때 m/gcd(q,m)는 q'과 서로소이므로 q'이 at-as를 나눈다.그러면 at와 as는 mod q'에 대해 합동,즉 q'으로 나눈 나머지가 같다.즉, 같은 묶음에 속해있는 xk값들은 모두 ak를 q'으로 나눈 나머지가 같다. 그래서 ak를 j*q'+r이라 할 수있다. 이때 r은 q'과 서로소이다.(만약 q'과 서로소가 아니면 ak는 q'가 공통인수를 가지고, 그러면 q와 공통인수를 가져 기약잉여계의 정의에 어긋난다.)이때 j*q'+r은 q이하 r이상이므로  j의 범위는 0<=j<=q/q'-1(r/q'<=1이여서)그래서 한 묶음의 원소 개수는 q/q'이다.(일단은) 하지만 이는 q'의 소인수들만 생각했을 경우이므로 q를 q'의 소인수를 가진 부분 a와 q'과 서로소인 부분 b로 나누자. 즉 q=ab.이때 b의 임의의 소인수 p는 j*q'+r과 서로소 이다. 즉, j*q'+r은 0과 합동이 아니다.(mod p에대해)즉, j는 r/q'과 합동이 아니다.(실제로는 r/q'이 아니라 (r+p*x)/q'이 정수가 나올때의 값이다.이는 q'과 p가 서로소 여서 가능하다.)이때 j는 mod p의 값중 단 하나의 값만 아니면 된다.이는 오일러 phi함수의 정의와 똑같다! 오일러 phi함수 또한 소수 p의 대해 phi(pk)은 1이상 pk이하인 수들 중 p의 배수가 아닌, 즉 mod p중 단 하나의 값(0)이 아닌 수들의 개수이므로 j도 똑같다. 이를 모든 b의 소인수에 대해 반복하면 j의 개수는 \frac{q}{q'}*\frac{\phi (b)}{b}

    가 된다. 이때 q는 ab이므로 이 식은 \frac{a}{q'}*\phi (b)가 된다. 이때 a와 q'의 소인수는 똑같다(a의 정의이므로) 이때 a,q'의 소인수 p를 살펴보자. a에서 p의 지수를 x, q'에서 p의 지수를 y라 하자. 이때 phi(px)= px-px-1이다.(p에 배수를 뺀것)마찬가지로 phi(py)= py-py-1이다. 그래서 phi(px)/phi(py)=( px-px-1)/( py-py-1)=px/py*(\frac{1-\frac{1}{p}}{1-\frac{1}{p}})= px/py 이제 모든 p에대해 보자 그러면 \frac{\prod\phi (p^{x}) }{\prod\phi (p^{y})}=\frac{\prod p^{x} }{\prod p^{y}} 이 된다.(모든 소인수는 서로 서로소여서 phi함수의 성질 1을 사용했다)즉, a/q'=phi(a)/phi(q')이다. 그러면  \frac{a}{q'}*\phi (b)=\frac{\phi (a)\phi (b)}{\phi (q')}가된다. 이때 성질 1에의해 phi(a)phi(b)=phi(ab)(이유는 a와 q'의 소인수는 다 같은데 b는 q'과 서로소이기 때문.b의 정의)그러면 위식은 \frac{\phi (ab)}{\phi (q')} 그리고 q=ab이므로 \frac{\phi (q)}{\phi (q')}가 된다. 즉, j의 개수가  \frac{\phi (q)}{\phi (q')}이므로 하나의 묶음의 원소 개수는 \frac{\phi (q)}{\phi (q')}이다.Q.E.D.

    댓글 작성하기 좋아요0 댓글수2
    •  
      조희승 Lv.4 2022.03.04 15:32

      +모든 묶음의 원소 개수는 다 같다.

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.06 23:34

      각 묶음이 정확히 \frac{\phi(q)}{\phi(q')}개의 원소를 가진다는 사실을 잘 보였습니다! 이를 이용해 문제의 식 x_1^m+\cdots+x_n^m=\frac{\phi(q)}{\phi(q')}\mu(q')을 증명해보세요

      좋아요0
  •  
    pure math Lv.6 2022.03.04 17:53
    확인요청중

    4.

    xnm = xkm(편의상 n <= k)이라 하자. 또한, xp = e2파이i * p/q이다. e^m(2파이i * n/q) = e^m(2파이i * k/q)이므로, e^m * 2파이i*(k-n)/q = 1이다. 즉, m(k-n)/q가 자연수가 되야 한다. m(k-n)은 q의 배수이다.

    이때, 양변에 gcd(q,m)으로 나눠주면 m(k-n)/gcd(q,m)은 q'의 배수가 된다. gcd(q', m/gcd(q,m)) = 1 이므로 k-n은 q'의 배수이다. 그래서 k와 n은 모듈러 q'에 대하여 합동이다. 그래서 k = q' * i + n으로 나타낼 수 있다. n <= k <= q이므로 0 <= i <= (q-n)/q'이다. 근데 q/q' - 1 < (q-n)/q' = q/q' - n/q < q/q' 이므로 최대의 정수 k는 q/q' -1 이고, 총 개수는 q/q'이 된다. 그런데, q와 q'의 최대공약수를 w라 하자. w의 임의의 소인수는 k와 서로소이며, gcd(w의 임의의 소인수, q' * i + n) = 1이므로 q*i+n \not\equiv 0 mod(w의 임의의 소인수)가 되고, 이는 phi(w의 임의의 소인수) 와 같게 되어서, 최종적으로 i의 개수는 q/q' * phi(w)/w가 된다. i의 개수 = q/q' * phi(w)/w = (q/w)/q' * phi(w)가 된다. 편의상 q/w = c라 하자. i의 개수 = c/q' * phi(w)이 되고, c/q' = phi(c)/phi(q')이므로, (c, q'는 소인수가 같기 때문에) c/q' * phi(w) = phi(c)phi(w)/phi(q')이고, phi함수의 특징 때문에 phi(c)phi(w)=phi(cw)=phi(q)가 되어서, 최종적으로 i의 개수는 phi(q)/phi(q')가 되고, 이는 한 묶음 속에 있는 원소들의 개수와도 같다.

    이는 모든 묶음(k, n...등등)에도 성립하기에, 모든 묶음은 phi(q)/phi(q')개수로 같다.

    모든 원시근들의 m제곱의 평균 = 모든 원시근들의 m제곱들의 합/전체 개수(=phi(q)) = 각 묶음의 원소들이 갖는 같은 양(xnm=xkm이런 값)들의 전체 합 * phi(q)/phi(q')(이것은 한 묶음의 원소의 개수)/phi(q) = 각 묶음의 대푯값(위의 원소들이 갖는 같은 양)/phi(q')이다. 근데, 각 묶음의 대푯값들은 xq'-1=0의 원시근들이다. (q' * m = q의 배수이기 때문)

    2번에서 증명했듯이 이 원시근들의 합 = 뫼비우스(q') = 각 묶음의 대푯값들의 합이고, 모든 m제곱들의 합은 phi(q) * 뫼비우스(q')/phi(q') = phi(q)/phi(q') * 뫼비우스(q')이 된다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      강지원 멘토 Lv.4 2022.03.06 23:42

      전체적으로 맞는 풀이입니다. 다만 \mod q를 \mod w와 \mod c로 pure math님의 풀이처럼 나누게 된다면(사실 q가 q'의 배수이므로 w=q', c=q/q'이나 마찬가지) c가 q'과 겹치는 소인수가 있을 수 있습니다. 예를 들어 q=12q'=2라면 c=12/2=6으로 c와 q'이 서로소가 아니게 됩니다. 그렇기 때문에 \mod q를 나눌 때 위의 조희승님의 풀이처럼 q를 소인수분해했을 때 q'의 소인수들의 곱으로 이루어진 부분, 그리고 나머지 부분으로 나누어야 합니다. 예를 들어 q=12q'=2라면 \mod 2\mod 6으로 나누는 게 아니라 12=2^2\cdot 3이므로 \mod 4\mod 3으로 나누는 것이죠.

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:48

      아아 제가 그걸 미처 쓰지 못했네요;; 여기서의 c, w도 소인수의 곱 부분과 나머지 부분으로 생각해주시면 되겠습니다!

      좋아요0
  •  
    pure math Lv.6 2022.03.04 20:40
    확인요청중

    5.
    Migotti의 성질로 인해 n이 최대 2개의 서로 다른 홀수인 소인수를 가지고 있으면
    n번째 원분다항식의 계수는 1, 0, -1중에서만 나타난다.
    고로, 인수가 1, 2개일 때는 다른 계수가 나타나지 못하니 3개일 때부터, 작을 때부터 살펴봐야 한다.
    가장 작은 n은 3*5*7 = 105인데, 여기에는 다른 계수가 나타나므로 이것이 최소의 n이다.
    그리고, 계수가 모두 0, -1, 1 중 하나가 되기 위한 필요충분 조건을 구할 수 없다고 봅니다.
    그 이유는, 소인수가 3개 이상이어도 0, -1, 1만 나타나는 q도 존재하기 때문입니다.
    하지만, 소인수가 2개 이하면 반드시 0, -1, 1중 하나이기 때문이깅
    소인수가 2개 이하인 것은 계수가 0, -1, 1중 하나로만 되는 충분조건이다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      강지원 멘토 Lv.4 2022.03.06 23:49

      맞습니다! 실제로 소인수가 3개 이상인데 계수에 0,1,-1만 나타나는 q의 예시로는 무엇이 있을까요?

      좋아요0
    •  
      pure math Lv.6 2022.03.06 23:55

      앞서 말씀드렸던 105와 165, 595등이 있습니다! 파이썬으로도 구현이 가능하네요;;

      좋아요0
  •  
    pure math Lv.6 2022.03.12 16:58
    확인요청중

    3.

    at\equiv\phi(b) mod (b)입니다. 이를 만족하는 최초의 t를 t1이라 한다면, tp=b(p-1)+t1입니다. tp<=bc-1이므로, tp를 대입해서 정리하면 p<=c+1-(t1+1)/b입니다.

    문제의 조건은 일단 생각하지 않으면, 모든 집합에서 p의 개수가 같습니다. (1<=t<=b-1) 이제 문제의 조건을 대입하여 생각하면, tp 중에서 \phi(c)가 아닌 p를 골라내야 합니다.

    \phi(c)가 아닌 최초의 p를 p1이라 하면, 모든 묶음에서 p의 개수는 \phi(c)에 비례할 것입니다. (공리) (전체적인 p의 개수는 같고, (부등식에서 p는 일단 최대 c개 이기 때문) t1과 상관없어졌으므로, \phi(c)에 대하여 모든 묶음에서 같음) 고로, 모든 묶음의 개수는 같습니다.

    고로, 각 묶음의 원소들의 개수가 같습니다.

    댓글 작성하기 좋아요0 댓글수6
    •  
      강지원 멘토 Lv.4 2022.03.15 23:51

      \phi(c)가 아닌 최초의 p를 p1이라 하면, 모든 묶음에서 p의 개수는 \phi(c)에 비례할 것입니다. (공리) (전체적인 p의 개수는 같고, (부등식에서 p는 일단 최대 c개 이기 때문) t1과 상관없어졌으므로, \phi(c)에 대하여 모든 묶음에서 같음) 고로, 모든 묶음의 개수는 같습니다.

       

      이 부분이 정확히 무엇을 의미하는지 설명이 더 필요합니다

      좋아요0
    •  
      pure math Lv.6 2022.03.16 15:54

      음.. 전체 p의 개수가 같고, 빠지는 p의 개수도 같으니 묶음의 원소의 개수가 같다는 말이었습니다!

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.19 23:30

      빠지는 p의 개수가 같다 부분이 증명의 핵심인 것 같은데 엄밀한 풀이로 완성되려면 왜 그런지에 대한 설명이 추가적으로 필요합니다.

      좋아요0
    •  
      pure math Lv.6 2022.03.20 11:18

      그런가요..? 근데 밑에 조희승님의 풀이를 보니 이 문제도 해결된 것 같고, 모둔 소문제가 해결된 것 같습니다!

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.21 23:00

      그렇습니다 결국 문제가 모두 해결되었네요!

      좋아요0
    •  
      pure math Lv.6 2022.03.21 23:25

      오오오ㅗ오오오오ㅗ오오 드디어.. !!!!!!!!!!!!! 요청을 드려주십시오!

      좋아요0
  •  
    조희승 Lv.4 2022.03.12 21:09
    확인요청중

    문제3.

    문제4의 방식과 비슷하게 하면 됨.

    일단 집합 T의 두 원소 at1을 b로 나눈나머지와 at2를 b 로 나눈 나머지가 같을려면 at1\equivat2(mod b)여야 함. 그러면 a(t1-t2)\equiv0(mod b)여야 함. 이때 a와 b는 서로소(문제정의) 이므로 a를 나눌 수 있어서 t1\equivt2(mod b)여야 한다. 그래서 같은 묶음에 속하는 원소들은 bk+r로 볼수있다.(이때 1<=r<=b,r과 b는 서로소)이때  1<=bk+r<=bc 이므로 k는 0<=k<=c-1

     이므로 일단 c개다.이때 c를 b와 공통 소인수를 가지는 q와 공통소인수가 없는 부분 w로 나눌 수 있다. 이때 c=qw.이때 q의 임의의 소인수 p에 대해 bk+r이 p와 서로소여야 하는데, bk는 p로 나누어 떨어져 패스하고, r은 r의 조건이 b와 서로소인데 p는 b의 소인수 이므로 서로소다. 어떤 k든 다 성립한다. 이제 w를 보면 w의 임의의 소인수 p에 대해 bk+r\equiv0(mod p)이므로 k\equiv-r/b(mod p)이다.(b가 p와 서로소여서 무조건 정수-r+pn/b가 존재.) 이때 k가 mod p에대해 하나의 값만 아니면 되니 오일러 phi함수에 대응시킬수 있다.(phi함수는 0 만 아니면 되는 거니 대응 가능하다.) 그래서 k의 개수는 c*phi(w)/w 로 다 똑같다.즉, 각 묶음의 개수가 모두 같다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      조희승 Lv.4 2022.03.12 21:11

      수정: 각 묶음의 개수가 모두 같다->각 묶음의 원소개수가 같다.

      좋아요0
    •  
      강지원 멘토 Lv.4 2022.03.15 23:53

      잘 풀었습니다!

      좋아요0
  •  
    pure math Lv.6 2022.03.14 23:54
    확인요청중

    정리

    1.

     \Phi_{3}(x)=\prod_{1\leq t\leq 3, gcd(t,3)=1}\left(x-e^{2i\pi\frac{t}{3}} \right )\Phi_{4}(x)=\prod_{1\leq t\leq 4, gcd(t,4)=1}\left(x-e^{2i\pi\frac{t}{4}} \right )\Phi_{6}(x)=\prod_{1\leq t\leq 6, gcd(t,6)=1}\left(x-e^{2i\pi\frac{t}{6}} \right ) 이고, 원분다항식의 차수는 x를 곱한 횟수, 즉 q 이하이면서 q와 서로소인 수들의 개수와 같으니 원분다하식의 최고차항의 지수는 \phi(q)인 것입니다. 또한, 원분다항식(q)는 xq-1=0을 정수 계수에서 인수분해한 것이기 때문에 정수 계수 다항식입니다.

    즉, 원분다항식(q)는 최고차항의 지수가 \phi(q)이면서 정수계수다항식입니다.

    2.

    이 문제는 모든 원시근의 합이 뫼비우스(q)와 같다는 것을 증명하는 것과 동치입니다. 우선, 1을 제외한 단위근들의 합은 -1입니다. 그런데, q의 약수인 임의의 p에 대해서도, p에 대한 단위근(1 제외)들의 합은 -1입니다. 또한, q-단위근에 p-단위근이 포함되어 있습니다. 포함-배제의 원리로 모든 원시근들의 합은, (교집합의 성질) -1 + q - qC2 ........+-qCq-1 이 됩니다. 어떤 q에 대해서든, 위의 식은 뫼비우스(q)이기에 모든 q-원시근들의 합은 뫼비우스(q)입니다.

    즉, 원분다항식(q)의 \phi(q)-1차항의 계수는 -뫼비우스(q)가 됩니다.

    3.

    at\equiv\phi(b) mod (b)입니다. 이를 만족하는 최초의 t를 t1이라 한다면, tp=b(p-1)+t1입니다. tp<=bc-1이므로, tp를 대입해서 정리하면 p<=c+1-(t1+1)/b입니다. 우선, 모든 집합에서 p의 개수가 c개로 같습니다. (1<=t<=b-1) 이제 문제의 조건을 대입하여 생각하면, tp 중에서 \phi(c)가 아닌 p를 골라내야 합니다. \phi(c)가 아닌 최초의 p를 p1이라 하면, 모든 묶음에서 p의 개수는 \phi(c)에 비례할 것입니다. 더 계산을 하자면, b와 c에서 c와 b의 최대공약수를 k, c/k를 q라 하자면 모든 묶음에서 p의 개수는 (답이 되는, 실제적인 묶음에서의 p의 개수) c*\phi(q)/q가 됩니다.

    즉, 모든 묶음에서 원소의 개수는 c*\phi(q)/q로 같습니다.

    4.

    xnm = xkm(편의상 n <= k)이라 하자. 또한, xp = e2파이i * p/q이다. e^m(2파이i * n/q) = e^m(2파이i * k/q)이므로, e^m * 2파이i*(k-n)/q = 1이다. 즉, m(k-n)/q가 자연수가 되야 한다. m(k-n)은 q의 배수이다.

    이때, 양변에 gcd(q,m)으로 나눠주면 m(k-n)/gcd(q,m)은 q'의 배수가 된다. gcd(q', m/gcd(q,m)) = 1 이므로 k-n은 q'의 배수이다. 그래서 k와 n은 모듈러 q'에 대하여 합동이다. 그래서 k = q' * i + n으로 나타낼 수 있다. n <= k <= q이므로 0 <= i <= (q-n)/q'이다. 근데 q/q' - 1 < (q-n)/q' = q/q' - n/q < q/q' 이므로 최대의 정수 k는 q/q' -1 이고, 총 개수는 q/q'이 된다. 그런데, q와 q'의 최대공약수를 w라 하자. w의 임의의 소인수는 k와 서로소이며, gcd(w의 임의의 소인수, q' * i + n) = 1이므로 q*i+n \not\equiv 0 mod(w의 임의의 소인수)가 되고, 이는 phi(w의 임의의 소인수) 와 같게 되어서, 최종적으로 i의 개수는 q/q' * phi(w)/w가 된다. i의 개수 = q/q' * phi(w)/w = (q/w)/q' * phi(w)가 된다. 편의상 q/w = c라 하자. i의 개수 = c/q' * phi(w)이 되고, c/q' = phi(c)/phi(q')이므로, (c, q'는 소인수가 같기 때문에) c/q' * phi(w) = phi(c)phi(w)/phi(q')이고, phi함수의 특징 때문에 phi(c)phi(w)=phi(cw)=phi(q)가 되어서, 최종적으로 i의 개수는 phi(q)/phi(q')가 되고, 이는 한 묶음 속에 있는 원소들의 개수와도 같다.

    이는 모든 묶음(k, n...등등)에도 성립하기에, 모든 묶음은 phi(q)/phi(q')개수로 같다.

    모든 원시근들의 m제곱의 평균 = 모든 원시근들의 m제곱들의 합/전체 개수(=phi(q)) = 각 묶음의 원소들이 갖는 같은 양(xnm=xkm이런 값)들의 전체 합 * phi(q)/phi(q')(이것은 한 묶음의 원소의 개수)/phi(q) = 각 묶음의 대푯값(위의 원소들이 갖는 같은 양)/phi(q')이다. 근데, 각 묶음의 대푯값들은 xq'-1=0의 원시근들이다. (q' * m = q의 배수이기 때문)

    2번에서 증명했듯이 이 원시근들의 합 = 뫼비우스(q') = 각 묶음의 대푯값들의 합이고, 모든 m제곱들의 합은 \phi(q)*뫼비우스(q')/\phi(q') = (\phi(q)/\phi(q'))*뫼비우스(q')이 된다.

    즉, 각 묶음은 정확히 \phi(q)/\phi(q′)개의 원소를 가지고, x1m부터 xnm의 합은 (\phi(q)/\phi(q')*뫼비우스(q')이다.

    5.

    Migotti의 성질로 인해 n이 최대 2개의 서로 다른 홀수인 소인수를 가지고 있으면 n번째 원분다항식의 계수는 1, 0, -1중에서만 나타난다. (이탈 계수가 없다.) 고로, 인수가 3개일때부터 살펴봐야 한다. 가장 작은 n은 3*5*7 = 105 이며, ㅇ기에는 이탈 계수가 나타나므로 최소의 n은 105이다. 그리고, 계수가 모두 0, -1, 1 중 하나가 되기 위한 필요충분 조건을 구할 수 없다고 봅니다. 그 이유는, 소인수가 3개 이상이어도 0, -1, 1만 나타나는 q도 존재하기 때문입니다. 하지만, 소인수가 2개 이하면 반드시 0, -1, 1중 하나이기 때문이기에 소인수가 2개 이하인 것은 계수가 0, -1, 1중 하나로만 되는 충분조건이다. 또한, n의 더 많은 예시로 3*5*11 = 165, 5*7*17 = 595 등이 있습니다.

    즉, 가장 작은 최소의 q값은 105이며, q의 필요충분조건은 구할 수 없지만 충분조건은 구할 수 있다. (소인수가 2개 이하)

    전체 문제 증명!

    댓글 작성하기 좋아요0 댓글수0
  •  
    pure math Lv.6 2022.03.14 23:56
    확인요청중

    정리

    1.

     \Phi_{3}(x)=\prod_{1\leq t\leq 3, gcd(t,3)=1}\left(x-e^{2i\pi\frac{t}{3}} \right )\Phi_{4}(x)=\prod_{1\leq t\leq 4, gcd(t,4)=1}\left(x-e^{2i\pi\frac{t}{4}} \right )\Phi_{6}(x)=\prod_{1\leq t\leq 6, gcd(t,6)=1}\left(x-e^{2i\pi\frac{t}{6}} \right ) 이고, 원분다항식의 차수는 x를 곱한 횟수, 즉 q 이하이면서 q와 서로소인 수들의 개수와 같으니 원분다하식의 최고차항의 지수는 \phi(q)인 것입니다. 또한, 원분다항식(q)는 xq-1=0을 정수 계수에서 인수분해한 것이기 때문에 정수 계수 다항식입니다.

    즉, 원분다항식(q)는 최고차항의 지수가 \phi(q)이면서 정수계수다항식입니다.

    2.

    이 문제는 모든 원시근의 합이 뫼비우스(q)와 같다는 것을 증명하는 것과 동치입니다. 우선, 1을 제외한 단위근들의 합은 -1입니다. 그런데, q의 약수인 임의의 p에 대해서도, p에 대한 단위근(1 제외)들의 합은 -1입니다. 또한, q-단위근에 p-단위근이 포함되어 있습니다. 포함-배제의 원리로 모든 원시근들의 합은, (교집합의 성질) -1 + q - qC2 ........+-qCq-1 이 됩니다. 어떤 q에 대해서든, 위의 식은 뫼비우스(q)이기에 모든 q-원시근들의 합은 뫼비우스(q)입니다.

    즉, 원분다항식(q)의 \phi(q)-1차항의 계수는 -뫼비우스(q)가 됩니다.

    3.

    at\equiv\phi(b) mod (b)입니다. 이를 만족하는 최초의 t를 t1이라 한다면, tp=b(p-1)+t1입니다. tp<=bc-1이므로, tp를 대입해서 정리하면 p<=c+1-(t1+1)/b입니다. 우선, 모든 집합에서 p의 개수가 c개로 같습니다. (1<=t<=b-1) 이제 문제의 조건을 대입하여 생각하면, tp 중에서 \phi(c)가 아닌 p를 골라내야 합니다. \phi(c)가 아닌 최초의 p를 p1이라 하면, 모든 묶음에서 p의 개수는 \phi(c)에 비례할 것입니다. 더 계산을 하자면, b와 c에서 c와 b의 최대공약수를 k, c/k를 q라 하자면 모든 묶음에서 p의 개수는 (답이 되는, 실제적인 묶음에서의 p의 개수) c*\phi(q)/q가 됩니다.

    즉, 모든 묶음에서 원소의 개수는 c*\phi(q)/q로 같습니다.

    4.

    xnm = xkm(편의상 n <= k)이라 하자. 또한, xp = e2파이i * p/q이다. e^m(2파이i * n/q) = e^m(2파이i * k/q)이므로, e^m * 2파이i*(k-n)/q = 1이다. 즉, m(k-n)/q가 자연수가 되야 한다. m(k-n)은 q의 배수이다.

    이때, 양변에 gcd(q,m)으로 나눠주면 m(k-n)/gcd(q,m)은 q'의 배수가 된다. gcd(q', m/gcd(q,m)) = 1 이므로 k-n은 q'의 배수이다. 그래서 k와 n은 모듈러 q'에 대하여 합동이다. 그래서 k = q' * i + n으로 나타낼 수 있다. n <= k <= q이므로 0 <= i <= (q-n)/q'이다. 근데 q/q' - 1 < (q-n)/q' = q/q' - n/q < q/q' 이므로 최대의 정수 k는 q/q' -1 이고, 총 개수는 q/q'이 된다. 그런데, q와 q'의 최대공약수를 w라 하자. w의 임의의 소인수는 k와 서로소이며, gcd(w의 임의의 소인수, q' * i + n) = 1이므로 q*i+n \not\equiv 0 mod(w의 임의의 소인수)가 되고, 이는 phi(w의 임의의 소인수) 와 같게 되어서, 최종적으로 i의 개수는 q/q' * phi(w)/w가 된다. i의 개수 = q/q' * phi(w)/w = (q/w)/q' * phi(w)가 된다. 편의상 q/w = c라 하자. i의 개수 = c/q' * phi(w)이 되고, c/q' = phi(c)/phi(q')이므로, (c, q'는 소인수가 같기 때문에) c/q' * phi(w) = phi(c)phi(w)/phi(q')이고, phi함수의 특징 때문에 phi(c)phi(w)=phi(cw)=phi(q)가 되어서, 최종적으로 i의 개수는 phi(q)/phi(q')가 되고, 이는 한 묶음 속에 있는 원소들의 개수와도 같다.

    이는 모든 묶음(k, n...등등)에도 성립하기에, 모든 묶음은 phi(q)/phi(q')개수로 같다.

    모든 원시근들의 m제곱의 평균 = 모든 원시근들의 m제곱들의 합/전체 개수(=phi(q)) = 각 묶음의 원소들이 갖는 같은 양(xnm=xkm이런 값)들의 전체 합 * phi(q)/phi(q')(이것은 한 묶음의 원소의 개수)/phi(q) = 각 묶음의 대푯값(위의 원소들이 갖는 같은 양)/phi(q')이다. 근데, 각 묶음의 대푯값들은 xq'-1=0의 원시근들이다. (q' * m = q의 배수이기 때문)

    2번에서 증명했듯이 이 원시근들의 합 = 뫼비우스(q') = 각 묶음의 대푯값들의 합이고, 모든 m제곱들의 합은 \phi(q)*뫼비우스(q')/\phi(q') = (\phi(q)/\phi(q'))*뫼비우스(q')이 된다.

    즉, 각 묶음은 정확히 \phi(q)/\phi(q′)개의 원소를 가지고, x1m부터 xnm의 합은 (\phi(q)/\phi(q')*뫼비우스(q')이다.

    5.

    Migotti의 성질로 인해 n이 최대 2개의 서로 다른 홀수인 소인수를 가지고 있으면 n번째 원분다항식의 계수는 1, 0, -1중에서만 나타난다. (이탈 계수가 없다.) 고로, 인수가 3개일때부터 살펴봐야 한다. 가장 작은 n은 3*5*7 = 105 이며, 여기에는 이탈 계수가 나타나므로 최소의 n은 105이다. 그리고, 계수가 모두 0, -1, 1 중 하나가 되기 위한 필요충분 조건을 구할 수 없다고 봅니다. 그 이유는, 소인수가 3개 이상이어도 0, -1, 1만 나타나는 q도 존재하기 때문입니다. 하지만, 소인수가 2개 이하면 반드시 0, -1, 1중 하나이기 때문이기에 소인수가 2개 이하인 것은 계수가 0, -1, 1중 하나로만 되는 충분조건이다. 또한, n의 더 많은 예시로 3*5*11 = 165, 5*7*17 = 595 등이 있습니다.

    즉, 가장 작은 최소의 q값은 105이며, q의 필요충분조건은 구할 수 없지만 충분조건은 구할 수 있다. (소인수가 2개 이하)

     

    전체 문제 증명!!!!!!!!!

    댓글 작성하기 좋아요0 댓글수4
    •  
      유지연_매니저 Lv.15 2022.03.22 14:27 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      pure math Lv.6 2022.03.22 19:50 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      유지연_매니저 Lv.15 2022.03.23 13:19 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      pure math Lv.6 2022.03.26 14:42

      네!

      좋아요0
  •  
    pure math Lv.6 2022.06.06 12:37
    확인요청중

    +1.보충

    왜 정수 계수 다항식인가:

    xq-1=0은 우선 정수 계수에서 인수분해가 되지 않는 기약다항식이 아닙니다. 또한, 이 기초식은 x-e2파이t/q의 곱으로 나타낼 수 있으므로, 만약 위 일차식 몇개의 곱이 정수 계수 다항식이 된다면 그 다항식은 기초식의 인수이므로, 기초식/다항식 = 정수 계수 다항식입니다.

    그런데, 만약 어떤 수 t가 있어 tq-1=0이며, t가 원시근이 아니라고 합시다. 복소평면 상에서 1을 점으로 가지고 무게중심이 0인 정q각형에서 t는 한 꼭짓점으로 존재합니다. 또한, 실수축에 대해 t와 대칭인 점도 정q각형에 존재하므로, 근이 되며, 이 또한 자명하게도 원시근이 아니게 됩니다. (유클리드 호제법으로 t가 원시근이 아니면 q-t도 원시근이 아니기 때문, 이는 지수에 해당)

    원분다항식은 기초식에서 원시근이 아닌 친구들을 근으로 가지는 일차식을 나눈 것이므로, 이는 기초식에서 "실수축 위의 원시근이 아닌 얘들"의 일차식 * "그 얘들을 실수축에 대칭한 얘들"의 일차식 들을 나눈 것입니다. 근데, 한 점 t에서 본다면, 또한 대칭점을 p라 하면 (x-t)(x-p)=x2-(t+p)x+tp이며, 대칭이기에 t+p는 정수, tp는 벡터의 곱으로 정수입니다. 따라서, 기초식에서 나눠야 하는 친구들은 정수계수다항식이기 때문에, 또한 맨 위에 썼던 정리로 인해

    원분다항식은 정수 계수 다항식입니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      강지원 멘토 Lv.4 2022.06.07 11:00

      q가 홀수라면 그 대칭점이 정q각형 위에 존재하지 않게 됩니다. 또한 대칭점을 찾았다 하더라도 t+p가 정수라는 사실은 일반적으로 성립하지 않을 수 있습니다. (예를 들어 q=8일 때 e^{\frac{i\pi}{4}}의 대칭점 e^{\frac{7i\pi}{4}}를 생각하면 둘의 합은 \sqrt{2}로 정수가 아니게 됩니다)

      좋아요0
    •  
      pure math Lv.6 2022.06.07 21:03

      아하 넵!

      좋아요0
  •  
    pure math Lv.6 2022.06.06 12:52
    확인요청중

    5번 보충

    Migotti의 성질에 덧붙이자면, q가 어떤 경우에 이탈계수가 나오는지는 모르는 임의성을 가지고 있습니다.

    하지만, 제 가설에 의하면 규칙 없는 것은 없으므로, 뭔가 규칙이 있을 것 같습니다.

    q가 2 이하의 개수의 소인수로 이루어져있으면 무조건 이탈계수는 생기지 않습니가-->증명

    q가 3개 이상의 소인수로 이루어졌으면 이탈계수가 생길 수 있습니다-->증명

    제 가설에 의하면, q가 4k-1꼴의 소인수로만 이루어져 있으면 (소인수가 3개 이상일 때) 무조건 이탈계수가 생기지 않으며, 이것은 한번 시도해봤더니 됐습니다.

    그리고 q에 이탈계수가 생기지 않을 필요충분 조건은 q가 2개 이하의 소인수로만 이루어져 있다는 것인데, 위의 가설을 증명한다면 제대로 된 필요충분 조건이 될 수 있겠죠.

    댓글 작성하기 좋아요0 댓글수1
    •  
      강지원 멘토 Lv.4 2022.06.23 10:06

      아직까지 규칙이 발견되지 않은 걸 보면 규칙이 없을 수도 있겠죠. 이러한 불규칙성이 정수론의 흥미로운 부분이 아닐까 생각합니다.

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911