Как найти остаток от деления большого числа

Остаток от деления числа в большой степени

@ampawd После цикла может оказаться слишком поздно — если x^n на много порядков превысит предельное значение для данного типа.

12 сен 2017 в 18:34

@Harry какого типа ?? в вопросе ничего не говорится о порядках чисел, но раз уж так то даже если всего несколько раз вычислять mod в цикле а не на каждой итерации, то это было бы нелохой оптимизацией

12 сен 2017 в 18:41

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Наприклад ми хочемо обчислити 7 222 (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4 . Одже згідно з теоремою Ейлера 7 4 ≡ 1 (mod 10) і як наслідок

7 222 ≡ 7 4×55 + 2 ≡ (7 4 ) 55 x 7 2 ≡ 1 55 x 7 2 ≡ 49 ≡ 9 (mod 10).

Моя попытка перевода:

Например мы хотим вычислить «7 222 (mod 10)». 7 и 10 являются взаимно-простыми и φ(10) = 4 (это число натуральных чисел не больших чем 10 и являющихся взаимнопростыми по отношению к 10 . Это следующие числа: 1,3,7,9 и всего их 4 ).

Следовательно согласно теореме Эйлера 7 4 ≡ 1 (mod 10) и как следствие:

7 222 ≡ 7 4×55 + 2 ≡ (7 4 ) 55 x 7 2 ≡ 1 55 x 7 2 ≡ 49 ≡ 9 (mod 10).

Следствия из теоремы:

если a φ(n) ≡ 1 (mod n), то и (a φ(n) ) k ≡ 1 (mod n) для любого положительного k , т.к.

(a φ(n) ) k ≡ a φ(n) mod n * (a φ(n) ) k — 1 mod n ≡ (a φ(n) ) k — 1 (mod n) и т.д.

теория-чисел — Как найти остаток от деления числа в степени?

Найдите остаток от деления чисел:
а) 23 в степени 277 на 9;
б) 17 в степени 332 на 10.
Нужно подробное решение. Заранее большое спасибо!

задан 15 Дек ’14 21:23

(16 Июн ’15 8:09) Dims Vs

1 ответ

Нужно воспользоваться свойствами сравнений и теоремой Эйлера. В первом примере 23 заменяем на 5 (остаток от деления на 9), и используем то, что $%\varphi(9)=6$%. Поскольку 5 взаимно просто с 9, из теоремы Эйлера следует, что $%5^6\equiv1\pmod9$%. Ввиду того, что $%277=6\cdot49+1$%, получается $%5^\equiv(5^6)^\cdot5\equiv5\pmod9$%, то есть остаток равен 5.

Во втором случае $%\varphi(10)=4$%, поэтому показатель степени делим с остатком на 4. Получается 0, поэтому остаток равен $%7^0=1$%. Здесь можно рассуждать даже проще, следя за последней цифрой произведения: ясно, что $%7^4$% оканчивается на 1, и при возведении в любую степень последняя цифра остаётся равна 1.

отвечен 15 Дек ’14 21:32

falcao
299k ● 9 ● 38 ● 53

Быстрое нахождениe остатка от деления больших чисел для делителей специального вида

В этой статье я расскажу об одном способе вычисления x mod p, для p вида (2 ** n — omega), причём omega значительно меньше 2 ** n. Напишу генератор констант на Python. Приведу пару игрушечных примеров на С++, для которых может быть выполнено исчерпывающее тестирование для всех возможных аргументов. А в качестве серьёзной проверки — вычислю 97! mod (2 ** 256 — 2 ** 32 — 977).

Зачем это нужно?

• Если у вас под рукой нет подходящей библиотеки для длинной арифметики (или чудесного Python’а);
• Если вам доступны только сложения, умножения и битовые сдвиги, а нужно реализовать вычисление остатка от деления;
• Для оптимизации под конкретные делители, если скорость работы универсальных библиотек не устраивает.

Теория

