Как научиться находить остаток от деления большого числа на небольшое?
Продолжаю штурмовать математику. Хотелось бы, чтобы участники БВ немного помогли мне. Как в общем случае научиться находить остаток от деления какого-то очень крупного числа, в частности степени, на некое небольшое число?
Например, предлагается следующая задача: найти остаток от деления 2¹⁹⁹⁷ на 7. Это частный пример.
Но хочется понять общий алгоритм, дабы не обращаться каждый раз за помощью, а не то вопросы грозят стать бесконечными.
Не припоминаю, к сожалению, чтобы нас в школе учили такой задаче.
Конкретно в Вашей задаче остаток от деления можно вычислить по такому алгоритму.
Можно заметить, что степени 2 при делении на 7 дают в остатке только 1, 2 и 4. Это верно для первых трех степеней 2, считая с 0 (1, 2 и 4), а для следующих начинает повторяться, потому что (7m+k)*2 = 14n+2k. Если k=1 (это остаток предыдущей степени 2), то 2k=2,
если k=4, то 2k=8 и остаток от следующей степени 2 будет равен 1 (т.е. следующая степень 2 будет равна 15m+1).
Последовательность остатков от деления 2^n на 7 можно выразить формулой 2^mod3(n).
теория-чисел — Как найти остаток от деления числа в степени?
Найдите остаток от деления чисел:
а) 23 в степени 277 на 9;
б) 17 в степени 332 на 10.
Нужно подробное решение. Заранее большое спасибо!
задан 15 Дек ’14 21:23
1 ответ
Нужно воспользоваться свойствами сравнений и теоремой Эйлера. В первом примере 23 заменяем на 5 (остаток от деления на 9), и используем то, что $%\varphi(9)=6$%. Поскольку 5 взаимно просто с 9, из теоремы Эйлера следует, что $%5^6\equiv1\pmod9$%. Ввиду того, что $%277=6\cdot49+1$%, получается $%5^<277>\equiv(5^6)^<49>\cdot5\equiv5\pmod9$%, то есть остаток равен 5.
Во втором случае $%\varphi(10)=4$%, поэтому показатель степени делим с остатком на 4. Получается 0, поэтому остаток равен $%7^0=1$%. Здесь можно рассуждать даже проще, следя за последней цифрой произведения: ясно, что $%7^4$% оканчивается на 1, и при возведении в любую степень последняя цифра остаётся равна 1.
Остаток от деления числа в большой степени
Как можно быстро вычислить (x^n)mod y. Уже когда-то копал этот вопрос и обнаружил теорему Эйлера (теория чисел).
Не относится к вопросу: Но вся проблема в том, что я учусь в школе, и мы не проходили еще подобных выражений, найденных мною на wiki, и теории чисел. Объясните пожалуйста:
- Как использовать эту теорему на практике(например, реализация на C).
- (Не так важно, но просто интересно)Кратко значение формулировки на
wiki. Буду рад какой-нибудь статье, etc для тех, кто еще не знаком с теорией чисел и математикой >9 классов.
Наприклад ми хочемо обчислити 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) и т.д.
Найти остаток от деления числа в степени
5.16. Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос — одна тема.
Задания и решения набирать ручками. Один вопрос — одна тема. Для формул есть редактор.
Найти остаток от деления числа в степени на другое число
Всем привет! Впервые столкнулся с задачей, где нужно найти остаток от деления числа в степени на.
Найти остаток от деления числа
Как это решить? (используя теоремы Эйлера, Ферма и пр) Найти остаток от деления 1040+1240 на 25
Найти остаток от деления числа
Найти остаток от деления числа <2004>^ <2001>на 7. Я решал так: Поскольку число 2001 не делится.
Найти остаток от деления числа a на число b
a = 7^218 m=11 я нашел НоД не могу применить теорему Эйлера чтоб найти остаток , помогите.
Сообщение было отмечено spvln как решение
Решение
Первый пункт можно было сделать сразу, воспользовавшись фактом, что любое нечётное число, кроме оканчивающегося на 5, в степени 100 при делении на 1000 даёт остаток 1.
Добавлено через 18 минут
Здесь можно было ограничиться степенью 400 с помощью функции Эйлера .
2) тоже не сложно, учитывая, что 4 3 = 1 (mod 7) А 1 k = 1, как известно
Добавлено через 2 минуты
3) совсем хорошо 2 4 = 3 4 = 1 (mod 5)
Itogo = 2
Добавлено через 4 минуты
spvln, Основная идея такая. При любых умножениях (и сложениях тож) тут же заменяем результат остатком.
даны целые числа A, B и C. Выведите остаток от деления AB (A в степени B) на C
Помогите, исправить программу,пожалуйста. Условие: Вам даны целые числа A, B и C. Выведите.
Даны два целых числа A и B. Получить их частное, остаток от целочисленного деления A на B, а также значение степени числа AB
Даны два целых числа A и B. Получить их частное, остаток от целочисленного деления A на B, а также.
Остаток от деления a в степени b на n
Здравствуйте. Теорию чисел изучал давно, поэтому уже многого не помню. Какие есть способы решения.
Найти остаток от деления числа
В данной задаче нельзя использовать цикл, т.к. не уложитесь по времени. Время выполнения программы.
Выведите остаток от деления A^B (A в степени B) на C
Помогите, пожалуйста, исправить программу Вам даны целые числа A, B и C. Выведите остаток от.
Найти остаток от деления длинного числа на 7
Подскажите, как найти остаток от деления длинного числа (более 20 цифр) на 7?