素敵な問題

問題13458(友人問)

正の整数a,b,cが次の4つの条件を満たすとする：

(1) a,b,c　の最大公約数は1である

(2) a,b+c　の最大公約数は1より大きい

(3) b,c+a　の最大公約数は1より大きい

(4) c,a+b　の最大公約数は1より大きい

このとき、a+b+cのとりうる最小の値を求めよ。

解答

・わたしの…

2*3, 3*5, 7*7 なら題意を満たす…^^;

so…

6+15+49=70

かいなぁ…^^;;

ずいぶん考えた結果…^^;;;

↑

やっぱ、理屈で考えなきゃダメだわ ^^; Orz…

↓

・鍵コメT様からのもの Orz～

例えば{2,3,25}も条件を満たしますね．

aとb+cの最大公約数，bとa+cの最大公約数，cとa+bの最大公約数を
順にg1,g2,g3とする．
条件(2),(3),(4)より，g1,g2,g3はいずれも1より大きい．…[1]
ここで，g1とg2が共通素因数pを持つと仮定すると，
a,b+c,bはすべてpの倍数だから，c=(b+c)-bもpの倍数となり，
a,b,cは共通素因数pを持つことになり，条件(1)に反する．
同様に考えて，g1,g2,g3はどの2つも共通素因数を持たない．…[2]

a+b+c=a+(b+c)はg1の倍数であり，同様にg2,g3の倍数でもあることがわかり，
[1],[2]から，a+b+cは少なくとも3種類の素因数を持つ．
これより，a+b+cは30より小さくはなり得ず，実例{2,3,25}から，
求める最小値は30.

なお，30を与える実例は，他に
{3,5,22},{4,5,21},{5,9,16}
があります．

既視感があったのですが，問題8547でした．

https://blogs.yahoo.co.jp/crazy_tombo/49833347.html#49833789 参照

*[2]が肝でした☆

具体的に見つけるのって難しいものねぇ ^^;

鍵コメT様はいとも簡単にいくつも見つけられてますが…もはやAI並みね ^^☆