задачи_про_катеньку - Найдите наименьшее возможное значение суммы выбранных Катей чисел

ab простое, одна из цифр чётна, другая нечётна => a чётнa, b нечётна. Сумма квадратов не равна 4k+3 => b=1 mod 4. Не подходит b=1 (21 не простое), b=5 (очевидно), остаётся b=9, то есть 89=8^2+5^2 с суммой 8+5=13.

Здесь не рассмотрены случаи более чем 2-значных чисел типа ...21, ...89, но там суммы явно больше.

@falcao, большое спасибо! Более чем 2-значные числа рассматривать действительно не нужно. Основная идея задачи в том, что простое число, образованное последними двумя цифрами, может быть только числом 89. Следовательно, Катя не могла выбрать ни одно из чисел 1, 2, 3, 4, 6, 7 (проверяется по арифмосту). Таким образом, наименьшее число, которое могла выбрать Катя, это число 5, а второе наименьшее — 8. Так как $%5^2+5^2=50$% не подходит, остаётся $%5^2+8^2=89$%, то есть, сумма равна 13 и является наименьшей из возможных. По-моему, неплохая задача.

@Казвертеночка: мне, честно говоря, не очень понравилось. Там сразу ясно, что 89 на конце, а для простого числа представление в виде суммы квадратов единственно. Но этим фактом пользоваться нельзя, и при оформлении решения требуется скучное расписывание.

@falcao, Вы пишете: "...для простого числа представление в виде суммы квадратов единственно". Откуда это следует?

@Казвертеночка: это называется "теорема Ферма о сумме квадратов". Проще всего она доказывается из соображений единственности разложения на множители в кольце целых гауссовых чисел.