Об одном диофантовом уравнении

Размещено на http://www.allbest.ru/

Об одном диофантовом уравнении

Морозов В.В. - учитель математики

и информатики, г. Полысаево

В этой работе мы будем рассматривать решение диофантова уравнения вида:

,

где - целые числа, и решение отыскивается также среди целых чисел.

Если , то уравнение принимает вид:

.

Решение этого классического уравнения подробно описано в литературе, программа его решения на компьютере опубликована http://morozko1967.boom.ru/soft.htm.

Пусть . Тогда уравнение:

(1)

можно записать в виде

(2).

Зададим себе вопрос: может ли быть равным нулю? Да, если c делится на a и . Тогда решение существует, если , иными словами, . Итак, мы получили такой вывод: если и c делится на а, то существует решение: , y - любое целое число. Точно также, если b делится на а, то существует решение x - любое число, . Если , но ни с, ни b не делятся на а, то решений нет.

Пусть теперь . Тогда нет целого х, обращающего в 0 выражение . В этом случае уравнение можно записать в виде:

(3)

Докажем, что уравнение (3) имеет конечное число целочисленных решений. Рассмотрим функцию:

.

Естественно, эта функция является биекцией. Графиком функции является гипербола.

.

Значит, при достаточно больших значениях переменной х значение переменной y близко к . Между какими целыми числами заключено это число? . Начиная с некоторого значения переменной х переменная y, стремясь к , остаётся дробной. Точно также, если отрицательное х велико по модулю, то переменная y, стремясь к , остаётся дробной. Следовательно, уравнение (3) имеет конечное число целочисленных решений, и их можно поручить отыскать компьютеру простым перебором.

Но для этого необходимо найти отрезок на оси абсцисс, вне которого гарантированно нет целочисленных решений уравнения (3).

Если b не делится на а, то, очевидно, что границы целочисленных х равны и .

Если b делится на а, то границы целочисленных х равны и .

Рассмотрим эти два случая отдельно.

Случай 1. Пусть сначала b не делится на а. Найдём . Обозначим . Числа

и удовлетворяют уравнению (1). Поэтому:

(4)

Далее нам потребуется.

Лемма. Пусть a, b - целые, отличные от нуля. Тогда . Если b не делится на а, то .

Доказательство. диофантовое уравнение программа компьютерная

Сначала докажем, что для любого нецелого х:

. (5)

Действительно, по определению целой и дробной частей:

, ;

,

.

.

Допустим противное, пусть . Возможны два случая: b делится на а, и b не делится на а. Если b не делится на а, то из (5) получаем:

,

,

,

то есть b делится на а, что невозможно.

Если же b делится на а, то:

,

по условию а отлично от нуля. Полученное противоречие доказывает, что .

Докажем теперь второе неравенство леммы. Пусть b не делится на а. Допустим противное, . Тогда:

,

используя (5), получаем:

,

.

Но дробная часть любого числа всегда меньше 1. Полученное противоречие доказывает, что если b не делится на а, то .

Лемма доказана.

Доказанная лемма позволяет из соотношения (4) найти:

,

и в случае, если b не делится на а:

.

Обозначим:

,

.

Тогда все целочисленные решения уравнения (3) удовлетворяют оценке , и уравнение (3) можно решить простым перебором, беря по очереди целые значения х от А до D, вычисляя соответствующие:

,

и проверяя, является ли найденное значение у целым. Если делится на , то существует решение .

Случай 2. Пусть b делится на а. Тогда границы целочисленных х равны и .

Найдём сначала . Обозначим:

.

Тогда F удовлетворяет соотношению

.

Учитывая, что в этом случае b делится на а, получаем:

,

. (6)

Теперь найдём . Обозначим . Тогда G удовлетворяет соотношению:

.

Учитывая, что в этом случае b делится на а, получаем:

,

. (7)

Обозначим

,

.

Тогда все целочисленные решения уравнения (3) удовлетворяют оценке

,

и уравнение (3) можно решить простым перебором, беря по очереди целые значения х от А до D, вычисляя соответствующие

,

и проверяя, является ли найденное значение у целым. Если делится на , то существует решение .

