Какие остатаки могут получится при дробленьи квадрата натурального числа на 6

   1. Представим естественное число n в виде:

• n = 6k + r, где
• k - приватное при разделеньи числа n на 6;
• r = 0, 1, 2, 3, 4, 5 - остаток от этого деления.

   2. Возведем n в квадрат и найдем вероятные остатки:

      N = n^2 = (6k + r)^2 = 36k^2 + 12kr + r^2 = 12k(3k + r) + r^2. (1)

   3. В правой доли равенства (1) 1-ое слагаемое делится на 6, значит, остаток зависит только от r^2. Осмотрим все случаи:

• 0^2 mod 6 = 0 mod 6 = 0;
• 1^2 mod 6 = 1 mod 6 = 1;
• 2^2 mod 6 = 4 mod 6 = 4;
• 3^2 mod 6 = 9 mod 6 = 3;
• 4^2 mod 6 = 16 mod 6 = 4;
• 5^2 mod 6 = 25 mod 6 = 1.

   Вероятные остатки: 0; 1; 3; 4.