整数の性質の問題

1. 最大公約数を指数の最大公約数で表す

正の整数 $a,b$ の最大公約数を $\gcd (a,b)$ と書く。また $\gcd (a,0)=a$ とする。

$n>m$ のとき
$$2^n-1=2^{n-m}(2^m-1)+(2^{n-m}-1)$$
が成り立つ。ユークリッドの互除法の原理（$A=QB+R$ ならば $\gcd (A,B)=\gcd (B,R)$）より
$$\gcd (2^n-1,2^m-1)=\gcd (2^m-1,2^{n-m}-1)$$
となる。つまり、指数の組 $(n,m)$ を $(m,n-m)$ に置き換えても最大公約数は変わらない。

この置き換えは、指数 $m,n$ に対して「大きい方から小さい方を引く」という引き算型の互除法そのものである。指数の最大公約数は $\gcd (n,m)=\gcd (m,n-m)$ と保たれる。これを繰り返すと、指数の組はやがて $(d,0)$（$d=\gcd (m,n)$）になる。$2^0-1=0$ であるから
$$\gcd (2^m-1,2^n-1)=\gcd (2^d-1,0)=2^{\gcd (m,n)}-1.$$

2. 条件の言い換え

$2^d-1=15$ を解くと $2^d=16$ より $d=4$ である。したがって条件は
$$\gcd (m,n)=4$$
と同値である。

このとき $m=4a,n=4b$（$a,b$ は正の整数）と書ける。条件は $\gcd (a,b)=1$ となり、$1\leqq m<n\leqq 60$ は $1\leqq a<b\leqq 15$ となる。

3. 互いに素な組を数える

各 $b$ に対して、$1\leqq a<b$ かつ $\gcd (a,b)=1$ を満たす $a$ の個数は、$1$ 以上 $b$ 以下で $b$ と互いに素な整数の個数に等しい（$b\geqq 2$ では $a=b$ は互いに素でないため）。$b=2,3,\dots ,15$ について数えると次のようになる。

• $b=2$：$1$ の $1$ 個
• $b=3$：$1,2$ の $2$ 個
• $b=4$：$1,3$ の $2$ 個
• $b=5$：$1,2,3,4$ の $4$ 個
• $b=6$：$1,5$ の $2$ 個
• $b=7$：$1\sim 6$ の $6$ 個
• $b=8$：$1,3,5,7$ の $4$ 個
• $b=9$：$1,2,4,5,7,8$ の $6$ 個
• $b=10$：$1,3,7,9$ の $4$ 個
• $b=11$：$1\sim 10$ の $10$ 個
• $b=12$：$1,5,7,11$ の $4$ 個
• $b=13$：$1\sim 12$ の $12$ 個
• $b=14$：$1,3,5,9,11,13$ の $6$ 個
• $b=15$：$1,2,4,7,8,11,13,14$ の $8$ 個

なお $b=1$ のときは $a<1$ となる $a$ がないので $0$ 個である。

合計すると
$$1+2+2+4+2+6+4+6+4+10+4+12+6+8=71.$$

よって、求める組の個数は $71$ である。

一般に $\gcd (2^m-1,2^n-1)=2^{\gcd (m,n)}-1$ が成り立つ。これが $15=2^4-1$ に等しいので $\gcd (m,n)=4$ となる。

そこで $m=4a,n=4b$ とおくと、$1\le a<b\le 15$ かつ $\gcd (a,b)=1$ である。この組の個数を数える。

$b$ を固定したとき、$a<b$ で $b$ と互いに素な $a$ の個数は $\phi (b)$ である。よって求める個数は ${\sum }_{b=2}^{15}\phi (b)$ となる。

$\phi (2)=1,\phi (3)=2,\phi (4)=2,\phi (5)=4,\phi (6)=2,\phi (7)=6,\phi (8)=4,\phi (9)=6,\phi (10)=4,\phi (11)=10,\phi (12)=4,\phi (13)=12,\phi (14)=6,\phi (15)=8$

これらの和は $1+2+2+4+2+6+4+6+4+10+4+12+6+8=71$ である。

検算として、累積和を順に取ると $1,3,5,9,11,17,21,27,31,41,45,57,63,71$ となり、最後は $71$ で一致する。

よって答えは $71$ 個。