AOP_Tom2 (1021737), страница 175
Текст из файла (страница 175)
(41)).] 10. Так как у> и уэ — взаимно простые числа, можно найти решение уравнения в>у2 — иэу> = т. Кроме того, (щ -Ь 491)уэ — (иг + ду2)у> = >п для всех 9, поэтому, выбирая подходящее целое 9, можно убедиться, что 2~и>д>+ и>дэ) < У> -Ь у>. Сейчас 2 у2(о> + ии2) ау уэи> — у>вэ = О (по модулю гл), у> и т должны быть взаимно простыми числами. Следовательно, и> + пот ш О. Окончательно, пусть ~и>у> + иэуэ) = пгп, и, + иэ = >>гл, У, + у2 = ут, справедливо 0 < и < дч и остаетсЯ показать, что и < -Д и 2 2 1 1 >37 > 1.
Тождество (и>уэ — иэу>) + (и>у>+ и>92) = (и>1+ и22)(у>-Ь у22 влечет равенство 1 + а~ = Дч. если а > —,' д, то справедливо 2а 7 > 1 + аэ, т. е. 7 — >/72 — 1 < а < — 2' 7. но Г2 йэ < 11~~ — 1 влечет неравенство ч > †, что приводит к противоречию. 2 4 11. Так как а нечетно, у>+ 92 должна быть четной. Чтобы избежать решения, где и у>, и уэ четные, положим у> = х>+хэ, ут = х>-хэ и решим уравнение х>2+хе 2= п>(Я вЂ” с при х> 2. хэ и четном х>.
Соответствующий множитель а будет решением уравнения (х2 — х>)а = хг + х> (па модулю 2'). не составляет труда доказать, что а = 1 (по модуля> 21э') тогда и только тогда, когда х> ш 0 (по модулю 2 ), поэтому получим наилучший потенциал, когда х>шо414 = 2. Проблема сводится к нахождению относительно простого решения Х21+Х2 = Х, где А1 — большов число вида 4к+ 1. Разлагая Ю на комплексные целые числа (гауссовские целые числа), мы получим, что решение существует тогда и только тогда, когда каждый простой множитель Х (среди обычных целых чисел) имеет вид 4ь' -~- 1.
В соответствии с известной теоремой Ферма каждое простое р вида 4й + 1 можно с точностью до знаков н и с записать единственным способом: р = и~+и~ = (и+ге)(и->о), где о четное. Числа и и о эффективно могут быть вычислены, если решить уравнение хэ = -1 (по модулю р) и затем вычислить и + гв = Вой(х + 1, р) с помощью алгоритма евклида по комплексным целым числам (гауссовским целым числам).
[Можно взять х = пЩ >ум шо6 р для почти половины всех целых п. Это применение алгоритма Евклида, по существу, такое же, как и нахождение наименьшей не равной нулю величины и + е, такой, что г и ххс = О (по модулю р). Значения и и е также появляются, когда алгоритм Евклида для целых чисел применяется обычным образом к р и х; см. работу Ж. А. Серре и К. Эрмита (Л. А. Беггег ао>1 С.
Неппйе, Х с(е 5>аГЬ. Ригез ес Арр!. 5 (1848), 12-15) ) Если разложение на простые множители х имеет виду",... р'„" = (и>+>с>)" (и>->о>)" ., (и,+>с„)'"(и, — >е,)", то получим 2" ' различима решений х21 + х22 — — Х, х> .1. хэ, х> четное, полагая )хз) +1)х>) = (и>+>о>)"' (оэхгеэ)'2... (и,х>о,)'". Подобным методом можно получить все такие решения. Замечание. Аналогичная процедура может использоваться, когда т = 10', но для этого потребуется в пять раз больше работы, так как необходимо хранить информацию до нахождения решения с х> ш О (по модулю 10). Например, когда гп = 10, получим >О ~(гп/Я) = 5773502691 и 5773502689 = 53 108934013 = (7+ 21)(7 — 21)(2203+ 102021) х (2203 — 102021). Из Решений )хэ) + 1)х1! = (7+ 21)(2203 + 102021) и (7+ 21)(2203 — 102021) первое дает )х>! = 67008 (не хорошее) и второе — )х>) = 75820, )хэ) = 4983 (это подходит).
Строка 9 из табл. 1 была получена, когда мы положилн х> = 75820, хэ = -4983. Строка 14 таблицы была получена следующим образом. (22~/эгЗ) = 2479700524; спустимся вниз к А> = 2479700521, равному 37 797 84089, и получим четыре решения: >4' = 4364 + 496052 = 26364 +422452 = 38640 +31411 = 11960 +48339 . Соответствующими множителями будут 2974037721, 2254986297, 4246248609 и 956772177. Проверим также Х вЂ” 4, но это число не подходит, поскольку оно не делится на 3. С другой стороны, простое число А> — 8 = 45088 + 21137 приводит к получению множителя 3825140801.
Аналогично получим дополнительные множители для А1 — 20, А1 — 44, А> — 48 и т. д. Множитель строки 14 — наилучший из первых шестнадцати множителей, найденных с помощью данной процедуры; это один из четырех множителей для Х вЂ” 68. 12. Ц' сг>л = П У> + 2~">х,д>((74 (71) + ~„д ~ ьх,9191(К 774). Взята вторая частная производная по йа от левой части (26). Если достигается минимум, то частная производная должна обращаться в нуль. 13. э»» = 1, нг» = иррациональны, ищ = ию = О. 14. После трехкратного применения алгоритма Евклида получим ьэг = 5' + 5 . Затем после выполнения шага Б4 получим (7 = -18 — 2 0 , У = -5 -5 -5 Результатом преобразования (7', дм дю дз) = (1, »,О, 2), (2, -4, », 1), (3, 0,0, »), (1,*,0, 0) будет / — 3 1 21 / -22 — 2 18'( Вж -5 -8 -7, У= — 5 — 5 -5, Е=(0 0 1).
1 — 2 1 9 -31 29 Таким образом, иэ = ь»б, как уже известно из упр. 3. 15. Наибольшее достижимое д в (11) минус наименьшее достижимое плюс 1 равно ]и»] + . + ]и»] — 6, где б = 1, если и,н, < 0 для некоторых» и у, В остальных случаях 6 = О. Например, если 1 = 5, и» > О, ээ > О, из > О, и» = О и иэ с О, наибольшее достижимое значение д равно д = щ + иэ + иэ — 1, а наименьшее равно д = и» + 1 = -]и»] + 1. ]Заметим, что число гиперплоскостей остается прежним при изменении с. Следовательно, ответ будет таким же, если вместо Ьо покрыть Ь Однако приведенная формула не всегда точна для покрытия Ьэ, поскольку не во всех гиперплоскостях, пересекающих единичный гиперкуб, содержатся точки из ба В приведенном выше примере можно никогда не достичь значения д = и» + иэ + иэ — 1 в Ьа, если и» + иэ + иэ > т. Это значение достигается тогда и только тогда, когда существует решение т — и» вЂ” и» вЂ” иэ = х» и» + хэиэ+ хзээ + х4]и»], где (х», хг, хз, х») — неотрицательные целые числа.
Возможно, верно, что данный предел всегда достижим, когда сумма ]и»] + + ]и»] минимальна, но это не кажется очевидным.] 16. Достаточно найти все решения (15), имеющие минимум )ь»]+ + ]и»], и вычесть 1, если какое-нибудь из этих решений имеет компоненты с противоположным знаком. Вместо положительно определенной квадратичной формы будем использовать функцию, в некотором смысле аналогичную ей, (1'(х»,..., х») = ]с»П» + + х»С»]), определяя ]1'] = ]9»]+ +]у»]. Неравенство (21) можно заменить неравенством ]х»] < /(щ,...,9») х (шах» <7 <» ] э»» ]) .
Таким образам может быть получен следующий работающий алгоритм. Заменить шаг Б1 шагом Б3: "Присвоить П»- (гп), У +- (1), г»- 1, э»- т, 1 +- 1". (Здесь С и У вЂ” матрицы размера 1 х 1. Следовательно, двумерный случай сводится к общему методу. Для 1 = 2 можно, конечно, использовать частную процедуру; см, работу, приведенную в ответе к упр.
5.) На шагах Б4 и Б7 присвоить э»- пнп(э,](7»]). На шаге Б7 присвоить х»»- ]п»вх»й,<»]с»»]э/»и]. На шаге Б9 присвоить э»- ппв(э, ]У] — 6) н на шаге Б10 выход, э = Г»о Иначе — оставьте алгоритм в том виде, э каком он сформулирован, так как ои уже производит достаточно короткие векторы. [МэгЬ. Со»пр. 29 (1975)„ 827-833.] 17. Когда й > г на шаге Б9 и К 1» < э, взять в качестве выхода К и -г' Кроме тога, есди )» )» < э, взять в качестве выхода предыдущие векторы для этого и ]При подготовке табл. 1 автор заметил, что существовал точно один вектор (и он же со знаком '"'минус") на выходе для»»», кроме случаев, когда у» = 0 или у» = 0.] 18.
(а) Пусть х = т, р = (1 — и»)/3, со — — у+ кбо, ио — — -у+ дп, Тогда У» Уэ -'(т — 1) дли 2 ~ л, У» У, = э(т~+ -'), 171 Е; = -'(п»~+ 2), э» ~/~д т. (Этот пример удовлетворяет (28) с а = 1 и работает для всех и»: — 1 (по модулю 3).) (Ь) Необходимо поменять местами П и У на шаге Бб. После замены присвоить также в в- пнп(в, К. К) для всех К. Например, когда гп = б4, это преобразование с г = 1, примененное к матрице из (а), сводит / 43 -21 -21'( /22 21 21'( У= ~-21 43 — 21), (/= ~21 22 21) -21 -21 43 21 21 22 У= -21 43 -21, Ы= -1 1 0 (Поскольку преобразование может привести к увеличению длины Ъ;, алгоритм, объединнющий оба преобразования, должен быть таким, чтобы не допускалось зацикливание. См. также упр.
23.) 19. Нет, так как произведение не единичных матриц со всеми неотрицательными элементами вне диагонали и со всеми диагональными элементами, равными единице, не мажет быть единичным. (Однако зацикливание было бы возможным, если бы последующее преобразование с о = -1 осуществлялось тогда, когда -2И 1'„= У; 1;. Правила округления должно быть несимметричным относительно знака. если допустимо несокращенное преобразование.) 20. Когда о пюс(8 = 5, точки 2 '(х, в(х),..., вр 0(х)) для х в периоде — это те же самые точки, что и 2г '(у,а(у),...,о' '(у)) для 0 < у < 2' г плюс (Ха шос(4)/2', где а(у) = (ау + (а/4)) ппк1 2' г. Поэтому в рассматриваемом случае следовала бы использовать алгоритм Б с т = 2' Когда а шоб8 = 3, максимальное расстояние между параллельныии гиперплоскостями, содержащими точки 2 "(х,в(х),...,з" "(х)) по модулю 1, такое же, как и максимальное расстояние между параллельными гиперплоскостями, содержащими точки 2 '(х,-в(х),..., ( — 1)' 'в" 0(х)), поскольку замена знака координат не изменяет расстояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
