Найти $n$ и $d$ так что $U_d(n)$ будет предоставлен набор.
Это сообщение, как-то связанное с тем, что я опубликовал ранее . В этом посте проблема решена так хорошо, однако я не могу использовать ту же идею в данной ситуации.
Предположим $n$ положительное целое число и $d$- его положительный делитель. Если$U(n)$ быть набором всех положительных целых чисел, меньших или равных $n$ и взаимно просты с $n$ и $$U_d(n)=\{x\in \mathbb{N}: x\equiv 1\pmod{d}\}$$ как найти $n,d$ такой, что $$U_d(n)=\{1,13,25,37\}$$ будет держать?
Ясно здесь $d$ делитель НОД $1-1,13-1,25-1,37-1$ т.е. $12$. Так$d=1,2,3,4,6,12$. Как показать$d$ является $12$только? В приведенной выше задаче было только два значения 1 и 7. Однако здесь мы также получаем составной делитель.
Как только мы это покажем, как найти $n$ тогда?
В основном то, что я ищу для общего подхода, если он есть. Кто-нибудь может мне помочь, пожалуйста?
Опубликовать работу
Получив подсказки и предложения (спасибо Эрику Вонгу и cgss), я пытаюсь решить эту проблему, насколько это возможно.
По ответу Эрика, теперь я понимаю, почему $d=12$только. Следовательно$U_d(n)$ становится сейчас $U_{12}(n)$. Более того,$12$ должен разделить $n$ и $n>37$ и каждый член $U_{12}(n)$ должен иметь форму $12k+1$. тем не мение$25\in U_{12}(n)$ что значит $25\in U(n)$ и другие $(25,n)=1$ подразумевая $(5,n)=1$. Таким образом$n$ должно быть 5 свободных.
Мы считаем, что $$n=2^{a_1}3^{a_2}.m$$ где $a_1\geqslant 2, a_2\geqslant 1, m\in \mathbb{N}$ с участием $(2.3.5, m)=1$. потом$$U_{12}(n)\simeq U\left(\frac{n}{12}\right)=U(2^{a_1-2}3^{a_2-1}m)$$ если только $(12, \frac{n}{12})=1$. Это говорит о том, что$a_1-2=0, a_2-1=0$ т.е. $a_1=2, a_2=1$ так что $n$ сводится к $n=2^2 3^1 m$.
Следовательно \begin{align*} &|U_{12}(n)|=|U(2^0 3^0 m)|\\ \Rightarrow &4=\varphi(m) \end{align*}
[Фактические ответы $n=48, d=12$. Это означает, что теперь мы должны показать$m=1$в приведенном выше уравнении. Решение$\varphi(m)=4$ находятся $m\in \{5,8,10,12\}$ Но как мы можем здесь показать $m=1$?]
Ответы
Я опубликовал гораздо более длинный ответ, не предполагая, что $d \mid n$, допускающий изрядное количество решений. Использование этого ограничения дает нам значительную структуру, а именно то, что$U_d(n)$ является подгруппой группы единиц $(\mathbb Z/n\mathbb Z)^\times$.
поскольку $U_d(n)$ имеет 4 элемента, каждый элемент имеет порядок деления $4$. Следовательно$n$ должен разделить оба $13^4 - 1$ и $25^4 - 1$, у которого НОД 48. Поскольку $n \ge 37$, это должно быть точно $48$. Мы легко заключаем, что$d=12$ как только мы узнаем $n$.
Сначала мы постараемся исключить меньшие значения $d$. Каждый из них попадает в одну из двух категорий$d \mid 4$ и $d \mid 6$ (эти два случая соответствуют двум простым факторам $12$).
Предположим $d \mid 4$: то факт, что $U_d(n)$ не содержит $5$ должно быть потому что $n$ делится на $5$, но тогда это противоречит $25 \in U_d(n)$.
Предположим $d \mid 6$: то факт, что $U_d(n)$ не содержит $7, 19, 31$ должно быть потому что $n$делится на все эти простые числа. Но потом$n > 169 = 13^2$, поэтому во избежание $U_d(n)$ содержащий $169$ нам нужно $n$ делиться на $13$, противоречащие $13 \in U_d(n)$.
Теперь, когда мы уверены $d=12$, есть несколько допустимых вариантов $n$, и некоторая проверка регистра неизбежна. Во-первых, в ассортименте$37 \le n < 49$, все значения $n$ должен работать, кроме тех, которые делятся на исключающие простые числа $5,13,37$.
Как только мы проверим значения $n \ge 49$нам нужно только рассмотреть $7 \mid n$. Вплоть до$n < 61$, этого также достаточно, чтобы исключить единственный $12k+1$ количество $49$ это вызывает проблемы.
После $n \ge 61$, нам нужно $7 \cdot 61 \mid n$. Но это заставляет$n \ge 169$, и, как указано выше, мы знаем, что это невозможно, потому что $13 \in U_d(n)$.
Общий принцип обеих частей этого аргумента (выделение $d$ а потом $n$) состоит в том, что исключения из-за некопримальности имеют тенденцию давать все большие и большие нижние оценки для $n$, и в конечном итоге заставить $[1,n]$ содержать число, состоящее только из простых чисел, о которых мы что-то знаем.