Часть 2. Разбор типовых задач с6

Тема 1. “Число по модулю…”

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

Необходимая теория.

Первообразный корень по модулю m ― целое число g такое, что и при где ― функция Эйлера.

Для первообразного корня g его степени g_­⁰ = 1,g,...,g^{φ(m) − 1} несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа a, взаимно простого с m, найдется показатель такой, что

Такое число называется индексом числа по основанию.

Например

Примеры.

№1

Решите в целых числах

Решение. Очевидно, что решений при отрицательных не будет, так как слева мы получим нецелое число. Предположим, что . Тогда будет справедливо:

Но у этого уравнения нет решений, так как видно, что не делится на 3. Значит представимо в виде (в зависимости какой остаток имеет при делении на 3), где – некоторое целое число. Следовательно, . Получаем, что если решения и есть, то только при .

Ответ:,

№2

Решить в целых числах

Решение. Сравнивая левую и правую части по , видим, что m может быть только нечетным числом, так как , то есть . Здесь мы исключаем случай, как тривиальное решение нашего уравнения. Итак, получаем . Сравниваем левую и правую части по , видим, что – четное число, так как . Итак, и . Предположим, что . Тогда

Сравнивая по , получаем . А это возможно только при . Тогда данное уравнение преобразуем в следующий вид:

Теперь сравним обе части уравнения по и получим, что

. А это возможно только при четных , так как То есть и . Это можно преобразовать в такой вид:

Но тогда левая часть делится на 10, а правая нет. Значит, наше предположение, что , неверно. Значит или .

При :

При :

Ответ: или

Номера для самостоятельного решения.

№1

Решить в целых числах

№2

Решить в целых числах

№3

Решить в целых числах

№4

Указать хотя бы одну пару решений

№5

Решить в целых числах

№6

Решить в целых числах

№7

Решить в целых числах

№8

Доказать, что уравнение не имеет решений в целых числах.

Ответы и решения.

№1

Приведем исходное уравнение к виду , откуда следует, что должно делиться на 3

При , при , при

Значит , найдем

Ответ: , (где )

№2

Сравнивая левую и правую части по mod 3, видим, что m может быть только нечетным числом, т.к. 2^m(-1)^m mod 3, т.е. m=2k+1. Здесь мы исключаем случай n=m=1 (k=0), как тривиальное решение нашего уравнения. Итак, получаем . Сравниваем левую и правую части по mod 4, видим, что n – четное число, т.к. 3ⁿ(-1)ⁿ mod 4. Итак, n=2j и . Отсюда имеем:

Но (p+1)(p-1) может делиться на 3 только при p=2 (разность между этими числами 2). Следовательно, ответ n=m=1 и n=2 и m=3.

Ответ: или

№3

Сравнивая левую и правую части по mod 4, видим, что n может быть только четным числом, т.к. 3ⁿ(-1)ⁿ mod 4, а 5ⁿ1mod 4. Итак, получаем . Сравним части равенства по mod 3, получим, что 5^k mod 31, т.е. k – четное число. Итак, , где k=2l. Мы получили опять сумму квадратов. 2^m = 2pq, значит q=1 и 3ⁿ = p² –q² = p² –1 = (p-1)(p+1). А это возможно только при p=2. Ч.т.д. см №2

Ответ:

№4

Ответ:

№5

Указание: рассмотреть случаи при

Ответ: или

№6

Указание: Действовать аналогично №1.

Ответ: или

№7

Указание: Применить формулу разности квадратов

Ответ: нет решений

№8

Указание: Так как , то и рассмотрим все возможные остатки от деления на 5