Някои Diophantine уравнения

Диофантово уравнение - уравнението на форма P (X1 ..., хп.) = 0, където лявата страна е полином в X1 променливите. ..., Xn с цели коефициенти. Всеки последователен набор (U1, ...; ООН) числа с Р (. U1 ..., не) = 0 се нарича собственост (самостоятелен) разтвор на диофантово уравнение P (. X1 ..., хп) = 0. решаване на уравнението Diophantine на - означава да се намери цялата си решения, т.е. общото решение на това уравнение.

Нашата цел е да се научите как да се намерят решения на някои Diophantine уравнения, ако тези решения там.

За да направите това, вие трябва да отговори на следните въпроси:

а. Винаги ли е уравнение Diophantine има решение, за да намерите условията за съществуването на решения.

б. Има ли алгоритъм за намиране на решение на уравнението Diophantine.

Примери: 1. диофантово уравнение 5x- 1 = 0 няма решение.

2. 5x- диофантово уравнение 10 = 0 има решение х = 2. която е уникална.

5.x2-Y2 = а - втора степен диофантово уравнение с две неизвестни х и у, за всяко цяло число. Той има решения за а = 1. но все още няма решение за а = 2.

§ 1. Linear Diophantine уравнения

Следващата ни цел - да се научат как да се намерят конкретните и общите решения на линейни уравнения с две Diophantine неизвестни. Очевидно е, че всеки хомогенен диофантово уравнение a1x1 + ... + anxn = 0 винаги има решение (0, ..., 0).

Очевидно е, че линейната Diophantine уравнението, всички, чиито коефициенти са равни на нула, едно решение, само когато дясната страна е нула. Като цяло, ние имаме следното

Теорема (съществуването на разтвори на линейни диофантово уравнение). Linear Diophantine уравнение a1x1 + ... + anxn = с. не всички, чиито коефициенти са равни на нула, има решение, ако и само ако НОД (a1, ... един.) | в.

Тази теорема осигурява конструктивен алгоритъм за намиране на конкретни решения на линейни диофантово уравнение.

Примери: 1. Линеен диофантово уравнение 12x + 21y = 5 няма решение, тъй като GCD (12, 21) = 3 5 не разделят.

2. Виж конкретен разтвор на диофантово уравнение 12x + 21y = 6.

Сега е очевидно, че ГРУ (12, 21) = 3 | 6. така че съществува разтвор. Ние напиши GCD на линейно разширение (12, 21) = 3 = 122 + 21 (-1). Следователно, пара (2 1) - конкретен разтвор на уравнение 12x + 21y = 3. двойка (4, -2) - изходен конкретен разтвор на уравнение 12x + 21y = 6.

3. Виж конкретен разтвор на линейното уравнение 12x + 21y - 2Z = 5.

Тъй като (12, 21, -2) = ((12, 21) -2) = (3, -2) = 1 | 5. че има решение. След доказателството на теоремата, първо се намери решение на уравнение (12,21) х-2y = 5. и след това заместване на линейно разширение на най-голям общ делител на предходния проблем, ние получаваме горното уравнение.

За решаване на уравнение 3 - 2у = 5 запис GCD линейно разширение (3, -2) = 1 = 31 - 21 очевидно. Следователно, двойката числа (1, 1), е разтвор на 3x- 2у = 1. и двойката (5, 5) - частичен разтвор диофантово уравнение 3 - 2у = 5.

По този начин, (12, 21) е 5-25 = 5. заместване намерено преди линейно разширение (12, 21) = 3 = 122 + 21 (-1). получаване (122 + 21 (-1)) 5 - 25 = 5 + 21 или 1210 (-5) - 25 = 5. т.е. Три числа (10; -5, 5) е определена разтвор изходен диофантово уравнение 12x + 21y - 2Z = 5.

Теорема (на структурата на общото решение на уравнението на линейна Diophantine). Linear Diophantine уравнение a1x1 + ... + anxn = с следните твърдения:

