Сравнения

От теорията на числата е известна следната теорема: Ако а е произволно цяло число, b - естествено число, то съществуват единствени цели числа q и r такива, че са изпълнени условията:
            a = bq + r, където 0 ≤ r < b.

Цялото число q се нарича частно, а цялото число r - остатък от делението на a с b. Ако остатъкът r е равен на 0 казваме, че a се дели ( без остатък) на числото b.

Обикновено при деление на едно число с друго ние се интересуваме повече от частното при това делене, отколкото от остатъка. При редица въпроси и най-вече при въпросите, свързани с делимостта на целите числа, съществен е остатъкът, докато частното има второстепенно значение. На тази основа например разделяме целите числа на четни и нечетни (при деление с две целите числа дават остатък 0 или 1).

На същата основа по отношение на естественото число m ≥ 1 множеството на целите числа може да се "разбие" на m непресичащи се подмножества. За тази цел всяко подмножество се съставя точно от тия числа, които при деление с m дават един и същи остатък. Понеже при деление с m на едно число за остатък може да се получи точно едно от 0, 1, 2, ..., m-1, които са на брой m, ще се получат следните подмножества:
... -2m, -m, 0, m, 2m, ...             остатък 0
... -2m + 1, -m + 1, 1, m + 1, 2m + 1, ...         остатък 1
... -2m + 1, - + 2, 2, + 2, + 2, ...       остатък 2
... -2m + (m - 1), -m + (m - 1), + ( -1), ....       остатък m-1

Числото m, по отношение на което извършваме посоченото "разбиване" на Z, се нарича модул, а самите подмножества - класове по модул m. Ако две цели числа a и b са от един и същи клас по модул m, казваме, че са сравними по модул m, т.е. даваме следното определение:
0: За две цели числа a и b казваме, че са сравними по модул m (m N, m > 1) точно тогава, когато при деленето им на m дават равни остатъци.

Това се означава така: а ≡ b (mod m). Чете се "а сравнимо с b по модул m". Самият запис се нарича сравнение.

Примери:
      27 ≡ 7 (mod 5), защото 27 = 5.5 + 2 и 7 = 5.1 + 2;
      35 ≡ 18 (mod 17), защото 35 = 17.2 + 1 и 18 = 17.1 + 1;
      3 ≡ -8 (mod 11), защото 3 = 11.0 + 3 и -8 = 11.(-1) + 3;

Освен чрез даденото определение, проверката за сравнимост на две числа по определен модул, може да става, като се използва и следната теорема:

T1:
Необходимото и достатъчно условие числото а да е сравнимоп с числото b по модул m e разликата a-b да се дели на m.

Необходимост: Нека a ≡ b (mod m). Съгласно 0 а = mq₁ + r и b = mq² + r, където q₁ Z; q₂ Z; r Z и 0 ≤ r < m. тогава а - b ≡ m(q₁ + q₂), т.е. a-b се дели на m.

Достатъчност: Нека а-b се дели на m, т.е. a - b = mq, q Z. Aкo a = mq₁ + r, където q₁ Z, r Z и 0 ≤ r < m, то b = a - mq = m(q₁ - q) + r, т.е. числата a и b при делене на m ще имат раавни остатъци и съгласно даденото определение а ≡ b (mod m).

Проверката на верността на сравнения чрез тази теорема е действително по-удобна. Наистина, съгласно определението, за да проверим верността, например на сравнението 372 ≡ -253 (mod 25), се изисква и -253 = 25.(-11) + 22 и да сравним остатъците им. Чрез доказаната теорема е достатъчно да проверим, чедразликата 372 - (-253) = 625 се дели на 25.

1. а ≡ а (mod m) (рефлексивност)
Наистина, за всяко а, а - а = 0 и следователно m дели а - а. Тогава, съгласно Т1 а ≡ а (mod m).

2. Ако а ≡ b (mod m), то b ≡ a (mod m). (симетричност)
Наистина, съгласно Т1, m дели а-b, от което следва, че m дели b-a. Тогава, пак съгласно Т1, b ≡ a (mod m).

3. Aко а ≡ b (mod m) и b ≡ c (mod m), то а ≡ с (mod m). (транзитивност)
От Т1 следва, че m дели а-b и b-c. тогава m дели a - b + b - c = a - c. Пак съгласно Т1 а ≡ с (mod m).

Посочените три свойста показват, че е вярно твърдението:

T2:
Релацията "сравнимост" в множеството на целите числа е релация на еквивалентност.

Класовете на еквивалентност по отношение на тази релация са посочените по-горе подмножества на Z, които нарекохме "класове по модул m". Това означава, че в сравнението а ≡ b (mod m) можем да заменяме а и b с други числа от техния клас и ще получаваме верни сравнения.

