『３ℓと５ℓで８ℓ』の続き

前回の質問に関して。容量の値が互いに素である二つの容器を使えば１リットルの水を計り出すことができ、１リットル～二つの容器の合計容量以内の任意の整数ℓの水を計ることができるということですが、これは逆も言えるのでしょうか？つまり、容器の容量は分かっているが、互いに素であるかどうかわからないとき、１ℓの水を計れれば、二つの容器の容量は互いに素であると判定できる、ということでよいのでしょうね？分かり切ったことかもしれませんが、念のため。

No.5 回答者： mtrajcp 回答日時： 2023/12/22 11:17

整数a,bが互いに素である

ならば

整数a,bに対して
ax+by=1 となる整数x,yが存在する

逆に
整数a,bに対して
ax+by=1 となる整数x,yが存在する
ならば

整数a,bは互いに素である

例えば
整数
a=3,b=5
に対して

3*2-5=1
だから
x=2
y=-1
とすると
ax+by=3*2-5=1

a=3Lの水をx=2回、b=5Lのバケツに入れれば
a=3Lのバケツの水に
1L
余るから
1Lの水を計れる

No.4 回答者： ありものがたり 回答日時： 2023/12/19 18:43

Aℓ と Bℓ の容器を使って Cℓ の水が測れたとすれば、

C が A,B の最大公約数の倍数であることが判ります。
参考→ https://manabitimes.jp/math/674#2
C = 1 の場合は、A,B が互いに素だということになります。

No.3 回答者： 銀鱗 回答日時： 2023/12/19 17:37

＞１ℓの水を計れれば、二つの容器の容量は互いに素であると判定できる、ということでよいのでしょうね？

( ﾟДﾟ) そんなわけないぞ。

3ℓ、5ℓ、8ℓなら、
３ℓ容器に水を満タンに入れて、それを８ℓ容器に移す
３ℓ容器に水を満タンに入れて、それを８ℓ容器に移す
３ℓ容器に水を満タンに入れて、それを８ℓ容器にあふれる寸前まで移す
３ℓ容器に１ℓの水が残る。
ということで、
８ℓ容器の扱いはどうなる？

No.2 回答者： usa3usa 回答日時： 2023/12/19 17:34

「１ℓの水を計れる」とは、「二つの容器の容量の最大公約数が１」ということでは？

No.1 回答者： ぷらぐろまあ 回答日時： 2023/12/19 17:25

2リットルと1リットルの容器。