(1), ако = (U1, ...; ООН) = (v1; ...; ил) - негови частични решения, разликата (u1- v1; ...; не- ил) - съответстващ на конкретно разтвор на хомогенна уравнението a1x1 + ... + anxn = 0

(2) множество специфични разтвори на линеен хомогенна уравнение Diophantine a1x1 + ... + anxn = 0 е затворен при събиране, изваждане и умножение на числа,

(3) Ако М - общото решение дадена линейна Diophantine уравнения и L - общото решение на съответното хомогенно уравнение Diophantine, за всеки отделен разтвор = (U1, ...; не) започване на равенството на уравнение М = + L.

= (U1, ...; ООН) = (v1; ...; ил) М L.

Това доказва, (1).

По същия начин доказва, (2):

,LzZLzL.

За да се докаже (3), първо се отбележи, че М + L. Тя От гореизложеното следва: М + L.

Обратно, ако а = (L1, ...; LN) и L = (U1, ...; не) М, тогава М:

Така + LM. и евентуално М = + L.

В горната теорема има ясна геометрична значение. Ако разгледаме линейното уравнение a1x1 + ... + anxn = с. където HIR. както е известно от геометрията, тя определя hyperplane в пространството Rn, L, получен от хомогенна уравнение в равнина a1x1 + ... + anxn = 0. преминаваща през началото е изместен от вектор на радон. Повърхността на формата + L се наричат ​​също линеен пространство колектор L с указание и вектор смяна. По този начин, е доказано, че общата М разтвор диофантово уравнение a1x1 + ... + anxn = С се състои от всички точки на линейна колектор с число координати. Координатите на вектор смяна също числа, и набор L разтвори на хомогенна Diophantine уравнение a1x1 + ... + anxn = 0 състои от всички точки с пространство координати число употреба. По тази причина често се казва, че множеството от разтвори произволна уравнение Diophantine е линейна колектор с вектор смяна и направляващата пространство L.

Пример: да диофантово уравнение х - у = 1 М общ разтвор се прилага чрез (1 + у, у), където Уз. неговия частичен разтвор = (1, 0). и общото решение на хомогенна уравнение L х - у = 0 могат да бъдат написани като (Y, Y). където UZ. Така, че е възможно да се направи следващото изображение, при което изходните разтвори диофантово уравнение и съответните хомогенна уравнението Diophantine изобразени мастни точки в линейната пространство на колектор М и L, съответно.

2. Виж общото решение на диофантово уравнение 12x + 21y - 2Z = 5.

Особено разтвор (10; -5, 5) на уравнението е установено по-горе, се намери общ разтвор на хомогенна уравнението 12x + 21y - 2Z = 0. еквивалент диофантово уравнение 12x + 21y = 2Z.

За платежоспособността на уравнението, ако и само ако условията на GCD (12, 21) = 3 | 2z, т.е. 3 | Z или Z = 3 тона за някои число т. Разделяне двете страни от 3. получи 4x + 7Y = 2 тона. Особено разтвор на (2, 1) диофантово уравнение 4x + 7Y = 1 открити в предишния пример. Следователно (4т; -2тон) - конкретен разтвор на уравнение 4x + 7Y = 2 т за всеки

TZ. Общият разтвор на съответния хомогенни уравнения

(7U; -4u) е намерен. По този начин, общото решение на уравнение 4x + 7Y = 2 тона има формата: (4T + 7U; -2тон - 4u). и общия разтвор 12x + 21y хомогенна уравнение - 2Z = 0 могат да бъдат написани като:

Това се вижда добре, че този резултат е в съответствие с гореизложеното, без доказателство за решаване на уравнението на хомогенна Diophantine a1h1 + ... + anhn = 0, ако P =, F и

(U; т) P - общото решение на хомогенна уравнението счита.

По този начин, общото решение на уравнението Diophantine 12x + 21y - 2Z = 5 е както следва: (10 + 4 т + 7U; -5 - 2 тона - 4U 5 + 3 тона).

3. В примера в предходните уравнения илюстрира друг метод за решаване на диофантово уравнение много неизвестни, който се състои от последователни модули намаляване на максималната стойност на коефициентите.