Упражнение 31.

a) Решите (в целых числах) уравнение -1=4X+Y;

b) Разделите с остатком -8 на 3.

c) Заполните таблицу и нанесите полученные значения на целочисленную координатную декартову плоскость:

Мы видим, что графиком этой функции является «пила» - через четыре деления значения функции повторяются (такие функции называются периодическими). Если провести параллельные оси 0Х прямые на высоте 1, 2,или 3 то их точки пересечения с графиком будут расположены на расстоянии 4 друг от друга. Теперь объясним, почему в уравнении a=bX+Y

оба целых числа Х и Y определяются однозначно. Рассмотри для примера b=5. Отметим на прямой все числа кратные 5:

Тогда число а попадёт на один из отрезков (длиной в 4 деления), на которые числа, кратные пяти разбивают целочисленную прямую. Расстояние (число делений) от а до ближайшего кратного пяти числа (до левой границы отрезка) не превышает общей длины отрезка минус 1, потому, что если а попадёт на правую границу, то оно само кратно 5 и тогда с=0. Левая граница – тоже кратное 5 число и поэтому имеет вид 5b при некотором b. Таким образом, 5Х – это наибольшее кратное 5, не превосходящее а (или само а, или ближайшее к нему слева от него).

Формальное доказательство описывает эти факт: то, что вся прямая разбивается на непересекающиеся участки по пять чисел в каждом. Вот оно:

пусть a=bX+Y и в то же время a=bZ+W. Тогда вычтем из первого равенства второе и получим

0=bX+Y-bZ-W. Отсюда b(X-Z)=W-Y. Если W-Y <0, то умножим это равенство на -1:

b(X-Z)=Y-W. Слева у нас стоит число, кратное b, а справа число меньше, чем b (так как 0£Y<b, 0£W<b и 0£Y-W). Этого, разумеется, не может быть, если только W-Y¹0 – среди чисел 0, 1, 2, …,b-1 только 0 делится на b. Но Но W-Y=0 означает, что W=Z и тогда b(X-Z)=0, а, значит, и X-Z=0 , т.е. и X=Z.

Введём теперь на Z бинарное отношение R: а~b, если оба дают один и тот же остаток при делении на 5. Записывают это так: aºb(mod5). Читают эту запись так: «а сравнимо с b по модулю пяти». Конечно, пятёрка служит только для иллюстрации, её можно заменить любым другим целым числом.