Решаването на уравнения в цели числа, платформа съдържание

решения на уравнения в цели числа, е един от най-старите математически проблеми.

Алгебрично уравнение с цели коефициенти, които имат повече от един непознат, когато задачата е да го намерите изцяло или рационално решение нарича неопределен или Diophantine, от името на гръцкия математик Diophantus, който е учил на проблема за решаване на тези уравнения. Според някои съобщения Diophantus живее до 364 години преди новата ера. д. Знаем само един вид биография на Diophantus, който според легендата е изсечен върху надгробната му плоча, а е задача-пъзел: "Бог му даде да бъде момче-шеста от живота; добавяне към този дванадесетия си част, покри бузите му с надолу; след седмия ден от го запали светлината на брака и пет години след сключването на брака му даде син. Уви! Нещастният късно детето решителни мерки от половината на живота на баща си, той беше пометен безмилостен съдба. Четири години по-късно, утешавайки скръбта му сполетява науката на номера, той [Diofant] приключи живота си. "

Целта на тази статия, за да обмислите някои методи за решаване на Diophantine уравнения. Много от тези методи включват използването на някои от понятията и алгоритмите за теория делимост във връзка с това, ние ги спомням.

Определяне 1.Naibolshim общ делител (ГРУ) на цели числа А1, А2, ..., един се нарича тази своя положителен общ делител, който се дели на всеки друг общ делител на тези номера.

Теорема 2. Ако, след което съществуват числа х и у, така че равенството притежава.

Забележка. Това уравнение се нарича линейна комбинация или линейното представяне на GCD чрез тези номера.

Определяне 3.Chisla а и б се наричат ​​взаимно прости, ако НОД на числата е равен на 1.

Теорема 4. (теорема на разделяне с остатък) За всяко цяло число като цяло и има само числа р и г, така че.

Забележка. Ако р е наречен частични коефициенти и R - остатъка от деление на от б. По-специално, ако. и след това се разделя на.

От теорема 4 следва, че за определен число m> 0 и всяко цяло число може да се изрази в един от следните видове:

Освен това, ако ще имаме, ако

На следващата теорема базиран метод за намиране на най-голям общ делител на числата.

Теорема 5.Pust а и б - две числа, 0 и след това.

Този метод се нарича алгоритъм на Евклид. Проблемът за намиране на НОД на номера А и В е намален до по-прост проблем за намиране на НОД на б а г. , Ако г = 0. нещо. Ако, обаче, аргументите се повтарят, като се започне от б а г. Резултатът е верига от равенства:

Получават намаляваща последователност на положителни числа

който не може да бъде безкраен. Следователно, не е остатък от нула: нека. Чрез теорема 10 от (**) следва, че.

1. Решението на неопределени уравнения от първа степен в две променливи в числа

Помислете два метода за решаване на Diophantine уравнения от първа степен в две променливи.

Алгоритъмът на този метод, помислете примера на решаването на конкретен уравнение. Стъпките на алгоритъма трябва да се прилагат при разглеждането такова уравнение в курсив.

Пример 1.Reshit уравнение в числа 5х + 8у = 39.

1. Нека неизвестното, като най-малката съотношението (в този случай, х) и да го изразят чрез друг неизвестен. ,

2. Маркирайте цялата страна. , Ясно е, че х е цяло число, ако проявата ще бъде едно цяло, което, от своя страна, ще се проведе, когато броят на 4 - 3y да се раздели с 5.

3. Ние въведе допълнително число peremennuyuz следва: 4 -3y = 5Z. В резултат на това, ние получаваме уравнение от същия тип като оригинала, но с по-малко коефициенти.

4. решаване вече в променливата у, мотивите както в претенция 1, 2 .. Отбелязването цялата част, получаваме:

5. Спор, както и преди, ще се въведе нов peremennuyuu. 3U = 1 - 2Z.

6. експресират неизвестното с най-ниското съотношение. В този случай, променливата Z. =. Изискване за да бъде цяло число, получаваме: 1 - ф = 2V. където U = 1 - 2V. Фракциите не повече са спускането е завършена (процесът продължава да Измервателен докато експресията на следващото променлива ще остане фракции).

7. Сега трябва да "издигне". Ние изрази първите проходни променливата Z об. тогава Y и тогава X:

8. Формула х = 3 + 8V и у = 3 - 5V. където V - произволно число, представлява общ разтвор на оригиналния уравнението в числа.

