การหาข้อมูล $n$ และ $d$ ดังนั้น $U_d(n)$ จะได้รับชุด

Aug 16 2020

นี่เป็นเรื่องที่เกี่ยวข้องกับการอย่างใดอย่างหนึ่งซึ่งผมโพสต์ก่อนหน้านี้ ในโพสต์นี้ปัญหาได้รับการแก้ไขอย่างดีอย่างไรก็ตามฉันไม่สามารถใช้แนวคิดเดียวกันนี้ได้ในสถานการณ์ปัจจุบันนี้

สมมติ $n$ เป็นจำนวนเต็มบวกและ $d$คือตัวหารบวก ถ้า$U(n)$ เป็นการรวบรวมจำนวนเต็มบวกทั้งหมดที่น้อยกว่าหรือเท่ากับ $n$ และ coprime ถึง $n$ และ $$U_d(n)=\{x\in \mathbb{N}: x\equiv 1\pmod{d}\}$$ วิธีค้นหา $n,d$ ดังนั้น $$U_d(n)=\{1,13,25,37\}$$ จะถือ?

ชัดเจนที่นี่ $d$ เป็นตัวหารของ gcd ของ $1-1,13-1,25-1,37-1$ กล่าวคือ $12$. ดังนั้น$d=1,2,3,4,6,12$. วิธีการแสดง$d$ คือ $12$เท่านั้น? ในปัญหาข้างต้นมีค่า 1 และ 7 เพียง 2 ค่าเท่านั้นอย่างไรก็ตามตรงนี้เราได้ตัวหารคอมโพสิตเช่นกัน

เมื่อเราแสดงให้เห็นแล้วจะหาอย่างไร $n$ แล้ว?

โดยทั่วไปสิ่งที่ฉันกำลังค้นหาวิธีการทั่วไปหากมี มีใครช่วยฉันเกี่ยวกับเรื่องนี้ได้ไหม

โพสต์งาน

หลังจากได้รับคำแนะนำและคำแนะนำ (ขอบคุณทั้ง Erik Wong และ cgss) ฉันพยายามแก้ปัญหานี้ให้ได้มากที่สุด

จากคำตอบของ Erik ตอนนี้ฉันเข้าใจแล้วว่าทำไม $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)$$ iff $(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$?]

คำตอบ

1 ErickWong Aug 16 2020 at 12:42

ฉันโพสต์คำตอบที่ยาวกว่านี้มากโดยไม่มีข้อสันนิษฐานว่า $d \mid n$ซึ่งยอมรับวิธีแก้ปัญหาจำนวนพอสมควร การใช้ประโยชน์จากข้อ จำกัด นี้ทำให้เรามีโครงสร้างจำนวนมากกล่าวคือ$U_d(n)$ เป็นกลุ่มย่อยของกลุ่มหน่วย $(\mathbb Z/n\mathbb Z)^\times$.

ตั้งแต่ $U_d(n)$ มี 4 องค์ประกอบทุกองค์ประกอบมีการแบ่งลำดับ $4$. ดังนั้น$n$ ต้องหารทั้งคู่ $13^4 - 1$ และ $25^4 - 1$ซึ่ง gcd คือ 48. ตั้งแต่ $n \ge 37$มันจะต้องเป็นอย่างนั้น $48$. เราสรุปได้ง่ายๆว่า$d=12$ เมื่อเรารู้ $n$.

1 ErickWong Aug 16 2020 at 11:51

ก่อนอื่นเราจะพยายามแยกแยะค่าที่น้อยกว่าของ $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]$ เพื่อให้มีตัวเลขที่ประกอบด้วยช่วงเวลาที่เรารู้บางอย่างเท่านั้น