Как использовать КТО здесь? Или же как другими способами решить?
1 лайк
Какие у вас продвижения/идеи?
1 лайк
Задача сводится к такой
Доказать что для любого n свободного от квадратов существует целое m и простое p, что (n,p) = 1, и n | m^p+p
Пытался найти m зависящее от p и n, но не получилось.
1 лайк
Попробуйте чуть по другому взглянуть на задачу
Что значит n - свободно от квадратов? На самом деле, это значит что оно представимо в виде n = p_1p_2 \ldots p_k, где все p - различные простые числа.
Теперь попробуйте взять какой нибудь p_i из этих, и по КТО подобрать решение системы
\{p_i + m ^ {p _ i} \equiv 0 \mod{p_j}| \forall j \neq i\}
С этого момента и начинаются хитрости
7 лайков
уважаю. Как говорил один студент MIT: how can you claim you know math if you don’t know Chinese Remainder Theorem?
5 лайков
Не очень понял для какой именно системы и относительно чего подобрать решение…
То есть, если возьмем p_1 , то надо доказать что существует m: n| m^{p_{1}}+ p_1?
1 лайк
не n \mid m^{p_1} + p_1, потомучто p_1 мы уже выкинули
в этом случае система будет выглядеть так
p_2 \mid m^{p_1} + p_1
p_3 \mid m^{p_1} + p_1
\ldots
p_k \mid m^{p_1} + p_1
3 лайка
Я пытался доказать что 1, 2^{p_1},... p_i^{p_1} - Полная система вычетов mod p_i , но это неверно. Пытался использовать свойства первообразных корней - тоже не получилось.
По КТО существует X: X \equiv -p_1(mod \hspace{0.1cm} p_i) но доказать что существует
m: m^{p_1} \equiv X (mod \hspace{0.1cm} n) элементарными методами тоже не получилось. Да и положив m делящееся на p_1 тоже особо ничего не вышло. Похоже я что-то делаю не так?
На самом деле, это так
Вернемся к идее Амира:
Положим, что p - наибольший делитель числа n, то есть:
n = p* p_1 * ... * p_k, что p>p_1>p_2>...>p_k
Теперь, достаточно показать выполнимость второго условия
p^2 + p*m^p : n=p * p_1 *... * p_k \Leftrightarrow p+m^p : p_1 * p_2 * ... * p_k
Допустим, что доказали, что существует такое m_i, что p+m_i^p : p_i, тогда достаточно положить m \equiv m_i (mod p_i), для всех i = 1,2,....,k, что осуществимо по КТОО
Осталось показать силу делимости (что такие m_i действительно существуют)
Докажем для p_1, для остальных аналогично. Для дальнейшего удобства положим p_1 = q, m_1 = k
(!) p + k^p : q => k^p \equiv -p ( mod q)
Рассмотрим числа 1^p , 2^p, ... , (q-1)^p , q^p, докажем что это полной вычет(набор) остатков по (mod q), тогда однозначно найдется k^p \equiv -p, ведь -p - равен какому-то из остатков
Теперь, предположим противное, что x^p \equiv y^p (mod q), где x \mp y
=> x\equiv yc(mod q), исходя из (x,q) = 1 => x^p \equiv (yc)^p \equiv y^p * c^p
Но, x^p \equiv y^p(mod q)
=> y^p \equiv y^p*c^p =>y^p(c^p - 1) : q => c^p \equiv 1 (modq)
, причем c \mp 1, так как иначе x = y, тогда пусть a - показатель, значит a | p => a=p, то есть p - показатель=> phi(q) : p \Leftrightarrow q-1 : p, то есть
q > q-1 \geq p , что неверно,так как p - наибольший простой делитель - противоречие.
6 лайков