【数学A】例題4.2.2：文字式におけるユークリッドの互除法（One More）★★★

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.2：文字式におけるユークリッドの互除法（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) $5n+1$と$4n+3$の最大公約数が11になるような60以下の自然数$n$をすべて求めよ．

(2) $8n-1$と$7n$が互いに素になるような100以下の自然数$n$は全部でいくつあるか．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.2の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1)

\begin{align*}
&5n+1=(4n+3)\times 1+n-2\\
&4n+3=(n-2)\times 4+11
\end{align*}

ここで，$5n+1$と$4n+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{align*}
&8n-1=7n\times 1+n-1\\
&7n=(n-1)\times 7+7
\end{align*}

$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：文字式におけるユークリッドの互除法（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) $6n+1$と$5n+3$の最大公約数が13になるような70以下の自然数$n$をすべて求めよ．

(2) $7n+4$と$3n+1$が互いに素になるような120以下の自然数$n$は全部でいくつあるか．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.2の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1)

\begin{align*}
&6n+1=(5n+3)\times 1+(n-2)\\
&5n+3=(n-2)\times 5+13
\end{align*}

ここで，$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{align*}
&7n+4=(3n+1)\times 2+(n+2)\\
&3n+1=(n+2)\times 3-5
\end{align*}

$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{個})$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.2の側注：文字式におけるユークリッドの互除法（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
余りが11となり，定数項になる．

% 側注2
$n$は60以下の自然数であることから，$n-2$の値の範囲を定める．

% 側注3
余りが7となり，定数項になる．

% 側注4
7の倍数となるとき（互いに素ではないとき）の個数を求め，全体の100個から引くことを考える．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.2の側注：文字式におけるユークリッドの互除法（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
余りが13となり，定数項になる．

% 側注2
$n$は70以下の自然数であることから，$n-2$の値の範囲を定める．

% 側注3
余りが5となり，定数項になる．

% 側注4
$a=bq-r$のときも，$a$と$b$の最大公約数は$b$と$r$の最大公約数と等しいことを利用する．

% 側注5
5の倍数となるとき（互いに素ではないとき）の個数を求め，全体の120個から引くことを考える．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.2の考え方・補足など：文字式におけるユークリッドの互除法（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ユークリッドの互除法を，文字式について利用することを考える．また，等式$a=bq+r$を満たす整数$a,b,q,r$について，$a$と$b$の最大公約数は$b$と$r$の最大公約数に等しいことを利用する．