모듈러 연산(Modular arithmetic)

이 개념 위에 세워진 것

이 개념을 언급하는 페이지

• 자연로그

  … x 근처의 수들 가운데 소수가 차지하는 비율은 약 1/\ln x 입니다. 나눗셈의 나머지만 보는 세계(모듈러 연산)에도 로그가 있습니다. "3을 몇 번 곱해야 17로 나눈 나머지가 13이 될까?"를 묻는 것이고, 1부터 …

• 허수 단위 i

  … ) 4로 나눈 나머지만 따라가면 된다는 점에서, 이것은 정수를 어떤 수로 나눈 나머지끼리 계산하는모듈러 연산과 같은 구조입니다. 네 번 대신 n번에 한 바퀴를 도는 수를 생각하면 n으로 나눈 나머지의 계산이 …

• 리사주 곡선

  … 상관없이 한 바퀴 안의 어디쯤인지만으로 정해집니다. 몇 바퀴인지는 버리고 나머지만 남기는 이 셈법은모듈러 연산과 같은 생각입니다. 비율이 무리수이면 두 주기의 공배수가 영원히 없어서 곡선은 결코 닫히지 않고, …

• 포함배제 원리

  … 나누어떨어지는지는 그 곱으로 나눈 나머지로만 정해지니, 한 줄마다 같은 무늬가 반복되기 때문입니다(모듈러 연산). 30과 서로소인(1 말고는 공약수가 없는) 나머지는 1, 7, 11, 13, 17, 19, 23, …

• 단사·전사·전단사

  … 시계 위의 수 0, 1, \dots, n-1 에 a = 를 곱하고 n = 으로 나눈 나머지를 취하는 함수(모듈러 연산)는 각 점 k에서 a·k mod n으로 화살표를 그렸습니다. 전단사가 될 조건은 \gcd(a, n) = …

• 비둘기집 원리

  … 생일 문제). 정수 n+1 개를 고르면 n 으로 나눈 나머지가 같은 두 수가 반드시 있습니다(모듈러 연산). 가장 멋진 응용은 디리클레의 근사 정리입니다. 무리수 \alpha = 에 대해 0, \alpha, …

• 동치관계와 분할

  … 원소로 삼은 집합이 \mathbb{Z}/n\mathbb{Z} 입니다. 여기서 덧셈과 곱셈을 하는 것이모듈러 연산입니다. 줄기들이 원을 따라 도는 모습은 원을 n 등분하는 1의 거듭제곱근과 같은 그림입니다. 분수도 …

• 최대공약수와 유클리드 호제법

  … 베주 항등식이라 합니다. 최대공약수가 1인 두 수, 12와 5 같은 두 수를 서로소 라 합니다. 이 식이모듈러 연산에서 나눗셈을 가능하게 합니다. 모듈러 연산은 어떤 수 m으로 나눈 나머지만 보는 계산이고, 이것을 '법 …

• 파스칼의 삼각형

  … 줄을 모두 더하면 멱집합의 크기 2^n 입니다. 이제 각 수를 m = 으로 나눈 나머지로 칠해 봅시다(모듈러 연산). 줄 수는 입니다. 어두운 칸은 m으로 나누어떨어지는 수, 밝은 칸은 나머지마다 다른 색입니다. 줄 …

• 진법

  … 나머지를 되풀이해 얻습니다. 맨 끝자리가 n \bmod b 이고, 몫을 다시 나누면 다음 자리가 나옵니다(모듈러 연산). 2진법에서 자리 하나는 "있다/없다"의 선택입니다. 그래서 앞자리 0을 허용한 k 자리 2진수(0부터 …

• 원 위의 곱셈표

  … 개의 점을 찍고, 점 k 에서 점 m\cdot k 로 줄을 긋습니다. 번호는 N 에서 다시 0으로 감기니모듈러 연산의 곱셈표 한 줄을 통째로 그리는 셈입니다. 곱하는 수는 m = 입니다. m을 천천히 1 늘리기 직선만 …

• 오일러 피 함수와 페르마 소정리

  모듈러 연산에서 역수가 있는 수, 곧 n 과 최대공약수가 1인 수를 단원 이라 부릅니다. n = 의 시계에서 …

• RSA 암호

  … 보면 같은 결론이 나옵니다(중국인의 나머지 정리). d 는 \varphi(n) 을 법으로 한 e 의모듈러역수이고, 확장 유클리드 호제법으로 순식간에 구합니다. e 가 \varphi(n) 과 서로소가 아니면 …

• 울람 나선

  … 정수). 변수의 제곱까지 들어간 이런 식을 2차 다항식, 줄여서 2차식이라 합니다. 어떤 2차식은나머지로 보았을 때 2, 3, 5, 7 같은 작은 소수로 나누어떨어지는 경우가 드물어서, 다른 식보다 소수가 …

