Среда, 25.05.2022, 06:38
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                              Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
КОНСПЕКТЫ УРОКОВ МАТЕМАТИКИ [183]
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО МАТЕМАТИКЕ [81]
ЗАДАЧИ НА ВЫРОСТ [141]
НЕСТАНДАРТНЫЕ УРОКИ МАТЕМАТИКИ [26]
ДИДАКТИЧЕСКИЕ ИГРЫ НА УРОКЕ МАТЕМАТИКИ [37]
ИНФОРМАТИКА В ИГРАХ И ЗАДАЧАХ ДЛЯ ПЯТИКЛАССНИКОВ [120]
УЧЕБНЫЕ ПРОГРАММЫ ДЛЯ УЧИТЕЛЯ МАТЕМАТИКИ [5]
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ [28]
КОНСПЕКТЫ УРОКОВ ИНФОРМАТИКИ [81]
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ [25]
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ [10]
МУЛЬТИМЕДИА И ВИРТУАЛЬНЫЕ МИРЫ [20]
ПРЕЗЕНТАЦИИ ПО МАТЕМАТИКЕ [24]
ТЕОРИЯ ЧИСЕЛ [36]
СФЕРЛАНДИЯ [32]
ДИДАКТИЧЕСКИЙ МАТЕРИАЛ ПО ИНФОРМАТИКЕ [10]
В МИРЕ ЗАДАЧ [182]
УВЛЕКАТЕЛЬНАЯ ЭКСКУРСИЯ В МИР МАТЕМАТИКИ [30]
МАТЕМАТИКА В 10 КЛАССЕ [34]
ТРЕНИРОВОЧНЫЕ ЗАДАНИЯ ДЛЯ ПОДГОТОВКИ К ЕГЭ [155]
МЕТОДИЧЕСКИЕ НАРАБОТКИ [82]
ПРЕПОДАЕМ АЛГЕБРУ И НАЧАЛА МАТЕМАТИЧЕСКОГО АНАЛИЗА [143]
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКТ К УРОКАМ [27]
МИР МАТЕМАТИКИ [778]
ОНЛАЙН-УЧЕБНИК ИНФОРМАТИКИ. 6 КЛАСС [36]
ПОДГОТОВКА К ГИА [11]
САМОСТОЯТЕЛЬНЫЕ РАБОТЫ ПО АЛГЕБРЕ. 10 КЛАСС [45]
ПРЕЗЕНТАЦИИ ПО ИНФОРМАТИКЕ [26]
МАТЕМАТИКА В 5 КЛАССЕ [43]
МАТЕМАТИКА. 7 КЛАСС [69]
АЛГЕБРА. 8 КЛАСС [25]
МАТЕМАТИКА. 9 КЛАСС [9]
МАТЕМАТИЧЕСКИЕ ДИКТАНТЫ/АЛГЕБРА [29]
МАТЕМАТИЧЕСКИЕ ДИКТАНТЫ/ГЕОМЕТРИЯ [12]
ОЛИМПИАДЫ ПО МАТЕМАТИКЕ [55]
РАБОЧИЕ МАТЕРИАЛЫ К УРОКАМ ИНФОРМАТИКИ [90]
МАТЕМАТИЧЕСКИЕ ЧУДЕСА И ТАЙНЫ [70]
МАТЕМАТИКА 8 КЛАСС [9]
МАТЕМАТИКА. 6 КЛАСС [78]
ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ [12]
ЕГЭ ПО МАТЕМАТИКЕ [0]
ИСТОРИЯ РАЗВИТИЯ МАТЕМАТИЧЕСКОЙ НАУКИ [47]
ГЕОМЕТРИЯ [0]
ГЕОМЕТРИЯ. 8 КЛАСС [36]
ТЕСТЫ ПО ИНФОРМАТИКЕ [31]
ЗАДАЧНИКИ ПО ИНФОРМАТИКЕ [26]
ЗАДАНИЯ ПОВЫШЕННОГО УРОВНЯ СЛОЖНОСТИ [29]
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ [7]
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ [82]
Главная » Файлы » ТЕОРИЯ ЧИСЕЛ

