On incompatibility of a nonlinear equations over set of natural numbers
Satisfaction problem of equation x m + y m = z m over set of positive natural numbers, where m and z are prime is consider. General case of this equation, is called “big” Fermata’s theorem, has been decided by using very complexity methods [1, 2]. In this paper is presented local result using by ele...
Saved in:
| Date: | 2015 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
PROBLEMS IN PROGRAMMING
2015
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/18 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-18 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/79/2916dd9cc738ba34895211a9ea121e79.pdf |
| spelling |
pp_isofts_kiev_ua-article-182018-10-09T10:09:09Z On incompatibility of a nonlinear equations over set of natural numbers О несовместности одного вида нелинейных уравнений в множестве натуральных чисел Про несумісність одного вигляду нелінійних рівнянь у множині натуральних чисел Krivoi, S.L. Nevmerzhitskiy, A.V. UDC 51.681.3 УДК 51.681.3 УДК 51.681.3 Satisfaction problem of equation x m + y m = z m over set of positive natural numbers, where m and z are prime is consider. General case of this equation, is called “big” Fermata’s theorem, has been decided by using very complexity methods [1, 2]. In this paper is presented local result using by elementary methods. Рассматривается проблема определения несовместности нелинейных уравнений вида x m+ y m = z m в множестве положительных натуральных чисел при условии простоты чисел m и z. Общее решение данного уравнения, имеющего название «великой» теоремы Ферма, получено чрезвычайно сложными методами и его можно найтив [1, 2]. Приведенный в данной статье результат получен совершенно элементарным способом. Розглядається проблема визначення несумісності нелінійних рівнянь вигляду x m + y m = z m у множині додатніх натуральних чисел за умови простоти чисел m і z. Загальний розв’язок даного рівняння, що має назву «великої» теореми Ферма, одержано надзвичайно складними методами і його можна знайти в [1, 2]. Наведений у даній статті результат є окремим випадком і одержаний цілком елементарним способом. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2015-07-01 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/18 PROBLEMS IN PROGRAMMING; No 3 (2003) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2003) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2003) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/18/22 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-10-09T10:09:09Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
UDC 51.681.3 |
| spellingShingle |
UDC 51.681.3 Krivoi, S.L. Nevmerzhitskiy, A.V. On incompatibility of a nonlinear equations over set of natural numbers |
| topic_facet |
UDC 51.681.3 УДК 51.681.3 УДК 51.681.3 |
| format |
Article |
| author |
Krivoi, S.L. Nevmerzhitskiy, A.V. |
| author_facet |
Krivoi, S.L. Nevmerzhitskiy, A.V. |
| author_sort |
Krivoi, S.L. |
| title |
On incompatibility of a nonlinear equations over set of natural numbers |
| title_short |
On incompatibility of a nonlinear equations over set of natural numbers |
| title_full |
On incompatibility of a nonlinear equations over set of natural numbers |
| title_fullStr |
On incompatibility of a nonlinear equations over set of natural numbers |
| title_full_unstemmed |
On incompatibility of a nonlinear equations over set of natural numbers |
| title_sort |
on incompatibility of a nonlinear equations over set of natural numbers |
| title_alt |
О несовместности одного вида нелинейных уравнений в множестве натуральных чисел Про несумісність одного вигляду нелінійних рівнянь у множині натуральних чисел |
| description |
Satisfaction problem of equation x m + y m = z m over set of positive natural numbers, where m and z are prime is consider. General case of this equation, is called “big” Fermata’s theorem, has been decided by using very complexity methods [1, 2]. In this paper is presented local result using by elementary methods. |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2015 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/18 |
| work_keys_str_mv |
AT krivoisl onincompatibilityofanonlinearequationsoversetofnaturalnumbers AT nevmerzhitskiyav onincompatibilityofanonlinearequationsoversetofnaturalnumbers AT krivoisl onesovmestnostiodnogovidanelinejnyhuravnenijvmnožestvenaturalʹnyhčisel AT nevmerzhitskiyav onesovmestnostiodnogovidanelinejnyhuravnenijvmnožestvenaturalʹnyhčisel AT krivoisl pronesumísnístʹodnogoviglâdunelíníjnihrívnânʹumnožinínaturalʹnihčisel AT nevmerzhitskiyav pronesumísnístʹodnogoviglâdunelíníjnihrívnânʹumnožinínaturalʹnihčisel |
| first_indexed |
2025-07-17T09:54:37Z |
| last_indexed |
2025-07-17T09:54:37Z |
| _version_ |
1850410987541233664 |
| fulltext |
Теоретические и методологические основы программирования
© С.Л. Крывый, А.В. Невмержицкий, 2003
ISSN 1727-4907. Проблемы программирования. 2003. № 3 41
УДК 51.681.3
С.Л. Крывый, А.В. Невмержицкий
О НЕСОВМЕСТНОСТИ ОДНОГО ВИДА НЕЛИНЕЙНЫХ
УРАВНЕНИЙ В МНОЖЕСТВЕ НАТУРАЛЬНЫХ ЧИСЕЛ
Рассматривается проблема определения несовместности нелинейных уравнений
вида x m + y m = z m в множестве положительных натуральных чисел при условии про-
стоты чисел m и z. Общее решение данного уравнения, имеющего название «вели-
кой» теоремы Ферма, получено чрезвычайно сложными методами и его можно найти
в [1, 2]. Приведенный в данной статье результат получен совершенно элементарным
способом.
Введение
В связи с интенсивным развити-
ем логического программирования и, в
частности, констрейнтного логического
программирования (CLP), проблема
определения совместности системы ог-
раничений (констрейнтов) играет важ-
ную роль. Случай систем линейных ог-
раничений исследовался во многих ра-
ботах [3—9]. Изложенное в данной
статье можно рассматривать как неко-
торый шаг на пути обобщения линей-
ного случая. Важность проблемы опре-
деления совместности системы конст-
рейнтов состоит в том, что во многих
реальных задачах нет необходимости
вычислять все множество решений та-
кой системы или базис ее множества
решений, а достаточно только знать,
что данная система ограничений со-
вместна (т.е. имеет хотя бы одно ре-
шение).
1. Формулировка задачи
Пусть N обозначает множество
натуральных чисел, N + = N \ {0} – мно-
жество положительных натуральных
чисел и pN – множество простых на-
туральных чисел.
Задача определения совместно-
сти, рассматриваемая в данной статье,
состоит в следующем: совместно ли
уравнение вида
m m mx y z+ = , (1)
где x, y, z – неизвестные, принимаю-
щие свои значения в множестве N + , а
m, z ∈ pN .
В случае m = 1 это будет линей-
ное уравнение и методы его решения
известны. При m = 2 проблема совме-
стности сводится к проблеме нахожде-
ния пифагоровых троек и методы по-
иска таких троек тоже известны [10].
Не ограничивая общности, можно счи-
тать, что выполнены условия
НОД(x, y) = 1 и НОД(x, y, z) = 1,
поскольку всегда можно сократить обе
части уравнения (1) на их общий дели-
тель. Следует также заметить, что об-
щие случаи уравнения (1) при m = 3 и
m = 4 были исследованы соответственно
Л. Эйлером и П. Ферма. Поэтому в
дальнейшем будет рассматриваться
случай простых чисел m и z, где m ≥ 3.
Рассмотрим некоторые общие свойства
чисел x, y, z, входящих в уравнение (1),
которые сформулируем в виде сле-
дующей теоремы.
Теорема 1. Для произвольных
натуральных чисел x и y верны такие
утверждения:
(a) если m = 2l + 1 нечетное, то
0 (mod ( ))m mx y x y+ ≡ + ;
(b) если m = 2l четное, то
2
2 1( 1) 2 (mod )m m l lx y S S+ ≡ − , где 1S x y= + ,
2S xy= .
Доказательство. Справедливость
пункта (а) непосредственно вытекает
из следующего простого тождества:
2 1 2 1 2 2 1
2 2 2 2 1 2
( )(
... )
l l l l
l l l
x y x y x x y
x y xy y
+ + −
− −
+ = + − +
+ − − + .
Теоретические и методологические основы программирования
42
Доказательство пункта (b) вы-
полняется индукцией по числу l тако-
му, что m = 2l.
Базис индукции (l = 1) очевидно
имеет место, т.к. 2 2 2( ) 2x y x y xy+ = + − , и
поэтому 2 2 2
12 (mod )x y xy S+ ≡ − .
Шаг индукции. Предположим,
что для любого k ≤ 2l утверждение лем-
мы верно. Рассмотрим случай k = 2l + 2.
Тогда можем записать
2 2 2 2 2 1 2 1
1
2 2 2 2
2 1 1 2
( )
( ) ( )
l l l l
l l l l
x y S x y
S x y S S R S x y
+ + + ++ = + −
− + = − +
на основании пункта (а) теоремы, если
его применить к первому слагаемому
данного выражения. Но из предполо-
жения индукции, если его применить
ко второму слагаемому выражения, по-
лучаем
2
2 1( 1) 2 (mod )m m l lx y S S+ ≡ − .
Теорема доказана.
2. Структуризация переменных
Заметим, что поскольку x, y, z ∈
∈ N + , то x < z, y < z и x + y > z. Поэтому
можно положить z = x + t' и z = y + t, где
t, t' > 0. Используя малую теорему Фер-
ма (напомним, что m ≥ 3 – простое
число), получаем справедливость сле-
дующих сравнений:
(mod )mx x m≡ , (mod )my y m≡ и
(mod )mz z m≡ .
Из уравнения (1) и общих
свойств сравнений получаем
( )(mod )m mx y x y m+ ≡ + и
(mod )m m mz x y z m= + ≡ ,
и, следовательно, (mod )x y z m+ ≡ . Кро-
ме того, из условия простоты числа
m ≥ 3 получаем НОД(2, m) = 1, а из того,
что числа x, y, z связаны равенством
(1), получаем (mod 2)x y z+ ≡ . Тогда из
того, что два числа сравнимы по раз-
ным модулям, следует их сравнимость
по модулю, являющемуся их наимень-
шим общим кратным, получаем спра-
ведливость сравнения (mod 2 )x y z m+ ≡
и, значит,
2x y z mT+ = + . (2)
Отсюда, учитывая то, что z = x + t'
и z = y + t, получаем
2 2 2x z mT y y t mT y mT t= + − = + + − = + , (3)
y = z + 2mT – x = x + t' + 2mT – x = 2mT + t', (4)
z = x + y – 2mT = 2mT + t + 2mT + t' –
– 2mT – y = 2mT + t + t'. (5)
Используя уравнение (1), полу-
чаем
( ) ( )m m m m mx y z x t y t′+ = = + = + , (6)
или
1
1
1
1
( ) ( )
m
m m m m i m i i m
m
i
m
m m i m i i m
m
i
x y x C x t t
y C y t t
−
− −
=
−
− −
=
′ ′+ = + + =
= + +
∑
∑ .
Отсюда получаем
1
1
m
m m i m i i m
m
i
x C y t t
−
− −
=
= +∑ , (7)
1
1
( ) ( )
m
m m i m i i m
m
i
y C x t t
−
− −
=
′ ′= +∑ . (8)
И, соответственно,
(mod ) 0 (mod )m m mx t mty x t= ⇒ = , (9)
( ) (mod ) 0 (mod )m m my t mt x y t′ ′= ⇒ ≡ . (10)
Используя пункт (а) теоремы 1,
получаем
1 1( 2 ) ( 2 ) 0 (mod )m m mz x y Tm S Tm S= + − = − ≡ ,
а отсюда следует, что
1(2 ) 0 (mod )mTm S≡ и
1 1( ) ( 4 ) 0 (mod )mt t S Tm S′+ = − ≡ ,
а также
1( ) 0 (mod )t t S′+ ≡ .
Это означает, что все простые
делители числа S1 = x + y являются де-
лителями каждого из чисел z, 2Tm и t + t′.
Следовательно число S1 не может быть
простым, так как в противном случае
Теоретические и методологические основы программирования
43
из сравнения 10 (mod )mz S≡ получаем,
что 10 (mod )z S≡ , но z < 1S . Аналогично
число 1S не может иметь два разных
простых делителя. Может быть, одна-
ко, случай, когда 1
kS z= (k > 1). Но это
равенство не может быть справедли-
вым, поскольку по условию имеем
z < x + y < 2z и, следовательно, 1S не мо-
жет быть равно kz при k > 1 и z ≥ 2. А
из того, что число 1S составное, следу-
ет, что и число z составное.
Таким образом, из всего выше-
сказанного следует справедливость та-
кого утверждения.
Теорема 2. Если m ≥ 3 – простое
число, то m-я степень любого простого
числа z не может быть равна сумме m-х
степеней двух натуральных чисел, т.е.
m m mx y z+ ≠ , если x, y ∈ N + , m, z ∈ pN и
m ≥ 3.
Заключение
Рассмотренные случаи ограниче-
ний типа (1) часто возникают в прак-
тических приложениях (например, в
криптоанализе) и, кроме того, имеют
прямое отношение к знаменитой «ве-
ликой» теореме Ферма [1, 2]. Получен-
ный результат показывает несовмест-
ность данного ограничения при усло-
вии простоты чисел m и z в области
положительных натуральных чисел.
1. Wiles A. Modular elliptic curves and Fermat’s
Last Theorem // Annals of Mathemat. –
1995. – 2, – N 141. – P. 443—551.
2. Taylor R., Wiles A. Ring-theoretic properties of
certain Hecke algebras // Ibid. – P. 553—572.
3. Contenjean E., Devie H. Solving systems of
linear diophantine equations // Proc. 3rd
Workshop on Unification. – Lambrecht: Uni-
versity of Kaiserslautern, 1989. – P. 19—26.
4. Pottier L. Minimal solutions of linear dio-
phantine systems: bounds and algorithms //
Proc. of the Fourth Intern. conf. on Rewriting
Techniques and Applications. – Como, –
1991. – P. 162—173.
5. Domenjoud E. Outils pour la deduction auto-
matique dans les theories associatives-
commutatives. Thesis de Doctorat d'Universite:
Universite de Nancy I. France. – 1991. –
176 p.
6. Clausen M., Fortenbacher A. Efficient solution
of linear diophantine equations // J. Symbolic
Computation. – 1989. – 8, – N 1, 2. –
P. 201—216.
7. Romeuf J. F. A polinomial Algorithm for Solv-
ing systems of two linear Diophantine equa-
tions // TCS. – 1990. – 74, – N 3. –
P. 329—340.
8. Filgueiras M., Tomas A.P. A Fast Method for
Finding the Basis of Non-negative Solutions
to a Linear Diophantine Equation // J. Sym-
bolic Computation. – 1995. –19, – N 2. –
P. 507—526.
9. Кривой С.Л. О некоторых методах реше-
ния и критериях совместности систем ли-
нейных диофантовых уравнений в множе-
стве натуральных чисел // Кибернетика и
системный анализ. – 1999. – N 4. –
P. 12—36.
10. Живые числа. Пять экскурсий. В. Боро,
Ю. Цагир, Ю. Рельфо и др. – М.: Мир. –
1985. – 126 с.
Получено 28.08.03
Об авторах
Крывый Сергей Лукьянович
доктор физ.-мат. наук, профессор, вед.
науч. сотрудник
Невмержицкий Александр Васильевич
аспирант института
Место работы авторов:
Институт кибернетики им. В.М. Глушкова НАН
Украины,
просп. Академика Глушкова, 42,
Киев-187, 03680, Украина
Тел. 266 0458
E-mail: krivoi@i.com.ua
|