Number Theory Marathon

[PP_nine]

เข้ามาปล่อยโจทย์ละกัน เห็นเงียบเหงามานาน



นิยาม : สำหรับเมตริกซ์ $A=[a_{ij}]_{m \times m}$ และ $B=[b_{ij}]_{m \times m}$ ซึ่ง $A,B \in \mathbb{Z} ^{m \times m}$

$A \equiv B \pmod{n}$ ก็ต่อเมื่อ $a_{ij} \equiv b_{ij} \pmod{n}$ สำหรับทุก $i,j \in \{ 1,2,...,m \}$



จงพิสูจน์ว่า ถ้า $(det(A),n)=1$ แล้ว จะมีบางจำนวนเต็มบวก $k$ ซึ่ง $A^k \equiv I_m \pmod{n}$

เมื่อ $I_m$ คือเมตริกซ์เอกลักษณ์มิติ $m \times m$

[PP_nine]

ขอขุดหน่อยนึงครับ ด้วย hint

hint

จำนวนเต็ม $a$ มี inverse modulo $n$ (หรือก็คือ มีจำนวนเต็ม $a'$ ซึ่ง $a \cdot a' \equiv 1 \pmod{n}$) ได้ก็ต่อเมื่อ $(a,n)=1$

hint2

สำหรับเมตริกซ์ $A$ มิติ $m \times m$ จะได้ $A \cdot adj(A) = det(A)I$

(hint สุดท้ายถ้าเปิดแล้วอาจจะหมดสนุกทันที เพราะเป็น key word ที่สำคัญที่สุด)

hint3

ในเซต $\{ A, A^2, A^3, ..., A^d\}$ เมื่อ $d=n^{m^2}+1$

โดยหลัก_____ จะได้ว่ามีอย่างน้อยสองสมาชิกใน $A$ ซึ่ง_____

[Aquila]

ข้อความเดิมเขียนโดยคุณ PP_nine

เข้ามาปล่อยโจทย์ละกัน เห็นเงียบเหงามานาน



นิยาม : สำหรับเมตริกซ์ $A=[a_{ij}]_{m \times m}$ และ $B=[b_{ij}]_{m \times m}$ ซึ่ง $A,B \in \mathbb{Z} ^{m \times m}$

$A \equiv B \pmod{n}$ ก็ต่อเมื่อ $a_{ij} \equiv b_{ij} \pmod{n}$ สำหรับทุก $i,j \in \{ 1,2,...,m \}$



จงพิสูจน์ว่า ถ้า $(det(A),n)=1$ แล้ว จะมีบางจำนวนเต็มบวก $k$ ซึ่ง $A^k \equiv I_m \pmod{n}$

เมื่อ $I_m$ คือเมตริกซ์เอกลักษณ์มิติ $m \times m$

ขอขุดข้อนี้ขึ้นมาหน่อยสิ ขนาด hint ให้ 3 อันแล้วยังยากอยู่เลย
มีใครทำข้อนี้ได้บ้างครับ ยากจริงๆ

[Amankris]

มันก้ไม่ได้ยากอะไรขนาดนั้น ทำๆไปก็หลุด

[nooonuii]

ใช้รังนกพิราบอ้างว่า $A^p=A^q$

$A^{-1}$ หาได้เพราะเราเขียน $1=\det(A)x+ny$ จึงได้ $A^{-1}=x adj(A)$

สมมติ $p>q$ ก็จะได้ $A^{p-q}=I_m$

เป็นสมบัติของพวก finite ring น่ะครับ

ถ้า $R$ เป็น finite ring และ $a$ เป็น unit จะได้ว่า $a^k=1$ บางค่า $k$

[Pitchayut]

ขอเข้ามาปล่อยโจทย์ด้วย กระทู้จะได้ไปต่อ ผมก็อยากมีส่วนร่วมด้วยนะครับถึงแม้จะเพิ่งเริ่มเล่นเมื่อต้นปีนี้ (ขอเอาข้อของตัวเองเป็นข้อ 67 ครับ)

67. จงหาค่ามากที่สุดพร้อมพิสูจน์ของ $\dfrac{(3a+4b,\ 4b+5c,\ 5c+6a)}{(a,\ b,\ c)}$

[ความรู้ยังอ่อนด้อย]

#231

ได้ 15 หรือเปล่าครับ ?

[Pitchayut]

ยังไม่ใช่ครับ ผมเจอมากกว่านั้นอีกครับ

[Beatmania]

: )

ให้ $d=(3a+4b,4b+5c,5c+3a)$

โดยไม่เสียนัย เราให้ $(a,b,c)=1$

จาก $d|3a+4b,d|4b+5c,d|5c+3d$

เราจะได้ว่า $d|3a+4b+4b+5c-8b-10c\rightarrow d|6a$

ในทำนองเดียวกัน $d|8b,d|10c$

เราจะแสดงว่า $max[d]=120$

เราให้ $d=xp,120=pt;\exists(x,120)=(x,t)=1$

เราจะได้ว่า $xp|120a,120b,120c\rightarrow x|ta,tb,tc\rightarrow x|a,b,c\rightarrow x|(a,b,c)\rightarrow x=1$

ดังนั้น $d=p\leq 120$

$d=120$ เมื่อ $a=20,b=15,c=12$

68. จงหาจำนวนเฉพาะ $p$ ทั้งหมดที่ $p^2+p$ สามารถเขียนในรูป $1+2+...+N$ $\exists N\in\mathbb{N}$

[pont494]

68. มีแค่ 2 ตัวเดียวหรือเปล่าครับ

[Beatmania]

ใช่แล้วครับ ง่ายไปใช่มะ ตั้งโจทย์ต่อได้เลยครับ

[pont494]

ใครอยากจะตั้งก็ตั้งเลยครับ ผมสละสิทธิ์ให้ละกัน คิดโจทย์ไม่เป็น

[Beatmania]

งั้นขอแก้มือด้วยโจทย์ปานกลางๆแล้วกันครับ

69. จงแสดงว่า ทุกๆ จำนวนเต็ม $n$ สามารถเขียนในรูป $\left\lfloor b\sqrt{2}\right\rfloor+\left\lfloor c\sqrt{3}\right\rfloor$ ได้โดย $b,c\in\mathbb{Z}$

[ความรู้ยังอ่อนด้อย]

ข้อความเดิมเขียนโดยคุณ Beatmania

งั้นขอแก้มือด้วยโจทย์ปานกลางๆแล้วกันครับ

69. จงแสดงว่า ทุกๆ จำนวนเต็ม $n$ สามารถเขียนในรูป $\left\lfloor b\sqrt{2}\right\rfloor+\left\lfloor c\sqrt{3}\right\rfloor$ ได้โดย $b,c\in\mathbb{Z}$

ขอ hint หน่อยครับ

[Beatmania]

ลองดูครับว่าถ้าหาก $n$ ไม่อยู่ในรูป $\left\lfloor b\sqrt{3}\right\rfloor $

แล้วค่าของ $n$ จะอยู่ห่างจากจำนวนที่อยู่ในรูป $\left\lfloor b\sqrt{3} \right\rfloor $ ที่ใกล้กับ $n$ ที่สุดอย่างมากเท่าไหร่

เราก็จะใช้อีกตัวนึงมากลบความต่างตรงนั้นได้ครับ