って, 容器 A, B を何回使っても5dL だけの水を採取できないものは
(b) と (c) のみ ( ③ )
(4) Nを1以上 89 以下の自然数とする。
方程式 90x by = N が負でない整数解 x, yをもつとき, 90dLの容器Aと
bdL の容器Bを使って NdLだけの水を採取できる。
N=1のとき, 方程式 90x-by=1 が整数解x=k', y=l' をもつとする。
' と'のうち少なくとも一方が負の数ならば, 適当な整数をそれぞれ加える
ことにより,負でない整数解 x=k, y=l にすることができる。
このとき
90k-bl=1
両辺にNを掛けると 90× Nk-bx NI=N
よって、方程式 90x - by = N は負でない整数解x=Nk, y=Nをもつ。
方程式 90x-by=1 が整数解をもつ条件は90とbが互いに素であることであ
るから,このような自然数の値の個数は89以下の90と互いに素な自然数
の個数に一致する。('①)
90=2×32×5 であるから,90と互いに素である自然数は2の倍数でも3の倍
数でも5の倍数でもない自然数である。
よって, 90 と互いに素な自然数で89 以下のものは
したがって
1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47,49, 53,59,61,67,71,73,77, 79,83,89
タチ24 個
の 24個
k'
を
