整数の性質の問題

1. 補題を示す。 正の整数 $a,b$ に対して
$$\gcd (2^a-1,2^b-1)=2^{\gcd (a,b)}-1$$
が成り立つ。

$a>b$ のとき
$$2^a-1=2^{a-b}(2^b-1)+(2^{a-b}-1)$$
である。互除法の原理（$A=QB+R$ ならば $\gcd (A,B)=\gcd (B,R)$）より
$$\gcd (2^a-1,2^b-1)=\gcd (2^{a-b}-1,2^b-1)$$
となる。つまり、指数の組 $(a,b)$ を $(a-b,b)$ に置き換えても最大公約数は変わらない。

これは指数どうしに引き算型のユークリッドの互除法を行っていることと同じである。この操作をくり返すと、指数の組は最終的に $(g,g)$（ただし $g=\gcd (a,b)$）になる。したがって
$$\gcd (2^a-1,2^b-1)=\gcd (2^g-1,2^g-1)=2^g-1$$
である。$a=b$ のときは明らかに成り立つ。

2. 条件を言い換える。 $4^m-1=2^{2m}-1$, $8^n-1=2^{3n}-1$ なので、補題より
$$\gcd (4^m-1,8^n-1)=2^{\gcd (2m,3n)}-1$$
である。$2^g-1$ は $g$ について単調に増加し、$2^6-1=63$ であるから、条件は
$$\gcd (2m,3n)=6$$
と同値である。

3. $m,n$ の形を決める。 $\gcd (2m,3n)=6$ ならば $3\mid 2m$ なので $3\mid m$ であり、$2\mid 3n$ なので $2\mid n$ である。そこで $m=3a$, $n=2b$（$a,b$ は正の整数）とおくと
$$\gcd (2m,3n)=\gcd (6a,6b)=6\gcd (a,b)$$
となる。よって条件は $\gcd (a,b)=1$ と同値である。

範囲は、$1\leqq 3a\leqq 20$ より $1\leqq a\leqq 6$、$1\leqq 2b\leqq 20$ より $1\leqq b\leqq 10$ である。

4. 互いに素な組を数える。 $a$ の値ごとに、$1\leqq b\leqq 10$ で $a$ と互いに素な $b$ の個数を数える。
- $a=1$：すべての $b$ で $10$ 個
- $a=2$：$b$ が奇数のとき $5$ 個
- $a=3$：$3$ の倍数 $3,6,9$ を除いて $7$ 個
- $a=4$：$b$ が奇数のとき $5$ 個
- $a=5$：$5,10$ を除いて $8$ 個
- $a=6$：$2$ でも $3$ でも割り切れない $b=1,5,7$ の $3$ 個

合計は $10+5+7+5+8+3=38$ である。

したがって、求める組の個数は $38$ である。

$\gcd (2^a-1,2^b-1)=2^{\gcd (a,b)}-1$ を用いる。$4^m-1=2^{2m}-1$、$8^n-1=2^{3n}-1$ なので、最大公約数は $2^{\gcd (2m,3n)}-1$ となる。これが $63=2^6-1$ に等しいのは $\gcd (2m,3n)=6$ のとき。

$6\mid 2m$ より $3\mid m$、$6\mid 3n$ より $2\mid n$ である。そこで $m=3a,n=2b$ とおくと、$1\le a\le 6$、$1\le b\le 10$ である。

このとき $\gcd (6a,6b)=6\gcd (a,b)$ なので、条件は $\gcd (a,b)=1$ となる。

各 $a$ について、条件を満たす $b$ の個数を数える。
- $a=1$: 10 個
- $a=2$: $b$ が奇数で 5 個
- $a=3$: $b$ が 3 の倍数でなく、$10-3=7$ 個
- $a=4$: $b$ が奇数で 5 個
- $a=5$: $b$ が 5 の倍数でなく、$10-2=8$ 個
- $a=6$: $b=1,5,7$ の 3 個

合計は $10+5+7+5+8+3=38$。

検算として $(m,n)=(3,2)$ を確かめる。$4^3-1=63$、$8^2-1=63$ なので最大公約数は 63 で、条件を満たす。