книги / Mathematica 5. ╨б╨░╨╝╨╛╤Г╤З╨╕╤В╨╡╨╗╤М

зуется для первого вывода на печать значений п, т, d = НОД(л, /и), а также двоичных представлений г и s. Чтобы облегчить распознавание определения, которое выполняет

дыдущую программу мож но переписать так.

Do [

Do [

D o [ { { g , [ r , s } } = E x t e n d e d G C D [ a a a [ a ,n ] , a a a [ a , m ] ] , p r n t } ,

{a , 2 , n+m+2} ] ,

{m ,n - 1 } ] ,

{n , 10} ]

этом определении предусмотрен вывод дополнительной информации: представления g и основания системы счисления а.

Теперь программу мож но модифицировать с учетом нового определения функции печати. Возникает соблазн написать программу так.

Do [

Do [ {

D o [ { { g , { r , s } } = E x t e n d e d G C D [ a a a [a ,n ] , a a a [ a , m ] ] , Л f [ a = = 2 , { [ g 0 , { r O ,s O } } = { g , { r , s } } , p r n t l } ] , I f [ { g 0 , { r 0 , s 0 } } ! = { g , { r , s } } , p r n t ] },

({a , 2 , n+m+2 } ] }, { m ,n - 1 } ] ,

{n , 1 0 }]

Но это совсем не то, что мы хотели! Ведь условие {g0,{rO,sO}} ! = {д, {г,s}} будет

выполнено при а ! =2. Все дело в том, что значения г и s зависят от основания системы счисления а\ Не зависит от основания системы счисления а лишь их представление в системе счисления с основанием а. Поэтому проверять нужно им енно неизменность представления в системе счисления с основанием я. Кроме того, проверка g 0 ! = g лишняя. Поэтому лучше добавить ещ е одно определение.

Теперь можно записать программу.

Do [

Do [ {

Do[{{g,{r,s}}=ExtendedGCD[aaa[a,n],aaa[a,m]],

I f [ a = = 2 , { { r O ,s O } = { r , s }, p r n t l } ] , I f [ n e w r s , p r n t ] },

{а, 2, n+m+2}]}, {m, n-1}•],

in,20}]

Теперь выполним программу. Сколько раз сработала вспомогательная печать? Ни разу! Это значит, что по всем найденным значениям г и s можно восстановить многочлены фг) и фх) и написать тождество d(x) = /<х)я(х)+фс)й(х)! Полученные ре­ зультаты стоят того, чтобы собрать их в таблицу (табл. Б.ЗЗ).

Полученная таблица заслуживает более внимательного рассмотрения. Рассмотрим, например, одну строку таблицы.

д-1 = (1+ х3+х<Ч х9+х12+х15) (дм-1)-(х*-х, +х6+х9+х,2+х'5+х") (д17 —1).

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

Давайте теперь сравним полученные значения для г и s в равенстве! НОД(а, b) = ra+sb для а = хп+| -1 , b = х т+1 -1 (х целое) с теми, которые были полу­ чены ранее для такого же равенства для чисел а и Ь, десятичная запись которых состоит из т единиц и п единиц. (Нужную таблицу мы подготовили заранее.) Не слу­ чайно ли значения г и s совпадают? Нет, не случайно. Дело в том, что если справедли­ во равенство НОД(о, b) = ra+sb для а = хя+| -1 , b = хя,+1 -1 (х целое, отличное от 1), то

с целым основанием х как раз и состоит из п единиц и т единиц. Поскольку равенст-

(х целое, отличное от 1) равносильны, то г и s принимают в них одинаковые значе­ ния, Отсюда, в частности, следует, что если числа г и s из равенства НОД(д,6) = ra+sb имели одно и то же представление для любого основания системы счисления х, то же

оЬ

^ги J зависят от основания системы счисления х! Эта независимость как

I

раз и является следствием полиномиальных тождеств. Причем тождества, получаемые для чисел, десятичная запись которых состоит из т единиц и п единиц, и тождества,

получаемые для чисел а = хп+] -1 и Ъ?= jcm+l -1 , фактически отличаются только мно­ жителем дг-1. Например, из тождества

