หรม....

[กระบี่ทะลวงด่าน]

จงหา หรม. ของ $3^{120}$-1 เเละ $3^{450}$-1

[Influenza_Mathematics]

ข้อความเดิมเขียนโดยคุณ กระบี่ทะลวงด่าน

จงหา หรม. ของ $3^{120}$-1 เเละ $3^{450}$-1

ก็ ใช้ $(a,b) = (a,r)$ เดี๋ยวก็ออกเองอะ

[กระบี่ทะลวงด่าน]

ไม่เข้าใจครับ ช่วยอธิบาย หน่อย krub thank you

[Amankris]

ใช้ Euclidean algorithm ครับ

[กระบี่ทะลวงด่าน]

เข้าใจหลักการครับ เเต่พอคิดเเล้วมันเเปลกๆครับ

[banker]

เขาพูดเรื่องอะไรกันครับ เด็ก ม.ต้น อ้าปากค้าง แถมน้ำลายยืดอีกต่างหาก

[กระบี่ทะลวงด่าน]

หรม. เเบบยุคลิดไงครับ

[yellow]

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

เขาพูดเรื่องอะไรกันครับ เด็ก ม.ต้น อ้าปากค้าง แถมน้ำลายยืดอีกต่างหาก

งั้นคิดแบบเด็ก ม.ต้น

$3^1 - 1 = 2$

$3^2 - 1 = 8 = 2(1 + 3)$

$3^3 - 1 = 26 = 2(1 + 3 + 3^2)$

$3^4 - 1 = 80 = 2(1 + 3 + 3^2 + 3^3)$

$3^5 - 1 = 242 = 2(1 + 3 + 3^2 + 3^3 + 3^4)$

$3^6 - 1 = 728 = 2(1 + 3 + 3^2 + 3^3 + 3^4 + 3^5)$


$\therefore 3^{120} - 1 = 2(1 + 3 + 3^2 + ... + 3^{119})$

$3^{450} - 1 = 2(1 + 3 + 3^2 + ... + 3^{449})$




$1 + 3 + 3^2 + ... + 3^{449} = (3^{330}+ 3^{210} + 3^{90}) (1 + 3 + 3^2 + ... + 3^{119})+ (1 + 3 + 3^2 + ... + 3^{89})$


$1 + 3 + 3^2 + ... + 3^{119} = 3^{30} (1 + 3 + 3^2 + ... + 3^{89}) + (1 + 3 + 3^2 + ... + 3^{29})$

$1 + 3 + 3^2 + ... + 3^{89} = (3^{60} + 3^{30} + 1) (1 + 3 + 3^2 + 3^3 + ... + 3^{29})$

หรม เท่ากับ

$2(1 + 3 + 3^2 + 3^3 + ... + 3^{29})$ = $3^{30} - 1$


รีบทำ ไม่แน่ใจเท่าไหร่

[Amankris]

#6

Euclidean algorithm เรียนตั้งแต่ประถมแล้วครับ

[gon]

ที่เวลา 4.40 แก้จาก เศษมากกว่าผลลัพธ์ เป็น เศษมากกว่าตัวหาร

[banker]

ท่านกรบรรยายเองเลย ขอบคุณครับ

[Mol3ius]

gcd ($\frac{135^{90} - 45^{90}}{90^2}$ , $90^2$) = ?

[yellow]

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

gcd ($\frac{135^{90} - 45^{90}}{90^2}$ , $90^2$) = ?

$135^{90} = (\frac{3}{2})^{90} \times 90^{90}$

$45^{90} = (\frac{1}{2})^{90} \times 90^{90}$

$135^{90} - 45^{90}= \frac{3^{90} -1}{2^{90}} \times 90^{90}$


$\frac{135^{90} - 45^{90}}{90^2} = \frac{3^{90} -1}{2^{90}} \times 90^{88}$


หรม = $90^2$

[nooonuii]

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

gcd ($\frac{135^{90} - 45^{90}}{90^2}$ , $90^2$) = ?

$\dfrac{135^{90}-45^{90}}{90^2}=\dfrac{(90+45)^{90}-45^{90}}{90^2}$

$~~~~~~~~~~~~~~~~~~~=\dfrac{90^{90}+\binom{90}{1}90^{89}\cdot 45+\cdots+\binom{90}{88}90^{2}\cdot 45^{88}+\binom{90}{89}90\cdot 45^{89}+45^{90}-45^{90}}{90^2}$

$~~~~~~~~~~~~~~~~~~~=\dfrac{90^{90}+\binom{90}{1}90^{89}\cdot 45+\cdots+45\cdot 89\cdot 90^{2}\cdot 45^{88}+90^2\cdot 45^{89}}{90^2}$

$~~~~~~~~~~~~~~~~~~~=90^{88}+\binom{90}{1}90^{87}\cdot 45+\cdots+45\cdot 89\cdot 45^{88}+45^{89}$

$~~~~~~~~~~~~~~~~~~~=90^{88}+\binom{90}{1}90^{87}\cdot 45+\cdots+90\cdot 45^{89}$

ดังนั้น

$\Big(\dfrac{135^{90} - 45^{90}}{90^2} , 90^2\Big)=(90\cdot 45^{89},90^2)$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=90\cdot 45 (45^{88},2)$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=90\cdot 45$

[banker]

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

gcd ($\frac{135^{90} - 45^{90}}{90^2}$ , $90^2$) = ?

$ \because \ \ \ 135^{90} - 45^{90} = 3^{90} \cdot 45^{90} - 45^{90}$

$ = 45^{90}(3^{90} -1) = \dfrac{90^{90}}{2^{90}} (3^{90} -1)$


$\dfrac{135^{90} - 45^{90}}{90^2} = \dfrac{90^{90}(3^{90} -1)}{(2^{90})(90^2)}$

$= \dfrac{90^{88}(3^{90} -1)}{(2^{90})} = \dfrac{90^2 \cdot 90^{86}(3^{90} -1)}{(2^{90})}$

gcd ($\frac{135^{90} - 45^{90}}{90^2}$ , $90^2$) =$ \ \ 90^2 \left(\dfrac{90^{86}(3^{90}-1)}{2^{90}} \right)$ , $90^2$) $ \ = \ 90^2$