Дано несколько белых и несколько чёрных точек. Из каждой белой точки идет стрелка в каждую чёрную, на каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на её концах?

   Решение

Докажите, что связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом.

   Решение

Пусть p – простое число и  p > 3.
  а) Докажите, что если разрешимо сравнение  x² + x + 1 ≡ 0 (mod p),  то  p ≡ 1 (mod 6).
  б) Выведите отсюда бесконечность множества простых чисел вида  6k + 1.

   Решение

Темы:    [ Простые числа и их свойства ] [ Малая теорема Ферма ] [ Уравнения в целых числах ] [ НОД и НОК. Взаимная простота ]

Сложность: 4 Классы: 9,10,11

Прислать комментарий

Условие

Пусть p – простое число и  p > 3.
  а) Докажите, что если разрешимо сравнение  x² + x + 1 ≡ 0 (mod p),  то  p ≡ 1 (mod 6).
  б) Выведите отсюда бесконечность множества простых чисел вида  6k + 1.

Решение

а) Решение x указанного сравнения удовлетворяет условиям  x^p–1 – 1 ≡ 0 (mod p)  и  x³ – 1 ≡ 0 (mod p).  Cогласно задаче 60507 а)  x^{(p–1, 3)} – 1 ≡ 0 (mod p).  Но x не сравнимо с 1 по модулю p, поскольку 3 на p не делится. Следовательно,  p – 1  делится на 3, то есть p имеет вид  6k + 1.

б) Пусть таких чисел всего n:  p₁, ..., p_n.  Рассмотрим число  x = 3p₁...p_n.  Пусть p – простой множитель числа  x² + x + 1.  Тогда  p > 3.  Согласно а)  p имеет вид  6k + 1.  С другой стороны,  x² + x + 1  не делится ни на одно из чисел p₁, ..., p_n. Противоречие.

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