Система конгруэнций

[Renfri]

помогите,пожалуйста,решить систему (дайте идею!!!)
Система конгруэнций:

x=1(mod 3)
x=2(mod 4)
x=3(mod 5)
Везде где = должно стоять тождественное равенство,разумеется.
Я попробовала записать системой:
x-3l=1
x-4m=2
x-5n=3
по определению, но ничего хорошего мне это не дано (( Как ршеаются такие штуки? Срочно надо!!! ((

[Бодигрим]

Вам нужна китайская теорема об остатках. Найдите и приведите ее формулировку.

Добавлено спустя 40 секунд:

Хотя в данном примере быстрее перебором решить.

[Echo-Off]

Берём первое попавшееся число. Например 58. Проверяем - опа, подходит

[Бодигрим]

Еще способ решения: из предложенной системы сравнений следует, что $x+2$ делится и на 3, и на 4 и на 5. То есть имеет вид $60k$.

[Renfri]

Если натуральные числа a_1, a_2, \dots , a_n попарно взаимно просты, то для любых целых r_1, r_2, \dots, r_n таких, что 0 \leq r_i < a_i при всех i = 1, 2, \dots, n, найдётся число N, которое при делении на ai даёт остаток ri при всех i = 1, 2, \dots, n.

Это отсюда: http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 0%B0%D1%85
Вот ( Только это ж почти и есть определение самой этой записи ((

Добавлено спустя 1 минуту 15 секунд:

Бодигрим писал(а):

Еще способ решения: из предложенной системы сравнений следует, что $x+2$ делится и на 3, и на 4 и на 5. То есть имеет вид $60k$.

Ой спасибо!!! А я и не заметала совсем (( БОЛЬШОЕ всем спасибо!!!!

[Бодигрим]

Ага, в русской википедии опустили самое интересное - что китайская теорема имеет конструктивное доказательство. Можно почитать в практически любой базовой книжке по теории чисел или залезть в английскую википедию: http://en.wikipedia.org/wiki/Chinese_re ... e_solution

[maxal]

Бодигрим, ну так добавьте в википедию "самое интересное" - в чем проблема?

[bot]

Проблема видимо в выборе самого интересного.
Лучше или нет, но уж точно короче описать для двух, а дальше очевидно по индукции.