На плоскости дано n точек, причем любые три из них можно накрыть кругом радиуса 1. Докажите, что тогда все n точек можно накрыть кругом радиуса 1.

   Решение

По заданному ненулевому x значение x⁸ можно найти за три арифметических действия: x² = x · x, x⁴ = x² · x², x⁸ = x⁴ · x⁴, а x¹⁵ — за пять действий: первые три — те же самые, затем x⁸ · x⁸ = x¹⁶ и x¹⁶ : x = x¹⁶. Докажите, что

а) x¹⁶ можно найти за 12 действий (умножений и делений);

б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log₂n действий.

   Решение

Темы:    [ Уравнения в целых числах ] [ Четность и нечетность ] [ Арифметика остатков (прочее) ]

Сложность: 3 Классы: 8,9,10

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

Условие

Доказать, что уравнение  m² + n² = 1980  не имеет решений в целых числах.

Подсказка

Числа m и n одной чётности.

Решение

  Если числа m и n разной чётности, то выражение слева нечётно, и равенства не будет.
  Если оба числа нечётны, то левая часть не делится на 4, а правая – делится.
  Если оба чётны  (m = 2k,  и n = 2s),  то  k² + s² = 495.  Но сумма двух квадратов не может быть сравнима с 3 по модулю 4.

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