• 1의 거듭제곱근

  … \omega^b = \omega^{(a+b) \bmod n} 입니다. 1의 거듭제곱근의 곱셈이 곧n을 법으로 하는 덧셈, 시계처럼 n에 닿으면 0으로 돌아가는 덧셈입니다(n = 12이면 9 + 5 = 2). 시계 산수가 원 …

• 원시근

  모듈러 연산의 시계 n = 에서 1부터 출발해 매번 a = 씩 곱해 봅시다. 자취는 입니다. 나머지는 n 가지뿐이니 …

• 중국인의 나머지 정리

  … n)에 적으면 0, 1, 2, …가 대각선으로 걸어가다 가장자리에서 반대편으로 넘어갑니다. 수 k 를 두나머지의 짝 (k \bmod m,\; k \bmod n) 에 적으면, k 가 1 늘 때마다 오른쪽 위로 한 칸씩 …

• 디피–헬먼 키 교환

  … 수를 하나씩 고릅니다. 앨리스는 a = , 밥은 b = 입니다. 각자 g 를 제 비밀 수만큼 거듭제곱해p로 나눈 나머지를 공개하고, 받은 수를 다시 제 비밀 수만큼 거듭제곱합니다. (g^b)^a = g^{ab} = …

• 소수 판정

  … 여전히 어렵습니다. 밑을 거듭제곱할 때 값이 도는 고리 구조는 원시근에서, 판정에 쓰는 나머지 계산은모듈러 연산에서 이어집니다. 그림의 회색 칸, 곧 n 과 공약수가 있는 밑을 가려내는 최대공약수 계산은 ⟦유클리드 …

