Тази статия е популяризирана в Menéame. Ако ви е харесало и искате да гласувате за него, влезте тук и го споменете.
Мотивация
Да предположим, че се сблъскваме със следния проблем:
Мъж отива в магазин за дрехи и купува 12 костюма, някои черни, а други сиви, за 1200 евро. Ако черните костюми са на стойност € 30 повече от сивите и сте купили възможно най-малко от последните, колко костюма сте купили от всеки цвят?
Нека го повдигнем:
Уравнението е:
Правейки математиката, имаме следното:
Ако си мислите, че ще имаме проста система от уравнения за решаване, грешите. Остава ни едно уравнение с две неизвестни. Липсват ли ни данни? Не. Можем да го разрешим. Добре дошли в прекрасния свят на Диофантови уравнения.
Диофантови уравнения
A диофантово уравнение е алгебрично уравнение, в което се появяват няколко променливи, чиито решения са цели числа. Тоест, решаването на диофантово уравнение се състои в определяне кои цели числа го удовлетворяват. Името му е взето от математика Диофант Александрийски, който, освен че беше един от първите, които използваха символиката в алгебрата, се посвети, наред с други неща, и на изучаването на тези уравнения
Диофантовите уравнения от горния тип се наричат Диофантови уравнения линейна. Този конкретен случай на този тип уравнения е този, който ще се научим да решаваме в тази статия. По-конкретно, ще покажем (и демонстрираме) метод за изчисляване на целочислените решения на уравнението
Наличие на решения
Първият резултат, който ще видим и демонстрираме, е свързан със съществуването на решения на тези уравнения. Да тръгнем с него:
Теорема:
Диофантово линейно уравнение на формата има цяло число решение тогава и само ако най-големият общ делител на y е делител на .
Също така, ако го наречем, имаме, че определено решение на споменатото уравнение може да се получи, както следва:
битие .
1. - Започваме с внушението отляво надясно:
има цяло число решение, тогава има такива, че
Както е общ делител на y, тогава y, с .
Тогава имаме следното:
Тоест имаме израз от типа, с всички тях цели числа. Следователно колкото те трябва да разделят a, като по този начин завършват тази част от доказателството.
2.- Сега отиваме с внушението отдясно наляво, получаваме като бонус добавката:
Да предположим, че сега е делител на. Тогава съществува такова, че. От друга страна, по теорема на Безу има такива, че. Умножаваме двата члена на това равенство по:
Къде да стигнем
С това, до което стигнахме до това и са решения на уравнение (1).
е решение на уравнение (1), което искахме да покажем.
Това, което постигнахме досега, е да знаем как да разпознаем кои линейни диофантови уравнения имат решения и да изчислим конкретно решение за тях. Но ние искаме общо решение, тоест всички решения на линейните диофантови уравнения, които могат да бъдат решени. Отиваме към това в следващата точка.
Общо решение на линейно диофантово уравнение
Ще докажем следната теорема:
Теорема:
Ако това е конкретно решение на уравнението
(1)
тогава всички целочислени решения от него са във формата:
(две)
с, битие .
Ако това е решение на уравнение (1), тогава е вярно, че. Но тогава изразите на (2) също са решение на това уравнение:
Тогава би било необходимо да се види, че всички решения на (1) са начина, по който описахме в (2). Да тръгваме:
Като се започне от предишното конкретно решение, да предположим, че имаме решение на линейното диофантово уравнение (1). След това имаме следните две уравнения:
Изваждаме двете уравнения, получавайки
Преминавайки втория, добавяйки другия член на равенството, до което стигаме
Сега разделяме на:
Тъй като и са относителни първични числа (тъй като като ги разделим на най-големия им общ делител, ние премахнахме факторите, които са били общи в началото), и разделяме a, трябва да е вярно, че разделя .
Това ни води до факта, че трябва да съществува така, че:
Откъдето получаваме, че трябва да е във формата:
Замествайки тази стойност на в уравнение (3), след няколко прости изчисления стигаме до израза, търсен за:
Практически пример
Да се върнем при нашия приятел в костюмите. Оставаме в следното линейно диофантово уравнение:
Да видим дали можем да намерим колко костюма от всеки цвят е купил този човек.
Тъй като е делител на нашето уравнение, той има решения. За да получим и трябва да използваме алгоритъма на Евклид за изчисляване на най-големия общ делител, заедно с идентичността на Безут, спомената по-горе. В този случай получавате
Тогава конкретното решение е следното:
От това е лесно да се намерят всички решения:
По принцип тези изрази ни дават всички решения на проблема, но все още не сме приключили. Има още неща, които трябва да се вземат предвид. Анализирайки получените данни, ние знаем, че броят на черните костюми, които сте закупили, е, така че броят на закупените сиви костюми е .
Като се има предвид, че броят на костюмите от всеки тип, закупени от нашия приятел, трябва да бъде положителен и по-малък от 12, се получава следното:
Следователно, единствените възможни стойности за са .
Но в изявлението се казва също, че той е закупил минималния брой сиви костюми, които са възможни. Тестване с предишните стойности, за които е изпълнено това условие. Следователно главният герой на нашия проблем купи сиви костюми и черни костюми.
Демо източник:
- Алгебра и дискретна математика I, от Кармен Морено Валенсия.