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