Dowiadywać się $n$ i $d$ po to aby $U_d(n)$ otrzyma zestaw.
To jest post związany w jakiś sposób z tym, który zamieściłem wcześniej . W tym poście problem jest tak ładnie rozwiązany, jednak nie mogę wykorzystać tego samego pomysłu w obecnej sytuacji.
Przypuszczać $n$ jest dodatnią liczbą całkowitą i $d$jest jego dodatnim dzielnikiem. Gdyby$U(n)$ być zbiorem wszystkich dodatnich liczb całkowitych mniejszych lub równych $n$ i względnie pierwsze do $n$ i $$U_d(n)=\{x\in \mathbb{N}: x\equiv 1\pmod{d}\}$$ jak znaleźć $n,d$ takie że $$U_d(n)=\{1,13,25,37\}$$ Będzie trzymać ?
Najwyraźniej tutaj $d$ jest dzielnikiem gcd of $1-1,13-1,25-1,37-1$ to znaczy $12$. Więc$d=1,2,3,4,6,12$. Jak pokazać$d$ jest $12$tylko? W powyższym zadaniu były tylko dwie wartości 1 i 7. Jednak i tutaj otrzymujemy dzielnik złożony.
Kiedy już to pokażemy, jak znaleźć $n$ następnie?
Zasadniczo to, czego szukam dla ogólnego podejścia, jeśli takie istnieje. Czy ktoś może mi w tym pomóc?
Praca po pracy
Po otrzymaniu podpowiedzi i sugestii (dzięki Erikowi Wongowi i cgss) staram się jak najbardziej rozwiązać ten problem.
Według odpowiedzi Erika, teraz rozumiem dlaczego $d=12$tylko. W związku z tym$U_d(n)$ staje się teraz $U_{12}(n)$. Ponadto,$12$ musi podzielić $n$ i $n>37$ i każdy członek $U_{12}(n)$ musi mieć formę $12k+1$. jednak$25\in U_{12}(n)$ co znaczy $25\in U(n)$ a więc $(25,n)=1$ sugerując $(5,n)=1$. A zatem$n$ musi być 5 za darmo.
Rozważamy zatem, $$n=2^{a_1}3^{a_2}.m$$ gdzie $a_1\geqslant 2, a_2\geqslant 1, m\in \mathbb{N}$ z $(2.3.5, m)=1$. Następnie$$U_{12}(n)\simeq U\left(\frac{n}{12}\right)=U(2^{a_1-2}3^{a_2-1}m)$$ iff $(12, \frac{n}{12})=1$. To sugeruje, że$a_1-2=0, a_2-1=0$ to znaczy $a_1=2, a_2=1$ po to aby $n$ zmniejsza się do $n=2^2 3^1 m$.
W związku z tym \begin{align*} &|U_{12}(n)|=|U(2^0 3^0 m)|\\ \Rightarrow &4=\varphi(m) \end{align*}
[Rzeczywiste odpowiedzi są $n=48, d=12$. Co oznacza, że teraz musimy się pokazać$m=1$w powyższym równaniu. Rozwiązanie$\varphi(m)=4$ są $m\in \{5,8,10,12\}$ Ale jak możemy tutaj pokazać $m=1$?]
Odpowiedzi
Opublikowałem znacznie dłuższą odpowiedź bez takiego założenia $d \mid n$, który dopuszcza wiele rozwiązań. Wykorzystanie tego ograniczenia daje nam znaczną część struktury, a mianowicie to$U_d(n)$ jest podgrupą grupy jednostek $(\mathbb Z/n\mathbb Z)^\times$.
Od $U_d(n)$ ma 4 elementy, każdy element ma podział porządkowy $4$. W związku z tym$n$ musi podzielić oba $13^4 - 1$ i $25^4 - 1$, którego gcd to 48. Od $n \ge 37$, to musi być dokładnie $48$. Z łatwością to stwierdzimy$d=12$ kiedy już wiemy $n$.
Najpierw spróbujemy wykluczyć mniejsze wartości $d$. Każdy z nich należy do jednej z dwóch kategorii$d \mid 4$ i $d \mid 6$ (te dwa przypadki odpowiadają dwóm głównym czynnikom $12$).
Przypuszczać $d \mid 4$: to fakt, że $U_d(n)$ nie zawiera $5$ musi być ponieważ $n$ jest podzielna przez $5$, ale to zaprzecza $25 \in U_d(n)$.
Przypuszczać $d \mid 6$: to fakt, że $U_d(n)$ nie zawiera $7, 19, 31$ musi być ponieważ $n$jest podzielna przez wszystkie te liczby pierwsze. Ale wtedy$n > 169 = 13^2$, więc aby tego uniknąć $U_d(n)$ zawierający $169$ potrzebujemy $n$ być podzielne przez $13$, zaprzeczając $13 \in U_d(n)$.
Teraz mamy pewność $d=12$, istnieje kilka prawidłowych opcji $n$, a pewna ilość sprawdzania przypadków jest nieunikniona. Po pierwsze w zakresie$37 \le n < 49$, wszystkie wartości $n$ powinny działać z wyjątkiem tych, które można podzielić przez wykluczające liczby pierwsze $5,13,37$.
Po sprawdzeniu wartości $n \ge 49$, musimy tylko rozważyć $7 \mid n$. Aż do$n < 61$, to również wystarczy, aby wykluczyć jedyny $12k+1$ numer $49$ to powoduje kłopoty.
Po $n \ge 61$, potrzebujemy $7 \cdot 61 \mid n$. Ale to zmusza$n \ge 169$i jak wyżej wiemy, że jest to niemożliwe, ponieważ $13 \in U_d(n)$.
Ogólna zasada w obu częściach tego argumentu (izolacja $d$ i wtedy $n$) polega na tym, że wykluczenia spowodowane brakiem roślinności mają tendencję do dawania coraz większych dolnych granic $n$i ostatecznie wymusić $[1,n]$ zawierać liczbę złożoną tylko z liczb pierwszych, o których coś wiemy.