% 例題A4.2.2：文字式におけるユークリッドの互除法 （One More）★★★
(1)$5 n+1$と$4 n+3$の最大公約数が11になるような60以下の自然数$n$をすべて求めよ. (2)$8n-1$と$7n$が互いに素になるような100以下の自然数$n$は全部でいくつあるか.
% 解答（例題A4.2.2）
(1)$$\begin{aligned} & 5 n+1=(4 n+3)\times 1+n-2 \\ & 4 n+3=(n-2)\times 4+11 \end{aligned}$$ここで,$5 n+1$と$4 n+3$の最大公約数は,$n-2$と11の最大公約数に等しい.$n-2$と11の最大公約数が11となるのは,$n-2$が11の倍数のときである.$n$は60以下の自然数より,$1 \leqq n \leqq 60$したがって,$-1 \leqq n-2 \leqq 58$この範囲において,$n-2$が11の倍数となるのは,$0,11,22,33,44,55$よって,$n-2=0,11,22,33,44,55$より,$n=2,13,24,35,46,57$(2)$$\begin{aligned} & 8n-1=7n \times 1+n-1 \\ & 7n=(n-1)\times 7+7 \end{aligned}$$$8n-1$と$7n$が互いに素であるとき,$n-1$と7も互いに素であるから,求める個数は,$n-1$と7が互いに素であるような100以下の自然数$n$の個数に等しい.$n$は100以下の自然数より,$1 \leqq n \leqq 100$したがって,$0 \leqq n-1 \leqq 99$この範囲において,$n-1$が7の倍数となるのは,$$n-1=7 \times 0,7 \times 1,7 \times 2,\ldots,7 \times 13,7 \times 14$$より,15個 よって,求める個数は,$100-15=85(\text{個})$
% 問題A4.2.2
(1)$6n+1$と$5n+3$の最大公約数が13になるような70以下の自然数$n$をすべて求めよ. (2)$7n+4$と$3n+1$が互いに素になるような120以下の自然数$n$は全部でいくつあるか.
% 解答A4.2.2
(1)$$\begin{aligned} & 6n+1=(5n+3)\times 1+(n-2)\\ & 5n+3=(n-2)\times 5+13 \end{aligned}$$ここで,$6n+1$と$5n+3$の最大公約数は,$n-2$と13の最大公約数に等しい.$n-2$と13の最大公約数が13となるのは,$n-2$が13の倍数のときである.$n$は70以下の自然数より,$1 \leqq n \leqq 70$したがって,$-1 \leqq n-2 \leqq 68$この範囲において,$n-2$が13の倍数となるのは,$0,13,26,39,52,65$よって,$n-2=0,13,26,39,52,65$より,$n=2,15,28,41,54,67$(2)$$\begin{aligned} & 7n+4=(3n+1)\times 2+(n+2)\\ & 3n+1=(n+2)\times 3-5 \end{aligned}$$$7n+4$と$3n+1$が互いに素であるとき,$n+2$と5も互いに素であるから,求める個数は,$n+2$と5が互いに素であるような120以下の自然数$n$の個数に等しい.$n$は120以下の自然数より,$1 \leqq n \leqq 120$したがって,$3 \leqq n+2 \leqq 122$この範囲において,$n+2$が5の倍数となるのは,$$n+2=5 \times 1,5 \times 2,\ldots,5 \times 23,5 \times 24$$より,24個 よって,求める個数は,$120-24=96(\text{個})$
