整数の性質の問題

整数 $a,b,k$ について「$a$ と $b$ の最大公約数は、$a-kb$ と $b$ の最大公約数に等しい」という性質（ユークリッドの互除法の原理）を繰り返し使う。最大公約数は符号を無視して考える。

$$5n+1-(3n+4)=2n-3$$
より、$5n+1$ と $3n+4$ の最大公約数は、$3n+4$ と $2n-3$ の最大公約数に等しい。

$$3n+4-(2n-3)=n+7$$
より、これは $2n-3$ と $n+7$ の最大公約数に等しい。

$$2n-3-2(n+7)=-17$$
より、これは $n+7$ と $17$ の最大公約数に等しい。

したがって、$3n+4$ と $5n+1$ の最大公約数は $n+7$ と $17$ の最大公約数に等しい。$17$ は素数であるから、この値は $1$ か $17$ である。よって、最大公約数が $1$ より大きくなるのは、最大公約数が $17$ のとき、すなわち $n+7$ が $17$ の倍数のときである。

$n+7=17m$（$m$ は整数）とおくと $n=17m-7$ となる。$m$ を $k+1$ に置き換えて $n=17k+10$（$k$ は整数）と表す。

$1\leqq 17k+10\leqq 100$ より $-\frac{9}{17}\leqq k\leqq \frac{90}{17}=5.29\cdots$ であるから、$k=0,1,2,3,4,5$ となる。このとき
$$n=10,27,44,61,78,95$$
である。

確認として $n=10$ のとき、$3n+4=34=17\cdot 2$、$5n+1=51=17\cdot 3$ となり、最大公約数は $17$ である。

よって、求める個数は $6$ 個である。

$d=\gcd (3n+4,5n+1)$ とおく。$5(3n+4)-3(5n+1)=17$ より $d$ は $17$ の約数である。$17$ は素数なので $d=1$ または $d=17$ となる。

よって $d>1$ となるのは $d=17$ のとき、すなわち $17\mid 3n+4$ かつ $17\mid 5n+1$ のときである。

$17\mid 3n+4$ とする。$3n\equiv -4\equiv 13(\mathrm{mod}17)$ である。$3$ の逆元は $6$（$3\cdot 6=18\equiv 1$）なので、$n\equiv 78\equiv 10(\mathrm{mod}17)$ となる。

このとき $5n+1\equiv 51\equiv 0(\mathrm{mod}17)$ なので、$17\mid 5n+1$ も成り立つ。したがって条件は $n\equiv 10(\mathrm{mod}17)$ と同値である。

$1\le n\le 100$ でこれを満たすのは $n=10,27,44,61,78,95$ の $6$ 個である。次の候補 $112$ は範囲外。

検算：$n=10$ のとき $3n+4=34$、$5n+1=51$ で、最大公約数は $17$ である。