Итак, оба случая рассмотрены, осталось написать программу для персонального компьютера.

Приложение

Программа решения диофантова уравнения на языке программирования Pascal.

program superdiofant;

{Программа решения диофантова уравнения вида

axy+bx+cy=d

(c) Морозов Владимир Владимирович

url: http://moroko1967.boom.ru/

mailto: morozko1967@mail.ru

ICQ 259920363}

uses crt;

var a,b,c,d,x,y,D0,A0,s,k:integer;

yy,DD,AA,ww,sgn:real;

l,ll:boolean;

hh,ha,hb,hc,hd:string;

f:Text; {Файл для вывода ответа}

{Далее идут процедуры для решения частного случая

a=0. Тогда уравнение принимает вид bx+cy=d }

procedure nod(a0,a1:longint; var x,y,nd:longint);

{Процедура находит nd=НОД(a0,a1) с помощью расширенного алгоритма Евклида, причём ищет x и y, такие, что x*a0+y*a1=nd}

var a2,q,x0,x1,x2,y0,y1,y2:integer;

begin

x0:=1; y0:=0; x1:=0; y1:=1;

while (a1 mod a0)<>0 do

begin

q:=a0 div a1;

a2:=a0-q*a1;

x2:=x0-q*x1;

y2:=y0-q*y1; {i++}

a0:=a1;

a1:=a2;

x0:=x1;

x1:=x2;

y0:=y1;

y1:=y2;

end;

nd:=a0;

x:=x0;y:=y0

end;

procedure diofant(a,b,c:longint);

{Процедура решения Дифантова уравнения ax+by=c.

На вход процедура получает коэффициенты a, b, c, а на выходе процедура печатает решение на экран и в файл}

var

x,y,ndd,nd:longint;

h,hx,hy,ha,hb,hc:string;

a1,b1,c1:longint;

tx,ty,ta:string;

begin

tx:='';

ty:='';

ta:=''; {Строки для красивого вывода ответа}

if (a<>0) and (b<>0)

then

begin

nod(a,b,x,y,nd); {Нашли Наибольший общий делитель}

if (c mod nd)<>0

then

ta:='Уравнение не имеет решений в кольце Z'

else

begin

a1:=a div nd;

b1:=b div nd;

c1:=c div nd;

nod(a1,b1,x,y,ndd);

x:=x*c1; y:=y*c1;

{Решение найдено! Формулируем ответ}

str(x,hx);str(y,hy);

str(a,ha);str(b,hb);str(c,hc);

if hx='0'

then

tx:='X='

else

tx:='X='+hx;

if hy='0'

then

ty:='Y='

else

ty:='Y='+hy;

if y<0

then hy:='('+hy+')';

if a<0

then ha:='('+ha+')';

if b<0

then hb:='('+hb+')';

if c<0

then hc:='('+hc+')';

h:=hx+'*'+ha+'+'+hy+'*'+hb+'='+hc;

ta:=h;

a1:=-a1; str(a1,ha);

if a1>0

then ha:='+'+ha;

if a1=1

then ha:='';

if a1=-1

then ha:='-';

str(b1,hb);

if b1>0

then hb:='+'+hb;

if b1=1

then hb:='';

if b1=-1

then hb:='-';

if ha='0'

then

tx:=tx+', где t - целое'

else

ty:=ty+ha+'t, где t - целое';

if hb<>'0'

then

tx:=tx+hb+'t'

end

end

else

begin

if (a=0) and (b<>0)

then

begin

if (c mod b)=0

then

begin

tx:='X - любое целое';

c1:=c div b;

str(c1,hy);

ty:='Y='+hy;

if c1>0

then hy:='+'+hy;

str(b,hb);

if b<0

then hb:='('+hb+')';

ta:='Любое*0'+hy+'*'+hb+'='+hc

end

else

ta:='Уравнение не имеет решений в кольце Z'

end;

if (a<>0) and (b=0)

then

begin

if (c mod a)=0

then

begin

ty:='Y - любое целое';

c1:=c div a;

str(c1,hx);

tx:='X='+hx;

str(a,ha);

if a<0

then ha:='('+ha+')';

ta:=hx+'*'+ha+'Любое*0='+hc

