โจทย์ในค่ายสอวน. เรื่องคอนกรูเอนซ์

[<KAB555>]

ให้ $A=a^4$ โดยที่ a เป็นจำนวนเต็มบวก จงหาจำนวนเต็มบวก x ทั้งหมดที่สอดคล้องกับ $A^{15x+1} \equiv A\pmod{6814407600} $

ให้ $n\in \mathbb{Z} ^+$ และ $\left\{a_1,a_2,...,a_k\,\right\} \subseteq \left\{1,2,3,...,n\,\right\} $ โดยที่ $a_1,a_2,...,a_k$ แตกต่างกัน และ $k\geqslant 2$ จงพิสูจน์ว่า
ถ้า $n\mid (a_i(a_{i+1}-1))$ สำหรับทุก $i\in \left\{1,2,...,k-1\,\right\} $ แล้ว $n\nmid a_k(a_1-1)$

ถ้ามีจำนวนเต็มบวก n ที่ทำให้ $3^n-2^n=p^\alpha $ สำหรับบาง $p\in P$ และ $\alpha \in \mathbb{N} $ แล้วจงพิสูจน์ว่า $n\in P$

[กขฃคฅฆง]

1. $6814407600 = 2^4\times 3^2\times 5^2\times 7\times 11\times 13\times 31\times 61$ แยกพิจารณาแต่ละตัวโดยใช้ออยเลอร์

[กขฃคฅฆง]

3. สมมติ $n$ เป็นจำนวนประกอบ ให้ $q\in P$ เป็นตัวประกอบของ $n$

พิสูจน์ให้ได้ว่า $q=p$ จะได้ว่า $n$ อยู่ในรูป $p^k$ เมื่อ $k\in\mathbb{Z} , k \geqslant 2$

จาก $3^p \equiv 3 \pmod{p}$ และ $2^p \equiv 2 \pmod{p}$ จะได้ $0 \equiv 3^n-2^n \equiv 3-2 \pmod{p} $ ขัดแย้ง

[กขฃคฅฆง]

2. สมมติ $n|a_k(a_1-1)$ และ $n = p_1^{b_1}p_2^{b_2}...p_m^{b_m}$ เมื่อ $b_i\geqslant 1$ และ $p_i$ แตกต่างกันทั้งหมด

พิจารณา $p_i \in \{p_1,p_2,...,p_m\}$ ใดๆ พิสูจน์ให้ได้ว่า $p_i|a_j $ ทุก $j=1,2,...,k$ หรือ $p_i|a_j -1$ ทุก $j=1,2,...,k$

ส่งผลให้ $p_i^{b_i}|a_j $ ทุก $j=1,2,...,k$ หรือ $p_i^{b_i}|a_j -1$ ทุก $j=1,2,...,k$

โดยไม่เสียนัยให้ $p_1^{b_1},...,p_r^{b_r}|a_j$ ทุก $j=1,2,...,k$ และ $p_{r+1}^{b_{r+1}},...,p_m^{b_m}|a_j-1$ ทุก $j=1,2,...,k$ โดยที่ $0\leqslant r\leqslant m$

จะได้ว่า $p_1^{b_1}...p_r^{b_r}|a_j$ ทุก $j=1,2,...,k$ และ $p_{r+1}^{b_{r+1}}...p_m^{b_m}|a_j-1$ ทุก $j=1,2,...,k$

ทำให้ $n|a_2(a_1-1)$ ที่เหลือก็ไม่ยากแล้วครับ

[Beatmania]

เพื่อความสะดวก กำหนดให้สัญลักษณ์ $a\equiv_n b$ หมายถึง $a\equiv b (mod n)$

สมมติขัดแย้ง โดยให้ $n|a_k(a_1-1)$ เราจะได้ว่า

$$a_1a_2...a_k\equiv_n a_1a_2...(a_{k-1}a_k)\equiv_n a_1a_2...a_{k-1} \equiv_n ... \equiv_n a_1 $$

แต่ในทำนองเดียวกัน

$$a_1a_2...a_k\equiv_n a_2a_3...(a_ka_1)\equiv_n a_2a_3...a_k \equiv_n a_2a_3...(a_{k-1}a_k) \equiv_n a_2a_3...a_{k-1} \equiv_n ... \equiv_n a_2 $$

ได้ว่า $a_1 \equiv_n a_2$ ขัดแย้งกับที่ $a_1,a_2\in (1,2,...,n) $ และ $a_1\neq a_2$

ดังนั้นจึงเป็นไปไม่ได้ที่ $n|a_k(a_1-1)$

[Thgx0312555]

@@Beatmania เป็น IMO 2009 ข้อ 1 ครับ

[Thgx0312555]

ข้อความเดิมเขียนโดยคุณ กขฃคฅฆง

3. สมมติ $n$ เป็นจำนวนประกอบ ให้ $q\in P$ เป็นตัวประกอบของ $n$

พิสูจน์ให้ได้ว่า $q=p$ จะได้ว่า $n$ อยู่ในรูป $p^k$ เมื่อ $k\in\mathbb{Z} , k \geqslant 2$

จาก $3^p \equiv 3 \pmod{p}$ และ $2^p \equiv 2 \pmod{p}$ จะได้ $0 \equiv 3^n-2^n \equiv 3-2 \pmod{p} $ ขัดแย้ง

ตรงพิสูจน์ $p=q$ ไม่น่าง่ายนะ (ไม่น่าพิสูจน์ได้นะ)
**ข้อนี้เคยเป็นข้อสอบเก่า สอวน.มข.ด้วย
Hint let $pq \mid n$, โดยที่ $p,q$ เป็นจำนวนเฉพาะ

[กขฃคฅฆง]

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

ตรงพิสูจน์ $p=q$ ไม่น่าง่ายนะ (ไม่น่าพิสูจน์ได้นะ)
**ข้อนี้เคยเป็นข้อสอบเก่า สอวน.มข.ด้วย
Hint let $pq \mid n$, โดยที่ $p,q$ เป็นจำนวนเฉพาะ

ผมให้ $n=aq$ ซึ่งจะได้ว่า $a>1$

$3^{aq}-2^{aq}=(3^a-2^a)(3^{a(q-1)}+3^{a(q-2)}2^a+...+2^{a(q-1)})$

จาก $a>1$ จะได้ว่า $3^a \equiv 2^a \pmod{p} $ ดังนั้น $3^{a(q-1)}+3^{a(q-2)}2^a+...+2^{a(q-1)} \equiv q3^{a(q-1)} \pmod{p} $

ซึ่งพิสูจน์ไม่ยากว่า $p\not= 3$ ดังนั้น $p\mid q$

[Thgx0312555]

ตอนแรกเข้าใจวิธีผิดไป แต่ก็วิธีนี้แหละ

[Oneboy]

อยากทราบว่าตรง $3^a \equiv 2^a \pmod{p}$ มายังไงเหรอครับ มันสามารถเป็นกรณีที่ $p\mid (3^{a(q-1)}+3^{a(q-2)}2^a+...+2^{a(q-1)})$ และ $p\nmid 3^a-2^a$ ได้หรือเปล่าครับ