일차합동식·중국인의 나머지 정리·오일러 φ 함수·원시근Linear Congruences, the Chinese Remainder Theorem, Euler's φ Function and Primitive Roots

Since $\gcd(13, 80) = 1$, by Theorem 1.37, $13x \equiv 4 \ (\bmod\ 80)$ has a unique solution. First find $13^{-1} \ (\bmod\ 80)$ by the Euclidean algorithm.

Back-substituting,

so $13^{-1} \equiv 37 \ (\bmod\ 80)$ (check: $13 \times 37 = 481 = 6 \times 80 + 1$). Therefore

Check: $13 \times 68 = 884 = 11 \times 80 + 4$.

Since $\gcd(3, 18) = 3 \neq 1$, Theorem 1.37 does not apply (as in Remark 2, the solution need not be unique in this case). Since $18 \mid 3x$ if and only if $6 \mid x$, it suffices to find all multiples of $6$ with $0 \le x \lt 18$. So the solutions are

and there are three of them.

In both cases $m_1 = 3, m_2 = 5, m_3 = 7$, so by step 1 of the algorithm (ALGO, Chinese remainder theorem algorithm), $M = m_1m_2m_3 = 105$ and

In step 2, $N_i$ is the inverse of $M_i$ modulo $m_i$. Since $M_1 = 35 \equiv 2 \ (\bmod\ 3)$ and $2^{-1} \equiv 2 \ (\bmod\ 3)$, $N_1 = 2$. Since $M_2 = 21 \equiv 1 \ (\bmod\ 5)$, $N_2 = 1$. Since $M_3 = 15 \equiv 1 \ (\bmod\ 7)$, $N_3 = 1$.

1. Since $a_1 = 2, a_2 = 4, a_3 = 6$, by step 3

Check: $104 \equiv 2 \ (\bmod\ 3)$, $104 \equiv 4 \ (\bmod\ 5)$, $104 \equiv 6 \ (\bmod\ 7)$.

2. Since $a_1 = 2, a_2 = 4, a_3 = 2$,

Check: $44 \equiv 2 \ (\bmod\ 3)$, $44 \equiv 4 \ (\bmod\ 5)$, $44 \equiv 2 \ (\bmod\ 7)$.

Since $85 = 5 \times 17$, by the Chinese remainder theorem (Theorem 1.39), $x^2 + 1 \equiv 0 \ (\bmod\ 85)$ is equivalent to $x^2 \equiv -1 \ (\bmod\ 5)$ and $x^2 \equiv -1 \ (\bmod\ 17)$. Modulo 5, $2^2 = 4 \equiv -1$ and $3^2 = 9 \equiv 4 \equiv -1$, so $x \equiv 2, 3 \ (\bmod\ 5)$. Modulo 17, $4^2 = 16 \equiv -1$ and $13^2 = 169 = 170 - 1 \equiv -1$, so $x \equiv 4, 13 \ (\bmod\ 17)$.

Combine the four cases by the CRT algorithm. $M = 85, M_1 = 17, M_2 = 5$, and $N_1$ is the inverse of $17$ modulo $5$, $N_2$ is the inverse of $5$ modulo $17$. Since $17 \equiv 2 \ (\bmod\ 5)$ and $2 \times 3 \equiv 1 \ (\bmod\ 5)$, $N_1 = 3$. Since $5 \times 7 = 35 = 34 + 1 \equiv 1 \ (\bmod\ 17)$, $N_2 = 7$. So $x \equiv a_1 \cdot 3 \cdot 17 + a_2 \cdot 7 \cdot 5 \ (\bmod\ 85)$.

So the solutions are $x \equiv 13, 38, 47, 72 \ (\bmod\ 85)$. For example, $13^2 + 1 = 170 = 2 \times 85$ confirms this.

$2010 = 2 \times 3 \times 5 \times 67$, and $2, 3, 5, 67$ are all prime. By Theorem 1.48,

Let $m = n = 2$. By Theorem 1.46, $\phi(4) = \phi(2^2) = 2^1(2 - 1) = 2$, while $\phi(2)\phi(2) = 1 \times 1 = 1$, so

(The example $\phi(3)\phi(3) = 4 \neq 6 = \phi(9)$ from Remark 4 is of the same kind.) This is exactly why Theorem 1.47 requires the assumption $\gcd(m, n) = 1$: multiplicativity fails when $m$ and $n$ are not relatively prime.

