Форум программистов, компьютерный форум, киберфорум
Алгебра, теория чисел
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.63/100: Рейтинг темы: голосов - 100, средняя оценка - 4.63
7 / 4 / 1
Регистрация: 08.12.2013
Сообщений: 150

X mod 3 = 2; x mod 5 = 3; x mod 15 = ?

10.05.2014, 22:02. Показов 18948. Ответов 18
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
x mod 3 = 2; x mod 5 = 3; x mod 15 = ?
mod - остаток от деления
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
10.05.2014, 22:02
Ответы с готовыми решениями:

1.Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то:
1.Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то:

Решить уравнение (с mod)
1296x=1105(mod 2413)

Что означает mod?
Что значит "M^e mod n" в шифровании RSA? Что означает mod? Извиняюсь если разделы перепутал. До формулы Эйлера в универе не...

18
Модератор
Эксперт по электронике
8961 / 6727 / 921
Регистрация: 14.02.2011
Сообщений: 23,748
10.05.2014, 22:06
что то мне подсказывает 8
8/3=2 остаток 2
8/5=1 остаток 3
8/15= 0 остаток 8
1
7 / 4 / 1
Регистрация: 08.12.2013
Сообщений: 150
10.05.2014, 23:03  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
что то мне подсказывает 8
8/3=2 остаток 2
8/5=1 остаток 3
8/15= 0 остаток 8
спасибо, конечно, но мне способ решения интересен (ответ то и так в книге есть, кстати, действительно 8 )
0
Модератор
Эксперт по электронике
8961 / 6727 / 921
Регистрация: 14.02.2011
Сообщений: 23,748
10.05.2014, 23:38
Лучший ответ Сообщение было отмечено andrejjjj как решение

Решение

Да очень просто
остаток от деления на 15 это числа от 1 до 14
в этом диапазоне смотрим числа остаток от деления на пять которых составляет 3
их всего 3
это 3 8 и 13
смотрим из этих трех какое при делении на 3 даст 2
это только 8
можешь сначала найти из диапазона 1-14 числа при делении на 3 даст остаток 2
это 2 5 8 11 14
потом из этих чисел выбрать с остатком 3 при делении на 5
опять же 8
1
7 / 4 / 1
Регистрация: 08.12.2013
Сообщений: 150
10.05.2014, 23:51  [ТС]
хмм, а я надеялся на формулу x mod ab (думал что там не просто так 3*5=15 )
0
 Аватар для Klavdia
135 / 112 / 13
Регистрация: 03.06.2013
Сообщений: 270
10.05.2014, 23:53
3n+2=5m+3
3n=5m+(10-9)
3n+9=5m+10
Отсюда, (3n+9) делится на 15, поэтому (3n+2) - имеет остаток=-7 или 8.
0
Модератор
Эксперт по электронике
8961 / 6727 / 921
Регистрация: 14.02.2011
Сообщений: 23,748
11.05.2014, 00:09
Цитата Сообщение от Klavdia Посмотреть сообщение
3n+2=5m+3
3n=5m+(10-9)
не могу врубится откуда 10 и 9 взялось

Добавлено через 1 минуту
Цитата Сообщение от andrejjjj Посмотреть сообщение
хмм, а я надеялся на формулу x mod ab (думал что там не просто так 3*5=15
да это так совпало
посмотри
вот тот же ответ а число другое
x mod 3 = 2; x mod 5 = 3; x mod 11 = ?

Добавлено через 5 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
x mod 3 = 2; x mod 5 = 3; x mod 11 = ?
хотя нет
19/11 остаток 8
19/3 остаток 1
надо подумать

Добавлено через 4 минуты
все правильно там шаг будет другой
при 3 5 15 шаг равен 15 (3*5==15)
8 mod 3 = 2; 8 mod 5 = 3; 8 mod 15= 8
8+15=23
23 mod 3 = 2; 23 mod 5 = 3; 23 mod 15 = 8

а при 11 шаг 3*5*11=165
итого
8 mod 3 = 2; 8 mod 5 = 3; 8 mod 11= 8
8+165=173
173 mod 3 = 2; 173 mod 5 = 3; 173 mod 11 = 8
0
 Аватар для Klavdia
135 / 112 / 13
Регистрация: 03.06.2013
Сообщений: 270
11.05.2014, 01:02
Цитата Сообщение от ValeryS Посмотреть сообщение
Сообщение от Klavdia
3n+2=5m+3
3n=5m+(10-9)
не могу врубится откуда 10 и 9 взялось

Простая подгонка, одно слагаемое делится на 5, другое - на 3, а сумма (всмысле, разница=1)


Цитата Сообщение от ValeryS Посмотреть сообщение
вот тот же ответ а число другое
x mod 3 = 2; x mod 5 = 3; x mod 11 = ?
Этот Ваш пример некорректен, поскольку не имеет единственного решения:
38/3=12 ост2, 38/5=7 ост3, 38/11=3 ост5.......

Вообще, если чуть-чуть продолжить мои выкладки, имеем:
3(n+3)=5(m+2),
т.е. достаточным условием для n+3 - делимость на 5, откуда
x=3n+2= 8, 23, 38, 53,.......
0
Эксперт по математике/физике
 Аватар для Том Ардер
4218 / 3413 / 396
Регистрация: 15.06.2009
Сообщений: 5,818
11.05.2014, 01:04
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}x\equiv 2 (mod\,  3)\Rightarrow x=2+3m\\ x\equiv 3 (mod\,  5)\Rightarrow x=3+5n\end{matrix}\right.

