949, 1/48 회원가입  로그인  
   /x7375696e6567
   수학질문입니다 (정수론)

http://www.hackerschool.org/HS_Boards/zboard.php?AllArticle=true&no=156 [복사]


정수론에서 잉여류에 대한 정의와 정리를 보고있는데요,
중국인이 기술한 나머지 정리가 하나 있더군요,
그 나머지 정리에서 질문인데요
일단 아래는 그 내용입니다.

중국인의 나머지 정리 (mod = %연산, n＼(a-b)일떄, a와 b는 법 n에 대하여 합동이라고 말한다.)

정수 n1,n2, ···, nk가 서로 소 일떄, 다음 연립 합동식은 근을 가지며 그 근은 법 n = n1n2···nk에 대하여 유일하다.

                                                           x = a1 mod n1
                                                           x = a2 mod n2
                                                           x = a3 mod n3
                                                                   ·
                                                                   ·
                                                                   ·
                                                           x = ak mod nk
가우스에 의하면 위 연립합동식의 근은 Ni = n/ni와 Mi = Ni(-1) mod ni {-1 은 위첨자입니다}} 에 대하여

      ㅡk
x = ＼
      /           ai * Ni * Mi mod n 으로 계산된다.
      ㅡi = 1

질문은요,
1.법 n이라는것은 규칙 n과 같다고 생각 해도 되는지
2.ai , Ni , Mi 여기서 합동식에서 초기화한 i=1 이 그대로들어가는지, 아니면 마지막 대입식인 i=k 로 들어가서
ak , Nk , Mi 와 동일이 되는지

일단 이 두가지가 의문이네요.
답변해주시면 감사하겠습니다.
아 그리고 저 시그마를 읽는 방법도좀 ㅋㅋ,, 그냥 발음나는대로 읽어주세요
  Hit : 5414     Date : 2011/04/10 10:59


    
멍멍 도움이 못되어 죄송... 2011/04/10  
/x7375696e6567 ㅠㅠ..
수학카페로 넘겨야겠네요		 2011/04/11  
Prox 1. 이해하기 쉽게 풀어써볼께요

a와 b가 법 n에대하여 합동이다 <=> a ≡ b (mod n)
<=> a를 n으로나눈 나머지와 b를 n으로나눈 나머지가 같다

위의 예에서 "x ≡ a1 mod n1" 이말은..
그냥 편하게 "x를 n1로 나누면 나머지가 a1이다"라고 이해해도 틀리지않음

또, "다음 연립 합동식은 근을 가지며 그 근은 법 n = n1n2···nk에 대하여 유일하다"
= n을 n1*n2*...*nk 라고 하면, 연립합동식을 전부 만족하는 x값은 0과 n-1 사이에 딱하나 존재한다.
두말이 동치에요


2. x ≡ { sigma from i=0 to k (ai*Ni*Mi) } (mod n)
= "엑스" 와 "시그마 아이는 영부터 케이까지 (ai*Ni*Mi)" 는 법n에대해 합동

참고로 시그마는 i를 시작값0부터 끝값k까지 한번씩대입해서 다더하라는말이에요
즉 x ≡ a0N0M0 + a1N1M1 + ... + akNkMk (mod n)		 2011/04/11  
uwang Prox님 말이 맞습니당. 덧붙여 추가하자면 a ≡ b (mod n)는 a-b=nq이다라고 보시면 됩니다.
책중에 기초정수론이란 책이있는데 그책보면 설명 자세히 나와있어욤 ㅎ_ㅎ저희 정수론 전공때 썻던 책이었는데 읽으면 도움되실듯..
그리고 =과 ≡의 뜻은 쓰이는곳이 약간 다릅니다.
또 정수론에서의 ≡의 뜻과 집합론에서의 ≡의 뜻도 다르니 잘 유의해주시고 뜻알아보시길..ㅎㅎ..
위에 보시니까 다 =로 쓰셧네욤..ㅎㅎ		 2011/04/15