end

else

ta:='Уравнение не имеет решений в кольце Z'

end;

if (a=0) and (b=0)

then

begin

if c=0

then

begin

ta:='Любое*0+Любое*0=0';

tx:='X - Любое целое';

ty:='Y - Любое целое'

end

else

ta:='Уравнение не имеет решений в кольце Z'

end

end;

TextColor(14);

{Ответ сформирован в строках. Печатаем ответ}

Writeln('Решение: ');

writeln(tx);

writeln(ty);

writeln(ta);

Writeln(f,'Решение: ');

writeln(f,tx);

writeln(f,ty);

writeln(f,ta)

end;

begin

TextColor(14);

TextBackGround(1);

ClrScr;

Assign(f,'c:/answer.txt'); {Файл для ответа}

rewrite(f);

writeln('Программа решения диофантова уравнения вида axy+bx+cy=d');

writeln('введите целые коэффициенты a,b,c,d');

read(a,b,c,d);

if a<>0

then

begin

l:=true; {Флаг существования решения}

k:=0; {Счётик количества решений}

{Определяем границы целочисленных значений х}

if (b mod a)<>0

then

begin

if b/a<0

then

ww:=-b div a

else

ww:=(-b div a)-1;

AA:=(d-c*(ww+1))/(b+a*(ww+1));

DD:=(d-c*ww)/(b+a*ww)

end

else

begin

AA:=(d*a-a*c+c*b)/a/a;

DD:=-(d*a+a*c+c*b)/a/a

end;

if AA<DD

then

begin

A0:=trunc(AA);

d0:=trunc(DD)+1

end

else

begin

a0:=trunc(DD);

D0:=trunc(AA)+1

end;

str(a,ha); str(b,hb); str(c,hc); str(d,hd);

if a<0 then ha:='('+ha+')';

if b<0 then hb:='('+hb+')';

if c<0 then hc:='('+hc+')';

hh:=ha+'xy+'+hb+'x+'+hc+'y='+hd;

Writeln('Поиск решения уравнения '+hh);

Writeln(f,'Поиск решения уравнения '+hh);

readln;

{Перебор}

for x:=a0 to d0 do

if a*x+c<>0

then

begin

yy:=(d-b*x)/(a*x+c);

{определяем знак уу}

if yy>=0

then sgn:=1

else sgn:=-1;

{Проверяем является ли уу целым}

if yy=int(yy+sgn*0.0000001)

then

begin

y:=trunc(yy+sgn*0.0001);

writeln('(',x,';',y,')');

writeln(f,'(',x,';',y,')');

L:=false;

inc(k);

writeln('Проверка...');

s:=a*x*y+b*x+c*y;

if s=d

then

begin

writeln('Решение выдерживает проверку:)');

writeln(f,'Решение выдерживает проверку:)')

end

else

begin

writeln('Решение не выдерживает проверку:(');

writeln(f,'Решение не выдерживает проверку:(');

end;

writeln;

writeln(f)

end

end;

ll:=false;

{Обрабатывается вырожденный случай

Этот случай может добавить некоторые решения}

if b*c+a*d=0

then

begin

if (c mod a)=0

then

begin

x:= -c div a;

writeln('(',x,';любое целое число)');

writeln(f,'(',x,';любое целое число)');

ll:=true;{Поднимаем флаг, что решений бесконечно много}

l:=false

end;

if (b mod a)=0

then

begin

y:= -b div a;

writeln('(Любое целое число;',y,')');

writeln(f,'(Любое целое число;',y,')');

ll:=true;{Поднимаем флаг, что решений бесконечно много}

l:=false

end;

end;

if l

then

begin

writeln('решений нет');

writeln(f,'решений нет')

end

else

if ll

then

begin

writeln('Количество найденных решений - бесконечно много');

writeln(f,'Количество найденных решений - бесконечно много');

end

else

begin

writeln('Количество найденных решений ',k);

writeln(f,'Количество найденных решений ',k)

end

end

else

begin

{Решаем диофантово уравнение bx+cy=d}

diofant(b,c,d)

end;

close(f);

repeat until keypressed

end.

Размещено на Allbest.ru

...