Возведение сравнений в степень
07.12.2013, 10:58

Предположим вновь, что имеется сравнение

ab (mod m).

Как мы только что видели, можно умножить это сравнение на себя, получив

а2b2 (mod m).

Вообще можно, умножив это сравнение на себя нужное количество раз, получить

anbn (mod m)

для любого целого положительного числа m.

Пример. Из сравнения

8 ≡ -3 (mod 11)

после возведения в квадрат следует сравнение

64 ≡ 9 (mod 11),

а после возведения в куб получаем сравнение

512 ≡ -27 (mod 11).

Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому покажем, как можно продолжить процесс возведения в степень. Предположим, например, что мы хотим найти остаток сравнения

389 (mod 7).

Одним из путей для выполнения этого является повторное возведение в квадрат. Мы находим:

9 = 32 ≡ 2 (mod 7),

34 ≡ 4,

38 ≡ 16 ≡ 2,

364 ≡ 4 (mod 7).

Так как

89 = 64 + 16 + 8 + 1 = 26 + 24 + 23 + 1,

то отсюда следует, что

389 = 364 • З16 • З8 • 3 = 4 • 4 • 2 • 3 ≡ 5 (mod 7).

Таким образом, остаток (по модулю 7) есть 5, или, говоря другими словами, в соответствии с изложенным в § 2, последняя цифра числа З89, записанного в системе счисления при основании 7, равна 5.

В действительности, для того чтобы найти этот остаток, мы записали показатель степени

89 = 26 + 24 + 23 + 1 = (1, 0, 1, 1, 0, 0, 1)

в двоичной системе счисления. Повторным возведением в квадрат мы нашли остатки (по модулю 7) тех степеней числа 89, которые сами являются степенями числа 2:

1, 2, 4, 8, 16, 32, 64.

Соответствующий метод можно использовать для любых других оснований. Однако в частном случае бывает возможность упростить вычисление, если заметить особенности этого случая. Например, в случае, разобранном выше, мы можем отметить, что

33 ≡ -1 (mod 7),

З6 ≡ 1 (mod 7),

откуда заключаем, что

384 = (36)14 ≡ 1 (mod7).

Поэтому

389 = 384 • 33 • 32 ≡ 1 • (-1) • 2 = -2 ≡ 5 (mod 7),

как и раньше.

В качестве другой иллюстрации сказанного можно рассмотреть числа Ферма, с которыми мы познакомились в § 3 гл. 2:

Fn = 22ⁿ+1.

Первые пять чисел Ферма таковы:

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.

Отсюда можно высказать предположение:

десятичная запись всех чисел Ферма, за исключением F0 и F1 оканчивается цифрой 7.

Докажем с помощью сравнений, что это действительно так. Очевидно, что оно равносильно утверждению, что числа

22ⁿ, n = 2, 3…

оканчиваются цифрой 6. Это можно доказать по индукции. Заметим, что

2 = 16 ≡ 6 (mod 10),

2 = 256 ≡ 6 (mod 10),

24 = 65536 ≡ 6 (mod 10),

Более того, если мы возводим в квадрат число 2k, то результатом будет число

Предположим, что для некоторого значения t

;

возводя в квадрат это сравнение, мы находим, что

,

что и требовалось.

Категория: ТЕОРИЯ ЧИСЕЛ | Добавил: admin | Теги: урок, занимательные задачи для школьников, математика в школе, мир чисел, дидактический материал по математик, нестандартные задачи по математике
Просмотров: 974 | Загрузок: 0 | Рейтинг: 5.0/1
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ

ИНФОРМАТИКА В ШКОЛЕ

ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"

ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ИГРОВЫЕ ЗАДАНИЯ ПО ИНФОРМАТИКЕ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты
  • Статистика

    Онлайн всего: 3
    Гостей: 3
    Пользователей: 0
    Форма входа


    Copyright MyCorp © 2022
    Яндекс.Метрика Top.Mail.Ru