a mod b

목차

1. 수의 모듈로 계산과 페르마의 정리

2. 6 * 6 = 1

 

---

 

 

---

 

 

1. 수의 모듈로 계산과 페르마의 정리

 

만약 꼬마곰 젤리 81개를 5명의 아이들에게 똑같이 나눠 준다면 각자에게 16개씩 돌아가고 하나가 남을 것입니다. 수학자들은 이것을 “81모듈로 5는 1”이라고 표현합니다. 일반적 표현으로는 “m 모듈로 n은 m을 n으로 나누었을 때의 나머지와 같다."고 합니다. 이 '모듈로' 계산법은 수학의 여러 분야에서 중요한 역할을 합니다.

 

수학자가 아닌 사람들도 일상생활에서 이 계산법을 아주 능숙하게 사용하고 있습니다. 예를 들어 39일 뒤에 어떤 요일이 오는지 알고 싶으면 직관적으로 39 모듈로 7로 계산합니다. 답은 4, 즉 오늘이 만약 월요일이라면 39일 뒤는 4일 후인 금요일이 되는 것이죠. 다른 예로 50시간 뒤에 시계의 시계바들이 어떤 숫자를 가리키고 있을지 생각해 볼 수 있습니다. 50 모듈로 24는 2입니다. 그러므로 50시간 뒤 시계바늘은 지금 시각보다 두 시간 뒤를 가리키고 있을 것입니다.

 

 

 

여기까지는 별로 특별한 것이 없고, 널리 사용되고 있는 계산법에 전문용어를 붙인 것뿐입니다. 그러나 수학자들에게 모듈로 계산은 그 이상의 큰 의미를 지니고 있습니다.

모듈로 테크닉을 사용함으로써 수의 놀라운 속성을 설명해낼 수 있기 때문이죠. 소수 n, 그리고 1보다 크고 n-1보다 작은 수를 상정해 봅니다. 만약 수 k를 자신의 수와 (n-1)번 곱한다면 어떻게 될까요? 재미있게도 모듈로 n을 계산했을 때의 결과는 언제나 1입니다.

꼬마곰 젤리의 예에서 n=5(아이들의 수는 5명, 이 수가 소수라는 것을 기억할 것), k=3이었습니다.

위에서 말한 대로 하면 81이라는 결과가 나옵니다. 3을 (5-1)번 곱하면 3*3*3*3=81이고, 81 모듈로 5는 1일 수밖에 없는 것입니다.

 

 

 

위의 예처럼 소수의 경우 모듈로 계산을 하면 항상 1이 나온다는 것은 이미 오래 전부터 알려진 사실이며, 프랑스의 수학자 피에르 드 페르마가 17세기에 발견했습니다. 모듈로 테크닉은 특히 최근의 암호화 연구에서 중요한 역할을 하고 있습니다. 이런 연구에 사용되는 소수는 수천, 수만 자리에 육박합니다.

 

---

 

2. 6 * 6 = 1 

 

덧셈과 곱셈을 일반적인 덧셈과 곱셈을 한 뒤 다시 모듈로 n으로 넘어가는 것이라고 생각하면 '나머지'(0, 1, …, n-1)도 다른 수와 다를 것이 없습니다.

예를 들어, 모듈로 7의 계산에서 3 곱하기 5는 1이며, 3*5 모듈로 7은 1이기 때문이고 같은 이유로 4 더하기 6은 3이 되며, 4+6 모듈로 7을 계산하면 3이 됩니다.

이처럼 모듈로 계산은 일반적인 계산과 많은 공통점을 가지고 있는데, 특히 수 n이 소수일 때는 더욱 그렇습니다. 이런 경우, (0만 빼고) 모든 수의 곱이 1이 되게 할 수 있습니다.

 

 

 

예를 들어 수 6을 모듈로 7로 계산해 봅니다. 1*6, 2*6, 3*6, 4*6, 5*6, 6*6을 모듈로 7로 차례대로 계산하면 그 나머지는 각각 6, 5, 4, 3, 2, 1이 됩니다. 즉, 6*6=1이다.(이것은 소수가 아닌 수에는 적용되지 않는다. 예를 들어 n=12라면 4*x= 1모듈로 12인 수 x를 찾는 것은 불가능하다. 4*x를 12로 나누면 0, 4, 8만이 나머지로 나오기 때문이다).

모듈로 계산의 핵심은 풍부한 대수적 속성에 있습니다. 덧셈의 교환법칙이 성립하는 것도 이런 이유에서이며, a+b=b+a이기 때문에 두 경우의 나머지 모듈로 n도 같은 것이입니다.