Соотношения сравнения, делимость и арифметические функции
Введено| English | Значение |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | конгруэнтность |
| totient/ˈtəʊʃənt/ | функция Эйлера |
Решение перед ответом
- Машина повторяет один цикл каждые четыре минуты, а другой — каждые семь. Одновременное положение — это задача наowner congruence, а не десятичное приближение.
- Ваша цель: Решать линейные congruence с использованием условий gcd.
Прочитайте соотношение
- Уравнение ax≡b по модулю n имеет решение тогда и только тогда, когда d=gcd(a,n) делит b. Если это так, разделите a, b и n на d, чтобы получить уравнение с обратимым коэффициентом. Оно имеет одно решение по модулю n/d и d различных решений по модулю n. Деление коэффициента при сохранении исходного модуля обычно приводит к потере решений. Разложение на простые множители дает еще один инструмент делимости: если n^k должно быть кратно произведению степеней простых p^a, то каждый показатель простого в n должен быть не менее ceil(a/k). Эти минимальные показатели независимо порождают наименьшее положительное допустимое n. Для n⁴, кратного 2⁷·3⁵, n должно содержать 2² и 3², поэтому наименьшее значение равно 36. Это условие показателей простых, а не congruence, решаемое через模块化 деление.
- Объединять взаимно простые congruence с помощью китайской теоремы об остатках.
How many distinct solutions modulo 18 satisfy 6x≡12?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
Используйте определяющее правило
- Расширенный алгоритм Евклида выражает gcd(a,n) как ua+vn. Когда gcd равен 1, u является обратным элементом a по модулю n. Выберите представитель в требуемом диапазоне после приведения. Для 7 и 26, 1=15·7−4·26, следовательно, 15 является обратным элементом для 7 по модулю 26; проверьте произведение, чтобы избежать ошибки знака.
- Применяйте теорему Эйлера только к обратимым вычетам.
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
Проверьте условия
- Для взаимно простых положительных модулей m,n китайская теорема об остатках дает ровно одно решение по модулю mn для каждой пары условий вычетов. Подставьте x=r+mk во второе congruence и решите относительно k. Если модули не являются взаимно простыми, их значения вычетов должны совпадать по модулю gcd(m,n); при согласованности единственность достигается по модулю наименьшего общего кратного, а не произведения.
- Используйте делимость показателей простых для нахождения наименьших допустимых целых чисел.
Решите 6x≡9 по модулю 15. НОД равен 3 и делит 9. Разделите все три величины, чтобы получить 2x≡3 по модулю 5; обратный элемент к 2 равен 3, поэтому x≡9≡4 по модулю 5. Исходные решения по модулю 15 равны 4,9,14. Для x≡2 по модулю 4 и x≡3 по модулю 7, запишите x=2+4k; тогда 4k≡1 по модулю 7, откуда k≡2. Следовательно, x≡10 по модулю 28.
phi(12) equals ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
Применяйте формат задания
- Функция Эйлера φ(n) считает вычеты, взаимно простые с n. Для различных простых делителей p, φ(n)=n умноженное на произведение (1−1/p). Теорема Эйлена дает a^φ(n)≡1 только когда gcd(a,n)=1. Случай простого числа — малая теорема Ферма. Уменьшайте показатели степени только после проверки этого условия; необратимый элемент может стать нулем под действием повторных степеней.
- Используйте делимость показателей простых для нахождения наименьших допустимых целых чисел.
Выражение a^φ(n)≡1 ложно для произвольного a. Например, 2 не является обратимым по модулю 8, а 2^4 равно нулю по модулю 8.
Какой ответ подходит к данному случаю?
Решать линейные сравнения, используя условия на НОД
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
Сохраняйте различия
- congruence — Равенство вычетов, поскольку модуль делит их разность.
- totient — Количество вычетов, взаимно простых с положительным целым модулем.
- Решать линейные congruence с использованием условий gcd.
- Объединять взаимно простые congruence с помощью китайской теоремы об остатках.
- Применяйте теорему Эйлера только к обратимым вычетам.
- Используйте делимость показателей простых для нахождения наименьших допустимых целых чисел.
Match each term with its precise meaning in this lesson.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.