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

@andrejjjj · Регистрация: 08.12.2013

Author24 — интернет-сервис помощи студентам

x mod 3 = 2; x mod 5 = 3; x mod 15 = ?
mod - остаток от деления

ValeryS · 10.05.2014, 22:06

что то мне подсказывает 8

8/3=2 остаток 2
8/5=1 остаток 3
8/15= 0 остаток 8

@andrejjjj · 10.05.2014, 23:03 **[ТС]**

Сообщение от ValeryS

что то мне подсказывает 8
8/3=2 остаток 2
8/5=1 остаток 3
8/15= 0 остаток 8

спасибо, конечно, но мне способ решения интересен

(ответ то и так в книге есть, кстати, действительно 8

)

ValeryS · 10.05.2014, 23:38

Да очень просто
остаток от деления на 15 это числа от 1 до 14
в этом диапазоне смотрим числа остаток от деления на пять которых составляет 3
их всего 3
это 3 8 и 13
смотрим из этих трех какое при делении на 3 даст 2
это только 8
можешь сначала найти из диапазона 1-14 числа при делении на 3 даст остаток 2
это 2 5 8 11 14
потом из этих чисел выбрать с остатком 3 при делении на 5
опять же 8

@andrejjjj · 10.05.2014, 23:51 **[ТС]**

хмм, а я надеялся на формулу x mod ab (думал что там не просто так 3*5=15

)

@Klavdia · 10.05.2014, 23:53

3n+2=5m+3
3n=5m+(10-9)
3n+9=5m+10
Отсюда, (3n+9) делится на 15, поэтому (3n+2) - имеет остаток=-7 или 8.

ValeryS · 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

@Klavdia · 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,.......

@Том Ардер · 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)$

ValeryS · 11.05.2014, 02:01

Сообщение от Klavdia

Этот Ваш пример некорректен, поскольку не имеет единственного решения:

а ты дальше не смотрел

Сообщение от ValeryS

надо подумать

число 11 я взял от балды, как простое число

Сообщение от Klavdia

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

ну а если взять 99 и 100 то такие же выкладки будут?

Том Ардер,
я правильно понимаю что
k=m-n-1 ???

@Том Ардер · 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

@Klavdia · 11.05.2014, 08:41

Сообщение от ValeryS

число 11 я взял от балды, как простое число

Так в этих задачках нельзя "от Балды", Теория чисел - не Физика всё-таки

Сообщение от ValeryS

ну а если взять 99 и 100 то такие же выкладки будут?

Конечно, какая разница...

ValeryS · 11.05.2014, 09:18

Сообщение от Klavdia

Так в этих задачках нельзя "от Балды",

согласен погорячился

Сообщение от Klavdia

Конечно, какая разница...

все равно не догоняю

Сообщение от Klavdia

Отсюда, (3n+9) делится на 15,

почему???
например n=1 3+9=12 не делится на 15

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

это мне напоминает старые советские учебники "очевидно что" ,"из этого следует" а начинаешь разбирать это "очевидно" и пол тетради испишешь

@Klavdia · 11.05.2014, 09:41

Сообщение от ValeryS

все равно не догоняю
Сообщение от Klavdia
Отсюда, (3n+9) делится на 15,
почему???

потому, что оно делится на 3 и ещё оно равно 5(m+2)

ValeryS · 11.05.2014, 10:02

Сообщение от Klavdia

потому, что оно делится на 3

согласен

Сообщение от Klavdia

ещё оно равно 5(m+2)

не согласен

Сообщение от ValeryS

например n=1 3+9=12

12 делится на 3
но какое m должно быть чтобы 5(m+2)=12??

@Klavdia · 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...

@Alex5 · 11.05.2014, 13:39

Сообщение от 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*( ... )

iifat · 11.05.2014, 14:32

Сообщение от ValeryS

какое m должно быть чтобы 5(m+2)=12??

Ты, надеюсь, что-то другое спросить хотел?

@emmure · 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

Новые блоги и статьи Все статьи Все блоги /
Асинхронные операции в Django с Celery py-thonny 05.04.2025 Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .	Использование кэшей CPU: Максимальная производительность в Go golander 05.04.2025 Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .	Создаем Telegram бот на TypeScript с grammY run.dev 05.04.2025 Одна из его самых сильных сторон Telegram — это интеграция ботов прямо в экосистему приложения. В отличие от многих других платформ, он предоставляет разработчикам мощный API, позволяющий создавать. . .	Паттерны распределённых транзакций в Event-Driven микросервисах ArchitectMsa 05.04.2025 Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .	Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .
Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .	Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .

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

Решение

Решение

@andrejjjj 7 / 4 / 1 Регистрация: 08.12.2013 Сообщений: 150

	X mod 3 = 2; x mod 5 = 3; x mod 15 = ? 10.05.2014, 22:02. Показов 18954. Ответов 18 Метки нет (Все метки) x mod 3 = 2; x mod 5 = 3; x mod 15 = ? mod - остаток от деления 0

ValeryS Модератор 8962 / 6728 / 921 Регистрация: 14.02.2011 Сообщений: 23,750
	10.05.2014, 22:06
	что то мне подсказывает 8 8/3=2 остаток 2 8/5=1 остаток 3 8/15= 0 остаток 8 1

@andrejjjj 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

ValeryS Модератор 8962 / 6728 / 921 Регистрация: 14.02.2011 Сообщений: 23,750
	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

@andrejjjj 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

ValeryS Модератор 8962 / 6728 / 921 Регистрация: 14.02.2011 Сообщений: 23,750
	11.05.2014, 00:09
	Сообщение от Klavdia 3n+2=5m+3 3n=5m+(10-9) не могу врубится откуда 10 и 9 взялось Добавлено через 1 минуту Сообщение от andrejjjj хмм, а я надеялся на формулу x mod ab (думал что там не просто так 35=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 (35==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 шаг 35*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

ValeryS Модератор 8962 / 6728 / 921 Регистрация: 14.02.2011 Сообщений: 23,750
	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

ValeryS Модератор 8962 / 6728 / 921 Регистрация: 14.02.2011 Сообщений: 23,750
	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

ValeryS Модератор 8962 / 6728 / 921 Регистрация: 14.02.2011 Сообщений: 23,750
	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

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	11.05.2014, 13:39
	Сообщение было отмечено andrejjjj как решение Решение Сообщение от andrejjjj думал что там не просто так 35=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 = a3 + b5, 2 = x(mod 3 ) = 0 + b2, следовательно b = 1 + 3k. 3 = x(mod 5 ) = a3 + 0, следовательно a = 1 + 5m. x = (1+5m)3 + (1+3k)5 = ... + 15*( ... ) 1

iifat 2800 / 1846 / 202 Регистрация: 05.06.2011 Сообщений: 5,358
	11.05.2014, 14:32
	Сообщение от ValeryS какое m должно быть чтобы 5(m+2)=12?? Ты, надеюсь, что-то другое спросить хотел? 0

@emmure 3 / 3 / 0 Регистрация: 15.12.2012 Сообщений: 94
	14.08.2024, 10:03
	Если под книгой вы имеете ввиду кнута, то то что 35 = 15 действительно можно использовать если воспользоваться "свойством D". Свойство D. Если r ⊥ s, то a ≡ b (по модулю rs) тогда и только тогда, когда a ≡ b (по модулю r) и a ≡ b (по модулю s). Уже опираясь на это свойство мы можем найти такое число в диапазоне от 1 до 14 которое бы давало те же остатки по модулю 3 и 5, и это же число по свойству будет конгруэтно по модулю 35 с X. А это только число 8 0