х-1 = ( l + j c 3 + j r 6 + jc 9 + j c l 2 + j t 15) (дс20 — 1) — ( JC+ JC3 + JC6 + JC9 + JC12 + JC15 -»-JC18 ) ( JC, 7 - 1 )

получается еще более длинное тождество:

1= (1+ Х Ъ + Х Ь + Х 9 +JC12 +*15 ) (JC19 +JC18 +JC17 + ... + JC+ 1) - ( Х + хъ+х6+ х9 +JC12 +дг15 +х18 )х

X ( JC16 +х15+дс14 + . . . + Х + 1).

Обратите, наконец, внимание на то, что в полученной таблице представления чи­ сел г и s содержат только нули и единицы. Это означает, что коэффициенты полино­ мов г(х) и s(x), построенных по представлениям чисел г и 5, тоже будут равны 0 и 1 (либо “ 1, если перед представлением стоит знак минус).

Наименьшее общее кратное — функция LCM

Во множестве всех кратных нескольких данных чисел всегда найдется такое, которое является делителем всякого другого общего кратного этих чисел: это — общее наименьшее кратное.

А. К. Сушкевич. Теория чисел. Глава 1. О делимости чисел. Теорема 8

Функция ьсм находит наименьшее общее кратное в области целых, рациональных и гауссовых чисел.

3 2

(LCM[2, 3 , 5 ] , L C M [ j , - у ] / LCM [2 + 3 i , 3 - 4 ж] }

{ 3 0 ,6 ,1 8 + 1 }

Что такое наименьшее общее кратное нескольких рациональных чисел? Это, ко­ нечно, такое наименьшее рациональное число, частные от деления которого на дан­ ные рациональные числа являются целыми.

Пример 6.11. Наименьшее общее кратное первой тысячи чисел. Вот как можно его найти.

LCM00Range [1 0 0 0 ]

7 1 2 8 8 6 5 2 7 4 6 6 5 0 9 3 0 5 3 1 6 6 3 8 4 1 5 5 7 1 4 2 7 2 9 2 0 6 6 8 3 5 8 8 6 1 8 8 5 8 9 3 0 4 0 4 5 2 0 0 1 9 9 1 1 5 4 3 2 4

0 8 7 5 8 1 1 1 1 4 9 9 4 7 6 4 4 4 1 5 1 9 1 3 8 7 1 5 8 6 9 1 1 7 1 7 8 1 7 0 1 9 5 7 5 2 5 6 5 1 2 9 8 0 2 6 4 0 6 7 6 2 1 0 0 9 2 5 1 4

6 5 8 7 1 0 0 4 3 0 5 1 3 1 0 7 2 6 8 6 2 6 8 1 4 3 2 0 0 1 9 6 6 0 9 9 7 4 8 6 2 7 4 5 9 3 7 1 8 8 3 4 3 7 0 5 0 1 5 4 3 4 4 5 2 5 2 3 7 3 9 7 4 5 2 9 8 9 6 3 1 4 5 6 7 4 9 8 2 1 2 8 2 3 6 9 5 6 2 3 2 8 2 3 7 9 4 0 1 1 0 6 8 8 0 9 2 6 2 3 1 7 7 0 8 8 61'979 5 4 0 7 9 1 2 4 7 7 5 4 5 5 8 0 4 9 3 2 6 4 7 5 7 3 7 8 2 9 9 2 3 3 5 2 7 5 1 7 9 6 7 3 5 2 4 8 0 4 2 4 6 3 6 3 8 0 5 1 1 3 7 0 3 4 3 3 1 2 1 4 7 8 1 7 4 6 8 5 0 8 7 8 4 5 3 4 8 5 6 7 8 0 2 1 8 8 8 0 7 5 3 7 3 2 4 9 9 2 1 9 9 5 6 7 2 0 5 6 9 3 2 0 2 9 0 9 9 3 9 0 8 9 1 6 8 7 4 8 7 6 7 2 6 9 7 9 5 0931603520000

