Математический форум Math Help Planet
http://mathhelpplanet.com/

Последовательность решения
http://mathhelpplanet.com/viewtopic.php?f=10&t=20600
Страница 1 из 2

Автор:  cypherpunks01 [ 18 дек 2012, 16:58 ]
Заголовок сообщения:  Последовательность решения

Дано: [math]9\left( 6^{8} \right) ^{-1}\mathbf{m}\mathbf{o}\mathbf{d} 11[/math]

В ответе должно быть: [math]5[/math]
Решаю:

[math]6^{8}=1679616[/math]

[math]1679616^{-1}=0.000000595374180765127267[/math]

[math]9 \times 0.000000595374180765127267=0.000005358367626886145403[/math]

[math]0.000005358367626886145403 \mathbf{m}\mathbf{o}\mathbf{d}11=0[/math]

Где я ошибаюсь?

Автор:  Avgust [ 18 дек 2012, 17:54 ]
Заголовок сообщения:  Re: Последовательность решения

А Вы не задумывались, почему

[math]13 \mod 11=2 \quad[/math] а [math]\frac{1}{13} \mod 11 = 6[/math] ?

Поэтому у Вас [math]\frac{1}{186624} \mod 11 = 5[/math]

Автор:  cypherpunks01 [ 18 дек 2012, 18:16 ]
Заголовок сообщения:  Re: Последовательность решения

Немного не понял первое уравнение.
Выходит, что решать надо так:

[math]9 \times \left( 1679616 \right) ^{-1}= 9 \times \left(\frac{1}{1679616}\right)=\left( \frac{1}{186624} \right)[/math]?

Автор:  Avgust [ 18 дек 2012, 19:04 ]
Заголовок сообщения:  Re: Последовательность решения

Да. Лучше сначала составить таблицу

Изображение

А поскольку [math]186624 \mod 11 = 9[/math]

то из таблицы (желтый цвет) видно, что обратная дробь - это [math]5[/math]

Автор:  cypherpunks01 [ 19 дек 2012, 10:30 ]
Заголовок сообщения:  Re: Последовательность решения

Спасибо! Разъяснили. Теперь буду думать это все перевести в компьютер.

Автор:  cypherpunks01 [ 19 дек 2012, 17:14 ]
Заголовок сообщения:  Re: Последовательность решения

Avgust писал(а):
Да. Лучше сначала составить таблицу

Изображение

А поскольку [math]186624 \mod 11 = 9[/math]

то из таблицы (желтый цвет) видно, что обратная дробь - это [math]5[/math]

А не подскажите формулу по которой рассчитывался правый столбец?

Автор:  Avgust [ 19 дек 2012, 21:44 ]
Заголовок сообщения:  Re: Последовательность решения

Вот алгоритм

[math]\frac 1a \mod b = \frac{b+1+x\cdot b}{a}[/math]

[math]x[/math] меняют, начиная от 0, до тех пор, пока дробь не будет целочисленной. Например:

[math]\frac 15 \mod 11 = \frac{11+1+3\cdot 11}{5}=9[/math]

Автор:  Avgust [ 20 дек 2012, 23:19 ]
Заголовок сообщения:  Re: Последовательность решения

Не знаю, все ли знакомы с общей схемой сравнения правильной дроби по модулю?

В этой связи хотелось бы прочитать небольшую лекцию. Процедуру эту я открыл сам еще в 1968 году, на первом семестре учебы в институте. Нигде в литературе такого не встречал (правда, просто не интересовался данной проблемой, ибо с задачами подобного вида не сталкивался). Итак, суть такая - найти решение

[math]\frac ab \mod c[/math]

где [math]b\ne 1[/math] (использую листинг записи в Maple , поскольку без тройной черты проще).

Алгоритм поиска элементарный

[math]\frac ab \mod c = \frac {a+c+x \cdot c}{b}[/math]

Здесь x - целое число, но необязательно положительное.

Приведу пример:

[math]\frac {43}{13} \mod 17 = \frac {43+17+x \cdot 17}{13}[/math]

Допустим, x = 0, 1, 2 ... . В результате получим, что только при [math]x=11[/math] дробь будет целой и равна [math]19[/math]

Но это число больше 17 . Поэтому еще раз проделаем так: [math]19 \mod 17 = 2[/math]

Это и есть ответ. Полученное нами 19>17 говорит о том, что x - число отрицательное. И верно:

[math]\frac {43+17-2 \cdot 17}{13}=2[/math]

Проверяем в Maple:

Изображение

Автор:  Avgust [ 21 дек 2012, 05:33 ]
Заголовок сообщения:  Re: Последовательность решения

Вот программная реализация в Maple

a := 43: b := 13: c := 17: x1 := trunc(b-a/c-1): x2 := -trunc(a/c+1): for x from x1 by -1 to x2 do if (a+c+x*c)/b-trunc((a+c+x*c)/b) = 0 then print(x, (a+c+x*c)/b); end if end do

-2, 2

Это последний наш пример. Ответ действительно 2 при x=-2

Автор:  Avgust [ 21 дек 2012, 08:16 ]
Заголовок сообщения:  Re: Последовательность решения

Ну а если добавить всего одно ограничение, то сравнение по модулю призводится и для целых чисел, то есть при [math]b=1[/math]

a := 9; b := 1; c := 11; x1 := trunc(b-a/c-1); x2 := -trunc(a/c+1); for x from x1 by -1 to x2 do if (a+c+x*c)/b-trunc((a+c+x*c)/b) = 0 and (a+c+x*c)/b<c then print(x, (a+c+x*c)/b); end if end do:

Результат будет

-1 9

Как и должно быть.

Вот теперь я все вспомнил. А именно, что вывел и доложил на уроке математики 44 года назад!

Страница 1 из 2 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/