互いに素な数を数える

Euler 絡みで出てきた問題で遊んでみた話。

$0 < x < n,\; \gcd(n, x) = 1$ を満たす $x$ がいくつあるか、という問題はよく知られていて、初等整数論をやればこの話が必ず出てくるでしょう。この数は $\varphi(n)$ と表され、 $\varphi$ はオイラー関数とか totient function などと呼ばれます。

では、区間 $(0, n)$ を $d$ 等分して、 $in/d < x < (i+1)n/d,\; \gcd(n, x) = 1$ を満たすものは各 $i$ についていくつあるでしょうか、という話。

とりあえず記号として $U(n) = \{x \mid 0 < x < n,\; \gcd(n, x)\},\; U(n, d, i) = \{x \mid in/d < x < (i+1)n/d,\; \gcd(n, x) = 1\}$ と書くことにしておきます。問題は要するに $| U(n, d, i) |$ がいくつか、ということです。

二等分の場合

$d = 2$ の場合はすんなりと出てきます。例えば $n = 9$ なら

$U(9, 2, 0) = \{1, 2, 4\}$
$U(9, 2, 1) = \{5, 7, 8\}$

となって、両者の位数は等しくなります。 $n = 15$ なら

$U(15, 2, 0) = \{1, 2, 4, 7\}$
$U(15, 2, 1) = \{8, 11, 13, 14\}$

となり、やはり位数が一致しています。

一般に、 $| U(n, 2, 0) | = | U(n, 2, 1) |$ が成り立つことが証明できます。これは気付けば簡単なことで、 $f(x) = n - x$ とすると $f$ が $U(n, 2, 0)$ と $U(n, 2, 1)$ の間の全単射を与えることからわかります。

一方 $U(n)$ は $U(n, 2, 0), U(n, 2, 1)$ の disjoint sum なので、等式 $| U(n, 2, 0) | + | U(n, 2, 1) | = | U(n) |$ が成り立ちます。この式の右辺は $\varphi(n)$ なので、結果 $| U(n, 2, 0) | = | U(n, 2, 1) | = \varphi(n)/2$ となります。*1

$d>2$ の場合はまた今度。

*1:補足: n > 2 が必要です。見落としていました。