Это, конечно же, существенно меньше, чем 1000!. В

1000 !/LCM0@Range[1 0 0 0 ]

5 6 4 4 4 7 8 3 9 2 7 5 5 1 1 5 2 0 7 2 1 7 3 4 6 9 6 7 3 4 8 4 3 4 9 2 7 0 8 4 3 4 0 3 8 0 2 0 2 8 6 5 0 7 6 1 3 1 3 4 8 6 1 8 8 7 8 0 9 9

3 3 7 1 0 9 9 7 9 7 2 5 2 6 0 9 6 9 7 0 8 6 8 0 3 0 3 4 4 3 4 1 8 4 5 6 8 1 5 0 8 7 3 2 2 3 8 9 6 8 6 8 7 2 5 9 5 6 6 5 4 6 3 4 7 9 5 0 9 0

4 2 4 1 9 0 0 5 7 3 6 7 1 7 3 2 6 0 5 4 0 5 8 1 3 9 0 2 1 7 1 7 9 0 2 7 3 2 9 1 1 7 9 3 5 2 1 4 7 9 7 9 2 4 9 0 6 4 4 1 1 9 7 6 2 1 2 0 1 6

2 1 8 5 5 8 0 2 3 9 1 6 5 8 8 5 9 5 9 7 8 9 1 1 3 2 3 8 5 9 7 1 4 5 7 5 0 4 3 9 6 9 4 7 3 8 0 6 3 9 0 5 2 4 6 4 9 5 5 1 3 5 3 4 9 2 6 0 7 8

6269240235976327708307400278060510041387149846139732431537416495360938

1131953517675333413439526744779132766911579673805361479699109899315840

2514786222371287563487122797718567505966000274864041649240503703312964

8944110921905225897893847784255235833563028640027449707297915920152663

5793744631801013481920273004153185432745697649289446291719568986968720

3419792935228989810950692529597394515927351449958319072841271244884591

9304373706635482530034667735673674820266712486162694399661471420747532

03120503170367033278.67740772926557874646883014191158013314020690145258

8063198721392150507236250301994683844900294618643762224657344930984696

6680312776306878099412928682069520281618125090171627537596507634046767

5248247585468526950093561397456484848397922331130363653941912093281755

1556922214647924545433219079357350385246350059813457324385952011410846

0239993192050052395124585731623165549285250318616802295761210452366701

9411997327786880368751581542010640315804829921622400668744894629837105

4577558260150893577331489234272856887857409955220456469558882770327261

6489819792161385271403640949968821800600426821467429016281300340818536

6740497847075783700955635816618307634240698753828518904983893744809533

6398201079736341935453147314308218498178386631522034419848915644774532

9514244821448400901893454119135235799727951785823723867849034064139605

8469511170217377411150861201294122776677572494130004598702648806925812

1145828704197168873503121891023633592374921184105574640450047298261226

0825457361064437007475267189689029999429238731902168522554489421543108

8885494912353647835912451288476186771607310924213835809370046973607936

оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо

оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо

оооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо

00000000000000000000000000000000000

раз! Заметьте, что наименьшее общее кратное первой тысячи чисел заканчивается всего лишь четырьмя нулями.

Пример 6.12. Графики функции ьсм.

Давайте теперь построим несколько графиков функции ьсм. Поскольку это функ­ ция двух аргументов, построим изображения поверхности z = ЬСМ[IntegerPart[х], IntegerPart [у] ]. Для этого используем функцию Plot3D.

