2^100 mod 7 в арифметике равно 2, а на машине с 53 битами — 0

Остаток вычисляется из округлённого частного, поэтому ответ на самом большом шаге — честное доказательство предела.

Арифметика и функции · Уровень: Экзамен и олимпиада · Обновлено 2026-11-10

Число 2^100 равно 1267650600228229401496703205376, тридцать одна цифра, и экран показывает его как 1.2676506002282⋅10+30. Спросите в том же окне 2^100 mod 7, и ответ будет 0. Спросите 2^4 mod 7, и будет 2 — вот это правильно: 2^3 = 8 ≡ 1 (mod 7), значит 2^99 ≡ 1 и 2^100 ≡ 2, или, что то же, 2^6 ≡ 1 и 100 mod 6 = 4, что сводит весь вопрос к 2^4 mod 7.

Со степенью всё в порядке; неверен остаток. Double хранит пятьдесят три бита, поэтому ближайшее представимое значение к 2^100/7 отстоит примерно на 10^13, а остаток, вычисленный как a − 7·floor(a/7), наследует ошибку, намного большую модуля. Правильный метод никогда не даёт числу вырасти: сначала привести, потом возводить в степень — именно это делает модульное возведение в степень в любой криптографической библиотеке, и это причина, по которой RSA работает с тысячебитными числами на аппаратуре, которая хранит пятьдесят три. Это тот же потолок, который делает 2^53 последним точным целочисленным счётчиком.

Ответ

0

Как его читать

2^100 mod 7 на калькуляторе — ответ машины, а не арифметики. Вторая ссылка — 2^6 mod 7 = 1, период; третья — сведённый вопрос 2^4 mod 7 = 2, истинное значение.

Источник

2^100 = 1267650600228229401496703205376 is exact in binary floating point, being a power of two, but the quotient by 7 has thirty significant digits and IEEE-754 binary64 carries only about sixteen, so a mod implemented as a − b·floor(a/b) returns a remainder taken from the rounded quotient

Пересчитать в калькуляторе

Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.

Это независимый сторонний информационный сайт. Он не связан с Casio, Texas Instruments или их дистрибьюторами, не спонсируется ими и не имеет их авторизации. Названия моделей и продуктов — товарные знаки соответствующих правообладателей; они приведены здесь только для идентификации устройств.

Последовательности нажатий клавиш в этих справочниках составлены на основе собственных данных о раскладке этого сайта — тех же данных, которые отображает онлайн-калькулятор, — а также общедоступных сведений о продуктах. Характеристики и региональные конфигурации проверяются на реальном устройстве и по последним материалам производителя.