1.4 Modulo arithmetic · 합동 산술
$n$을 고정된 양의 정수라 하자. 두 정수 $a$와 $b$가 법 $n$에 대하여 합동이라는 것은,
$n|a - b$라는 뜻이다.
Let $n$ be a fixed positive integer. Two integers $a$ and $b$ are said to be congruent modulo n,
if $n|a - b$.
$a = q_1 n + r_1$ $(0 \le r_1 \lt |n|)$이고 $b = q_2 n + r_2$ $(0 \le r_2 \lt |n|)$라 하자. 그러면
Suppose that $a = q_1 n + r_1$ $(0 \le r_1 \lt |n|)$ and $b = q_2 n + r_2$ $(0 \le r_2 \lt |n|)$. Then
1. $12 \equiv 7 \ (\bmod\ 5)$
2. $23 \equiv 7 \ (\bmod\ 8)$
3. $1000 \equiv 6 \ (\bmod\ 7)$
역주. 원문 (3)은 "$1000 \equiv 4 \ (\bmod\ 7)$"으로 인쇄되어 있으나 $1000 - 4 = 996$은 7의 배수가 아니므로 성립하지 않는다. $1000 = 7 \cdot 142 + 6$이므로 $1000 \equiv 6 \ (\bmod\ 7)$이다. 위에서 바로잡아 옮겼다. (아래 예제 1.18 (1)의 $10000 \equiv 4 \ (\bmod\ 7)$은 옳다.)
1. $12 \equiv 7 \ (\bmod\ 5)$
2. $23 \equiv 7 \ (\bmod\ 8)$
3. $1000 \equiv 4 \ (\bmod\ 7)$
$n \gt 1$을 고정하고 $a$, $b$, $c$, $d \in \mathbb{Z}$라 하자. 그러면 다음 성질이 성립한다:
1. $a \equiv b \ (\bmod\ n)$이고 $c \equiv d \ (\bmod\ n)$이면, $a + c \equiv b + d \ (\bmod\ n)$이고 $ac \equiv bd \ (\bmod\ n)$이다.
2. $\gcd(t, n) = 1$이라 하자. $ta \equiv tb \ (\bmod\ n)$이면 $a \equiv b \ (\bmod\ n)$이다.
역주. 원문 (1)의 둘째 결론은 "$ac \equiv bc \ (\bmod\ n)$"으로 인쇄되어 있다. 이는 $a \equiv b$만으로도 얻어지는 약한 주장이고, 가정 $c \equiv d$까지 쓰는 본래의 성질은 $ac \equiv bd \ (\bmod\ n)$이다. 위에서 바로잡아 옮겼다(아래 연습문제 1.22의 풀이도 이 형태를 쓴다).
정리 1.16 (2).
Let $n \gt 1$ be fixed and $a$, $b$, $c$, $d \in \mathbb{Z}$. Then the following porperties hold:
1. If $a \equiv b \ (\bmod\ n)$ and $c \equiv d \ (\bmod\ n)$, then $a + c \equiv b + d \ (\bmod\ n)$ and $ac \equiv bc \ (\bmod\ n)$.
2. Suppose that $\gcd(t, n) = 1$. If $ta \equiv tb \ (\bmod\ n)$, then $a \equiv b \ (\bmod\ n)$.
Theorem 1.16 2).
1. $3 \cdot 6 \equiv 3 \cdot x \ (\bmod\ 35)$라 하자. 그러면 $\gcd(3, 35) = 1$이므로 $x \equiv 6 \ (\bmod\ 35)$이다.
2. $3 \cdot 4 \equiv 3 \cdot 8 \ (\bmod\ 6)$이지만 $4 \not\equiv 8 \ (\bmod\ 6)$이다 $(\because (3, 6) \neq 1)$.
1. Suppose that $3 \cdot 6 \equiv 3 \cdot x \ (\bmod\ 35)$. Then $\gcd(3, 35) = 1$. So $x \equiv 6 \ (\bmod\ 35)$.
2. $3 \cdot 4 \equiv 3 \cdot 8 \ (\bmod\ 6)$. But $4 \not\equiv 8 \ (\bmod\ 6)$ $(\because (3, 6) \neq 1)$.
1.
2. $273 \cdot 107 \equiv 3 \cdot 2 \equiv 1 \ (\bmod\ 5)$
3. $5^3 \equiv 25 \cdot 5 \equiv 1 \cdot 5 \equiv 5 \ (\bmod\ 12)$
1.
2. $273 \cdot 107 \equiv 3 \cdot 2 \equiv 1 \ (\bmod\ 5)$
3. $5^3 \equiv 25 \cdot 5 \equiv 1 \cdot 5 \equiv 5 \ (\bmod\ 12)$
공식 $a^x \equiv y \ (\bmod\ n)$을 생각하자. $a, x$를 알고 $y$를 구하는 것은 비교적 쉬운 문제이다. 하지만 $a, y$를 알고 $x$를 구하는 것은 어려운 문제이다. 이 문제가 어렵다는 사실 때문에 RSA 암호를 푸는 것이 어려워진다.
Consider the formula $a^x \equiv y \ (\bmod\ n)$. Suppose that we know that $a, x$ and find $y$. It’s a relatively easy problem. But suppose that we know that $a, y$ and find $x$. It’s a hard problem. The fact that this problem is hard makes it difficult to solve the RSA password.
1. $3^4 \equiv (3^2)^2 \equiv 9^2 \equiv 81 \equiv 4 \ (\bmod\ 11)$
2. $3^8 \equiv (3^4)^2 \equiv 4^2 \equiv 5 \ (\bmod\ 11)$
3. $3^{16} \equiv (3^8)^2 \equiv 5^2 \equiv 3 \ (\bmod\ 11)$
4. $3^{32} \equiv (3^{16})^2 \equiv 3^2 \equiv 9 \ (\bmod\ 11)$
5. $3^{40} \ (\bmod\ 11)$을 계산하자. $40 = 2^5 + 2^3$임에 유의하라.
곱셈을 6번만 사용했음에 유의하라.
1. $3^4 \equiv (3^2)^2 \equiv 9^2 \equiv 81 \equiv 4 \ (\bmod\ 11)$
2. $3^8 \equiv (3^4)^2 \equiv 4^2 \equiv 5 \ (\bmod\ 11)$
3. $3^{16} \equiv (3^8)^2 \equiv 5^2 \equiv 3 \ (\bmod\ 11)$
4. $3^{32} \equiv (3^{16})^2 \equiv 3^2 \equiv 9 \ (\bmod\ 11)$
5. Calculate $3^{40} \ (\bmod\ 11)$. Note that $40 = 2^5 + 2^3$.
Notice that we only did 6 multiplications.
$r \in \mathbb{Z}_{>0}$이고 $r = b_n 2^n + \cdots + b_1 2 + b_0$ ($b_i \in \{0, 1\}$)라 하자. 2진 표현(2-digit expression)을 이용하여 $a^r \ (\bmod\ m)$을 계산하자.
위 식을 계산하는 데 필요한 곱셈의 횟수를 세어 보자.
1. $a^{2^n}, \cdots, a^2$을 계산한다. $n$번의 곱셈이 필요하다.
2. $a^{b_n 2^n} \times \cdots a^{b_0}$을 계산한다. $n$번 이하의 곱셈이 필요하다.
Let $r \in \mathbb{Z}_{>0}$ and $r = b_n 2^n + \cdots + b_1 2 + b_0(b_i \in \{0, 1\})$. Calculate $a^r \ (\bmod\ m)$ using 2-digit expression.
Let’s count the number of multiplication of calculate above formula.
1. Calculate $a^{2^n}, \cdots, a^2$. It requires $n$ times multiplication.
2. Calculate $a^{b_n 2^n} \times \cdots a^{b_0}$. It requires $n$ or fewer times multiplication.
$a^N \ (\bmod\ m)$을 $2\lfloor \log_2 r \rfloor$번의 곱셈만으로 계산할 수 있다.
역주. 원문은 지수를 $N$으로 쓰면서 로그 안에는 앞 단락의 문자 $r$을 그대로 두었는데, 둘은 같은 지수를 가리킨다. 즉 $a^N \ (\bmod\ m)$을 $2\lfloor \log_2 N \rfloor$번의 곱셈으로 계산할 수 있다는 뜻이다(연습문제 1.23이 이 형태를 묻는다).
It is possible to calculate $a^N \ (\bmod\ m)$ using only $2\lfloor \log_2 r \rfloor$ multiplication.
예를 들어 어떤 컴퓨터가 법 $n$에 대한 곱셈을 초당 10억 번 수행한다고 하자. $N = 10^{20}$일 때 $a^N \ (\bmod\ n)$을 계산하자. 곱셈을 그대로 $10^{20}$번 하면 약 3000년이 걸린다. 하지만 위 방법을 쓰면 곱셈을 $2\lfloor \log_2 10^{20} \rfloor$번만 해서 0.1마이크로초가 걸린다.
For example, suppose a computer does 1 billion modulo $n$ multiplication per a second. Compute $a^N \ (\bmod\ n)$ when $N = 10^{20}$. By multiplication itself $10^{20}$times take about 3000 years. But using the above method, multiplication $2\lfloor \log_2 10^{20} \rfloor$ times take 0.1 micro seconds.
입력 : $x \in \mathbb{Z}, n, N \in \mathbb{Z}_{>0}$이고 $n \le 2$.
출력 : $\operatorname{power}(x, N)$ ($x^N \equiv \operatorname{power}(x, N) \ (\bmod\ n)$이고 $0 \le \operatorname{power}(x, N) \lt n$을 만족하는 정수)
(재귀 알고리즘)
역주. 원문의 입력 조건은 "$n \le 2$"로 인쇄되어 있으나 문맥상 법에 대한 조건 $n \ge 2$이다(출력이 $0 \le \operatorname{power}(x, N) \lt n$이려면 $n \ge 2$여야 하고, 정리 1.32·1.37도 법에 $n \ge 2$를 요구한다). 지수에 대한 조건 $N \ge 2$로 읽을 수는 없다 — $N = 1$이 이 재귀의 기저 단계이기 때문이다.
Input : $x \in \mathbb{Z}, n, N \in \mathbb{Z}_{>0}$ and $n \le 2$.
Output : $\operatorname{power}(x, N)$ (integer such that $x^N \equiv \operatorname{power}(x, N) \ (\bmod\ n)$ and $0 \le \operatorname{power}(x, N) \lt n$
(a recursive algorithm)
$24x + 9y = 3$의 정수해를 구하라.
$24, 9$에 유클리드 호제법을 적용하면
이므로 $\gcd(24, 9) = 3$이고, $3 \mid 3$이므로 정수해가 존재한다. 후진대입하면
이므로 $24 \cdot (-1) + 9 \cdot 3 = 3$이다. 즉 $(x_0, y_0) = (-1, 3)$은 하나의 특수해이다. $\gcd(24, 9) = 3$이므로 정리 1.9와 정리 1.10에 의해 일반해는
이다. (검산: $24(-1 + 3n) + 9(3 - 8n) = -24 + 72n + 27 - 72n = 3$.)
Find an integral solution of $24x + 9y = 3$.
Applying the Euclidean algorithm to $24, 9$,
so $\gcd(24, 9) = 3$, and since $3 \mid 3$ an integral solution exists. Back-substituting,
so $24 \cdot (-1) + 9 \cdot 3 = 3$. That is, $(x_0, y_0) = (-1, 3)$ is a particular solution. Since $\gcd(24, 9) = 3$, by Theorems 1.9 and 1.10 the general solution is
(Check: $24(-1 + 3n) + 9(3 - 8n) = -24 + 72n + 27 - 72n = 3$.)
$1001 \cdot 409 \ (\bmod\ 9)$를 계산하라.
$1001 = 9 \cdot 111 + 2$이므로 $1001 \equiv 2 \ (\bmod\ 9)$이고, $409 = 9 \cdot 45 + 4$이므로 $409 \equiv 4 \ (\bmod\ 9)$이다. 정리 1.16 (1)에 의해
이고 $0 \le 8 \lt 9$이므로 $1001 \cdot 409 \equiv 8 \ (\bmod\ 9)$이다.
Compute $1001 \cdot 409 \ (\bmod\ 9)$.
Since $1001 = 9 \cdot 111 + 2$, $1001 \equiv 2 \ (\bmod\ 9)$, and since $409 = 9 \cdot 45 + 4$, $409 \equiv 4 \ (\bmod\ 9)$. By Theorem 1.16 (1),
and since $0 \le 8 \lt 9$, $1001 \cdot 409 \equiv 8 \ (\bmod\ 9)$.
다음 명제를 완성하라.
"$a^N \ (\bmod\ n)$은 곱셈을 $\boxed{\qquad\qquad}$번만 써서 계산할 수 있다."
정리 1.20에 의해 $a^N \ (\bmod\ n)$은 곱셈을 $2\lfloor \log_2 N \rfloor$번만 써서 계산할 수 있다. 따라서 빈칸은 $2\lfloor \log_2 N \rfloor$이다.
Complete the following statement.
It is possible to calculate $a^N \ (\bmod\ n)$ using only $\boxed{\qquad\qquad}$ times multiplications.”
By Theorem 1.20, it is possible to calculate $a^N \ (\bmod\ n)$ using only $2\lfloor \log_2 N \rfloor$ multiplications. Hence the blank is $2\lfloor \log_2 N \rfloor$.
2진 표현을 이용하여 $2^{341} \ (\bmod\ 340)$을 계산하라.
$341 = 101010101_{(2)}$임에 유의하라.
$2 \equiv 2 \ (\bmod\ 340)$, $2^2 \equiv 4 \ (\bmod\ 340)$, $2^4 \equiv 16 \ (\bmod\ 340)$, $2^8 \equiv 256 \ (\bmod\ 340)$, $2^{16} \equiv 65536 \equiv 256 \ (\bmod\ 340)$임을 안다. 마찬가지로 $2^{256} \equiv 2^{128} \equiv 2^{64} \equiv 2^{32} \equiv 256 \ (\bmod\ 340)$이다.
따라서 $2^{341} \equiv 32 \ (\bmod\ 340)$이다.
Compute $2^{341} \ (\bmod\ 340)$ by using the 2-digit expression.
Note that $341 = 101010101_{(2)}$.
We know that $2 \equiv 2 \ (\bmod\ 340)$, $2^2 \equiv 4 \ (\bmod\ 340)$, $2^4 \equiv 16 \ (\bmod\ 340)$, $2^8 \equiv 256 \ (\bmod\ 340)$, $2^{16} \equiv 65536 \equiv 256 \ (\bmod\ 340)$. Similarly $2^{256} \equiv 2^{128} \equiv 2^{64} \equiv 2^{32} \equiv 256 \ (\bmod\ 340)$.
Therefore $2^{341} \equiv 32 \ (\bmod\ 340)$.
알고리즘을 단계별로 적용하여 $2^{341} \ (\bmod\ 340)$을 계산하라.
Compute $2^{341} \ (\bmod\ 340)$ by the algorithm step by step.
1.5 The inverse of an integer modulo n · 법 n에 대한 정수의 역원
$3 \times 7 \equiv 1 \ (\bmod\ 5)$임에 유의하라. 그러면 3은 법 5에 대한 7의 곱셈 역원처럼 보인다.
Note that $3 \times 7 \equiv 1 \ (\bmod\ 5)$. Then 3 looks like a multiplicative inverse of $7 \bmod 5$.
$a \in \mathbb{Z}$에 대하여 $ab \equiv 1 \ (\bmod\ n)$을 만족하는 $b \in \mathbb{Z}$가 존재하면, $b$를 법 $n$에 대한 $a$의 역원이라 하고 $a^{-1}(\bmod\ n)$으로 나타낸다.
For $a \in \mathbb{Z}$, if $b \in \mathbb{Z}$ satisfies $ab \equiv 1 \ (\bmod\ n)$, then $b$ is called the inverse of $a$ modulo $n$, denoted by $a^{-1}(\bmod\ n)$.
1. $3 \cdot 4 \equiv 1 \ (\bmod\ 11)$임에 유의하라. 그러면 3은 법 11에 대한 4의 역원이다.
2. $5 \cdot 5 \equiv 1 \ (\bmod\ 12)$임에 유의하라. 그러면 5는 법 12에 대한 5의 역원이다.
3. 법 10에 대한 2의 역원이 되는 $x \in \mathbb{Z}$가 존재한다고 하자. 그러면
그런데 $2x - 1$은 홀수이므로 이는 불가능하다. 따라서 2는 법 10에 대한 역원을 갖지 않는다.
1. Note that $3 \cdot 4 \equiv 1 \ (\bmod\ 11)$. Then 3 is inverse of $4 \ (\bmod\ 11)$.
2. Note that $5 \cdot 5 \equiv 1 \ (\bmod\ 12)$. Then 5 is inverse of $5 \ (\bmod\ 12)$.
3. Suppose that there exists $x \in \mathbb{Z}$ such that a inverse of 2 mod 10. Then
However $2x - 1$ is odd and so it is impossible. Therefore 2 has no inverse mod 10.
$n$을 고정하자. 어떤 정수 $a$가 가역인가?
Let’s fix $n$. Which integer $a$ is invertible?
$a, b, n \in \mathbb{Z}$에 대하여 $a \equiv b \ (\bmod\ n)$이면 $\gcd(a, n) = \gcd(b, n)$이다.
$a \equiv b \ (\bmod\ n)$이라 가정하자. 그러면 $n|(a - b)$이다. 따라서 어떤 $q \in \mathbb{Z}$에 대하여 $a - b = nq$이다. 그러므로 $\gcd(b, n)|nq + b = a$이고 $\gcd(a, n)|a - nq = b$이다. $\gcd(b, n)|n$이고 $\gcd(a, n)|n$임을 안다. 실제로 $a, b, m \in \mathbb{Z}$에 대하여 $m|a$이고 $m|b$이면 $m|\gcd(a, b)$이다. 따라서 $\gcd(b, n)|\gcd(a, n)$이고 $\gcd(a, n)|\gcd(b, n)$이다. $A, B \in \mathbb{Z}_{>0}$이고 $A|B$이며 $B|A$이면 $A = B$임에 유의하라. 따라서 $\gcd(a, n) = \gcd(b, n)$이다.
For $a, b, n \in \mathbb{Z}$, if $a \equiv b \ (\bmod\ n)$, then $\gcd(a, n) = \gcd(b, n)$.
Assume that $a \equiv b \ (\bmod\ n)$. Then $n|(a - b)$. So $a - b = nq$ for some $q \in \mathbb{Z}$. Therefore $\gcd(b, n)|nq + b = a$ and $\gcd(a, n)|a - nq = b$. We know that $\gcd(b, n)|n$ and $\gcd(a, n)|n$. In fact, for $a, b, m \in \mathbb{Z}$, if $m|a$ and $m|b$, then $m|\gcd(a, b)$. Therefore $\gcd(b, n)|\gcd(a, n)$ and $\gcd(a, n)|\gcd(b, n)$. Note that if $A, B \in \mathbb{Z}_{>0}, A|B$, and $B|A$, then $A = B$. Therefore $\gcd(a, n) = \gcd(b, n)$.
$a, n \in \mathbb{Z}$에 대하여, 정수 $a$가 법 $n$에 대하여 가역일 필요충분조건은 $\gcd(n, a) = 1$인 것이다.
For $a, n \in \mathbb{Z}$, integer $a$ is an invertible $\bmod n$ if and only if $\gcd(n, a) = 1$.
$a, n \in \mathbb{Z}$에 대하여 $a$가 법 $n$에 대하여 가역이라 하자. $b \equiv a \ (\bmod\ n)$이면 $b$도 법 $n$에 대하여 가역이다.
$b \equiv a \ (\bmod\ n)$이므로 $\gcd(n, a) = \gcd(n, b)$임을 안다. $a$가 법 $n$에 대하여 가역이므로 $\gcd(a, n) = 1$이다. 따라서 $\gcd(b, n) = 1$이다. 그러므로 $b$는 법 $n$에 대하여 가역이다.
For $a, n \in \mathbb{Z}$, let $a$ be an invertible $\bmod n$. If $b \equiv a \ (\bmod\ n)$, then $b$ is an invertible $\bmod n$.
Since $b \equiv a \ (\bmod\ n)$, we know that $\gcd(n, a) = \gcd(n, b)$. Since $a$ invertible $\bmod n$, we have $\gcd(a, n) = 1$. Therefore $\gcd(b, n) = 1$. Finally, $b$ is invertible $\bmod n$.
$n \in \mathbb{Z}_{>0}$에 대하여, 법 $n$에 대한 $a$의 가역성은 $a \ (\bmod\ n)$에 의해 결정된다. $p$가 소수이면 $p \nmid a$인 모든 $a \in \mathbb{Z}$가 가역임에 유의하라.
For $n \in \mathbb{Z}_{>0}$, the invertible of $a$ modulo $n$ is associated with $a \ (\bmod\ n)$. Note that if $p$ is a prime, then every $a \in \mathbb{Z}$ such that $p \nmid a$ is invertible.
$1, 5, 7$, $11$이 법 12에 대하여 가역임을 안다. 따라서 $12k + 1, 12k + 5, 12k + 7$, $12k + 11$은 법 12에 대하여 가역이다.
We know that $1, 5, 7$, and 11 is invertible $\bmod 12$. Therefore $12k + 1, 12k + 5, 12k + 7$, and $12k + 11$ are invertible $\bmod 12$.
$n \in \mathbb{Z}_{>0}$, $n \ge 2$이고 $a \in \mathbb{Z}$라 하자.
1. $a$가 법 $n$에 대한 역원을 가지면 그 역원은 법 $n$에 대하여 유일하다. 즉 $ab \equiv 1 \ (\bmod\ n)$이고 $ac \equiv 1 \ (\bmod\ n)$이면 $b \equiv c \ (\bmod\ n)$이다.
2. $a$가 법 $n$에 대하여 가역이면 $(a^{-1})^{-1} = a$이다.
1. $ab \equiv ac \equiv 1 \ (\bmod\ n)$이라 가정하자. 그러면 $ab - ac \equiv a(b - c) \equiv 0 \ (\bmod\ n)$이다. 그러므로 $n|a(b - c)$이다. $\gcd(n, a) = 1$이므로 $n|b - c$이다. 따라서 $b \equiv c \ (\bmod\ n)$이다.
2. $a \cdot a^{-1} \equiv 1 \ (\bmod\ n)$이므로 $a$는 $a^{-1}$의 역원이다. 따라서 $(a^{-1})^{-1} = a$이다.
Let $n \in \mathbb{Z}_{>0}$, $n \ge 2$, and $a \in \mathbb{Z}$.
1. If $a$ has an inverse modulo $n$, then its inverse is unique modulo $n$. In other words, if $ab \equiv 1 \ (\bmod\ n)$ and $ac \equiv 1 \ (\bmod\ n)$, then $b \equiv c \ (\bmod\ n)$.
2. $(a^{-1})^{-1} = a$ if $a$ is an invertible $\bmod n$.
1. Assume that $ab \equiv ac \equiv 1 \ (\bmod\ n)$. Then $ab - ac \equiv a(b - c) \equiv 0 \ (\bmod\ n)$. And so $n|a(b - c)$. Since $\gcd(n, a) = 1$, $n|b - c$. Therefore $b \equiv c \ (\bmod\ n)$.
2. Since $a \cdot a^{-1} \equiv 1 \ (\bmod\ n)$, $a$ is inverse of $a^{-1}$. Therefore $(a^{-1})^{-1} = a$.
입력 : $\gcd(a, n) = 1$을 만족하는 0이 아닌 정수 $a, n$
출력 : $a^{-1}(\bmod\ n)$
유클리드 호제법으로 $ax + ny = 1$을 만족하는 $x, y \in \mathbb{Z}$를 구한다. 그러면 $a^{-1} \equiv x \ (\bmod\ n)$이다.
Input : nonzero integers $a, n$ such that $\gcd(a, n) = 1$
Output : $a^{-1}(\bmod\ n)$
Find $x, y \in \mathbb{Z}$ such that $ax + ny = 1$ by Euclidean algorithm. Then $a^{-1} \equiv x \ (\bmod\ n)$.
$0 \le a \le 19$ 중 법 20에 대하여 가역인 수를 모두 구하라.
정리 1.29에 의해 $a$가 법 20에 대하여 가역일 필요충분조건은 $\gcd(a, 20) = 1$인 것이다. $20 = 2^2 \cdot 5$이므로 $\gcd(a, 20) = 1$은 $a$가 $2$의 배수도 $5$의 배수도 아님과 같다. $0 \le a \le 19$ 중 이를 만족하는 수를 모두 나열하면
이고, 이 $8$개의 수가 법 20에 대하여 가역인 수 전부이다.
Which numbers $0 \le a \le 19$ are invertible modulo 20?
By Theorem 1.29, $a$ is invertible modulo 20 if and only if $\gcd(a, 20) = 1$. Since $20 = 2^2 \cdot 5$, $\gcd(a, 20) = 1$ is equivalent to $a$ being a multiple of neither $2$ nor $5$. Listing all such $a$ with $0 \le a \le 19$,
and these $8$ numbers are exactly the numbers invertible modulo 20.
$a$가 법 $n$에 대하여 가역이면 그 역원이 유일함을 증명하라.
$a$의 역원이 법 $n$에 대하여 유일함을 보이면 된다. $b, c \in \mathbb{Z}$가 모두 $a$의 역원, 즉
이라 하자. 그러면 $ab \equiv ac \ (\bmod\ n)$이므로 $a(b - c) \equiv 0 \ (\bmod\ n)$, 즉 $n \mid a(b - c)$이다. $a$가 법 $n$에 대하여 가역이므로 정리 1.29에 의해 $\gcd(a, n) = 1$이다. $n \mid a(b - c)$이고 $\gcd(a, n) = 1$이므로 $n \mid (b - c)$이다. 따라서 $b \equiv c \ (\bmod\ n)$이다. 즉 $a$의 역원을 만족하는 정수는 법 $n$에 대하여 모두 서로 합동이므로, $a$의 역원은 법 $n$에 대하여 유일하다. (이는 정리 1.32 (1)의 내용이기도 하다.)
Prove that if $a$ is invertible modulo $n$, then its inverse is unique.
We must show that the inverse of $a$ is unique modulo $n$. Suppose $b, c \in \mathbb{Z}$ are both inverses of $a$, that is,
Then $ab \equiv ac \ (\bmod\ n)$, so $a(b - c) \equiv 0 \ (\bmod\ n)$, i.e. $n \mid a(b - c)$. Since $a$ is invertible modulo $n$, Theorem 1.29 gives $\gcd(a, n) = 1$. As $n \mid a(b - c)$ and $\gcd(a, n) = 1$, we get $n \mid (b - c)$. Hence $b \equiv c \ (\bmod\ n)$. That is, any two integers satisfying the inverse condition for $a$ are congruent modulo $n$, so the inverse of $a$ is unique modulo $n$. (This is also the content of Theorem 1.32 (1).)
$a$가 법 $n$에 대하여 가역일 필요충분조건은 $\gcd(\text{“}\boxed{\ (A)\ }\text{”}) = \boxed{\ (B)\ }$이다. (A)와 (B)를 채워라.
정리 1.29(가역일 필요충분조건은 $\gcd(n, a) = 1$인 것)에 의해 $(A) = a, n$, $(B) = 1$이다. 즉 완성된 명제는 "$a$가 법 $n$에 대하여 가역일 필요충분조건은 $\gcd(a, n) = 1$인 것이다."이다.
$a$ is invertible modulo $n$ if and only if $\gcd(\text{“}\boxed{\ (A)\ }\text{”}) = \boxed{\ (B)\ }$. Fill the $(A)$ and $(B)$.
By Theorem 1.29 ($a$ is invertible if and only if $\gcd(n, a) = 1$), $(A) = a, n$ and $(B) = 1$. That is, the completed statement reads: “$a$ is invertible modulo $n$ if and only if $\gcd(a, n) = 1$.”
유클리드 호제법으로 $14^{-1} \ (\bmod\ 23)$을 구하라.
법 $n$ 역원 알고리즘에 따라, 유클리드 호제법으로 $14x + 23y = 1$을 만족하는 $x, y \in \mathbb{Z}$를 구하면 $14^{-1} \equiv x \ (\bmod\ 23)$이다. $23, 14$에 유클리드 호제법을 적용하면
이므로 $\gcd(14, 23) = 1$이다. 후진대입하면
이므로 $1 = 5 \cdot 14 - 3 \cdot 23$, 즉 $14 \cdot 5 \equiv 1 \ (\bmod\ 23)$이다. 따라서
이다.
By the Euclidean algorithm, find $14^{-1} \ (\bmod\ 23)$.
By the Inverse mod $n$ Algorithm, finding $x, y \in \mathbb{Z}$ with $14x + 23y = 1$ by the Euclidean algorithm gives $14^{-1} \equiv x \ (\bmod\ 23)$. Applying the Euclidean algorithm to $23, 14$,
so $\gcd(14, 23) = 1$. Back-substituting,
so $1 = 5 \cdot 14 - 3 \cdot 23$, that is $14 \cdot 5 \equiv 1 \ (\bmod\ 23)$. Therefore