Забележка. По този начин, методът за спускане включва първи последователна експресия на единичен вариабилен чрез друг, докато в представителството на променливата ще остане фракции и след това последователно "катерене" нагоре по веригата на уравнения за общия разтвор.

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

Теорема 1.1.Esli в уравнението, уравнението е при, поне един разтвор.

2.2.Esli теорема в уравнението, и не се дели на, а след това цялото уравнение все още няма решения.

3.3.Esli теорема в уравнението, и това е еквивалентно на уравнението, където.

4.4.Esli теорема в уравнението, тогава всички интегрални разтвори на това уравнение са затворени във формулите:

където x0, Y0 - неразделна разтвор на уравнението - всяко цяло число.

Както е отбелязано по-горе, формулиран теоремата ни позволи да се направят следните алгоритми разтвори в числа на формата на уравнението.

1. Намерете най-голям общ делител на номера А и Б

и ако не се дели на, а след това цялото уравнение все още няма решения;

2. Разделете уравнение termwise нататък, докато получава уравнение, в което.

3. Виж разтвор число (x0, y0) от уравнение 1 като представяне на линейна комбинация от числа и;

4. Създаване обща формула целочислени разтвори на уравнението

където x0, Y0 - неразделна разтвор на уравнението - всяко цяло число.

Пример 2.Reshit уравнение в числа 407h - 2816y = 33.

Ние използваме алгоритъм състои.

1. Използване на евклидовата алгоритъм, ние откриваме най-голям общ делител на 407 и 2816:

2816 = 407 + 374 · 6;

= 11 · 33 3. Следователно (407.2816) = 11, и 33, разделени от 11

2. Разделете двете страни на първоначалното уравнение 11, ние получаваме уравнението 37Н - 256y = 3, и (37, 256) = 1

3. Използване на Euclidean алгоритъм намери линейна представяне на числата от 1 до 37 и 256.

Експресна един от последните уравнение, след това последователно се веригата на равенства ще експресират 3; 34 и получените изрази, ние замести изразът за 1.

1 = 34 - 3 х 11 = 34 - (37 - 34 · 1) · 11 = 34 · 12-37 · 11 = (256 - 37 · 6) · 12-37 · 11 =

- 83 · 37 - · 256 (-12). По този начин, 37 + (- 83) - 256 + (-12) = 1, следователно двойката числа = x0 - Y0 = 83 и - 12 е разтвор на 37Н - 256y = 3.

4. Запис на общата формула решенията оригинален уравнение

където Т - е всяко цяло число.

Забележка. Ние можем да докажем, че ако двойката (x1, y1) - неразделна решението на уравнението, където, след което всички цялостни решения на това уравнение се изчислява по формулата :.

2. Методи за решаване на някои нелинейни уравнения Diophantine

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

Метод за факторинг

Оригиналният уравнението чрез групиране на условия и да направи общи фактори за формата, когато от лявата страна на уравнението е продукт на факторите, съдържащи неизвестно, както и правото е число. Ние считаме, че всички делителите на числото от дясната страна на уравнението. Проведено изследване, в което всеки фактор от дясната страна на уравнението е равна на съответната делителя на застанал от дясната страна на уравнението.

Пример 3.To решава уравнение в число chislahy3 - x3 = 91.

Решение. 1) Използване Инициали формула умножаване на десния разградими factorizations:

2) Добави всички делители на 91: ± 1; ± 7; ± 13; ± 91

3) провеждане на изследвания. Имайте предвид, че за всякакви цели числа х и у редица

следователно, двете кофактори в лявата страна на уравнението трябва да бъдат положителни. След това уравнение (1) комплект от уравнения е еквивалентен на:

4), определена система, ние получаваме първата система има разтвори (5, 6), (-6, -5); трета (-3, 4), (- 4; 3); второ и четвърто число решения не са.

A: Уравнението (1) има четири разтвори (5; 6); (-6, -5); (-3, 4); (-4, 3).

Пример 4.Reshit в числа уравнение х + у = XY.

Решение. 1) Трансфер на всички членове на уравнението на ляво и от двете страни на полученото уравнение добавя (1): х + у - XY - 1 = - 1

Група първият - на четвърто, а вторият - трети ред и извадете често срещаните фактори, в резултат получаваме уравнението: (х - 1) (Y - 1) = 1