• Делитель p вида (2 ** n — omega), причём omega значительно меньше (2 ** n);
• Делимое x, размера m бит, причём m > n;
• Размер битового слова s, s

Для начала, заметим что (2 ** n) mod p = (2 ** n) mod (2 ** n — omega) == omega.

Пусть x_low — младшие n бит числа x, а x_high — старшие (m — n) бит числа x, т.е. x можно представить в виде x_low + x_high * (2 ** n).

Тогда x mod p = (x_low + x_high * (2 ** n)) mod p == x_low + x_high * omega (mod p). Применение этой формулы не гарантирует, что результат окажется в диапазоне [0; p — 1], однако при достаточно большом количестве рекурсивных применений результат окажется в диапазоне [0; (2 ** n) — 1]. С вероятностью примерно omega / (2 ** n) потребуется вычесть p из результата, чтобы он оказался в диапазоне [0; p — 1].

Разобьем x на слова w[i] размера s бит: x = sum(i = 0 .. (m / s — 1); w[i] * 2 ** (i * s)). К такому представлению делимого также можно применить формулу x mod p == x_low + x_high * omega (mod p); в результате показатель степени у старших слов уменьшится, а коэффициент при слове будет домножен на omega. Применив формулу рекурсивно достаточное количество раз можем добиться того, что коэффициент при каждом битовом слове будет меньше (2 ** n). То есть, будет получено представление x mod p в виде суммы битовых слов w[i] размера s бит, домноженных на коэффициенты размером не более n бит.

Генератор коэффициентов на Python

def build_reducer(input_bits, target_bits, limb_size_bits, omega): num_input_limbs = input_bits // limb_size_bits target_limit = 2 ** target_bits def split_and_reduce(coeff): low_part = coeff % target_limit high_part = coeff // target_limit return low_part + high_part * omega coeffs = [2 ** (limb_size_bits * i) for i in range(num_input_limbs)] while any([k >= target_limit for k in coeffs]): coeffs = [split_and_reduce(k) for k in coeffs] return coeffs def print_reducer(coeffs, target_bits): for k in coeffs: print('%0*x' % (target_bits // 4, k))

• input_bits — количество бит на входе (m);
• target_bits — желаемое количество бит на выходе (n);
• limb_size_bits — размер битового слова (s);
• omega — одна из констант, задающих делитель (2 ** n — omega).

1. Определяем количество битовых слов размера s, необходимых для представления числа из m бит;
2. Находим степень двойки (2 ** n), по границе которой будем разбивать каждый коэффициент на «младшие» (1..n) и «старшие» (n+1..m) биты;
3. Находим степени двойки, являющиеся коэффициентами битовых слов в разложении делимого;
4. Пока хотя бы один из коэффициентов превышает (2 ** n) — дробим такие коэффициенты на «младшие» и «старшие» биты и пересобираем из них новый коэффициент: («младшие биты» + «старшие биты» * omega).

Примеры работы генератора коэффициентов:

1. Коэффициенты для сокращения 32-битного числа до 8-битного по модулю (2 ** 8 — 17) = 239; размер слова — 8 бит:

>>> r = build_reducer(32, 8, 8, 17) >>> print_reducer(r, 8) 01 11 32 85

1. Коэффициенты для сокращения 32-битного числа до 16-битного по модулю (2 ** 16 — 666) = 64870; размер слова — 8 бит:

>>> r = build_reducer(32, 16, 8, 666) >>> print_reducer(r, 16) 0001 0100 029a 9f34

1. Коэффициенты для сокращения 512-битного числа до 256-битного по модулю (2 ** 256 — 2 ** 32 — 977); размер слова — 32 бита; для удобства разряды сгруппированы по 32 бита:

