Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Август 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 8371
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Профессор
Рейтинг: 2601
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2146
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная

Номер выпуска:249
Дата выхода:22.08.2011, 02:30
Администратор рассылки:Асмик Гаряка (Академик)
Подписчиков / экспертов:56 / 67
Вопросов / ответов:1 / 3

Консультация # 183884: Здравствуйте! Прошу помощи в следующем вопросе по дробям: а)Необходимо представить √315 в виде периодической цепной дроби и вычислить ее с точностью до e=10^-4 ^-степень б)Вычислить 66/71 в кольце вычетов по модулю 85. Заранее благодарю за помощь!...

Консультация # 183884:

Здравствуйте! Прошу помощи в следующем вопросе по дробям:
а)Необходимо представить √315 в виде периодической цепной дроби и вычислить ее с точностью до e=10^-4
^-степень
б)Вычислить 66/71 в кольце вычетов по модулю 85.

Заранее благодарю за помощь!

Дата отправки: 17.08.2011, 02:08
Вопрос задал: barhat (3-й класс)
Всего ответов: 3
Страница онлайн-консультации »

Консультирует coremaster1 (Профессионал):

Здравствуйте, barhat!
Задача Б. Чтобы вычислить 66/71 = 66•71-1 необходимо найти элемент кольца, обратный к 71 по умножению. То есть надо найти такое x, что 71•x ≡ 1 (mod 85). Обратный элемент существует, если элемент заимно прост с модулем кольца. В нашем случае верно, что 71 ⊥ 85.

Вариант 1. Уравнение 71•x ≡ 1 (mod 85) можно расписать как:
71x - 85y = 1, при целых x и y
Такое уравнение можно решить с помощью расширенного алгоритма Евклида. Алгоритм даёт решение: x = 6, y = 5, значит 71-1 = 6 в кольце Z85. Таким образом 66/71 = 66•6 = 56 (mod 85)

Вариант 2. Обратный элемент можно найти используя теорему Эйлера:
71-1 = 71φ(85) - 1, где φ(n) - функция Эйлера
φ(n) = ∏piα(pi - 1), где pi - простой множитель числа n со степенью α.
Так как 85 = 5•17, то φ(85) = 4• ;16 = 64. Значит 71-1 = 7163 = 6 (mod 85)

Вариант 3. Если заметить, что 716 = 66 (mod 85), то выражение упрощается:
66•71-1 = 716•71-1 = 715 = 56 (mod 85)

Ответ: 66/71 = 56 в кольце по модулю 85.

Консультировал: coremaster1 (Профессионал)
Дата отправки: 17.08.2011, 09:43

5
нет комментария
-----
Дата оценки: 18.08.2011, 01:04
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Гордиенко Андрей Владимирович (Модератор):

Здравствуйте, barhat!



С уважением.

Консультировал: Гордиенко Андрей Владимирович (Модератор)
Дата отправки: 17.08.2011, 10:07

5
нет комментария
-----
Дата оценки: 18.08.2011, 01:04
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Коцюрбенко Алексей aka Жерар (Профессор):

Здравствуйте, barhat!

а) Для решения этой задачи используем следующую теорему:

Если D и Q - натуральные числа, причём D не является квадратом и D > Q2, то число √D/Q разлагается в периодическую цепную дробь вида [a0;(a1,a2,...,ak-1,2a0)].

Для x = √315 имеем D = 315, Q = 1. Найдем разложение в цепную дробь:











Так как a3 = 2a0, то √315 = [17; (1, 2, 1, 34)]. Найдём последовательность подходящих дробей:
[17; 1] = 18;
[17; 1, 2] = 17 2/3 ≈ 17.6667;
[17; 1, 2, 1] = 17 3/4 ≈ 17.75;
[17; 1, 2, 1, 34] = 17 104/139 ≈ 17.7482;
[17; 1, 2, 1, 34, 1] = 17 107/143 ≈ 17.74825;
[17; 1, 2, 1, 34, 1, 2] = 17 318/425 ≈ 17.74824.

Таким образом, √315 ≈ 17.7482.

б) Частное будет решением сравнения 71x ≡ 66 (mod 85). Так как НОД(71,85) = 1 (71 и 85 - взаимно простые числа), то существует единственное решение. Оно равно 56 (71·56 = 3976 = 85·46 + 66).

Консультировал: Коцюрбенко Алексей aka Жерар (Профессор)
Дата отправки: 17.08.2011, 11:21

5
нет комментария
-----
Дата оценки: 18.08.2011, 01:04
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2011, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.32 от 07.08.2011
В избранное