4. Ако а ≡ b (mod m) и с ≡ d (mod m), то а ± c ≡ b ± d (mod m).
От условието и Т1 следва, че m дели а-b и c-d. Тогава m дели a-b ± (c - d), т.е. дели a ± c - (b ± d). Пак от Т1 следва, че а ± c ≡ b ± d (mod m).

Следствие: Ако а ≡ b (mod m) и c Z, то а ± с ≡ b ± с (mod m) .
Като приложим свойство 4 за сравненията а ≡ b (mod m) и с ≡ с (mod m), ще получим а ± с ≡ b ± с (mod m).

5. Ако а ≡ b (mod m) и c ≡ d (mod m), то аc ≡ bd (mod m).
От това, че m дели а-b и c-d следва, че m дели d(a - b) + a(c - d) или m дели ac - bd, т.е. аc ≡ bd (mod m).

Следствия:

a) aко а ≡ b (mod m) и с Z, то ас ≡ bс (mod m).
б) ако а ≡ b (mod m) и k N, то а^k ≡ b^k (mod m).
От свойства 4 и 5 имаме следствието:
Aко f(x) e произволен полином и а ≡ b (mod m), то f(а) ≡ f(b) (mod m).

Teoрията на сравенията ни дава възможност да решаваме някои математически задачи, при които използването на други свойства би довело до големи технически трудности. Това ще илюстрираме с няколко примера.

1. Намерете остатъка от делението на 2¹⁰¹ с 5.
Търсеният остатък ще бъде равен на най-малкото цяло неотрицателно число х, за което е вярно сравнението 2¹⁰¹ ≡ x (mod 5), т.е. той трябва да удовлетворява условията 2¹⁰¹ ≡ x (mod 5) и 0 ≤ x < 5.
Да потърсим остатъците от деленето на първите последователни степени на 2 (с естествен показател) на 5. Ще получим:
    2 = 5.0 + 2, т.е. 2 ≡ 2 (mod 5);
    2² = 5.0 + 4, т.е. 2² ≡ 4 (mod 5);
    2³ = 5.1 + 3, т.е. 2³ ≡ 3 (mod 5);
    2⁴ = 5.3 + 1, т.е. 2⁴ ≡ 1 (mod 5).
Съгласно следствие б) на свойство 5, от последното сравнение получаваме (2⁴)²⁵ ≡ 1²⁵ (mod 5), т.е. 2¹⁰⁰ ≡ 1 (mod 5). Като приложим следствие а) на същото свойство за числото 2, получаваме 2¹⁰⁰.2 ≡ 1.2 (mod 5) или 2¹⁰¹ ≡ 2 (mod 5). последното сравнение показва, че търсеният остатък е 2.

Да разгледаме сега последователните степени на числото 5 и остатъците от делението им с 5.

веднага се вижда, че пресметнатите остатъци периодично се повтарят. Наистина, след четирите остатъка 3, 4, 2, 1 отново в същия ред се повтарят същите остатъци.

Да подредим по същия начин степените на 2 и остатъците им от деленето на 48. Получаваме:
    2, 2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸, 2⁹, 2¹⁰, ...
    2, 4, 8, 16, 32, 16, 32, 16, 32, 16, ...
И при този пример остатъците се повтарят, но не от самото начало - първите три не се повтарят, а след това имаме периодично повторение на числата 16 и 32.

Естествено е да възникне предположението, че за кои да е естествени числа а и m остатъците от деленето на последователните степени на а - а, a², a³, a⁴, .... с m е от известно място нататък (може и от началото) се повтарят периодично. Доказва се, че това предположение е вярно.

Наистина да вземем първите m+1 степени на а - а, а², a³, ..., a^m+1 и да разгледаме техните остатъци про деленето им на m. Тъй като при него можем да получим само m остатъка (0, 1, 2, ...., m-1), а броят на степените е m+1, то сред разгледаните степени на а ще има поне две с равни остатъци (Принцип на Дирихле). Нека това са степените a^k и a^k+p (p > 0). Тогава а^k ≡ a^k+p (   ). Да приложим свойство 5 за това сравнение и сравнението а^n-k ≡ a^n-k (mod m) при n > k. Ще получим аⁿ ≡ a^n+p (mod m). Това означава, че започвайки от остатъка на а^k, остатъците периодично ще се повтарят или, което е все същото, започвайки от остатъка на а^k, ще следват p остатъка, които постоянно ще се повтарят.