Plot3D[ЬСМ[IntegerPart[х],IntegerPart[у]], {х,1,100}, {у,1,50),

PlotPoints->50, PlotRange->All,Mesh->FalseJ;

100

А вот вид вблизи.

plot3D[LCM[IntegerPart[х],IntegerPart[у]],{х,1,10}/{у,1,10},PlotPoints-

>50,PlotRange->All/Mesh->False] ;

Резюме

Задача нахождения наибольшего общего делителя и наименьшего общего кратного нескольких чисел столь важна, что ее приходится решать практически постоянно. Даже занимаясь решением задач вариационного исчисления, математической физики, линейной алгебры, математического анализа, аналитической геометрии или просто решая какие-нибудь дифференциальные уравнения, вам практически не удастся из­ бежать сложения или вычитания дробей — действий, которым учатся в пятом классе. И как только вам приходится выполнять эти действия, вы так или иначе вспоминаете о наибольшем общем делителе и наименьшем общем кратном. К счастью, система Mathematica если и не позволяет забыть об этих двух важнейших понятиях арифмети­ ки, то избавляет вас от рутинной работы по их нахождению. В системе Mathematica реализованы весьма эффективные, вполне современные алгоритмы нахождения наи­ большего общего делителя и наименьшего общего кратного. Пользуясь ими, вы може­ те быть уверены, что используете самые современные инструменты. Конечно, их применение целиком зависит от вас. Вы можете составить таблицы, найти тождества, решить неопределенные уравнения...

Задачи

Задача 6.1 (линейное представление наибольшего общего делителя чисел Фибоначчи). Так как наибольший общий делитель п- и т-го чисел Фибоначчи равен числу Фибо­ наччи с номером d = НОД(л, /и), то это число можно представить в виде линейной комбинации л- и /w-го чисел Фибоначчи. Составьте таблицу коэффициентов г и s ли­ нейного представления в зависимости от л и т. Иными словами, найдите такие числа

гИ 5, что

НОД(Fibonacci[n],Fibonacci[m]) = Fibonacci[НОД(n,m)] =

= r Fibonacci[n] +s Fibonacci[m].

Глава 7

Модулярная арифметика: деление с остатком,

вычеты, сравнения

и китайская теорема об остатках

Вэт ой главе...

♦Деление с остатком

♦Возведение в степень в модулярной арифметике — функция PowerMod

♦Китайская теорема об остатках — функция ChineseRemainder

♦Корни в системе остаточных классов

♦Критерии простоты чисел специального вида

♦Резюме

♦Задачи

Существует один интересный способ выполнения ариф­ метических действий с большими целыми числами, осно­ ванный на некоторых простых фактах теории чисел. Идея этого метода состоит в том, чтобы иметь несколько модулей т , , т , , тг , которые взаимно просты, и оперировать не

непосредственно с числом и, а с его “остатками” и mod /и,,

иmod т2 , ..., и mod тг .

Д.Кнут. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы. Глава 4. Арифметика. §4.3.

Арифметика многократной точности. п°4.3.2. Модулярная арифметика

В области целых чисел есть только два делителя, на которые делятся все числа: 1и -1. На остальные же числа деление выполняется далеко не всегда без остатка. Именно делению с остатком и действиям над остатками как раз и посвящена настоящая глава.

Деление с остатком

При выполнении операции деления с остатком получается частное и остаток. Для нахождения частного и остатка в системе Mathematica предусмотрены функции

Quotient и Mod.

Частное при делении с остатком — функция Quotient

Чтобы получить частное при делении (с остатком) п на т, нужно воспользоваться функцией Quotient [n,m]. Рассмотрим пример.

Quotient[16,5]

3

Для целых п и т выражение Quotient [n,m] равносильно Floor [m/n]. Однако п и: тмогут быть вещественными и даже комплексными числами.

Quotient [ЕА10,Е Л8] 7

Quotient [Ел 10+25*1 ,Ел8+41] 7-1

В случае вещественных чисел Quotient[n,m] — это такое целое число х, что 0<л-/и х<т. Однако часто нужно найти целое число х, такое, что d<n—m x<d+m. По­ жалуйста, укажите сдвиг d третьим параметром.

Quotient [16, 5,14]

О

Вот как можно найти частные от деления чисел 0, 1,2, ..., 21 на 3.

Quotient [Range [0,21] , 3]

{О, 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 5 , 5, 5, 6, б, 6,7}

А вот частные, когда задан сдвиг 1.

Quotient [Range [0,21], 3,1]

{-1,0,0, 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 5 , 5 , 5, б, 6,6}

А вот частные, когда задан сдвиг 2.

Quotient [Range [0,21] ,3,2]

{1,-1,0, 0, 0, 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 5 , 5, 5, 6, 6}

Пример 7.1. Графики функции Quotient.

Давайте теперь построим несколько графиков функции Quotient. Поскольку это функция двух аргументов, построим изображения поверхности z = Q u o t i e n t [х, у]. Для этого используем функцию Plot3D.

Остаток отделения — функция Mod

Чтобы получить остаток от деления п на /я, нужно воспользоваться функцией Mod[n,mb Наименьший возможный остаток в этом случае равен нулю, а наиболь­ ший... Как вы думаете, чему равен наибольший возможный остаток? “ Конечно, т -1 " , — возможно, подумали вы. Ну, что же, я, конечно, приветствую ваши глубокие познания в теории чисел, ибо именно так написано во всех классических учебниках по этой дисциплине, если, конечно, именно в этом месте нет какой-либо досадной опечатки. Но должен вас разочаровать: вы не угадали. Зато, надеюсь, вам будет при­ ятно узнать, что возможности функции Mod значительно шире, чем требуется для ре­ шения задач из задачников по классической теории чисел. Дело в том, что аргументы

этой функции могут быть не только целыми (это предусмотрено классическими учеб­ никами теории чисел), но и вещественными и даже комплексными! А во множестве вещественных чисел, как вы, надеюсь, ещ е помните, полно сюрпризов... Н о сначала давайте рассмотрим простейший случай целых аргументов.

Mod[ 7 ,5 ]

2

Ну вот, при делении 7 на 5 остаток равен 2. Просто и понятно, даже в уме можно вычислить. Вот ещ е один пример.

Mod[3A1 0 , 5]

4

Тоже в уме, и тоже просто и понятно. Н о вот несколько примеров с вещественны­ ми числами.

Mod[Pi / 1 ]

-3+71

Mod[ 1 4 9 / 1 0 , 5 ]

i i

10

Mod[ 1 4 9 9 / 1 0 0 , 5]

499

100

Mod[ 1 4 9 9 9 /1 0 0 0 ,5 ]

4999

1000

Теперь, надеюсь, вы поняли, что множество значений Mod[n,m] не имеет наболь­ шего элемента. М ож но лишь утверждать, что при вещественных т и п 0<M od[n,m ]<m , причем все значения из открытого справа интервала [0, т) функция Mod[n,m] при­ нимает. Но иногда нужно сдвинуть этот интервал на d. Нет проблем: укажите сдвиг d

третьим параметром.

Вот как можно найти остатки от деления чисел 0, 1 ,2 , ..., 21 на 3.

Mod [Range [ 0 ,2 1 ] , 3]

{0,1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 }

А вот те же остатки, когда задан сдвиг 1.

Mod[Range [ 0 ,2 1 ] , 3 , 1 ]

{ 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 }

А вот те же остатки, когда задан сдвиг 2.

Mod[Range[0,21] , 3 , 2 ]

1 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 , 4 , 2 , 3 }

Ниже приведены основные свойства функций Q u o t i e n t и Mod:

Ну и, наконец, полезно иметь в виду, что аргументы функции Mod могут быть сп и ­ сками. Это, например, позволяет найти остаток от деления данного числа сразу на не­ сколько чисел.