• 쌍둥이 소수

  … 간격 2, 노랑이 6의 배수입니다. (3, 5)를 빼면 쌍둥이는 모두 6k - 1, 6k + 1 꼴입니다.6으로 나눈 나머지가 1이나 5인 수만 2와 3의 배수를 피하기 때문입니다. 같은 이유로 간격 6( 2 \cdot 3 의 …

• 가우스 소거법

  … 수로 언제나 나눌 수 있는 수 체계(체)라면 어디서든 쓸 수 있어서, 소수 p 로 나눈 나머지의 세계(모듈러 연산)에서도 그대로 통합니다. 마르코프 연쇄의 정상 분포, 곧 한 걸음 더 가도 각 상태에 있을 확률이 …

• 오일러 경로

  … 나가는 다리 하나를 씁니다. 그러니 출발점과 도착점이 아닌 땅에는 다리가 짝수 개 있어야 합니다. 차수를2로 나눈 나머지만 보면 되는 셈입니다. 홀수 차수인 점은 많아야 둘(출발점과 도착점)이고, 제자리로 돌아오는 회로라면 …

• 해밍 거리

  … p₁, p₂, p₃를 더하는데, 그림의 세 원 안에서 1의 개수가 각각 짝수가 되도록 정합니다. 짝수인지는2로 나눈 나머지로 봅니다. 보낼 데이터를 (이진수 )로 정하면 부호어는 입니다. 비트를 눌러 뒤집어 보세요(잡음). 받은 …

• 불 대수

  … 왼쪽 입력 원을 눌러 0과 1을 바꿔 보세요. 노란 선에는 1이, 어두운 선에는 0이 흐릅니다. XOR은2를 법으로 하는 덧셈입니다. 1 ⊕ 1 = 0이고, 넘친 1은 올림으로 넘어갑니다. 반가산기 둘과 OR 하나로 올림까지 받는 …

• 처치–튜링 논제

  … 규칙 30은 무작위처럼 보이는 무늬를 만듭니다. 규칙 90을 한 칸에서 시작하면 파스칼의 삼각형의 수를2로 나눈 나머지가 나오는데, 이것이 삼각형 가운데를 되풀이해 파낸 무늬인 시에르핀스키 삼각형입니다(폴란드 수학자 바츨라프 …

• 유한 오토마톤

  … 그러니 m을 3으로 나눈 나머지 r만 알면 다음 나머지 (2r + b) \bmod 3 을 알 수 있고(모듈러 연산), 상태 셋이면 충분합니다. 수를 끌어 바꿔 보세요: . 입력이 그 수의 이진수( )로 바뀝니다. 같은 …

• 순열

  … 최대공약수로 구하고, 순환 하나를 k번 돌린 결과는 k를 순환 길이로 나눈 나머지로 정해지니모듈러 연산의 문제가 됩니다.

• 분할수

  … 것도 발견했습니다(p(4) = 5, p(9) = 30, p(14) = 135, …). 이런 나머지의 규칙은모듈러 연산의 언어로 씁니다. 이어지는 곳. 순서를 따지면 분할이 아니라 합성이 되고, 그 수는 별과 막대로 …

• 반 데르 바르던 정리

  … 소수가 무한히 많다는 것을 증명했습니다. 이것은 'd로 나눈 나머지가 a인 소수가 무한히 많다'는 말이어서모듈러 연산의 언어로 쓰입니다. 그린–타오 정리와 달리 한 수열에 소수가 많다는 것이지, 소수만으로 된 긴 등차수열이 …

• 해시 테이블

  … 찾습니다. 비결은 키(이름)를 해시 함수라는 함수로 뒤섞어 큰 수로 만들고, 칸의 개수 m으로 나눈나머지를 칸 번호로 쓰는 것입니다. 넣을 때도 찾을 때도 같은 계산을 하니 그 칸만 보면 됩니다. 칸 수 m = …

• 오류 정정 부호

  … 쓰는 부호는 선형입니다. 두 부호어를 자리마다 XOR로 더해도 다시 부호어가 된다는 뜻입니다. 비트를2로 나눈 나머지의 수로 보면 데이터 벡터에 생성 행렬을 곱한 것이 부호어이니, 부호어들은 생성 행렬의 …

• 수 체계: 자연수에서 실수까지

  … 상수가 아닌 모든 다항식이 1차식의 곱으로 쪼개집니다. 정수 안에서의 나눗셈은 정수론(소수,모듈러 연산)으로 갑니다. 역원이 있게 하려고 수를 넓혀 온 이 이야기는 군의 이야기이기도 하고, 수의 바탕을 …

• 다항식

  … k명이 모이면 다항식을, 따라서 비밀을 되찾지만 k − 1명으로는 비밀에 대해 아무것도 알 수 없습니다(나머지 연산으로 계산할 때. 1979년 아디 샤미르의 비밀 분산). 리드–솔로몬 부호는 데이터를 다항식으로 보고 …

• 군

  … 시계에서는 9 + 5 = 2입니다. 0부터 11까지의 수와 '더한 뒤 12로 나눈 나머지'라는 연산(모듈러 연산)이 이루는 이 군을 ℤ₁₂라 씁니다. 1부터 6까지의 수와 '곱한 뒤 7로 나눈 나머지'도 군입니다. …

• 정수론

  … \equiv b \pmod m 로 씁니다. 시계가 13시를 1시로 적는 것이 12를 법으로 한 셈입니다(모듈러 연산). 이 기호는 가우스가 1801년, 스물네 살에 펴낸 『산술 연구』(Disquisitiones …

• 라틴 방진

  … (i + j) \bmod n , 곧 i + j를 n으로 나눈 나머지에 해당하는 기호를 넣는 것입니다(모듈러 연산). 한 줄을 내려갈 때마다 윗줄을 한 칸씩 밀어 쓰는 셈이라 가로줄과 세로줄마다 기호가 한 번씩 돕니다. …

• 층: 국소에서 전체로

  … 국소에서 전체로가 여러 분야에서 따라가는 주제이고, 나머지를 붙이는 일은 중국인의 나머지 정리와모듈러 산술에서 볼 수 있습니다. 편각이 한 바퀴 돌면 360° 어긋나는 현상은 극형식과 복소수에서 다시 …

• 님과 스프라그–그런디 정리

  … 1의 개수의 홀짝을 적은 수를 님 합 이라 하고 a \oplus b 로 적습니다. 받아올림 없이 자리마다2를 법으로더하는 셈이며, 컴퓨터의 비트 연산 XOR과 같습니다. 규칙이 옳은 까닭은 세 가지 사실입니다. (1) …

• 페르마의 마지막 정리

  … 0부터 p − 1까지의 x, y 가운데 양변을 p로 나눈 나머지가 같은 쌍의 개수를 N_p 라 합니다(모듈러 연산). p = 5이면 x = 0, 1일 때 오른쪽이 0이고, 왼쪽 y^2 + y 를 5로 나눈 나머지가 0인 …

• 배타적 논리합

  … = 1입니다. 받아올림을 버린 덧셈과 같습니다. 1 + 1 = 2를 2로 나눈 나머지는 0이니, XOR은2를 법으로 하는 덧셈입니다. 그래서 덧셈의 성질이 그대로 따라옵니다. 순서를 바꿔도( a \oplus b = b \oplus …

이 페이지가 가리키는 개념