Головоломки недели

CHALLENGE

Ученики экспериментируют со всеми числами, которые можно получить, взяв любое число, кратное 4, и прибавив к нему любое число, кратное 7. Не зная об этом, они изучают так называемую теорему Безу. Эта теорема гласит, что все возможные комбинации чисел, кратных (как положительных, так и отрицательных) двум числам, составляют множество чисел, кратных наибольшему общему делителю этих двух чисел. Наибольший общий делитель чисел 4 и 7 равен 1, поэтому мы должны иметь возможность получить все возможные числа. Более того, существует бесконечное количество способов получить каждое из них.

Вот несколько примеров чисел от 1 до 12:

• 1 = 4 + 4 – 7 = 9 x 4 – 5 x 7 = 16 x 4 – 9 x 7
• 2 = 7 + 7 – 4 – 4 – 4 = 6 x 7 – 10 x 4 = 10 x 7 – 17 x 4
• 3 = 7 – 4 = 5 x 7 – 8 x 4 = 9 x 7 – 15 x 4
• 4 = 4 = 4 x 7 – 6 x 4 = 8 x 7 – 13 x 4
• 5 = 3 x 4 – 7
• 6 = 2 x 7 – 2 x 4
• 7 = 7
• 8 = 2 х 4
• 9 = 3 x 7 – 3 x 4
• 10 = 2 x 7 – 4
• 11 = 4 + 7
• 12 = 3 х 4

Как только вы найдете комбинацию, содержащую наибольший общий делитель, вы можете использовать ее для получения любого кратного этому наибольшему общему делителю. Для чисел 4 и 7 один из способов получить 1 — это 2 x 4 – 7. Мы можем получить любое другое число, например, 23, записав 23 = 23 (2 x 4 – 7) = 46 x 4 – 23 x 7. Как только мы получим одно решение для числа, мы можем получить все остальные решения, прибавив к нему 0 (я знаю, это звучит странно). Например, у нас есть 1 = 2 x 4 – 7 = (2 x 4 – 7) + (7 x 4 – 4 x 7) = 9 x 4 – 5 x 7). Мы можем добавить любое кратное (7 x 4 – 4 x 7), и это не изменит значение.

РАЗВЕДКА

Как упоминалось выше, в результате этого процесса будут получены все числа, кратные наибольшему общему делителю двух чисел. Если этот НОД равен 1, то будут получены все числа.

Возьмем, к примеру, 4 и 6. Их наибольший общий делитель равен 2. Любая комбинация чисел, кратных 4 и 6, всегда будет четной, поэтому невозможно получить все возможные числа. Это становится более очевидным, если рассматривать 4 и 6 как 2, умноженное на 2 и 3. Вы знаете, что суммы чисел, кратных 2 и 3, дадут все возможные числа, потому что они взаимно просты. Однако, если взять каждую из этих сумм чисел 4 и 6, то все они будут кратны 2, поэтому вы получите все числа, кратные 2!