$n = 18$ を法とする合同のもとで、位数（order）が 6 となるような $a$ ($0 < a < 18$) はいくつあるかを求める問題です。

1. 問題の内容

$n = 18$ を法とする合同のもとで、位数（order）が 6 となるような $a$ ($0 < a < 18$) はいくつあるかを求める問題です。

2. 解き方の手順

法 $n$ に関する $a$ の位数とは、

$a^k \equiv 1 \pmod{n}$

となる最小の正の整数 $k$ のことです。

今回の問題では、$n = 18$ であり、位数 $k = 6$ となる $a$ を探します。

つまり、$a^6 \equiv 1 \pmod{18}$ となる最小の $k$ が 6 となる $a$ を探します。

まず、$18 = 2 \times 3^2$ であることに注目します。

$a^6 \equiv 1 \pmod{18}$ ということは、

$a^6 \equiv 1 \pmod{2}$

$a^6 \equiv 1 \pmod{9}$

が同時に成り立つということです。

$a^6 \equiv 1 \pmod{2}$ より、$a$ は奇数でなければなりません。($a$が偶数なら、$a^6$ も偶数となり、1と合同になりません。）

$a$ が奇数であるとき、$a = 1, 3, 5, 7, 9, 11, 13, 15, 17$ のいずれかです。

$a^6 \equiv 1 \pmod{9}$

となるものを探します。

$\phi(9) = 9(1 - \frac{1}{3}) = 9 \times \frac{2}{3} = 6$

ここで、$a$ の位数が 6 であるということは、$a^k \not\equiv 1 \pmod{9}$ ($k = 1, 2, 3$) である必要があります。

$1 \le a \le 8$ で、$a$ が 9 と互いに素なものについて、$a$ の位数を調べます。

$a = 1, 2, 4, 5, 7, 8$

$a \equiv 1 \pmod{9}$ のとき、位数は 1

$a \equiv 2 \pmod{9}$ のとき、

$2^1 \equiv 2 \pmod{9}$

$2^2 \equiv 4 \pmod{9}$

$2^3 \equiv 8 \pmod{9}$

$2^4 \equiv 16 \equiv 7 \pmod{9}$

$2^5 \equiv 14 \equiv 5 \pmod{9}$

$2^6 \equiv 10 \equiv 1 \pmod{9}$

したがって、2 の位数は 6

$a \equiv 4 \pmod{9}$ のとき、$4 \equiv 2^2$ なので、

$4^3 \equiv (2^2)^3 \equiv 2^6 \equiv 1 \pmod{9}$

したがって、4 の位数は 3

$a \equiv 5 \pmod{9}$ のとき、$5 \equiv -4$ なので、位数も 6

$5^1 \equiv 5 \pmod{9}$

$5^2 \equiv 25 \equiv 7 \pmod{9}$

$5^3 \equiv 35 \equiv 8 \pmod{9}$

$5^4 \equiv 40 \equiv 4 \pmod{9}$

$5^5 \equiv 20 \equiv 2 \pmod{9}$

$5^6 \equiv 10 \equiv 1 \pmod{9}$

したがって、5 の位数は 6

$a \equiv 7 \pmod{9}$ のとき、$7 \equiv -2$ なので、$7^6 \equiv (-2)^6 \equiv 2^6 \equiv 1 \pmod{9}$

$7^2 \equiv 49 \equiv 4 \pmod{9}$

$7^3 \equiv 28 \equiv 1 \pmod{9}$

したがって、7 の位数は 3

$a \equiv 8 \pmod{9}$ のとき、$8 \equiv -1$ なので、$8^2 \equiv 1 \pmod{9}$

したがって、8 の位数は 2

$0 < a < 18$ で $a \equiv 2 \pmod{9}$ となるものは $2, 11$

$0 < a < 18$ で $a \equiv 5 \pmod{9}$ となるものは $5, 14$

$a$ は奇数なので、$2, 5, 11, 14$ のうち、$5$ と $11$ が候補。

$a = 5$ のとき、$5^1 \equiv 5 \pmod{18}$, $5^2 \equiv 25 \equiv 7 \pmod{18}$, $5^3 \equiv 35 \equiv -1 \pmod{18}$, $5^6 \equiv 1 \pmod{18}$なので位数6

$a = 11$ のとき、$11^1 \equiv 11 \pmod{18}$, $11^2 \equiv 121 \equiv 13 \pmod{18}$, $11^3 \equiv 143 \equiv -1 \pmod{18}$, $11^6 \equiv 1 \pmod{18}$なので位数6

3. 最終的な答え

2つ