>>> r = build_reducer(512, 256, 32, 2 ** 32 + 977) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000000_00000000_00000000_00000001_000003d1 00000000_00000000_00000000_00000000_00000000_00000001_000003d1_00000000 00000000_00000000_00000000_00000000_00000001_000003d1_00000000_00000000 00000000_00000000_00000000_00000001_000003d1_00000000_00000000_00000000 00000000_00000000_00000001_000003d1_00000000_00000000_00000000_00000000 00000000_00000001_000003d1_00000000_00000000_00000000_00000000_00000000 00000001_000003d1_00000000_00000000_00000000_00000000_00000000_00000000 000003d1_00000000_00000000_00000000_00000000_00000000_00000001_000003d1

1. Коэффициенты для сокращения 512-битного числа до 256-битного по модулю (2 ** 256 — 2 ** 32 — 977); размер слова — 64 бита; для удобства разряды сгруппированы по 64 бита:

>>> r = build_reducer(512, 256, 64, 2 ** 32 + 977) >>> print_reducer(r, 256) 0000000000000000_0000000000000000_0000000000000000_0000000000000001 0000000000000000_0000000000000000_0000000000000001_0000000000000000 0000000000000000_0000000000000001_0000000000000000_0000000000000000 0000000000000001_0000000000000000_0000000000000000_0000000000000000 0000000000000000_0000000000000000_0000000000000000_00000001000003d1 0000000000000000_0000000000000000_00000001000003d1_0000000000000000 0000000000000000_00000001000003d1_0000000000000000_0000000000000000 00000001000003d1_0000000000000000_0000000000000000_0000000000000000

1. Коэффициенты для сокращения 512-битного числа до 256-битного по модулю (2 ** 256 — 432420386565659656852420866394968145599); размер слова — 32 бита; для удобства разряды сгруппированы по 32 бита:

>>> r = build_reducer(512, 256, 32, 432420386565659656852420866394968145599) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf 00000000_00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000 00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000_00000000 00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000_00000000_00000000 45512319_50b75fc4_402da173_2fc9bec0_45512319_50b75fc4_402da173_2fc9bebf 50b75fc4_402da173_2fc9bec0_9d671cd5_1b343a1b_66926b57_d2a4c1c6_1536bda7 402da173_2fc9bec0_9d671cd5_81c69bc5_9509b0b0_74ec0aea_8f564d66_7ec7eb3c 2fc9bec0_9d671cd5_81c69bc5_e697f5e4_1f12c33a_0a7b6f4e_3302b92e_a029cecd

1. Коэффициенты для сокращения 512-битного числа до 256-битного по модулю (2 ** 256 — 432420386565659656852420866394968145599); размер слова — 64 бита; для удобства разряды сгруппированы по 64 бита:

>>> r = build_reducer(512, 256, 64, 432420386565659656852420866394968145599) >>> print_reducer(r, 256) 0000000000000000_0000000000000000_0000000000000000_0000000000000001 0000000000000000_0000000000000000_0000000000000001_0000000000000000 0000000000000000_0000000000000001_0000000000000000_0000000000000000 0000000000000001_0000000000000000_0000000000000000_0000000000000000 0000000000000000_0000000000000001_4551231950b75fc4_402da1732fc9bebf 0000000000000001_4551231950b75fc4_402da1732fc9bebf_0000000000000000 4551231950b75fc4_402da1732fc9bec0_4551231950b75fc4_402da1732fc9bebf 402da1732fc9bec0_9d671cd581c69bc5_9509b0b074ec0aea_8f564d667ec7eb3c