https://www.cyberforum.ru/cgi-bin/latex.cgi?2+3m=3+5n\Rightarrow 3m=3+3n+2n-2\Rightarrow 2n-2=3k\Rightarrow k=2l

https://www.cyberforum.ru/cgi-bin/latex.cgi?x=8+15l\Rightarrow x\equiv 8(mod\, 15)
1
Модератор
Эксперт по электронике
8961 / 6727 / 921
Регистрация: 14.02.2011
Сообщений: 23,748
11.05.2014, 02:01
Цитата Сообщение от Klavdia Посмотреть сообщение
Этот Ваш пример некорректен, поскольку не имеет единственного решения:
а ты дальше не смотрел
Цитата Сообщение от ValeryS Посмотреть сообщение
надо подумать
число 11 я взял от балды, как простое число
Цитата Сообщение от Klavdia Посмотреть сообщение
Простая подгонка, одно слагаемое делится на 5, другое - на 3, а сумма (всмысле, разница=1)
ну а если взять 99 и 100 то такие же выкладки будут?

Том Ардер,
я правильно понимаю что
k=m-n-1 ???
0
Эксперт по математике/физике
 Аватар для Том Ардер
4218 / 3413 / 396
Регистрация: 15.06.2009
Сообщений: 5,818
11.05.2014, 02:36
Цитата Сообщение от ValeryS Посмотреть сообщение
я правильно понимаю что
k=m-n-1 ???
Это не нужно, k - промежуточная переменная. Проходя по цепочке обратно:
2n-2 = 6l
n = 1 + 3l
3m = 3 + 3(1+3l) + 6l
x = 2 + 3m = 8 + 15l
0
 Аватар для Klavdia
135 / 112 / 13
Регистрация: 03.06.2013
Сообщений: 270
11.05.2014, 08:41
Цитата Сообщение от ValeryS Посмотреть сообщение
число 11 я взял от балды, как простое число
Так в этих задачках нельзя "от Балды", Теория чисел - не Физика всё-таки

Цитата Сообщение от ValeryS Посмотреть сообщение
ну а если взять 99 и 100 то такие же выкладки будут?
Конечно, какая разница...
0
Модератор
Эксперт по электронике
8961 / 6727 / 921
Регистрация: 14.02.2011
Сообщений: 23,748
11.05.2014, 09:18
Цитата Сообщение от Klavdia Посмотреть сообщение
Так в этих задачках нельзя "от Балды",
согласен погорячился
Цитата Сообщение от Klavdia Посмотреть сообщение
Конечно, какая разница...
все равно не догоняю
Цитата Сообщение от Klavdia Посмотреть сообщение
Отсюда, (3n+9) делится на 15,
почему???
например n=1 3+9=12 не делится на 15

можно по шагам с краткими комментариями
а то я в ваших решениях с Том Ардер, поплыл

это мне напоминает старые советские учебники "очевидно что" ,"из этого следует" а начинаешь разбирать это "очевидно" и пол тетради испишешь
0
 Аватар для Klavdia
135 / 112 / 13
Регистрация: 03.06.2013
Сообщений: 270
11.05.2014, 09:41
Цитата Сообщение от ValeryS Посмотреть сообщение
все равно не догоняю
Сообщение от Klavdia
Отсюда, (3n+9) делится на 15,
почему???
потому, что оно делится на 3 и ещё оно равно 5(m+2)
0
Модератор
Эксперт по электронике
8961 / 6727 / 921
Регистрация: 14.02.2011
Сообщений: 23,748
11.05.2014, 10:02
Цитата Сообщение от Klavdia Посмотреть сообщение
потому, что оно делится на 3
согласен
Цитата Сообщение от Klavdia Посмотреть сообщение
ещё оно равно 5(m+2)
не согласен
Цитата Сообщение от ValeryS Посмотреть сообщение
например n=1 3+9=12
12 делится на 3
но какое m должно быть чтобы 5(m+2)=12??
0
 Аватар для Klavdia
