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

Новые блоги и статьи
Обработка числовой информации hw_wired 28.01.2025 Введение в обработку числовой информации В современном мире обработка числовой информации стала неотъемлемой частью как профессиональной деятельности, так и повседневной жизни. Электронные таблицы. . .	Мультимедиа hw_wired 28.01.2025 Введение в мультимедийные технологии В современном мире мультимедийные технологии стали неотъемлемой частью нашей жизни, проникнув во все сферы человеческой деятельности. Термин "мультимедиа". . .	Обработка текстовой информации hw_wired 28.01.2025 Введение в обработку текстовой информации В современном мире обработка текстовой информации играет фундаментальную роль в различных сферах человеческой деятельности. Текстовые редакторы стали. . .	Обработка графической информации hw_wired 28.01.2025 Введение в компьютерную графику Компьютерная графика стала неотъемлемой частью современного цифрового мира, пройдя впечатляющий путь развития от простейших черно-белых изображений до сложных. . .	Python в Алгоритмике: Решение задач hw_wired 28.01.2025 Введение в Python и Алгоритмику В современном мире программирование стало неотъемлемой частью образования и профессионального развития. Python зарекомендовал себя как один из самых популярных и. . .	Компьютер как универсальное устройство для работы с информацией hw_wired 28.01.2025 Введение в устройство компьютера Компьютер представляет собой универсальное электронное устройство, предназначенное для автоматической обработки информации. В современном мире компьютер стал. . .
Информация и информационные процессы hw_wired 28.01.2025 Понятие информации и ее виды В современном мире информация является одним из фундаментальных понятий, пронизывающих все сферы человеческой деятельности. Под информацией понимают любые сведения об. . .	Алгоритмика hw_wired 28.01.2025 Введение: Основы алгоритмики и её роль в информатике В современном мире программирование и алгоритмическое мышление стали неотъемлемой частью образования и профессиональной деятельности. . . .	Информационное моделирование hw_wired 28.01.2025 Введение в информационное моделирование В современном мире информационное моделирование стало неотъемлемой частью научной, образовательной и профессиональной деятельности. Это мощный инструмент. . .	Объекты и их имена hw_wired 28.01.2025 Введение: Основы объектного подхода и их роль в информатике В современном мире информационных технологий объектный подход стал фундаментальным принципом организации и обработки информации. Этот. . .	Элементы алгоритмизации hw_wired 28.01.2025 Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .	Человек и информация hw_wired 28.01.2025 Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .

@andrejjjj 7 / 4 / 1 Регистрация: 08.12.2013 Сообщений: 150
		1
	X mod 3 = 2; x mod 5 = 3; x mod 15 = ? 10.05.2014, 22:02. Показов 18689. Ответов 18 Метки нет (Все метки) x mod 3 = 2; x mod 5 = 3; x mod 15 = ? mod - остаток от деления 0

ValeryS Модератор 8954 / 6720 / 921 Регистрация: 14.02.2011 Сообщений: 23,717
	10.05.2014, 22:06	2
	что то мне подсказывает 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 [ТС]	3
	Сообщение от ValeryS что то мне подсказывает 8 8/3=2 остаток 2 8/5=1 остаток 3 8/15= 0 остаток 8 спасибо, конечно, но мне способ решения интересен (ответ то и так в книге есть, кстати, действительно 8 ) 0

ValeryS Модератор 8954 / 6720 / 921 Регистрация: 14.02.2011 Сообщений: 23,717
	10.05.2014, 23:38	4
	Сообщение было отмечено 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 [ТС]	5
	хмм, а я надеялся на формулу x mod ab (думал что там не просто так 3*5=15 ) 0

@Klavdia 135 / 112 / 13 Регистрация: 03.06.2013 Сообщений: 270
	10.05.2014, 23:53	6
	3n+2=5m+3 3n=5m+(10-9) 3n+9=5m+10 Отсюда, (3n+9) делится на 15, поэтому (3n+2) - имеет остаток=-7 или 8. 0

ValeryS Модератор 8954 / 6720 / 921 Регистрация: 14.02.2011 Сообщений: 23,717
	11.05.2014, 00:09	7
	Сообщение от 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	8
	Сообщение от 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	9
	$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 Модератор 8954 / 6720 / 921 Регистрация: 14.02.2011 Сообщений: 23,717
	11.05.2014, 02:01	10
	Сообщение от Klavdia Этот Ваш пример некорректен, поскольку не имеет единственного решения: а ты дальше не смотрел Сообщение от ValeryS надо подумать число 11 я взял от балды, как простое число Сообщение от Klavdia Простая подгонка, одно слагаемое делится на 5, другое - на 3, а сумма (всмысле, разница=1) ну а если взять 99 и 100 то такие же выкладки будут? Том Ардер, я правильно понимаю что k=m-n-1 ??? 0

	14.08.2024, 10:03

@Том Ардер $Эксперт по математике/физике$ 4218 / 3413 / 396 Регистрация: 15.06.2009 Сообщений: 5,818
	11.05.2014, 02:36	11
	Сообщение от 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	12
	Сообщение от ValeryS число 11 я взял от балды, как простое число Так в этих задачках нельзя "от Балды", Теория чисел - не Физика всё-таки Сообщение от ValeryS ну а если взять 99 и 100 то такие же выкладки будут? Конечно, какая разница... 0

ValeryS Модератор 8954 / 6720 / 921 Регистрация: 14.02.2011 Сообщений: 23,717
	11.05.2014, 09:18	13
	Сообщение от 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	14
	Сообщение от ValeryS все равно не догоняю Сообщение от Klavdia Отсюда, (3n+9) делится на 15, почему??? потому, что оно делится на 3 и ещё оно равно 5(m+2) 0

ValeryS Модератор 8954 / 6720 / 921 Регистрация: 14.02.2011 Сообщений: 23,717
	11.05.2014, 10:02	15
	Сообщение от 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	16
	Так я, конечно, могу ещё раз это написать, мне не трудно: Сообщение от 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	17
	Сообщение было отмечено 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 2769 / 1817 / 200 Регистрация: 05.06.2011 Сообщений: 5,273
	11.05.2014, 14:32	18
	Сообщение от ValeryS какое m должно быть чтобы 5(m+2)=12?? Ты, надеюсь, что-то другое спросить хотел? 0

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

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

Решение

Решение