The answer is $a = 3$.

Since $\phi(1) = 1$, $\phi(2) = 1$, $\phi(3) = 2$, both $1$ and $2$ occur as values of $\phi$. We now show that $\phi(n)$ is always even for $n \ge 3$.

Suppose $n$ is divisible by an odd prime $p$. Take $k \ge 1$ with $p^k \| n$. Since $\gcd(p^k, n/p^k) = 1$, by Theorem 1.47 and Theorem 1.46,

and since $p$ is odd, $p - 1$ is even. Hence $\phi(n)$ is even.

If $n$ has no odd prime factor, then $n = 2^k$, and since $n \ge 3$, $k \ge 2$. By Theorem 1.46, $\phi(n) = \phi(2^k) = 2^{k-1}(2 - 1) = 2^{k-1}$, and since $k - 1 \ge 1$, this is also even.

So $\phi(n)$ is even for every $n \ge 3$, hence no $n$ satisfies $\phi(n) = 3$. Since $1$ and $2$ both occur as values, the least positive integer that is not a value of $\phi$ is $a = 3$.

$524 = 2^2 \times 131$, and $131$ is prime (checking division by every prime $2, 3, 5, 7, 11$ up to $11$ confirms this). By Remark 3, the number of invertible $a$ $(1 \le a \le 524)$ modulo 524 equals $\phi(524)$. By Theorem 1.48,

So the number is $260$.

$7^2 = 49 \equiv 13 \ (\bmod\ 18)$ and $7^3 \equiv 13 \times 7 = 91 \equiv 1 \ (\bmod\ 18)$ (since $91 = 5 \times 18 + 1$). Since $7^1 = 7 \not\equiv 1$ and $7^2 = 13 \not\equiv 1$, the order of 7 modulo 18 is $3$. Since $\phi(18) = 6$ and $3 \mid 6$, this is consistent with Theorem 1.51.

We split into two cases according to whether $p \mid a$.

If $p \mid a$, then $a \equiv 0 \ (\bmod\ p)$, so $a^p \equiv 0 \equiv a \ (\bmod\ p)$.

If $p \nmid a$, then $\gcd(a, p) = 1$, so by the Fermat little theorem (Theorem 1.62), $a^{p-1} \equiv 1 \ (\bmod\ p)$; multiplying both sides by $a$ gives $a^p \equiv a \ (\bmod\ p)$.

$\phi(12) = 4$. The invertible elements modulo 12 are $1, 5, 7, 11$ (Example 1.31). Computing their orders,

so $5, 7, 11$ all have order $2$, and $1$ has order $1$. No element has order $\phi(12) = 4$, so there is no primitive root of mod 12. (This agrees with Theorem 1.60: $12 = 2^2 \times 3$ is not of the form $2, 4, p^k$ or $2p^k$ for any prime $p$ and positive integer $k$.)

$\phi(10) = 4$. The invertible elements modulo 10 are $1, 3, 7, 9$. Computing powers of 3,

so 3 has order 4. Computing powers of 7,

so 7 also has order 4. Meanwhile $9^2 = 81 \equiv 1 \ (\bmod\ 10)$, so 9 has order 2. Only 3 and 7 have order $\phi(10) = 4$, so the primitive roots of mod 10 are $\{3, 7\}$.

Since $\gcd(6, 11) = 1$, by the Fermat little theorem, $6^{10} \equiv 1 \ (\bmod\ 11)$. Since $10004 = 10 \times 1000 + 4$,

Since $6^2 = 36 \equiv 3 \ (\bmod\ 11)$, $6^4 = (6^2)^2 \equiv 3^2 = 9 \ (\bmod\ 11)$. Therefore

Since $\gcd(2, 13) = 1$, by the Fermat little theorem, $2^{12} \equiv 1 \ (\bmod\ 13)$. Since $10000 = 12 \times 833 + 4$,

So $2^{10000} \equiv 3 \ (\bmod\ 13)$.

Since $18 = 2 \times 3^2$, by Theorem 1.48, $\phi(18) = \phi(2)\phi(3^2) = 1 \times 6 = 6$. By Remark 3, this equals the number of invertible $a$ $(1 \le a \le 18)$ modulo 18. Indeed, the invertible elements are

(those relatively prime to 18, i.e. not multiples of 2 or 3), which are $6$ in total, matching $\phi(18) = 6$.