Największy wspólny dzielnik

MatrixirtaM · Post autor: **MatrixirtaM** » 12 lut 2017, o 19:55

Suma pewnych czterdziestu dziewięciu (49) liczb dodatnich, całkowitych wynosi 999. Jaki może być największy możliwy wspólny dzielnik tych liczb?

kerajs · Post autor: **kerajs** » 12 lut 2017, o 22:20

Postawię na \(\displaystyle{ NWD=9}\).
Tak jest np: dla trzynastu 27 i trzydziestu sześciu 18.
\(\displaystyle{ NWD (27,...,27,18,......................,18)=9}\)

MatrixirtaM · Post autor: **MatrixirtaM** » 13 lut 2017, o 19:27

Ale jakoś trzeba to udowodnić, że to właśnie 9. I jak do tego dojść :/

kerajs · Post autor: **kerajs** » 13 lut 2017, o 21:40

Rozkładając liczbę \(\displaystyle{ 999}\) na sumę liczb dodatnich to przynajmniej jeden ze składników sumy musi być nieparzysty. Ergo, \(\displaystyle{ NWD}\) nie może być liczbą parzystą.
Ponieważ \(\displaystyle{ 999:49<21}\) to potencjalnymi \(\displaystyle{ NWD}\) mogą być tylko \(\displaystyle{ 1,3,5,7,9,11,13,15,17}\) lub \(\displaystyle{ 19}\).
Zauważ, że liczbą będącą \(\displaystyle{ NWD}\) będzie składnik sumy i/lub składnik sumy musi ją zawierać w rozkładzie na czynniki pierwsze. Oznacza to, że \(\displaystyle{ NWD}\) można wyciągnąć z sumy przed nawias, więc jest on dzielnikiem liczby \(\displaystyle{ 999=3^3 \cdot 37}\)
Największą z liczb spełniających powyższe jest \(\displaystyle{ 9}\). Pozostaje jeszcze tylko sprawdzić czy \(\displaystyle{ 999}\) można rozłożyć na \(\displaystyle{ 49}\) składników podzielnych przez \(\displaystyle{ 9}\). Jest to np: \(\displaystyle{ 567}\) i czterdzieści osiem liczb \(\displaystyle{ 9}\).