ในขณะที่อ่าน หลักสูตรการเข้ารหัสทางคณิตศาสตร์ โดย Baumslag และคณะ ฉันมีปัญหาในการทำความเข้าใจบางส่วนของการพิสูจน์ทฤษฎีบท 2.3.3 นั่นคือเงื่อนไขที่จำเป็น:
อนุญาต $n\in\mathbb{N}$ กับ $n=2^m,m\geq1$ และปล่อยให้ $a,b\in\mathbb{Z}$ ดังนั้น $f:\mathbb{Z}_n\to\mathbb{Z}_n, x\to\overline{a}x+\overline{b}$ เป็นตัวสร้างความสอดคล้องเชิงเส้น ให้ต่อไป $s\in\{0,1,\dots,n-1\}$ ได้รับและ $x_0=\overline{s},x_1=f(x_0),\dots.$ จากนั้นเป็นลำดับ $x_0,x_1,\จุด$ เป็นช่วงที่มีระยะเวลาสูงสุด $n=2^m$ หากมีดังต่อไปนี้:
หลักฐานเป็นไปตามนี้สำหรับ $ม\geq2$ และด้วยเหตุนี้ $n\geq 4$:
สมมติว่า (1), (2) และ (3) เป็นที่น่าพอใจ แสดงว่าเราได้รับ lenth ระยะเวลาสูงสุด $n = 2^m$ สำหรับ $x_0=\โอเวอร์ไลน์{0}$ ซึ่งพิสูจน์ทฤษฎีบท
อนุญาต $x_0=\overline{0}.$ เราได้รับซ้ำ $$x_k = (\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})\overline{b}$$ สำหรับ $k\geq1.$ เนื่องจาก $ข$ เป็นเรื่องแปลกที่เรามี $$x_k=\overline{0}\iff(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=\overline{0}.$$ พวกเราเขียน $k = 2^rt$ กับ $r\geq0$ และ $t$ แปลก. แล้ว $$\overline{0}=(\overline{1}+\overline{a}+\dots+\overline{a}^{k-1})=(\overline{1}+\overline{a}+\ จุด+\overline{a}^{2^r-1})(\overline{1}+\overline{a}^{2^r}+(\overline{a}^{2^r})^2+ \dots+(\overline{a}^{2^r})^{t-1}).$$ ปัจจัยที่สองสอดคล้องกับ 1 โมดูโล 2 และด้วยเหตุนี้ $$2^m|(1+a+\dots+a^{k-1})\iff2^m|(1+a+\dots+a^{2^r-1}).$$
จำนวนเต็ม $1+a+\dots+a^{2^r-1}$ หารด้วย $2^r$ เนื่องจากเป็นผลรวมของ $2^r$ เลขคี่แต่หารไม่ลงตัว $2^{r+1}.$ ก็เป็นไปตามนั้น $r\geq m\iff2^m|k.$ ดังนั้น $x_k=\โอเวอร์ไลน์{0}$ เกิดขึ้นเพื่อ $k\geq1$ เป็นครั้งแรกเมื่อ $k=n=2^m$.
ฉันไม่ติดตามส่วนสุดท้ายเป็นตัวเอียง (จาก "จำนวนเต็ม...") ฉันจะดีใจถ้ามีคนสามารถสอนฉัน
มันไม่ค่อยแม่นยำนักแต่ควรสังเกตว่าจำนวนเต็ม $1+a+\cdots+a^{2^r-1}$ เป็นผลรวมของความก้าวหน้าทางเรขาคณิตด้วย $a\equiv1\pmod 4$ และหารด้วย $2^r$ แต่ไม่ $2^{r+1}$. หากต้องการดูสิ่งนี้เราเขียน $a=1+2^su$ กับ $u$ แปลกและ $s\ge2$ และดูว่า $$1+a+\cdots+a^{2^r}=\frac{a^{2^r}-1}{a-1}.$$ จากนั้นเราจะพิจารณาตัวเศษ $$a^{2^r}-1=(2^su+1)^{2^r}-1 =\left(1+2^r(2^su)+2^{r-1}(2^r-1)(2^{2s}u^2)+\cdots\right)$$ และ $$\left(1+2^r(2^su)+2^{r-1}(2^r-1)(2^{2s}u^2)+\cdots\right)\equiv 2^ {r+s}u\equiv 2^{r+s}\pmod{2^{r+s+1}}$$ ดังนั้น $2^{r+s}$ เป็นกำลังที่ใหญ่ที่สุดของ 2 หารตัวเศษ เช่นเดียวกัน $2^s$ เป็นกำลังที่ใหญ่ที่สุดของ 2 หารตัวส่วนและอื่นๆ $2^{r+s-s}=2^r$ เป็นกำลังที่ใหญ่ที่สุดของ 2 หาร $1+a+\cdots+a^{2^r-1}$. ก็เป็นไปตามนั้น $2^m|(1+a+\cdots+a^{k-1})$ ถ้าและถ้า $k$ เป็นรูปแบบ $2^rt$ กับ $t$ แปลกและ $r\ge ม$. ตามมาด้วยค่าดังกล่าวน้อยที่สุดของ $k$ ซึ่ง $x_k=\โอเวอร์ไลน์ 0$ เป็น $k=2^m$.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
