ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60715
Тема:    [ Арифметика остатков (прочее) ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Решите сравнения:
  а)  8x ≡ 3 (mod 13);
  б)  17x ≡ 2 (mod 37);
  в)  7x ≡ 2 (mod 11);
  г)  80x ≡ 17 (mod 169).


Решение

  а)  8x ≡ 16 (mod 13),  поэтому  x ≡ 2 (mod 13).

  б) Первый способ.  –20x ≡ 2 (mod 37)  ⇒  10x ≡ 36 (mod 37)  ⇒  5x ≡ 18 ≡ 55 (mod 37)  ⇒  x ≡ 11 (mod 37).
  Второй способ. Решим уравнение  17x – 37y = 2  в целых числах.
  17(x – 2y) – 3y = 2;  сделав замену  z = x – 2y,  получим  3(5z – y) = 2(1 – z).  Отсюда  1 – x = 3t,  5z – y = 2t,  z = 1 – 3t,  y = 5z – 2t = 5 – 17x,
x
= 2y + z = 11 – 37t.

  в)  7x ≡ 35 (mod 11),  поэтому  x ≡ 5 (mod 11).

  г) Первый способ.  80x ≡ 186 (mod 169)  ⇒  40x ≡ 93 ≡ 262 (mod 169)  ⇒  20x ≡ 300 (mod 169)  ⇒  x ≡ 15 (mod 169).
  Второй способ.  80x ≡ 17 (mod 169)  ⇒  2x ≡ 4 (mod 13)  ⇒  x ≡ 2 (mod 13),  то есть  x = 13n + 2.  80(13n + 2) ≡ 17 (mod 169)  ⇒  80n + 11 ≡ 0 (mod 13)  ⇒  2n ≡ 2 (mod 13)  ⇒  n = 13k + 1  ⇒  x ≡ 15 (mod 169).


Ответ

а)  x ≡ 2 (mod 13);   б)  x ≡ 11 (mod 37);   в)  x ≡ 5 (mod 11);   г)  x ≡ 15 (mod 169).

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 4
Название Арифметика остатков
Тема Деление с остатком. Арифметика остатков
параграф
Номер 3
Название Сравнения
Тема Деление с остатком. Арифметика остатков
задача
Номер 04.089

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .