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

Число 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.

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

Вычисление остатка числа при делении на 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 единиц.