Question

Найти сумму всех целых 0 ≤ k ≤ 11, для которых нет решения x²+y² ≡k mod 12 в целых (x, y).

Answer 1

Ответ:

21.

Объяснение:

Найдем, какие остатки бывают от деления квадрата целого числа на 12 (иными словами, с какими целыми числами от 0 до 11 могут быть сравнимы квадраты целых чисел). Чтобы упростить вычисления, заметим сначала, что достаточно найти остатки для квадратов любых шести подряд идущих целых чисел, так как если два числа отличаются на число, кратное 6, то их квадратиы сравнимы по модулю 12. В самом деле, если

               $a=b+6n\Rightarrow a^2=b^2+12n+36n^2\equiv b^2\ (\mod 12).$

Остановимся на такой шестерке чисел:

                                        $-2;\ -1;\ 0;\ 1;\ 2;\ 3.$

Из этой шестерки можно отбросить ещё минус 2 и минус 1, так как при возведении в квадрат минусы исчезают. Остается четыре числа

                                                  $0;\ 1;\ 2;\ 3.$

Вычисляем их квадраты:

                                                    $0;\ 1;\ 4;\ 9.$

Остается посмотреть, какие числа можно получить, складывая два числа, каждое из которых берется из этого списка,

$0+0=0;\ 0+1=1;\ 0+4=4;\ 0+9=9;\ 1+1=2;\ 1+4=5;\ 1+9=10;$

       $4+4=8;\ 4+9=13\equiv 1 \ (\mod 12);\ 9+9=18\equiv 6\ (\mod 12).$

Вывод: сумма двух квадратов целых чисел может быть сравнима (среди чисел от 0 до 11) только с 0, 1, 2, 4, 5, 6, 8, 9 и 10.

А условию задачи соответствуют числа, не попавшие в этот список - это   3, 7 и 11. Их сумма равна 21.