gH = {gh: h는 H의 원소}를 H의 좌잉여류라 하고,
Hg = {hg: h는 H의 원소}를 H의 우잉여류라 한다.
좌잉여류와 우잉여류가 일치할 필요충분조건은 H가 정규부분군이라는 것이다.
아벨군의 경우를 비롯해 덧셈 기호를 사용할 때에는 잉여류를 g+H나 H+g 등으로 표시한다
함께 보기
이중잉여류
라그랑주의 정리
잉여군
안녕하세요
아래 사항은 제가 중학교 1학년 때 수학선생님이 가르쳐 주신 내용입니다. 참고로 저는 충북 청주시 무심천 옆에 위치한 운호중학교를 1983년 졸업했습니다.
요일을 척척 알아 맞추기 위해서는 아래사항을 우선 알아야 합니다.
- 1년은 365일(윤년일 경우 366일)
- 윤년은 4의 배수가 되는 해로 윤년의 2월은 29일까지 있습니다.(그러나 4의 배수가 되는 해더라도 100의 배수가 되는 해는 윤년이 아니고 400의 배수가 되는 해는 윤년입니다. 2000년은 400년에 한번 오는 뜻 있는 윤년의 해입니다.)
비고 | 날짜수 | 매월 1일의 요일 | 암기1 | 암기2 |
1 월 | 31일 | 월요일(기준일) | 길 | ㄱ |
2 월 | 28일 | 목요일 | 러 | ㄹ |
3 월 | 31일 | 목요일 | 라 | ㄹ |
4 월 | 30일 | 일요일 | 소 | ㅅ |
5 월 | 31일 | 화요일 | 나 | ㄴ |
6 월 | 30일 | 금요일 | 무 | ㅁ |
7 월 | 31일 | 일요일 | 섣 | ㅅ |
8 월 | 31일 | 수요일 | 달 | ㄷ |
9 월 | 30일 | 토요일 | 밤 | ㅂ |
10 월 | 31일 | 월요일 | 구 | ㄱ |
11 월 | 30일 | 목요일 | 름 | ㄹ |
12 월 | 31일 | 토요일 | 비 | ㅂ |
왼쪽 그림은 왼손 집게손가락 입니다. 왼손 엄지로 집게손가락 마디를 짚으면서 시계방향으로 "ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ" 순으로 돌아 갑니다. 상기 표에서 알 수 있듯이 "월요일(ㄱ), 화요일(ㄴ), 수요일(ㄷ), 목요일(ㄹ), 금요일(ㅁ), 토요일(ㅂ), 일요일(ㅅ)" 입니다. 또한 1년은 365일 이므로 365 ÷ 7 하면 1일 남는다. 따라서 올해 1월 1일이 "월요일"이면 내년 1월 1일은 "화요일" 그 다음 해는 "수요일"이 된다. 산수책에 나오는 잉여류 법칙을 적용하면 각 년도에는 0부터 6까지(일주일은 7일 이므로)숫자 중의 하나를 잉여류로서 가지게 된다.
산수에서 "X + Y = Z"일 때 2개를 알면 나머지 하나를 알 수 있듯이 "날짜, 날짜의 요일, 그 해의 잉여류" 중 2개를 알면 나머지 하나를 알 수 있습니다. 잉여류를 알고 싶을 때는 달력만 보면 된다. 달력에는 날짜와 그 요일이 나와 있으므로 잉여류를 역산할 수 있기 때문입니다.
잉여류는 다음과 같습니다.
잉여류의 해 | 잉여류 | 잉여류의 해 | 잉여류 |
1990년 | 6 | 2001년 | 6 |
1991년 | 0 | 2002년 | 0 |
1992년 2월까지 | 1 | 2003년 | 1 |
1992년 3월부터 | 2 | 2004년 2월까지 | 2 |
1993년 | 3 | 2004년 3월부터 | 3 |
1994년 | 4 | 2005년 | 4 |
1995년 | 5 | 2006년 | 5 |
1996년 2월까지 | 6 | 2007년 | 6 |
1996년 3월부터 | 0 | 2008년 2월까지 | 0 |
1997년 | 1 | 2008년 3월부터 | 1 |
1998년 | 2 | 2009년 | 2 |
1999년 | 3 | 2010년 | 3 |
2000년 2월까지 | 4 | 2011년 | 4 |
2000년 3월부터 | 5 | 2012년 2월까지 | 5 |
[실습1] 1999년 12월 25일은 무슨 요일 일까요?
- "길러라소나무섣달밤구름비"을 읊조리니 12월은 "비"
- "비"는 "ㅂ"
- 왼손을 펴고 왼손 엄지로 검지 마디를 짚으면서 "ㅂ"까지 간다.
- 1999년 잉여류는 3
- 25일 + 3 = 28
- "ㅂ" 위치에서 시계방향으로 28칸 돌아봐도 제자리이므로 "토요일"(월요일(ㄱ), 화요일(ㄴ),수요일(ㄷ), 목요일(ㄹ), 금요일(ㅁ), 토요일(ㅂ),일요일(ㅅ)이므로)"
위와 같은 배경을 검토해 보면 다음과 같은 재미있는 사실을 도출할 수 있습니다.
- 첫째, 평년의 경우 1월,10월// 2월, 3월, 11월// 4월,7월// 9월,12월 달력의 날짜 배열이 동일함.
- 둘째, 달력은 28년을 주기로 똑 같음.
4(윤년의 주기) x 7(7의 잉여류 수: 0부터 6까지 모두 7개) = 28 - 세째, X년도 = [X + 7N(N은 양수) ± 윤년(X년도와 X+7N년도 사이에 있는)의 수에 윤년을 감안한 수(단, N이 양의 정수이면 -, 음의 정수이면 +임)]년도 --- *이때는 윤년을 감안해야 함.
[실습 2] 1990년과 28년 후인 2018년의 달력은 동일한가 ?
1990년 = 1990 + 7 x 5 - 9(1992, 1996, 2000, 2004, 2008, 2012, 2016, 2020, 2024) = 2017이 되는 것이 아니고 1990 + 7 x 5 = 2025에서 9번의 잉여류 해를 뒤로 무르는 것으로서2024, 2024, 2023, 2022, 2021, 2020, 2020, 2019, 2018이 되어 1990년과 2018년은 같게 되는 것입니다.
[실습 3] 1990년과 28년 전인 1962년의 달력은 동일할까요 ?
1990년 = 1990 - 7 x 5 +9(1956, 1960, 1964, 1968, 1972, 1976, 1980, 1984, 1988)번의 잉여류 해를 더하는 것으로서, 1990 - 7 x 5 = 1955가 되므로 9번의 잉여류 해를 더하면 1956, 1956, 1957, 1958, 1959,1960, 1960, 1961, 1962가 되어서 1990년과 1962년은 같게 됩니다. 즉, 이는 상기 둘째 정리와 일치합니다.
감사합니다.
다음은 Math Awareness Week 97 에 Paul Davis 가 쓴 Theme Essay를 이에 관심을 가진 노 효 민, 황 병 렬 군에게 읽고 번역하여 정리시킨 것입니다. 숙제가 있을 예정이니 잘 읽고 21세기에 수학과를 졸업한 학생의 미래에서 수학의 의미를 다시 한번 생각해봅시다.
성대 수학과 이상구교수
Mathematics and the Internet (수학과 인터넷) :
MAW 97 Theme Essay by Paul Davis (노 효 민, 황 병 렬 역- 이상구교수 감수)
목 차
Introduction
Managing data on the Internet
Security on the Internet
Databases and searching
Routing and network configuration
Mathematics on the web
Introduction
수학과 인터넷의 관계는 언어와 셰익스피어의 작품 사이의 관계와 흡사하다. 그의 시와 연극들이 쓰이게 되어서 언어는 발전하였고 그런 언어 없이는 그의 작품은 창작되어질 수 없었다.
컴퓨터는 수학적 언어로 탄생했다. 이진수로 컴퓨터의 언어, 음악, 이미지가 대체되는가 하면 더 나아가 지금의 기기는 0과 1의 문자 체계로 인터넷을 통해 대화가 가능하다. 수학적 논리의 공정한 규칙들로 컴퓨터 기능, 인터넷 주소, 심지어 Web 검색 장치들까지 관리하고 있는 것이다.
인터넷에서, 수학은 메시지 안전과 금전상 업무의 심장부 역할을 한다. 큰 파일을 보내기 위해 에러를 수정하고 부호화 시키며 데이터를 압축하는데 있어서 수학은 기본적인 도구이다. E-mail을 관리하고 World Wide Web(www)을 찾기 위한 데이터베이스의 기초도 수학이며 메시지의 루트(rout)를 정하고 Networks를 관리하는 대리인도 수학이다.
인터넷은 또한 수학적 조사나 교육의 발전을 도와 준다. 교육자와 조사자들로 이루어진 그룹들은 E-mail, newsgroups, 그리고 특별한 World Wide Web Sites로 대화를 한다. 인터넷은 또한 대중의 안전을 고려한 코드를 풀기 위해 수십 여 개의 나라들이 컴퓨터에 올려놓고 합심해 나온 최신 계산결과로 분배되는 것을 가능하게 하며 또 지원한다.
1997 Mathematics Awareness Week theme 포스터는 World Wide Internet traffic의 2시간의 퍼레이드로 표현되는 Bell Laboratories에 의해 발전되어진 아이디어를 사용했다. 각 나라들 사이의 호들의 색과 두께는 다량의 교류를 하면 더 높고 붉게 표시되도록 해서 나라들 사이의 정보 교류 현황을 보여주었다.
Managing data on the Internet
대부분 사람들이 알다시피, 인터넷 메시지 E-mail, graphics, sound, database 검색 결과들은 0과 1의 나열로써 보내진다. 수학은 이런 계수형 번역과 전송 두 부분의 중앙에 있다.
텍스트 메시지와 소리의 정확한 전송에는 이진수로 번역되고 에러를 찾아 수정하기 위한 코드(숨겨진 코드 제외)가 요구된다. 그리고 이미지에서 data의 부피를 줄이는 것, 예를 들면, data 압축도구를 사용하여 원본의 본래 성질을 보존하고 그 data를 재 구축하여 전송하는 것 또한 요구된다.
0과 1의 거대한 나열들이 computer networks 에서 장애가 있었을 때, 약간의 에러는 피할 수 없이 생겨나고, 심지어 그 작은 data의 손실로 엄청난 피해에 이를 수도 있다. 에러 검색 코드는 수많은 문자열 검색을 통해 그 mail 내에 어떤 내용이 손실됐는지 또는 안됐는지를 결정해 그런 많은 손실을 지적하기 위한 수학적 도구로 소개된다.
인터넷 전송에서 에러 검색을 위한 기본적인 도구는 cyclic codes(순환 코드)이다; 선형대수학의 벡터공간의 이론을 이용하는 코딩이론에서 시작한 우리의 일반적 선택은 CRC-16이고, 메시지를 16개의 연속적인 bits 만큼 많은 에러를 지적할 수 있는 a cyclic redundancy code(순환 여분 코드)이다. CRC-16은 16bits보다 더 긴 에러를 약 99% 잡을 수 있다. 에러가 지적 됐을 때, 받는 쪽 컴퓨터에서는 그것의 도착 인식을 간단히 거부하면 전송자는 다시 전송해야 함을 알게 되는 것이다. 이런 코드들은 수로 표현된 메시지들을 특별하게 나누어서 실행한다. 전송자는 그 메시지들의 길이를 추가할 필요 없이 그것을 나눈 나머지를 접하게 되고 그 나머지의 정보로부터 나눗셈에 의해 수신자가 그 메시지를 확인할 수 있다. 다른 나머지가 확인되면 메시지가 와전됐다는 것을 의미한다.
The relevant coding ideas(부호화 관련 아이디어)는 1950년대에 처음으로 소개되었다; R.W. Hamming 과 D.A. Huffman이 최초로 그 작업을 했다. 대수학의 부호화 이론의 수학적 관념들은 1960년대에 나왔고 유한체에서의 오랜 규율이 세워졌다. 그리고 그것의 효과적인 면을 발전시켜 에러를 찿아 수정할 수 있게 되었다. 예를 들면, the Reed-Solomon error-correcting codes로 1960년대에 Reed와 Gustave Solomon이 유한 체에 그 개념들을 적용시켜 소개되었고 위성에서 compact disks까지 정렬하는 장치를 사용함으로써 효과적으로 에러를 지적하고 수정하는 개념이 생겼다. 에러 수정 코드(error collecting code)와 같이 data압축 개념 또한 최신 디지털 TV를 포함한 기술들이 넓게 공유된다.(극단적인 정의로 1초는, 압축이 안된 비디오로 가정용 모뎀을 사용해 받으려면 7시간 이상이 요구된다.) 데이터 압축에 대한 도전은 데이터 부피의 크기가 수많은 질서 정연한 상태로 즉 모든 보여지는 중요 부분의 이미지를 보전하며 전송시간과 함께 줄어들게 되는 것이다. 좋은 data압축은 빠르고 정확하게 컴퓨터 스크린에 재생되어 나타나게 하는 것이다. 같은 도구들이 sound files로 귀에 들리게 되고 심지어 선택된 부분이 제거되거나 재 구축되어 지기도 한다. 지금까지는 주로 Singular Value Decomposition 을 이용하여 data 압축을 해왔으며, 최근에는 data압축에 multiscale analysis tool의 종류인 wavelets를 사용하기도 한다.
wavelets는 A. Grossman, Stephen Mallet, Ingrid Daubechies 와 기본적으로 빈번하게 해석되어지는 것을 제한하는 고전 Fourier 해석의 한계를 넘어 지난 12년 동안 발전되어진 수학적 도구이다. 푸리에의 방법은 그 키의 조화의 진폭을 알아냄에 의해서 길고 끊임없는 톤, 음을 쉽게 창출해 매는 것이다. 그러나 생 음악에서 들을 수 있는 소리나 지문처럼 이미지로 보여지는 것과는 같은 짧고 파괴된 신호들은 time windows를 통해 작업이 가능한 추가적인 도구를 요구한다. 비록 푸리에 해석은 이 작업을 한 데 묶었음에도 불구하고, wavelets는 기본적인 부호 요소의 알맞은 규모의 관점에서 재생되어 만들어졌기 때문에 많은 부호-처리 적용에 상당히 적합하다. 그것들은 자연적으로 지문 같은 이미지의 압축저장에 편리하다. 예를 들면, 심지어 그것의 지문 능선양상이 한 페이지의 유한적 범위 내에서 확장되어 간다.
인터넷상의 보안은 은행 금고의 보안만큼이나 중요하다. 보안 사항들은 전달의 사적인 자유; 인터넷에 연결된 컴퓨터들의 완전성 그리고 상거래에서의 신뢰도를 많은 다른 의논 사항들 사이에서 포괄한다. 예를 들면, 인터넷 시장의 빠른 성장은 지난 이 십여 년간의 발전들을 잉태해온 오래된 정수론 이론과 결부된 암호 코드에 깊이 의존한다. 더욱이, 그런 코드들을 파괴하려는 노력들이 광대역 전산망의 일 처리 부담을 가중시키기 위해 인터넷을 경유해 나타난다. 그런 잘 이식되어 나간 순차적인 처리 기법들은 커다란 소인수를 체계적으로 찾기 위한 Fermat의 과거 아이디어들의 현대적 재해석에 결정적으로 의존한다.
인터넷 암호는 우선 두 부분에서 이해될 수 있다. 하나는 수신자만이 해독할 수 있는 자료가 다른 곳으로 새어 나가지 않으면서 조작되지 않은 자료인지를 보증할 수 있는 전송의 문제이다. 또 하나는 송신자의 신원 확인이다. 처음 것은 빠른 전송과 해독하는 동안만이라도 침입할 수 없는 코드를 찾는 문제에 해당한다. 두 번째 사항은 전자 서명의 문제이다. 어떻게 인터넷 사업가가 전자 서명이 진짜인지를 확신할 수 있겠는가? 두 문제들의 해결 방법은 믿지 못할 정도로 깊은 수학의 한 분야인 정수론의 책임으로 떠 넘겨진다.
잠겨진 우편함을 연상시키는 DES같은 전통적인 암호 생성 기술들은 송신자와 수신자 각각 단지 두 개의 key만 가지고 있을 뿐이다. 여기서 문제는 대응되는 새로운 암호 생성 key와 암호 해독 key의 순서쌍을 은밀히 보내고, 빈번히 사용될 암호들의 목록을 관리하는 데 있다. Public key 또는 RSA system은(R.L Rivest, A. Shamir, 그리고 L. Adleman을 기리어 이름 지어 졌으며, 그들은 W.Diffie와M.Hellman의 고안에 기초해 1978년 실용적인 첫 기법을 출판했다.) 메시지를 은밀히 보내고자 하는 사람에게는 투입구가 열려있고 우편함의 내용은 그 소유주에 의해서만 열릴 수 있는 것과 같다. 그것은 누구든지 정해진 수신자를 위해 암호화 할 수 있지만, 수신자만이 그 암호를 풀 수 있다.
Public key 전달 암호화는 두 개의 (커다란) 수들을 요구하는데 그들이 소위 공공 key이다; 그것을 해독하는 데는 앞의 두 수와 관련 있는 또 다른 수를 요구하는데, 그 개인 key는 단지 수신자만이 알고 있는 해독 key이다. 암호화와 해독 절차들은 바늘 시계의 산수(예를 들면, 아무리 시간이 흘러도 도착한 날의 시간을 알려면 24로 나눈 나머지만 알면 되는 것) 같은 잉여류(Residue)적 계산을 사용한다. 새 공공 key 사용 가입자들이 그들의 key를 설정하기 위한 첫 작업은 두 개의 큰 소수를 (무작위적으로) 선택하는 것이다. 그러면, 그 key들은 2세기 전쯤의 Euler정리에 기초한 일련의 과정들을 거쳐 위에서 선택한 두 소수로부터 계산된다. 공공key로 제공된 수들로부터 애초의 소수가 계산될 수 없다면 공공key 암호 체계는 완전하다; RSA system은 공공 key의 소인수를 찾아내기 어렵도록 하기 위해 129자리 이상의 수를 사용한다.
확실히, Rivest, Shamir, 그리고 Adleman은 1977년에 그들이 128자리로 암호화 했던 전문을 해독해 보라고 온 세계에 내기를 걸 만큼 안전하다고 확신했다. 그 당시 그들은 해독에 필요한 시간이 23,000년 이상 걸릴 거라고 추정했다. 그러나, 1994년에 24개국이상의 인터넷을 통해서만 대화해온 600명 정도의 지원자들로 구성된 비공식적 모임은 모든 종류의 CPU, 컴퓨터 자원들을 모아 결집시켜 심지어 fax까지도 350년 이상 내려온 Fermat의 이차 체 알고리즘인 1981년의 Carl Pomerance의 작업을 계승했다. 그들은 8개월 뒤에 64와 65자리의 소인수들을 발견했다. (1976년 public key code 라는 개념으로 암호론에 새로운 아이디어가 소개된 후 Rivest, Shamir, Adelman 이라는 세 명의 교수에 의해 RSA code 로 알려진 코드가 개발되고 현재 RSA Data Security Inc. 라는 큰 회사도 생겼다. 이들은 자신의 code 가 풀리려면 129 자릿수의 소인수 분해를 하는 기술이 필요한데 아마 23,000년 정도 후에나 가능할 것이라고 예언하고 이를 해독하는 첫 번째 사람에게 상금으로 $100.00을 걸면서 이를 연리 6%의 복리로 예금해두면 약 20,000년 후에는 어마어마한 500자리수의 큰돈이 될 것이라고 호언했다. 이는 그림에서 보는 RSA-129 라고 알려진 수의 소인수 분해와 관련되는데 이 RSA-129를 인수분해 하는 프로젝트는 여러 수학자의 손을 거쳐 {0,1}-행렬과 "Structured Gauss"라고 알려진 선형대수학의 기법을 이용하여 super computer를 이용하여 Arjen Lenstra에 의해 1994년 4월 마무리 지어 졌다. - 이상구교수의 주)
RSA 128자리의 암호key는 그리 빠르지는 않지만 인터넷을 사용해 해독되었다. 인터넷상의 분산처리는 국지적인 의사소통 암호 보안의 벽을 여지없이 깨버렸다. 더 안전한 보안은 더 많은 자리로 구성된 공공 key를 사용하면 쉽게 얻어질 수 있다. 전자 서명 문제는 예로 전자 수표 결재 공공 key 과정을 전환시켜 해결할 수 있다. 보내는 사람이 전달문과 해독된 내용을 동시에 보낸다. 만약에 수신자가 해독된 암호로 원본을 복구할 수 있다면 그것은 진짜이다. 다시 말하지만, 커다란 수의 소인수를 찾는 어려움으로 인해, 필요로 하는 안전성을 확보할 수 있다. 그 동안 수학은 다양한 보안 기술 위에 가해진 또 다른 습격들에도 깊이 연루되어 있다. system들을 관련 코드의 수학적 key를 시험해 보도록 유혹하는 것이다. National Security Agency 의 최근 보고서는 정보화 사회에서의 보안상 암호의 역할 더 많은 자료를 구축하고 있다.
Databases and searching
강력한 web은 'Altavista'나 'Yahoo'같은 엔진들을 필요로 한다. 인터넷 사용자들이 가상공간 위에 숨겨진 모든 종류의 정보들의 일부를 찾는다고 해보자. 대부분의 검색 수단은 keyword에 의한 것이다; 각각의 entry는 keyword를 포함하는 web sites의 목록을 나열한다. (수학 entry를 한 엔진으로 검색해 보면 332,966 개의 sites를 토해낼 것이다.) 이상적으로, 검색 엔진은 검색 어를 모두 만족하는 sites만 골라 뿌려주는 것이 아니라 검색자의 필요에 따라 나열된 주제와 잠재적인 관련성을 갖을 만한 목록을 제공한다.
주제에 의한 포괄적인 균형 잡힌 검색상에서의 최근의 어떤 개념은 주제들에 귀속된 자료에 대한 vector공간 모형과 상당히 유사하다. 그 공간의 좌표는 색인의 조건과 검색의 매체인 검색어이다. 각각의 web sites는 아마도 가장 포괄적인 검색 어 목록에 올려 놓은, keyword인 "hits"에 의해 결정된 좌표를 갖는다. 비슷한 자료를 갖는 sites는 어떤 의미에서 다른 sites보다 더 가까이에 위치한 점이라 생각해도 무방하다.
검색은 그런 의미에서 매우 높은 차원을 가진 공간에서 이상적으로 그 공간의 차원에 구애 받지 않는 계산효율을 이용해 가장 가까운 이웃을 찾는 문제가 되어버린다. 이런 공간상에서 분산 처리 과정의 확률 모형의 의미는 전혀 다른 형태의 기하학과 관련이 있다; 예를 들어, 잘 알려진 삼각 부등식 삼각형의 두 변의 길이의 합은 언제나 다른 한 변보다 더 길다. 이러한 수학적 사실이 더 나아가 능률적인 검색 알고리즘을 찾아낼 때의 어려움들을 해결해 줄 수 있는 것이다.
대수적인 관점으로부터 keyword에 의한 좌표들의 vector는 주어진 keyword에 대응하며, keyword를 포함하는 각각의 sites로 이루어진 행 vector를 늘어놓은 행렬을 keyword에서 web sites로 보내는 변환으로 간주하여 keyword들의 열vector를 그 행렬에 대입하는 과정으로 검색을 이해할 수 있다. 목표는 keyword사이에서 눈에 띄는 관계에 부합하는 유사성을 지닌 sites를 찾는 것이며 그 관련성은 예를 들면, "수학"과 "수"처럼 같은 keyword를 입력해도 검색자 마다 맞는 범위의 검색결과를 얻을지도 모른다.
이런 빈도행렬로부터, 누구든지 keyword vector space에서, 확실히 보존되는 방향 vector를 찾아낼 수 있으며, 이 vector는 일반적으로 고유 vector로 알려져 있다. 각각의 대응하는 고유 vector로의 중요성의 척도로 인식되며, 그 중요성은 소위 고정점(fixed point)의 값이라 불린다. 고유 vector상에 정의된 방향에 놓인 sites는 그것이 묘사하는 공통의 자료를 분담해서 갖고 있다. 더 큰 고정 값들은 의미상 덮어씌운 대부분의 분류를 명확히 해준다. 고유 vector와 고유값 계산은 그 같은 커다란 행렬상에서는 부담되는 문제이지만, 여전히 이 기술은 완벽하며 깊은 연관성을 지닌 결과를 생성해내는 검색 절차의 기법을 속속히 파헤치고 있다. 실제로, 검색 엔진은 수 백 수 천의 행과 열을 가진 행렬들을 직접 다루지는 못한다. 대신에, 그들은 저장된 자료의 교묘한 계산상 취급에 의존한다.
많은 자료 체제들은 tree로 알려진 수학적 대상물로 바꾸어 생각할 수 있다. 이런 tree들은 부모들과 아이들과 그 조상들 그리고 후손들 사이의 관계를 기록한 족보와도 같다. 예로, 알파벳 문자와 하나씩 대응시킨 26명의 구성원들로 이루어질 지도 모른다. 아이들의 세대는 모두 법률상 정해진 두 문자와 기타 문자의 조합으로 이름 지을 수도 있다; 예로, aardvark 는 aa의 먼 후손일 수도 있다. 부모와 아이의 연관성을 배경으로, 가계도는 그들의 지위들 사이에서 부가적인 관계성을 부여한다. 관계 자료 모양의 힘은 그런 관계들을 다루는 능력으로부터 유래한다; 자세히 말하면 두 개의 서로 다른 외양의 문자열이 지니는 공통적인 조건을 모두 만족하는 목록을 추출하는 연산을 수행하는 일이다. 연산처리는 자료구조를 분류하는데 일반적인 대수나 계산 이론들을 필요로 한다. 수학은 자료체계 구성을 묘사하기 위한 틀이며, 수학적 도구는 그들의 능률과 신뢰도를 개선하는데 있어서 기초가 된다.
Routing and network configuration
웬만한 규모의 국부지역 통신망은 10,000 쌍 이상의 지점들을 가지고 있고 각 지점들마다 또 다른 분기점과 각각 연결되어 있을 수도 있다. 할당된 전송 문은 통신망이라는 선로 위를 빛의 속도로 달려나가는 기차와도 같다. 기차에서 각각의 차량은 마치 길다란 편지를 여러 장의 엽서에 쪼개어 적은 뒤 하나의 카드를 하나의 차량에 싣는 것처럼 전달문의 부분들의 일부씩을 전달한다. 전형적으로 많은 전달 문들의 카드는 한 기차에 섞여서 한꺼번에 옮겨진다.
통신망의 한계는 열차의 길이 --- 전달 문 뭉치의 크기---와 열차들 사이의 간격에 의존한다. 예를 들어, 긴 전달 문이 부적절한 시간에 도달한다면 그것이 통과할 때까지 다른 전달 문들은 지체될 수 있으며; 짧은 전달 문들은 적당한 공간만 차지하므로 다른 전송들 사이를 비집고 들어갈 수 있다. 배열 이론의 수학적 동기는 자료 크기와 전달 문 뭉치들의 형태에 기초한 통신 규약의 구성을 제시한다. (배열 이론의 고전적 응용은 은행에서 고객과 상담원 사이에서의 대화상 지연 시간 측정이다.) 그러나, 바뀐 전송규약 정착은 수학적 전달 모형에 기초한다. 훌륭한 모형은 새로운 규약이 배열 이론이 제시한대로, 잘 수행될 것임을 확인시켜준다; 나쁜 모형은 통신 규약 개발자가 의도한 대로 수행한 사항들에 대한 한계범위를 제시하지 못할 것이다.
Bellcore, AT&T Lab. 그리고, Boston University의 과학자들은 통신 전달이 프렉탈의 시간 추이에 따른 자기 상사성을 가지고 있으며, 그러한 성질들은 제안된 규약을 시험하기 위한 인터넷에서의 더욱 정밀한 모형을 제시하는 데 있어서 음향물리를 필요로 한다는 사실을 깨달았다. 자기 상사성의 동기는 Benoit Mandelbrot에 의한 상품 시장의 주기적인 변동의 해석으로부터 이끌어진다. 중추적인 물리 개념은 복잡한 통신망에 맞물린 컴퓨터가 오랜 시간 동안 일으키는 상호 작용과 한 대의 컴퓨터를 가진 인간의 컴퓨터와의 상호 작용이 별반 다를 바 없다는데 있다. 통신망의 유용한 전달 모형으로, 통신망 규약 관리 설계자들은 가장 짧은 경로로 자료 전송을 할 것인지 혼잡함을 줄일지 사이에서의 미묘한 선택에 직면하는데, 이와 같은 상황은 직접 연결된 혼잡한 고속도로로 가느냐 텅텅 빈 우회도로를 택할 것이냐에 비유될 수 있을 것이다.
전달 매체가 빛일 때, 시간 지연 현상이 두드러지고 전달 묶음이 최단 경로로 가장 잘 보낼 수 있다. 통신망 상에서 최단 경로 찾기는 수학의 한 분야인 그래프 이론에서 착실히 연구된 문제이다. ( R. E. Bellman, L. R. Ford, 그리고, E. W. Dijkstra는 1950년대 말 첫번째로 최단 경로 알고리즘을 개발한 수학자들 중에 해당한다.) 소통량이 늘어 날수록 통신 라우터는 보내는 사람과 받는 사람 사이의 모든 경로를 찾아내는 것을 필요로 하는데, 여기엔 1970년대 R. E. Tarjan, J. E. Hopcroft 외 다른 수학자들에 의해 개발된 근대적 그래프 검색 기술을 적용할 수 있는 문제로 전환되어 적용된다. 최단 경로와 가장 위험이 적은 경로는 발견될 수 있다는 사실은 알려졌으므로, 많은 통신망 프로토콜은 짧은 경로이지만 정체의 위험을 갖고 있을 가능성 있는 루트와 길지만 막힘 없이 뚫린 경로 사이에서의 교환기의 선택에 빚어내는 달라지는 결과에 초점을 맞추고 있다.
Mathematics on the web
수학자들은 월드 와이드 웹(www)과 인터넷의 이점을 충분히 활용해 왔으며 잘 활용하고 있다. 이런 도구들은 수학자들이 교육과와 연구를 발전시키기 위해 지리적인 그리고 학문적인 경계를 넘나들며 아이디어, 기술, 재원들을 공유할 수 있도록 해준다.
사회에서의 수학의 역할에 대한 고려를 포함해 광대한 수학적 활동의 범주의 일면을 엿보고 싶다면, 다음 홈페이지들을 보기 바란다. Math Forum, the American, Mathematical Society, the Mathematical Association of America, Society for Industrial and Applied Mathematics. 더 많은 세부분야 사이트들의 예로는 Math Archive가 있으며, 이 사이트는 교육적인 주제들을 주로 다루고, 또 다른 사이트인 Geometry Center는 기하학적 구조의 계산과 가시화에 초점을 두고 있다. 수론 전공자들은 소위 메르잔느 소수 찾기에 관심을 가지며 그들의 성과는 Great Internet Mersenne Prime Search에 망라되어 있다. 상당히 여러 해 동안 수리 과학자들은 NA-Net을 통해 문제들과 해법들 그리고 접근 방법들을 공유해 왔으며, 이 사이트는 가장 범용의 수치해석 소프트웨어를 다운 받는 데 유용한 곳이다.
Mathematics and the Internet
수학은 문자와 영상을 묘사해주는 이진수로부터 World Wide Web의 검색 엔진의 복잡한 자료 구조에 이르기까지 인터넷 구성의 언어이다. 수론과 같은 영역으로부터 오래되었으며 동시에 새로운 고안들의 적절한 결합은 안전한 상거래를 위한 자료 암호화에서 보듯이 인터넷 기술의 핵심을 이룬다. 동시에, 인터넷은 교수와 연구원 사이의 협력, 유치원에서 대학까지나 순수와 응용 수학의 가장 어려운 부류의 문제들에 관한 이해 이 모두를 한 차원 끌어올리기 위한 공동 연구를 태동 시키고 있다.
(노 효 민, 황 병 렬 역- 이상구교수 감수)
정수를 분류 한다는 것은 정수 전체를 일반적인 표현으로 나타내 주는 걸 의미한다.
일반적 표현이란 문자로 전체를 나타낸다는 뜻이야. 예를 들어 3을 기준으로 분류한다는
건 정수 전체가 3으로 나누어 ㅇ이 남는 집합, 1이 남는 집합, 2가 남는 집합의 세 집합으
로 나뉜다는 걸 뜻한다. 그런데 그걸 집합으로 {...0, 3, 6, 9, 12, 15.....} {...1, 4, 7, 10, 13,
16...} {... 2, 5, 8, 11, 14, 17...} 이렇게 나타낼 수는 없는거지. 그래서 이 세 집합을 문자
를 써서 3n, 3n+1, 3n+2 (n은 정수) 이렇게 나타내는거야. n 대신에 ...-1, 0, 1, 2, 3, 4, 5,
6...을 차례로 집어 넣어봐. 그럼 위의 세 집합이 나타나지? 이런 걸 어려운 말로 잉여류
라고 한다. 잉여류, 잉여계는 정수에서 중요한 부분이지만 고등학교에서 배우지는 않으
니 굳이 용어를 외울 필요는 없다. 다시 한 번, 4를 기준으로 분류하라 이러면 4k, 4k+1,
4k+2, 4k+3 (k는 정수) 이렇게만 써 주면 된단다. 문자는 k나 n대신 아무거나 써도 된다.
보통, n,m,k,l,등을 주로 쓴다.
문제; 정수를 2를 기준으로 분류하라.
잉여류입니다. 잉어류가 아니고 잉여류예요.
잉어류는 잉어 종류의 물고기라는 뜻인것 같기는 한데. 그럼 잉여류는 무슨 뜻일까요? 잉여라는 말은 들어 본 적이 있을 겁니다. 경제나 무역에 관련된 교과를 배우다 들어 보았을 수도 있겠고, 신문을 읽다가 들어 보았을 수도 있고. . . 잉여라는 것은 나머지라는 뜻이지요. 그리고, 잉여류는 나머지에 따라서 분류한 집합으로 생각하면 되겠군요.
많고 많은 정수를 으로 나누어 봅시다. 아무리 많은 정수를 나누어 보아도 그 나머지는 , , 중의 어느 하나가 될 것입니다. 나머지가 이나 가 된다는 것은 의미가 없는 말입니다. 즉, 나머지는 보다 크거나 같고 나누어 주는 수 보다는 작아야 합니다. 정수들을 으로 나누었을 때 나머지가 같은 정수끼리 모아볼 수 있겠지요. 예를 들자면 나머지가 인 정수들을 모아 보면
가 될 것입니다. 나머지가 이나 인 경우도 마찬가지일 것입니다.
이 각각을 원으로 하는 집합을 , , 라고 하면 (는 정수의 집합) 이 됩니다. 모든 정수는 세 집합 , , 중의 어느 하나에 반드시 속하게 되지만, 동시에 두 개의 집합에 속하는 원은 없습니다. 이 때 , , 를 각각 잉여류라고 합니다. 그리고, 이 , , 에서 각각 한 원씩을 택하여 만든 집합을 잉여계라고 합니다. 잉여계를 만들 때 잉여류 중의 어느 원소를 사용해도 괜찮습니다. 예를 들어 과 같이 만들어도 무방한 것입니다만 보통은 가장 간단하게 이해할 수 있는 수 즉, , 를 사용하여 나타내고, 으로 나누었을 때의 잉여계를 기호로 나타냅니다. 그러므로, 로 표현할 수 있습니다. 정리하면 다음과 같습니다.
정수의 집합 의 임의의 원 를 양의 정수 으로 나눌 때, 나머지가 인 정수의 집합을 이라 하면 i) 어떤 정수도 , , , , 의 어느 것인가에 속하고 ii) 와 (단, )에 공통원이 존재하지 않는다. , , , , 을 각각 으로 나누었을 때의 잉여류라 하고, , , , , 의 각각의 임의의 한 원을 택하여 만든 집합을 잉여계라고 하고 기호 으로 나타냅니다.
어떻습니까? 이렇게 정리한 것이 더 눈과 머리에 잘 들어 오나요? 보다 쉽게 설명하기 위해서 나도 말로 풀어서 설명을 하고는 있습니다만, 때로는 수학적으로 정돈된 상태로 읽고 이해하고 정리하는 것도 꼭 필요한 일입니다.(그렇다고 위의 정리 내용이 특별히 중요하다고 강조하는 것은 아닙니다.) 하지만, 완벽한 이해가 뒷받침되지 않은 상태에서 간단히 정리된 것을 외우는 것만으로는 좋은 실력을 갖추기 어려운 것은 물론이고, 좋은 점수도 기대하기 어렵다는 것은 여러분이 더 잘 알고 있겠죠.
어떤 정수를 양의 정수로 나누면 몫과 나머지가 생깁니다. 그런데, 이 때 몫과 나머지는 오직 하나씩 존재한다는 것입니다. 너무나 당연한 말인 듯 싶은데 혹시 이 말에 고개를 갸우뚱하는 학생은 잉여류를 설명하면서 언급했던 나머지의 범위를 유념해야 합니다. 나머지는 보다 크고 나누어 주는 수보다는 작은 수라고 이야기 했지요? 예를 들어보면 을 로 나누어 보면 몫이 이고 나머지는 가 됩니다. 다른 몫이나 나머지는 없습니다. 이것을 식으로 표현하면 이렇게 나타낼 수 있습니다.
임의의 정수 를 양의 정수 으로 나눌 때, (단, )인 정수 , 은 오직 하나 정해진다.
실제로 잉여류에 관한 문제에서는 대부분 잉여류라는 직접적인 표현을 잘 사용하지 않습니다. 특히나 수능시험같은 큰 시험에서는 어떤 정의를 문제에 주어 주는 경우가 많습니다. 많이 보는 예로 허수단위인 의 경우도 이라는 정의를 문제에 주어줍니다. 이것 말고도 많은 것들을 그 용어를 직접적으로 사용하지 않고 정의해 주는 경우가 많이 있습니다. 그런데, 이런 친절함(?)이 고마운 것 같으면서도 전혀 그렇지 않은 경우도 많습니다. 그 용어를 직접 사용하지 않고 정의를 해 주는 것이 도리어 더 어렵게 만드는 것이지요. 용어를 보면 금방 생각이 났을 문제인데, 그 정의만 보고는 무슨 내용인지를 몰라서 아는 내용의 문제인데도 방향조차도 못 잡고 놓치는 경우가 있습니다. 정말 문제를 못 읽어서 틀리는 경우가 생기는 것입니다.(문제를 읽지 못해서 틀리는 일이 아주 많다는 것을 알고 있나요?) 그러니 여러분은 이 해설을 읽은 다음 문제를 풀 때 문제를 잘 읽으면서 생각해 보세요. 문제에서 어떻게 잉여류, 잉여계를 표현하고 있는지를.
(pi,qj는 소수)
로 하고, a의 하나의 소인수분해에 나타나는 소인수의 개수가 r-1일 때는 정리가 성립된다고 가정하여 r의 경우를 증명한다.
일 때 a는 소수가 아니므로, 당연히 s도 
이다. 그리고 소수 p1이 
를 나누어떨어지게 할 수 있으므로, 명제3에 의해 qi중의 적어도 하나가 p1로 나누어떨어집니다. 필요하다면 번호를 바꾸어 달아서, 이를테면 
이라 하면 
도 소수이므로 
이라야만 합니다. 따라서
으로 약분하면
의 순서를 적당히 바꾸어 배열하면, 
, 
,…,
이 됩니다. 
(mod n)
(mod 3)
(mod 5)
(mod 12)
(mod n)
(mod n) 이면 
(mod n)
(mod n), 
(mod n) 이면 
(mod n)
(mod n)
, 여기서 
은 집합 A의 원소개수
)일 때 R을 A에 관한 관계(relation on A)라고 한다.
이면 "x는 y에 대하여 R관계가 있다"라 고 하며 xRy로 표시한다.
의 첫 번째 원소의 집합을 R의 정의역이라 하고 Dom(R), 두 번째 원소의 집합을 R의 치역이라 하고 Ran(R)로 표시한다. 
또는 
관계 R이 AxB의 부분집합에서
가 주어질 때
이 주어질 때 R을 화살표 도표로 표현하라 
를 집합적 관계로 표현하라. 
에 대하여 R을 A에서 B로의 관계라 할 때
을 MR로 표현하라
R
이면 정점 
의 내차수(in-degree) ∼ a를 끝점으로 하는 간선의 수
인 b의 개수
인 b의 개수
일 때 모든 정점에 대한 내차수와 외차수를 구하라.
일 때 R={(1,3),(1,4)}, S={(3,5),(4,5)}이다. AxC이 순서쌍 중에서 R·S에 속하는 것은?
일 때
의 정의
을 mxn 부울 행렬일 때
이면 
임을 보여라.
이면
에 대하여 관계 
와 
는 각각 
의 크기를 가지며 
은 nxm크기를 가진다. 또한 
이다
에 대하여
라 하면 R은 비 반사관계이다.
: 반사, 비 반사도 아님
: 반사
: 반사아님
: 비 반사관계
: 반사관계
: 반사관계
에 대하여
일 때 R을 비 대칭관계
로 표현했을 때 대칭관계는 
이면 
이면 
라 표시했을 때 
.
이고 모든 i에 대하여 
일 때 
은 어떤 관계인가?
이면 
또는 
이므로 반 대칭관계
인 관계 R을 추이관계라 한다. 
일 때 
인 논리행렬 즉, 
일 때 R은 추이관계이다.
에 대하여 
그러나 
따라서 R은 대칭관계가 아니다. 
은 동치관계이다. 
로 정의한다. 
이 주어질 때 
이 A의 분할이라 하는 것은 다음의 조건을 만족하여야 한다.
내에 있는 부분집합 
을 블록(block)라 한다.
는 Z의 분할이다.
라 정의하면 
은 반사적 페쇄이다.
은 대칭적 폐쇄이다.
이 존재하고 유한수열 
을 나타낸다.
으로 표시하기로 한다. 
에 대하여, 
일 때, 
은 시점 a에서부터 종점 b까지 길이 n인 경로가 있음을 의미한다.
를 R의 추이적 폐쇄라고 한다.
에 속하므로
. R가 집합 A에 관한 관계일 때 
이다. 즉, 
의 1을 
로 모두 옮겨 쓴다.
와 성분1인 
을 나열
의 위치에 1을 쓴다.
이다.
의 1열의 위치 (
=2행)
=2열) 이므로 (
의 1이 있는 위치를 
의 같은 위치에 1을 넣고 
=2행)
=2열, 
=3열)이므로
의 4열 위치 (1, 2 ; 3행), 4행 위치 (없음)