Задача о семи кёнигсбергских мостах — Википедия

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июля 2019; проверки требуют 2 правки. Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июля 2019; проверки требуют 2 правки. Запрос «Семь мостов Кёнигсберга» перенаправляется сюда; о самих городских мостах см. Мосты Кёнигсберга. Кёнигсберг в XVII—XVIII вв. (карта 1652 года)

Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах (лат. Problema Regiomontanum de septem pontibus, нем. Königsberger Brückenproblem^[1]) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером^[2][3][4], доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог^{[источник не указан 945 дней]}.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Джованни Джакобо Маринони^[de] от 13 марта 1736 года. В этом письме Эйлер приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя»^[2]. В письме Карлу Готлибу Элеру^[en] от 3 апреля 1736 года Эйлер обосновывает найденное им правило

[3], а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae»^[4].

На упрощённой схеме города (графе) мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

• Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
• Если все вершины графа чётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
• Если ровно две вершины графа нечётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.
• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все) — следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. Всего до 2016 года в Калининграде было восемь мостов.

Задача Лемера о функции Эйлера — Википедия

Материал из Википедии — свободной энциклопедии

Задача Лемера о функции Эйлера задаёт вопрос, существует ли какое-либо составное число n, такое, что функция Эйлера φ(n) делит n − 1. Задача остаётся нерешённой.

Для любого простого числа n мы имеем φ(n)=n−1{\displaystyle \varphi (n)=n-1}, так что φ(n){\displaystyle \varphi (n)} делит n−1{\displaystyle n-1}. Д. Г. Лемер в 1932 высказал гипотезу, что не существует составных чисел с таким свойством^[1].

• Лемер показал, что если какое-либо решение n существует, оно должно быть нечётным, свободным от квадратов числом, делящимся на не менее чем на семь различных простых чисел (т.е. ω(n)⩾7{\displaystyle \omega (n)\geqslant 7}). Такое число должно быть также числом Кармайкла.
• В 1980 Коэн и Хагис доказали, что для любого решения n задачи, n>1020{\displaystyle n>10^{20}} и ω(n)⩾14{\displaystyle \omega (n)\geqslant 14}^[2].
• В 1988 Хагис показал, что если 3 делит любое решение n, то n>101937042{\displaystyle n>10^{1937042}} и ω(n)⩾298848{\displaystyle \omega (n)\geqslant 298848}^[3].
• Число решений задачи, меньших X, равно O(X1/2(log⁡X)3/4){\displaystyle O\left({X^{1/2}(\log X)^{3/4}}\right)}^[4].
• В 2017 китайский любитель Шень Ликсинг написал две программы на языке C и нашёл около 21568 чисел Кармайкла (максимальный простой делитель равен 241921) с ω(n)=14{\displaystyle \omega (n)=14} и 87 чисел Кармайкла с ω(n)=15{\displaystyle \omega (n)=15} меньших 10²⁶. Ни одно из них не является решением для проблемы. Согласно предыдущим результатам Ричарда Пинча мы можем сказать, что n>1026{\displaystyle n>10^{26}}. На сайте он неверно поместил 21568 в столбец 10²⁷.

• Graeme L. Cohen, Peter Hagis, jun. On the number of prime factors of n if φ(n) divides n−1 // Nieuw Arch. Wiskd., III. Ser.. — 1980. — Т. 28. — С. 177–185. — ISSN 0028-9825.
• Richard K. Guy. Unsolved problems in number theory. — 3rd. — Springer-Verlag, 2004. — ISBN 0-387-20860-7.
• Peter Hagis, jun. On the equation M⋅φ(n)=n−1 // Nieuw Arch. Wiskd., IV. Ser.. — 1988. — Т. 6, вып. 3. — С. 255–261. — ISSN 0028-9825.
• Lehmer D. H. On Euler’s totient function // Bulletin of the American Mathematical Society. — 1932. — Т. 38. — С. 745–751. — ISSN 0002-9904. — DOI:10.1090/s0002-9904-1932-05521-5.
• Paulo Ribenboim. The New Book of Prime Number Records. — 3rd. — New York: Springer-Verlag, 1996. — ISBN 0-387-94457-5.
• Handbook of number theory I / József Sándor, Dragoslav S. Mitrinović, Borislav Crstici. — Dordrecht: Springer-Verlag, 2006. — ISBN 1-4020-4215-9.
• Péter Burcsi, Sándor Czirbusz, Gábor Farkas. Computational investigation of Lehmer’s totient problem // Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput.. — 2011. — Т. 35. — С. 43–49. — ISSN 0138-9491.

