953,

7/48

/x7375696e6567

수학질문입니다 (정수론)

http://www.hackerschool.org/HS_Boards/zboard.php?id=QNA_ETC&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 : 4375 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을 n1n2...nk 라고 하면, 연립합동식을 전부 만족하는 x값은 0과 n-1 사이에 딱하나 존재한다. 두말이 동치에요 2. x ≡ { sigma from i=0 to k (aiNiMi) } (mod n) = "엑스" 와 "시그마 아이는 영부터 케이까지 (aiNi*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