Тези разсъждения показват още, че периодичността на остатъците започва от това място, от което за първи път се открива повторение на остатък. За да се получи такова повторение, е достатъчно да се разгледат остатъците на първите m+1 степени на а.
Особено лесно се открива периодът на повторение на остатъците, ако можем да намерим такъв показател р, че a^p ≡ 1 (mod m). Като умножим това сравнение със сравнението aⁿ ≡ aⁿ (mod m), получаваме а^n+p ≡ aⁿ (mod m). Този резултат показва, че от самото начало първите р остатъка периодично се повтарят. Посоченото свойство на остатъците на степените на едно число с естесвен показател при деленето им с естествено число m > 1, дава възможност за решаване на някои задачи и опростяването на други.

2. Намерете остатъка от деленето на числото 222⁵⁵⁵ със 7.
Тъй като 222 = 7.31 + 5, то 222 ≡ 5 (mod 7). Тогава 222⁵⁵⁵ ≡ 5⁵⁵⁵ (mod 7). Разглеждаме последователните остатъци от деленето на 5ⁿ (където n ≤ 8) със 7. Получаваме:
5 ≡ 5 (mod 7);       5² ≡ 4 (mod 7);       5³ ≡ 5².5 ≡ 5.4 ≡ 6 (mod 7);      
5⁴ ≡ (5²)² ≡ 4² ≡ 2 (mod 7);       5⁵ ≡ 5².5³ ≡ 4.6 ≡ 3 (mod 7);      
5⁶ ≡ 5.5⁵ ≡ 5.3 ≡ 1 (mod 7).
Тъй като 5⁶ ≡ 1 (mod 7), то остатъците на 5ⁿ при делене със 7 се повтарят периодично от началото с период 6. Но 555 ≡ 3 (mod 6). Тогава 5⁵⁵⁵ ≡ 5³ ≡ 6 (mod 7). От 222⁵⁵⁵ ≡ 5⁵⁵⁵ (mod 7) и 5⁵⁵⁵ ≡ 6(mod 7) => 222⁵⁵⁵ ≡ 6 (mod 7), т.е. търсеният остатък е 6.

3. Намерете последната цифра на 14¹⁴¹⁴.
С последната цифра на кое да е число се записва остатъкът от деленето му с 10, т.е. ако х е последната цифра на 14¹⁴¹⁴, то вярно е сравнението 14¹⁴¹⁴ ≡ x (mod 10), където 0 ≤ x ≤ 10.
Остатъците при деленето на първите три степени на 14 с 10 са 4, 6, 4. Това означава, че остатъците от деленето на 14ⁿ с 10 се повтарят периодично с период 2, като степените с нечетен показател "дават" остатък 4, а тези с четен - 6. Тъй като 14¹⁴ e произведение на четни множители, то 14¹⁴ e четно число. Тогава 14¹⁴¹⁴ ≡ 6(mod 10), т.е. последната цифра на 14¹⁴¹⁴ e 6.

1. Кои от следните сравнения са верни:
      a) 45 ≡ 10 (mod 7);       e) 28 ≡ -7 (mod 5);
      b) 28 ≡ 3 (mod 5);       f) 312 ≡ -3 (mod 5);
      c) 45 ≡ 10 (mod 7);       g) -3 ≡ 10 (mod 13);
      d) 256 ≡ 135 (mod 11);       h) -200 ≡ -25 (mod 9).

2. Проверете принадлежат ли на един и същи калс по модул р числа:
      a) 57; 257; p = 8;       d) -53; 2; p = 11;
      b) 12; 116; p = 13;       d) -5; 1; p = 3;
      c) 273; 88; p = 4;       d) -123; -487; p = 11.

Намерете най-малкото неотрицателно число х, което удовлетворява сравненията:
            a) x ≡ 27 (mod 13);
            b) 124 ≡ x (mod 11);
            c) x ≡ -9 (mod 13);
            d) x² ≡ 27² (mod 13);
            e) x¹⁰⁰ ≡ 27¹⁰⁰ (mod 13);
            f) x ≡ 27².(-9) (mod 13).

4. 1.I.1983г. е било в събота. В какъв ден на седмицата ще бъде 1.I.2000г.?

5. Тринадесетият рожден ден на Иван бе в понеделник на 17.I.1983г. В какъв ден на седмицата ще бъде двадесетият му рожден ден?

6. Да се пресметне остатъкът от деленето със 7 на числата:
            a) 7778 + 7779 + 7780 - 7777;
            b) 5723.248;
            c) 5723.248 - 3021.512;
            d) 556.36 - 558.251 + 2557.7856.

7. Намерете остатъка от деленето:
      a) (7¹⁰⁰ + 11¹⁰⁰):12;
      b) 6⁵⁰²:11;

8. Дели ли се числото 222⁵⁵⁵ + 555²²² на 7?

9. Докажете, че 10¹⁰ - 1 се дели на 100.

10. На каква цифра окончава числото 777⁷⁷⁷?