135 / 112 / 13
Регистрация: 03.06.2013
Сообщений: 270
11.05.2014, 10:31
Так я, конечно, могу ещё раз это написать, мне не трудно:

Цитата Сообщение от Klavdia Посмотреть сообщение
3n+2=5m+3
3n=5m+(10-9)
3n+9=5m+10
3(n+3)=5(m+2)
n=1 тут не подходит по условию, т.к. оно должно иметь остаток 2 от деления на 5...
0
1130 / 789 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
11.05.2014, 13:39
Лучший ответ Сообщение было отмечено andrejjjj как решение

Решение

Цитата Сообщение от andrejjjj Посмотреть сообщение
думал что там не просто так 3*5=15
Да, Вы правильно это заметили.
Если числа p и q взаимно просты, то зная остатки числа x(mod p ), x(mod q),
можно однозначно определить остаток x( mod p q ).
( Китайская теорема об остатках. )

Добавлено через 13 минут
Найдём a, b, такие что x = a p + b q.

x = 0 + b q ( mod p ), можно найти b(mod p), если x(mod p ) известно.
x = a p + 0, ( mod q ), находим a(mod q).

x = a*3 + b*5,
2 = x(mod 3 ) = 0 + b*2, следовательно b = 1 + 3k.
3 = x(mod 5 ) = a*3 + 0, следовательно a = 1 + 5m.

x = (1+5m)*3 + (1+3k)*5 = ... + 15*( ... )
1
2799 / 1845 / 202
Регистрация: 05.06.2011
Сообщений: 5,357
11.05.2014, 14:32
Цитата Сообщение от ValeryS Посмотреть сообщение
какое m должно быть чтобы 5(m+2)=12??
Ты, надеюсь, что-то другое спросить хотел?
0
3 / 3 / 0
Регистрация: 15.12.2012
Сообщений: 94
14.08.2024, 10:03
Если под книгой вы имеете ввиду кнута, то то что 3*5 = 15 действительно можно использовать если воспользоваться "свойством D".
Свойство D. Если r ⊥ s, то a ≡ b (по модулю rs) тогда и только тогда, когда
a ≡ b (по модулю r) и a ≡ b (по модулю s).

Уже опираясь на это свойство мы можем найти такое число в диапазоне от 1 до 14 которое бы давало те же остатки по модулю 3 и 5, и это же число по свойству будет конгруэтно по модулю 3*5 с X. А это только число 8
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
14.08.2024, 10:03
Помогаю со студенческими работами здесь

Mod с отрицательной степенью
Как высчитать мод с отрицательной степенью? Например: X^-y mod Z. По подробней, пожалуйста, если Вас не затруднит :) Спс !! P.S. ...

док-ть что p mod 6 = 1 или 5
док-ть что p mod 6 = 1 или 5; p - простое >=5;

Деление mod с отрицательными числами
Здравствуйте, 13 mod 5 = 3, вычисляем как 13 = 2*5+3 а вот споткнулся об отрицательные числа -13 mod 5 = -3 или +2 -13 =...

Решить конгруэнтность 12х конгруэнтно -15 (mod 66)
Решить конгруэнтность 12х конгруэнтно -15 (mod 66)

Найти последние 3 цифры числа 2^2012 по mod 1000
Собственно, сабж. Вообще в эту тему не втыкнулся полностью. Что делать нужно и в какой последовательности?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Новые блоги и статьи
Контейнеризация React приложений с Docker
Reangularity 03.04.2025
Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .
Свой попап в SwiftUI
mobDevWorks 03.04.2025
SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .
Антипаттерны микросервисной архитектуры
ArchitectMsa 03.04.2025
Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .
std::mutex в C++: Советы и примеры использования
bytestream 03.04.2025
std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .
Не удержался от оценки концепции двигателя Стирлинга.
Hrethgir 03.04.2025
Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
Метод с двумя буферами (или double buffering) или ping-pong buffering
Hrethgir 02.04.2025
Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .
На любовном киберфронте
Alexander-7 01.04.2025
Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .
Как работает Node.js изнутри
run.dev 29.03.2025
Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .
Моки в Python: Mock Object Library
py-thonny 29.03.2025
Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .
JavaScript: Управление памятью и улучшение производительности
run.dev 29.03.2025
В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер