MathLabs

第4問

和が 19761976 となる正の整数の積として表される最大の数を、証明付きで求めよ。
ステップ 6/6: 33での剰余を使う
前のステップ次のステップ
ざっくり言うと

22で割った余り 33 により、22を0個や2個ではなく1個使うことが決まり、残りは最も効率的な因子である 33 に充てられる。

1976=3⋅658+2,f(S)=2⋅36581976=3\cdot658+2,\quad f(S)=2\cdot3^{658}
詳しい解説

1976=3⋅658+21976=3\cdot658+2 であり、22 の個数は高々2なので、22 の個数はちょうど1個でなければならない。2つの 22 は 4≡1(mod3)4\equiv1\pmod3 となる一方、1つなら 2(mod3)2\pmod3 となるからである。残りの和は 1974=3⋅6581974=3\cdot658 である。したがって最大化する多重集合は 22 を1個と 658658 個の 33 からなり、積は 2⋅3658\boxed{2\cdot3^{658}} である。