Теореми за еквивалентни сравнения - Методи на теорията на сравненията
Теорема 1. Нека е дадено сравнение
Тогава важат следните твърдения:
- 1) Ако към двете части на сравнението (3.6) се добави полином, тогава ще се получи сравнение, еквивалентно на сравнение (3.6).
- 2) Ако и двете части на сравнението (3.6) се умножат по едно и също цяло число, взаимнопросто с модула, тогава получаваме сравнение, еквивалентно на сравнение (3.6).
- 3) Ако двете части на сравнението и модула се умножат по едно и също естествено число, тогава получаваме сравнение, еквивалентно на сравнение (3.6).
Доказателство. Нека класът остатъци модулира решението на конгруентност (3.6), т.е. за сравнение
е вярно сравнение, така че сравнението
където също е правилно. Следователно класът на остатъчния модул е решението на сравнението
Обратното също е вярно: ако решението на сравнението (3.9), тогава за , сравнението (3.8) е вярно и, следователно, сравнението (3.7) е вярно и следователно е решението на сравнението (3.6).
Следователно сравненията (3.6) и (3.9) са еквивалентни.
1) Нека класът на остатъците е решението на конгруенцията (3.6), тогава за, получаваме правилната конгруенция. Нека вземем цяло число, взаимнопросто с модула:. Умножете последния термин за сравнение по термин по, получаваме правилното сравнение:
оттук получаваме, че класът остатъци по модула на решението на конгруенцията
Обратно, ако класът остатъци по модул е решението на конгруенцията (3.11), тогава конгруентността (3.10) е вярна за; следователно конгруентността също ще бъде вярна:
(обърнете внимание, че , тъй като иначе би било: ). Следователно класът на остатъците по модул е решението на конгруентността (3.6).
Така сравненията (3.6) и (3.11), където, ще бъдат еквивалентни.
- 3) Нека класът остатъци по модул е решението на конгруентност (3.6), тогава конгруентността е вярна за, a,така че сравнението е вярно
- 4)
за всяко естествено число, така че класът на остатъците по модула на решението за сравнение
Обратно, ако класът на остатъците по модул е решението на конгруентност (3.13), тогава конгруентността (3.12) е вярна за, но тогава, чрез свойството на сравненията, конгруентността е вярна:, така че класът на остатъците по модул е решението на конгруентността (3.6). Следователно сравненията (3.6) и (3.13) са еквивалентни. Теоремата е доказана.
По-долу сравнението (3.6) може да бъде заменено с еквивалентно сравнение:
където теорема 1 е доказана.
Теорема 2. Нека са дадени сравнения, тогава сравненията са еквивалентни.
Доказателство. Умножете валидните сравнения термин по термин по някакво цяло число:
Нека добавим получените сравнения термин по термин, след което получаваме сравнението:
следователно получаваме това. Но тогава също. Следователно сравненията и са еквивалентни. Теорема 2 е доказана.
Обърнете внимание, че от доказаната теорема по-специално следва, че сравнението ще бъде заменено с еквивалентно, ако изхвърлим (или добавим) член с коефициенти, делими на модула.
3. 4 сравнения на модули с едно неизвестно
Преминавайки от сравнения на 1-ва степен към сравнения на по-високи степени, препоръчително е първо да разгледаме случая, когато модулът е просто число. В случая има редица много важни теореми, които най-общо казано не са верни за съставните модули. В същото време теорията на конгруенциите по модул a prime е основата, върху която се изгражда изследването на конгруенциите по модул a composite.
В цялата тази глава буквата ще обозначава модула, който е просто число.
Теорема 1. Ако, тогава сравнение
може да се замени с еквивалентно сравнение с коефициент с най-висок член, равен на единица.
Доказателство. Помислете за сравнение от 1-ва степен; защото това сравнениеима решение. Нека намерим число, което удовлетворява това сравнение, т.е. такова, че .
Тогава сравнението е еквивалентно на сравнението
и следователно сравнението
Пример 1. Заменете сравнението
еквивалентно сравнение с коефициента при най-висок член, равен на 1.
Решаваме сравнението и намираме. Даденото ни сравнение е еквивалентно на сравнението
Теорема 2. Ако и са полиноми с цели коефициенти, тогава сравненията по модул прости
Доказателство. Нека удовлетворява сравнението (3.15), т.е. тъй като за всяко според теоремата на Ферма, тогава
Използвайки същата теорема на Ферма, получаваме, че ако сравнението (3.16) удовлетворява, тогава и, следователно, сравненията (3.15) и (3.16) са еквивалентни.
Следващата теорема следва директно от тази теорема.
Теорема 3. Сравнение по модул на просто число, чиято степен е по-голяма или равна на този модул, може да бъде заменено с еквивалентно сравнение на степен, по-малка от .
Доказателство. Нека полином с цели коефициенти на степен . Когато се раздели на), частното и остатъкът също ще бъдат полиноми с цели коефициенти:
където степента е по-малка от степента, т.е. по-малко от . Съгласно предходната теорема сравненията и са еквивалентни.
Пример 2. Заменете сравнението с еквивалентно сравнение със степен по-малка от 7.
Решение. Получаваме еквивалентно сравнение, ако заменим с , с , с . Така даденото сравнение е еквивалентно на сравнението
Теорема 4. Ако полиноми с цели коефициенти: и всички коефициенти се делят на просто число, тогава всяко решение за сравнение
е решение на поне едно от сравненията:
Доказателство. Нека решението на сравнението (3.17), т.е. тъй като всички коефициенти се делят на , ние също ще имаме , следователно
От съпоставимостпроизведение с нула по модул следва, че поне един от тези множители е конгруентен с нула по модул това, т.е. решение на поне една от конгруенциите (3.18).
Пример 3. При сравнение лявата страна може да бъде представена като и намираме всички решения на това сравнение чрез решаване на сравнения:, , т.е. Всички тези четири класа отговарят на нашето сравнение.
За съставните модули тази теорема не е вярна. Например сравняване
удовлетворява класа, който не е решение на нито едно от сравненията:
Теорема 5. Сравняването на степента по модул с коефициента при най-високия член, който не се дели на , може да има не повече от решения.
Доказателство. Твърдението на теоремата е вярно за . Наистина, в този случай имаме сравнение от 1-ва степен: където, т.е. и такова сравнение има точно едно решение. Нека сега приложим метода на пълната математическа индукция, за да докажем теоремата.
Да приемем, че твърдението на теоремата е вярно за всички полиноми () -та степен с водещи коефициенти, които не се делят на прост модул. Нека сега вземем произволен полином от та степен:
, където и разгледайте сравнението
Ако това сравнение няма решения, тогава броят на решенията е по-малък от .
Ако това сравнение има решения, тогава вземаме всяко число, което го удовлетворява, и го разделяме на . Според теоремата на Безу ще имаме: .
Коефициентите на полином от степен th могат да бъдат намерени с помощта на схемата на Horner и са цели числа, и .
Тъй като удовлетворява конгруенцията (3.19), , тогава всички решения на (3.19) са сред решенията на конгруенциите и , удовлетворяващи или едното от тях, или и двете.
Сравнението има едно решение и сравнението е сравнение на () - та мощност по модул с коефициента при най-високиячлен, който не се дели на , и по предположение може да има не повече от решения. Така сравнението (5) няма повече от, т.е. нищо повече от решения.
Съгласно принципа на математическата индукция се доказва валидността на теоремата.
Пример 4. удовлетворява сравнение Намерете всички решения на това сравнение.
Очевидно е, че заедно с класа това сравнение удовлетворява и класа . Коефициентът при най-високия член не се дели на прост модул, така че сравнението не може да има повече от две решения.
За съставните модули тази теорема не е вярна. Сравняването на степента по модул с коефициента на най-високия член, който не се дели на модула или дори взаимно прост на модула, може да има повече от решения. Например сравнението има 4 решения: .
Теорема 6. Ако сравнението на степента по модул има повече от решения, тогава всички сравнителни коефициенти се делят на .
Доказателство. Вземете произволно просто число. Ако сравнението има повече от едно решение, тогава, т.е. Следователно, за теоремата е вярна. Да приемем, че твърдението на теоремата е вярно за полиноми със степен по-малка от , т.е. да предположим, че броят на решенията за сравнение със степен по-малка от може да надвишава степента на сравнение само ако всички коефициенти се делят на модул.
Вземете всяко сравнение на степени:
има повече от решения. При такова сравнение той се разделя на и след това сравнението
еквивалентно на сравнение (3.20) също има повече от решения.
В сравнение (3.21), чиято степен е по-малка от , а броят на решенията надвишава степента според предположението, всички коефициенти трябва да се делят на , т.е. тъй като вече беше установено по-рано, че , твърдението на теоремата е вярно за . Съгласно принципа на математическата индукция се доказва валидността на теоремата.
Теорема 7. Нека полином с цели коефициенти и свободен член , където е просто число и . Сравнението има решения тогава и само ако всички коефициенти на остатъка след разделяне на са кратни на .
Доказателство. Нека, където и са полиноми с цели коефициенти и степента е по-малка от .
1) Нека докажем достатъчността на условието. Нека коефициентите се разделят на .
Означаваме с и съответно броя на решенията на конгруенции
Сравнението чрез теоремата на Ферма има решения. Всяко от тези решения е решение на поне едно от сравненията: (3.22) или (3.23), т.е.
Сравнението (3.23) на степен има коефициент при водещия член, равен на единица, така че, следователно,
Тъй като в този случай получаваме, т.е. от делимостта на коефициентите на следва, че броят на решенията на сравнението (3.22) е равен на .
2) Нека докажем необходимостта от условието. Нека съответствието (3.22) има решения. Ако решението за сравнение (3.22), тогава и в същото време, тъй като , тогава , и следователно, съгласно теоремата на Ферма, така че
Така всяко от решенията на сравнението (3.22) е решение на сравнението , чиято степен е по-малка от . Следователно всички коефициенти се делят на .
Пример 5. Класовете и удовлетворяват сравнението. Това сравнение има ли друго решение?
така и следователно това сравнение има три решения.
3.5 Модулопрости сравнения с множество неизвестни
Някои от теоремите, които разгледахме, могат лесно да бъдат обобщени в случай на сравнения с няколко неизвестни от формата:
където е полином с цели коефициенти, a е просто число.
Теорема 1. Ако от лявата страна на сравнението (3.24) някои от неизвестните се появяват като степен с показател , тогава сравнението (3.24) може да бъде заменено с еквивалентно сравнение, в което степента на всекина неизвестните не надвишава .
Доказателство. Сравнението (3.24) е еквивалентно на сравнението
където е произволен полином с цели коефициенти.
Ако сред условията има член на формата
където , тогава можем да вземем
заменете го с , тогава и т.н.
Ако къде, тогава в експонента за можете да отхвърлите и да получите еквивалентно сравнение, в което терминът ще бъде заменен с Чрез извършване на такива операции за всички термини по отношение на всяко от неизвестните, включени в индикатора, получаваме сравнение, еквивалентно на оригиналното, в което степента по отношение на всяко неизвестно няма да бъде повече от .
Теорема 2. Ако сравнението, чиято степен във всяко неизвестно е по-малко от , е изпълнено за всички цели числа, тогава всички коефициенти на полинома се делят на .
Доказателство. Нека проведем индукция върху броя на неизвестните. Когато твърдението на теоремата е вярно. Да приемем, че твърдението на теоремата е вярно за , и да вземем произволно идентично сравнение, чиято степен във всяко неизвестно е по-малка от . Ако най-големият показател на неизвестното е , тогава сравнението може да бъде представено като:
където всички са полиноми с цели коефициенти, чиято степен във всяко неизвестно е по-малка от . Ако вместо да заместим някакви цели числа, тогава получаваме идентично сравнение с неизвестна степен. Всички коефициенти на това сравнение: трябва да се делят на за всяка стойност. Тъй като според предположението за полиноми с аргументи твърдението на теоремата е вярно, всички коефициенти на тези полиноми, а оттам и полиномът, трябва да се делят на .
Според принципа на пълната математическа индукция твърдението на теоремата е вярно за произволен брой аргументи.