8.2 Устойчивость сжатого стержня. Задача Эйлера

П

Р

ри определении критической силы, вызывающей потерю устойчивости сжатого стержня, предполагается, что стержень идеально прямой и силаР приложена строго центрально. Рассматриваемый метод решения основан на том, что при достижении силой Р критического состояния (Р=Р_кр) стержень находится в безразличном состоянии и ему присущи две формы равновесия: прямолинейная и криволинейная (в таких случаях говорят, что происходит ветвление, или бифуркация, равновесных состояний). Для выявления криволинейной формы равновесия достаточно приложить к стержню малую поперечную возмущающую нагрузку Q, которая вызовет малый прогиб. Если Р < Р_кр, то при удалении Q стержень будет сохранять прямолинейную форму равновесия. Если Р > Р_кр, то равновесие стержня становится неустойчивым и сколь угодно малое возмущение достаточно для того, чтобы возникли большие прогибы. Задачу о критической нагрузке сжатого стержня с учетом возможности существования двух форм равновесия при одном и том же значении силы решил академик Петербургской Академии наук Л. Эйлер в 1744 году.

Рассмотрим шарнирно опертый по концам стержень, сжатый продольной силой Р. Допустим, что по какой-то причине стержень получил малое искривление оси, вследствие чего в нем появился изгибающий момент M:

, (8.3)

где y – прогиб стержня в произвольном сечении с координатой x.

Для определения критической силы можно воспользоваться приближенным дифференциальным уравнением упругой линии:

, (8.4)

где E – модуль Юнга; J – осевой момент инерции сечения стержня относительно оси z в данном случае; E·J ­– жесткость стержня при изгибе. Знаки левой и правой части согласованны в данной системе координат.

Проведя преобразования, можно увидеть, что минимальное значение критическая сила примет при n = 1 (на длине стержня укладывается одна полуволна синусоиды) и J = J_min (стержень искривляется относительно оси с наименьшим моментом инерции)

(8.5)

Это выражение обычно называют формулой Эйлера, а определяемую с ее помощью критическую силу – эйлеровой силой.

8.3. Зависимость критической силы от условий закрепления стержня

Формула Эйлера была получена для основного случая – шарнирного опирания стержня по концам (рис.8.3). На практике встречаются и другие случаи закрепления стержня. При этом можно получить формулу для определения критической силы для каждого из этих случаев, решая, как в предыдущем параграфе, дифференциальное уравнение изогнутой оси балки с соответствующими граничными условиями. Но можно использовать и более простой прием, если вспомнить, что, при потере устойчивости на длине стержня должна укладываться одна полуволна синусоиды.

Рассмотрим некоторые характерные случаи закрепления стержня по концам и получим общую формулу для различных видов закрепления.

1. Стержень длиной l закреплен в жесткой заделке и сжат продольной силой (рис.8.4,а). Из сравнения вида изогнутой оси балки для рассматриваемого и основного случаев можем сделать вывод, что ось стержня, защемленного одним концом, находится в тех же условиях, как и верхняя половина шарнирно опертого стержня длиной 2·l. Таким образом, критическая сила для стержня длиной l с одним защемленным концом может быть найдена так же, как и для шарнирно опертой балки длиной 2·l, то есть

. (8.6)

Р_кр= Р_кр

Р_кр= Р_кр

Р_кр= Р_кр

2. Стержень длиной l, у которого оба конца жестко защемлены (рис.8.4,б). Средняя часть стержня, с двумя жестко защемленными концами находится в тех же условиях, что и шарнирно опертая балка длиной l/2. Таким образом, критическая сила для стержня длиной l с двумя защемленными концами может быть определена так же, как и для шарнирно опертой балки длиной l/2, то есть

. (8.7)

3. Стержень длиной l, у которого один конец жестко заделан, а другой шарнирно оперт (рис.8.4,в). Критическая сила для стержня длиной l с защемленным и шарнирно опертым концами может быть определена так же как и для шарнирно опертой балки длиной 0,7·l, то есть

. (8.8)

Все полученные решения можно объединить в одну общую формулу

, (8.9)

где ·l = l_пр – приведенная длина стержня; l – фактическая длина стержня; – коэффициент приведенной длины, показывающий во сколько раз необходимо изменить длину стержня, чтобы критическая сила для этого стержня стала равна критической силе для шарнирно опертой балки. (Другая интерпретация коэффициента приведенной длины:показывает, на какой части длины стержня для данного вида закрепления укладывается одна полуволна синусоиды при потере устойчивости.)