p.s. (2 ** 256 — 2 ** 32 — 977) — параметр p эллиптической кривой SECP256K1; (2 ** 256 — 432420386565659656852420866394968145599) — параметр N эллиптической кривой SECP256K1. (См. https://en.bitcoin.it/wiki/Secp256k1)

Что можно сказать, глядя на эти коэффициенты:

1. Чем меньше единичных бит в представлении числа omega — тем проще выглядят коэффициенты;
2. Чем меньше размер битового слова — тем быстрее происходит перенос в младшие разряды и тем самым сокращается длина битового представления x mod p;
3. Коэффициенты при младших битовых словах содержат по одному единичному биту на позициях, соответствующим началам битовых слов. Т.е. первые n бит числа берутся как есть, и к ним прибавляются группы старших битов, помноженные на вычисленные коэффициенты.

Игрушечные примеры

Для первого примера коэффициентов:

const uint32_t modulus = (1 uint32_t mod_manual(uint32_t x) < while (x & 0xFFFFFF00) < uint32_t buffer = 0; buffer += 0x01 * (x & 0xFF); x >>= 8; buffer += 0x11 * (x & 0xFF); x >>= 8; buffer += 0x32 * (x & 0xFF); x >>= 8; buffer += 0x85 * (x & 0xFF); x >>= 8; x = buffer; > return (x

Для второго примера коэффициентов:

const uint32_t modulus = (1 uint32_t mod_manual(uint32_t x) < while (x & 0xFFFF0000) < uint32_t buffer = (x & 0xFFFF); x >>= 16; buffer += 0x029a * (x & 0xFF); x >>= 8; buffer += 0x9f34 * (x & 0xFF); x >>= 8; x = buffer; > return (x

Программа для исчерпывающего тестирования двух примеров выше:

#include // put some implementation of mod_exact() and mod_manual() here int main() < uint32_t number = 0, fails = 0; do < uint32_t exact = mod_exact(number); uint32_t manual = mod_manual(number); fails += ((exact == manual) ? 0 : 1); if ((number & 0x00FFFFFF) == 0) < std::cout number++; > while (number != 0); std::cout void reduce_512(const uint32_t x[16], uint32_t y[8]) < // check if any of bits[257..512] is set uint32_t mask = 0; for (int i = 8; i < 16; mask |= x[i++]); if (mask == 0) return; uint64_t buffer = 0; // stage 1: reduce 16 limbs into 9 // (2 ** 0) * (w[0] + 977 * w[8] + 977 * w[15]) + buffer += (uint64_t)x[0] + 977 * (uint64_t)x[8] + 977 * (uint64_t)x[15]; y[0] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 32) * (w[1] + w[8] + 977 * w[9] + w[15]) + buffer += (uint64_t)x[1] + (uint64_t)x[8] + 977 * (uint64_t)x[9] + (uint64_t)x[15]; y[1] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 64) * (w[2] + w[9] + 977 * w[10]) + buffer += (uint64_t)x[2] + (uint64_t)x[9] + 977 * (uint64_t)x[10]; y[2] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 96) * (w[3] + w[10] + 977 * w[11]) + buffer += (uint64_t)x[3] + (uint64_t)x[10] + 977 * (uint64_t)x[11]; y[3] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 128) * (w[4] + w[11] + 977 * w[12]) + buffer += (uint64_t)x[4] + (uint64_t)x[11] + 977 * (uint64_t)x[12]; y[4] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 160) * (w[5] + w[12] + 977 * w[13]) + buffer += (uint64_t)x[5] + (uint64_t)x[12] + 977 * (uint64_t)x[13]; y[5] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 192) * (w[6] + w[13] + 977 * w[14]) + buffer += (uint64_t)x[6] + (uint64_t)x[13] + 977 * (uint64_t)x[14]; y[6] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 224) * (w[7] + w[14] + 977 * w[15]) buffer += (uint64_t)x[7] + (uint64_t)x[14] + 977 * (uint64_t)x[15]; y[7] = buffer & 0xFFFFFFFF; buffer >>= 32; // stage 2: reduce 9 limbs into 8 while (buffer != 0) < // save 9th limb (10 bits max) and flush buffer const uint64_t overflow256 = buffer & 0xFFFFFFFF; buffer >>= 32; assert(buffer == 0); // (2 ** 0) * (w[0] + 977 * w[8]) + buffer += (uint64_t)y[0] + 977 * overflow256; y[0] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 32)* (w[1] + w[8]) + buffer += (uint64_t)y[1] + overflow256; y[1] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 64) * w[2] + buffer += (uint64_t)y[2]; y[2] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 96) * w[3] + buffer += (uint64_t)y[3]; y[3] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 128) * w[4] + buffer += (uint64_t)y[4]; y[4] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 160) * w[5] + buffer += (uint64_t)y[5]; y[5] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 192) * w[6] + buffer += (uint64_t)y[6]; y[6] = buffer & 0xFFFFFFFF; buffer >>= 32; // (2 ** 224) * w[7] buffer += (uint64_t)y[7]; y[7] = buffer & 0xFFFFFFFF; buffer >>= 32; > // 512 bits are now reduced to 256 bits, however the result may exceed // (2^256 - 2^32 - 977) and an additional subtraction may be necessary >

Тестовая программа, в которую зашита пара чисел — факториал 97 (число размером около 500 бит) и правильный результат вычисления (97! mod (2 ** 256 — 2 ** 32 — 977)), необходимый для проверки результатов работы функции:

#include #include void reduce_512(const uint32_t x[16], uint32_t y[8]) < // put function code here >int main() < // math.factorial(97), this is about 500 bits long // least significant limbs go first const uint32_t x[16] = < 0x00000000, 0x00000000, 0xc0000000, 0xc63bc975, 0xcb0e1818, 0xfe74c03b, 0x13559f1a, 0xca00bb56, 0xef9d44bc, 0xf57bf161, 0xf3e3d5c3, 0xab918234, 0xb69daa20, 0x4532ed8b, 0xafb0a77f, 0x01d62e2f >; // math.factorial(97) % (2 ** 256 - 2 ** 32 - 977) // least significant limbs go first const uint32_t y_expected[8] = < 0x7999b163, 0xcf77a9bd, 0x7dfec23d, 0x80718b50, 0x6655e0fc, 0xcc6efc90, 0xd9b7c95d, 0x7c17a6d2 >; uint32_t y[8]; reduce_512(x, y); // stage 2 is ran once for this input // print/verify bool ok = true; for (int i = 0; i < 8; ok &= (y[i] == y_expected[i]), i++) < std::cout std::cout

p.s. Все примеры проверены в Microsoft Visual Studio 2022 (v17.5.4)

• алгоритмы
• остаток от деления
• длинная арифметика

Найти остаток от деления числа в степени

Помогите пожалуйста! Найдите остаток от деления чисел с подробным объяснением:
1) 23^277 на 9
2) 17^332 на 10
Хочется понять, как это делается. Заранее большое спасибо!

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 15 дек 2014, 22:20

Последняя инстанция

Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Вы знакомы с таким представлением ваших задач?

[math]23^\equiv x\pmod 9[/math]

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 16 дек 2014, 11:38

Оракул

Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

гуглите "малая теорема Ферма", "теорема Эйлера", "китайская теорема об остатках", "функция Кармайкла".

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 18 дек 2014, 16:07

Одарённый

Зарегистрирован:
05 дек 2014, 15:39
Сообщений: 129
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 3

Допустим нам нужно найти остаток от деления числа [math]A^n[/math] на число [math]B[/math] .
Остаток от деления [math]A[/math] на [math]B[/math] мы знаем. (Пусть он будет - [math]d[/math] .) Т.е.:

[math]A=kB+d[/math]

Где [math]k[/math] - какое-то целое. (не важно - какое именно)

Задача свелась к нахождению остатка от деления такого выражения:

[math](kB+d)^n[/math]

Если возвести в степень сумму, то мы получим сумму степеней, в которой все слагаемые делятся на [math]B[/math] , кроме одного слагаемого. И это слагаемое [math]d^n[/math] . Т.е., задача свелась к нахождению остатка от деления от степени остатка от деления. Т.е.

[math]A^nmod B=d^nmod B[/math]
[math]23^<277>mod\ 9=5^<277>mod\ 9[/math]

[math]5^<277>mod\ 9=(5\cdot 25^)mod\ 9=(5\cdot 7^)mod\ 9=(5\cdot 49^)mod\ 9=(5\cdot 4^)mod\ 9=(5\cdot 64^)mod\ 9=(5\cdot 1^)mod\ 9=5\ mod\ 9=5[/math]

На радиофаке (где я учился) теории чисел не было.
Поэтому я действую по прицыпу, изложенному в старом еврейском анекдоте:

-- Авраам, ты умеешь играть на скрипке?
(Пауза. Задумался.)
-- Никогда не пробовал. Наверно умею.

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 18 дек 2014, 17:32

Последняя инстанция

Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Все гораздо проще, если знать теорию сравнений.
Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 19 дек 2014, 17:26

Одарённый

Зарегистрирован:
05 дек 2014, 15:39
Сообщений: 129
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 3

vorvalm писал(а):
Все гораздо проще, если знать теорию сравнений.
Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 19 дек 2014, 18:03

Последняя инстанция

Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Masterov писал(а):

Не надо ёрничать. По теореме Эйлера при (a,m)=1

[math]a^\equiv 1\pmod m[/math] или [math]a^\equiv 1\pmod m[/math]

В данном случае 1) [math]\varphi(9)=6[/math] и 2) [math]\varphi(10)=4[/math]

А дальше, я думаю, понятно и школьнику.

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 19 дек 2014, 18:14

Одарённый

Зарегистрирован:
05 дек 2014, 15:39
Сообщений: 129
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 3

vorvalm писал(а):
[math]a^\equiv 1\pmod m[/math]

Мне эта запись непонятна.
Я много раз её в Википедии встречал,
но никто её определения не дает.

Я понимаю, что это значит:

[math]a\ mod\ m=d[/math]

Это я понимаю.
А та запись похожа на бред.

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 19 дек 2014, 18:36

Последняя инстанция

Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Masterov писал(а):
vorvalm писал(а):
[math]a^\equiv 1\pmod m[/math]
Мне эта запись непонятна.
Я много раз её в Википедии встречал,
но никто её определения не дает.

Это азы теории чисел. Смотрите не Википедию, но А.А.Бухштаба. Это означает:

Заголовок сообщения: Re: Найти остаток от деления числа в степени
Добавлено: 19 дек 2014, 20:18

Одарённый

Зарегистрирован:
05 дек 2014, 15:39
Сообщений: 129
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 3

vorvalm писал(а):
Masterov писал(а):
vorvalm писал(а):
[math]a^\equiv 1\pmod m[/math]
Мне эта запись непонятна.
Я много раз её в Википедии встречал,
но никто её определения не дает.

Это азы теории чисел. Смотрите не Википедию, но А.А.Бухштаба. Это означает:

1. Если в Википедии это понятие встречается, а нигде это не поясняется (в Википедии), то это - не правильно.

2. Я имею очень неплохую подготовку прикладного математика по специальности "нелинейная динамика". На форуме опубликована моя монография, где изложены три метода (два - авторские) анализа нелинейных моделей в интегральной форме записи (нелинейные интегро-дифференциальные уравнения). Я имею математическую подготовку, которой могут позавидовать многие физики, но даже я не знаю, что означает запись:
[math]a^\equiv 1\pmod m[/math]
Если я не понимаю этой записи, то (очевидно) её не понимают большинство физиков.
(Проверьте сами.)

Я это говорю к тому, что математики (и не только математики, но математики - особенно) выдумывают понятия и записи, которые понятны только им. А потом жонглируют ими и раздувают щёки, дескать - вот мы какие умные, нас даже не понимают.

Физики тоже так делают. (Выдумывают жаргонные словечки, а потом ими публично жонглируют.)

Всё это делает бездари, чтобы создать видимость научной деятельности.
На то, чтобы придумать что-то полезное людям, у них просто не хватает потенции учёного.

Последний раз редактировалось Masterov 19 дек 2014, 20:54, всего редактировалось 2 раз(а).