Укажите наименьшее количество единиц записи числа 11 ... 1, если известно что оно делится на 41

Задачу можно решить несколькими способами.

Вычисление остатка числа при делении на 41

Увеличим количество единиц в искомом числе x до тех пор, пока не получим число, кратное 41:

x = 1, не делится на 41; x = 11, не делится на 41; x = 111 = 2 * 41 + 29, не делится на 41; x = 1111 = 27 * 41 + 4, не делится на 41; x = 11111 = 271 * 41, делится на 41.

Следовательно, наименьшее количество единиц в числе x равно 5.

Использование понятия сравнимости чисел

Если разность чисел m и n делится без остатков на целое число k, то такие числа называются сравнимыми по модулю k. Для сравнимости двух чисел используется специальное обозначение:

m ≡ n (mod k). (1)

Сравнение (1) читается так: число m сравнимо с числом n по модулю k.

Если обе части верного сравнения (1) умножить на одно и то же целое число a или возводить в одну и ту же натуральную степень p, то получим верное сравнение:

a * m ≡ a * n (mod k);

m^p ≡ n^p (mod k).

Исходя из этих понятий, будем искать такое значение p, при котором

10^p ≡ 1 (mod 41). (2)

Последовательно умножим обе части сравнений на 10, пока не достигнем значения p, для которого верно сравнение (2):

10^1 ≡ 10 (mod 41); 10^2 ≡ 10 * 10 ≡ 100 ≡ 100 - 2 * 41 ≡ 18 (mod 41); 10^3 ≡ 10 * 18 ≡ 180 ≡ 180 - 4 * 41 ≡ 16 (mod 41); 10^4 ≡ 10 * 16 ≡ 160 ≡ 160 - 3 * 41 ≡ 37 (mod 41); 10^5 ≡ 10 * 37 ≡ 370 ≡ 370 - 9 * 41 ≡ 1 (mod 41).

Следовательно, для значения p = 5 получили желаемый результат:

10^5 ≡ 1 (mod 41).

Что же это нам дает? Эта запись означает, что значение выражения 10^5 - 1 делится на 41. Действительно:

10^5 - 1 = 100 000 - 1 = 99 999 = 9 * 11 111 = 9 * 41 * 271.

Получили такой же результат, как и при предыдущем способе - наименьшее количество единиц в искомом числе равно 5.

Заметим, что в данном примере первый способ решения задачи более легкий; но если вдруг количество единиц оказалось бы достаточно большим числом, то второй способ, безусловно, стал бы более эффективным.

Ответ: 5 единиц.

Число 41 является простым числом. Хорошо изучены признаки делимости на это число. В частности, известно, что 11111 кратно числу 41. Это один из признаков делимости на 41.

Задача сформулирована так, что не сложно решить её методом перебора.

1) 11 - число слишком мало;

2) 111 - не является кратным, делится на 41 с остатком. 111 = 2 * 41 + 29;

3) 1111 - не является кратным, делится на 41 с остатком. 1111 = 27 * 41 + 4;

4) 11111 кратно числу 41. Это наименьшее из таких чисел. 11111 = 271 * 41.