Найдите наименьшее натуральное число n, при котором сумма 1+2+3+...+n делится на 64 с подробным объяснением

Предыдущий
вопрос Следующий
вопрос

Для того чтобы найти такое наименьшее число n, нужно рассмотреть сумму первых n натуральных чисел в формуле:

S(n) = n*(n+1)/2

Для суммы 1+2+3+...+n:

S(n) = n*(n+1)/2

Нужно найти такое наименьшее число n, при котором S(n) делится на 64. Поскольку 64 = 2^6, то S(n) должно делиться и на 2^6 = 64. Это возможно только если n*(n+1) делится на 128 (т.к. 2^6 = 64).

n*(n+1) должно делиться на 128, поэтому одно из чисел n или (n+1) должно содержать множитель 128, который является степенью 2. Проверим все числа, начиная с 8, умножая n и (n+1) и убеждаясь, что результат делится на 128.

89 = 72 (не делится на 128)
1617 = 272 (не делится на 128)
3233 = 1056 (не делится на 128)
6465 = 4160 (не делится на 128)
128*129 = 16512 (делится на 128)

Таким образом, наименьшее натуральное число n, при котором сумма 1+2+3+...+n делится на 64, является n = 128.