Теорема Эйлера (теория чисел) — Википедия

Материал из Википедии — свободной энциклопедии

Теоре́ма Э́йлера в теории чисел гласит:

Важным следствием теоремы Эйлера для случая простого модуля является малая теорема Ферма:

Если a{\displaystyle a} не делится на простое число p{\displaystyle p}, то ap−1≡1(modp){\displaystyle a^{p-1}\equiv 1{\pmod {p}}}.

В свою очередь, теорема Эйлера является следствием общеалгебраической теоремы Лагранжа, применённой к приведённой системе вычетов по модулю m{\displaystyle m}.

С помощью теории чисел[править | править код]

Пусть x1,…,xφ(m){\displaystyle x_{1},\dots ,x_{\varphi (m)}} — все различные натуральные числа, меньшие m{\displaystyle m} и взаимно простые с ним.

Рассмотрим все возможные произведения xia{\displaystyle x_{i}a} для всех i{\displaystyle i} от 1{\displaystyle 1} до φ(m){\displaystyle \varphi (m)}.

Поскольку a{\displaystyle a} взаимно просто с m{\displaystyle m} и xi{\displaystyle x_{i}} взаимно просто с m{\displaystyle m}, то и xia{\displaystyle x_{i}a} также взаимно просто с m{\displaystyle m}, то есть xia≡xj(modm){\displaystyle x_{i}a\equiv x_{j}{\pmod {m}}} для некоторого j{\displaystyle j}.

Отметим, что все остатки xia{\displaystyle x_{i}a} при делении на m{\displaystyle m} различны. Действительно, пусть это не так, тогда существуют такие i1≠i2{\displaystyle i_{1}\neq i_{2}}, что

xi1a≡xi2a(modm){\displaystyle x_{i_{1}}a\equiv x_{i_{2}}a{\pmod {m}}}

или

(xi1−xi2)a≡0(modm).{\displaystyle (x_{i_{1}}-x_{i_{2}})a\equiv 0{\pmod {m}}.}

Так как a{\displaystyle a} взаимно просто с m{\displaystyle m}, то последнее равенство равносильно тому, что

xi1−xi2≡0(modm){\displaystyle x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}} или xi1≡xi2(modm){\displaystyle x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}}.

Это противоречит тому, что числа x1,…,xφ(m){\displaystyle x_{1},\dots ,x_{\varphi (m)}} попарно различны по модулю m{\displaystyle m}.

Перемножим все сравнения вида xia≡xj(modm){\displaystyle x_{i}a\equiv x_{j}{\pmod {m}}}. Получим:

x1⋯xφ(m)aφ(m)≡x1⋯xφ(m)(modm){\displaystyle x_{1}\cdots x_{\varphi (m)}a^{\varphi (m)}\equiv x_{1}\cdots x_{\varphi (m)}{\pmod {m}}}

или

x1⋯xφ(m)(aφ(m)−1)≡0(modm){\displaystyle x_{1}\cdots x_{\varphi (m)}(a^{\varphi (m)}-1)\equiv 0{\pmod {m}}}.

Так как число x1⋯xφ(m){\displaystyle x_{1}\cdots x_{\varphi (m)}} взаимно просто с m{\displaystyle m}, то последнее сравнение равносильно тому, что

aφ(m)−1≡0(modm){\displaystyle a^{\varphi (m)}-1\equiv 0{\pmod {m}}}

или

aφ(m)≡1(modm).{\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}.} ■

С помощью теории групп[править | править код]

Рассмотрим мультипликативную группу Zn∗{\displaystyle \mathbb {Z} _{n}^{*}} обратимых элементов кольца вычетов Zn{\displaystyle \mathbb {Z} _{n}}. Её порядок равен φ(n){\displaystyle \varphi (n)} согласно определению функции Эйлера. Поскольку число a{\displaystyle a} взаимно просто с n{\displaystyle n}, соответствующий ему элемент a¯{\displaystyle {\overline {a}}} в Zn{\displaystyle \mathbb {Z} _{n}} является обратимым и принадлежит Zn∗{\displaystyle \mathbb {Z} _{n}^{*}}. Элемент a¯∈Zn∗{\displaystyle {\overline {a}}\in \mathbb {Z} _{n}^{*}} порождает циклическую подгруппу, порядок которой, согласно теореме Лагранжа, делит φ(n){\displaystyle \varphi (n)}, отсюда a¯φ(n)=1¯{\displaystyle {\overline {a}}^{\varphi (n)}={\overline {1}}}. ■

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — М.: Мир, 1987.