2) Продуктът от две числа може да бъде равно на 1, ако и само ако и двете от тези номера са равни на 1 или (-1).

3) Писане съответната система от уравнения и решаването им за получаване на горното уравнение. A: (0,0) и (2,2).

Пример 5.Dokazat че уравнение (х - у) 3 + (Y - Z) 3 + (Z - х) 3 = 30 все още няма решения в числа.

Решение. 1) разлагане на лявата страна на уравнение и факторинг разделение двете страни на уравнение 3, като в резултат се получи уравнението:

2) броят на делител 10 са ± 1, ± 2, ± 5, ± 10. Забележете също, че сумата от факторите лявата страна на уравнение (2) е равен на 0. Лесно е да се провери, че сумата от всеки три от множеството брой разделители 10, до получаване на продукта 10 няма да бъде равно на 0. Следователно, първоначалното уравнение не е решим в числа.

остатъци метод за изпитване

Този метод се основава на изследване на възможните останки от лявата и дясната страна на уравнение чрез разделяне на фиксирана положително цяло число.

Помислете за примерите, които разкриват същността на този метод.

Пример 6.Reshit в числа уравнение х2 + 1 = 3Y.

Решение. 1) Имайте предвид, че дясната страна на уравнение 3 е разделен на произволно число у.

2) се изследва кои остатъци могат да имат, когато разделена на три лявата страна на това уравнение.

Чрез теорема разделяне с остатък на число х или разделена на три или когато е разделен от три до получаване на остатък, 1 или 2.

Ако X = 3k. дясната страна на уравнението 3 не се разделя.

Ако X = 3k + 1, тогава х 2 + 1 = (3k + 1) 2 + 1 = 2 трим следователно отново лявата част не се дели на три.

Ако X = 3k + 2, тогава х 2 + 1 = (3k + 2) 2 + 1 = трим 2, следователно в този случай от лявата страна на уравнението не се дели на три.

Така че ние имаме, че при никакви числа х лявата страна на уравнението не се дели на 3, независимо от факта, че от лявата страна на уравнението е разделена на три за всяка стойност на променливата у. Следователно уравнението в числа все още няма решения.

Пример 7.Reshit изцяло chislahx³ - 3y³ - 9z³ = 0.

Решение. 1) Очевидно е, че решението на уравнение ще бъде три числа (0, 0, 0).

2) Разберете, ако уравнението има и други решения. За да направите това, ние се превърне в уравнението на формата

От дясната страна на това уравнение се дели на 3, в ляво разделена на три затова длъжен, като 3 - просто число х се дели на 3, т.е. х = 3k ... заменен с този израз в уравнението (3): 27k 3 = 3Y ³ + 9z ³, където

следователно, у ³ неделими от 3 и у = 3 м. Заместването на този израз в уравнение (4): 9k 3 = 27метър ³ + 3Z ³, където

От друга страна, от това уравнение следва, че Z3 е разделена на три, и Z = 3N. Замествайки този израз в (5), откриваме, че к 3, трябва да се дели на три.

Така че, се оказа, че броят на задоволяване на оригиналния уравнението са кратни на три, и колко пъти не сме ги разделя на 3 отново трябва да произвежда кратни на три. Само число отговарят на това условие ще бъде нула, т.е., решението на това уравнение е (0, 0, 0) .. Той е уникален.

Контрол задача №1

M.9.1.1. След като решила проблема, най-напред се поставя на статията, за да се определи колко години Diophantus живял.

M.9.1.2. Решаване на уравнението в числа

M.9.1.3. Намери ми рожден ден, ако сумата от цифрите са равни на произведението от датата на раждане на 12-те стаи и месец на раждане е 31 380.

M.9.1.4. Парче тел дължина от 102 см трябва да се нарязва на парчета с дължина 15 см и 12 см, така че се използва цялата проводник. Как да го направя?

M.9.1.5. Решаване на уравнението в числа

M.9.1.6. Докаже, че уравнението х 2 - Y 2 = 30 все още няма решения в числа.

1. Bashmakova, стъклопакети Diophantus и Diophantine уравнения. - М. Science 1972.

4. Babinski, IL Задачи математически олимпиади. - М. 1975.

8. Sierpinski, W. От решаването на уравнения в цели числа. - М 1961.

9. Перелман, YI забавни алгебра. - М. Science, 1975.