잉여역수

1. 개요

---

a가 하나의 정수일 때, 법 n에 대한 a의 잉여역수(arithmethic inverse) 란 aa'를 n으로 나눈 나머지가 1임을 만족하는 수 a'를 말한다. 이는 윌슨 정리 증명 시 사용되는 개념이다. 잉여역원이라고도 한다.
법 n이 소수일경우 페르마의 소정리를 응용한 방법으로 잉여역수를 구할 수 있다.

2. 일반항

---

a'가 법 n에 대한 a의 잉여역수일 때, aa'=kn+1(k는 정수)이므로 $$\displaystyle a'=\frac{1+kn}{a}$$(k는 정수)가 성립하며, 이것이 일반항이라고 할 수 있다. 따라서 잉여역수의 일반항을 수열이라고 하면 이것은 등차수열이다. 예를 들어 법 5에 대한 3의 잉여역수는 3a'를 5로 나눈 나머지가 1인 수 a'로, $$\displaystyle a'=\frac{1+5k}{3}$$(k는 정수)꼴이며, k=1일 때 a'=2가 한 예이다.

3. 유일성

---

c, d가 법 n에 대한 a의 잉여역수일 때, ac=ad=1(mod n)이라고 할 수 있고, 이 식에 의하여 ac-ad=a(c-d)=0(mod n)임을 알 수 있고, 이것을 a(c-d)=kn으로 나타낼 수 있다. 이때 a와 n이 서로소이면 a(c-d)뿐만 아니라 (c-d) 역시 n으로 나누어 떨어진다는 것을 알 수 있고, 따라서 c와 d를 n으로 나눈 나머지는 서로 같으며, 이때 c=d=x (mod n)로 나타낼 수 있다. 이것을 잉여역수의 유일성이라고 한다.