ช่วยพิสูจน์เกี่ยวกับ Carmichael Numbers ให้หน่อยค่ะ

[ying_sassy]

ทบ.1 ให้ n เป็นจำนวนเต็ม ดังนั้น n เป็น Carmichael Numbers ก็ต่อเมื่อ ผลคูณของจำนวนเฉพาะที่แตกต่างกัน สอดคลองกับเงื่อนไข สำหรับแต่ละตัวประกอบเฉพาะ p ของ n ซึ่งทำให้ (p-1) หาร (n-1) ลงตัว

ทบ.2 ไม่มี Carmichael Number ที่เป็นจำนวนคู่

ทบ.3 ทุกๆ Carmichael Number ต้องมีตัวประกอบอย่างน้อย 3 ตัว

ปล. ใครสามารถพิสูจน์ได้ ขอความกรุณาด้วยนะคะ ช่วยพิสูจน์ด้วยนะคะ

[chikage - a thousand shadows]

ก่อนอื่นจะพิสูจน์ว่า Carmichael numbers เป็นจำนวน squarefree นั่นคือไม่มีตัวประกอบที่เป็นจำนวนกำลังสองสมบูรณ์

สมมติว่ามีจำนวนเฉพาะ p ซึ่ง p²|n เราสามารถเลือก a เป็น primitive root ของ p² ได้ นั่นคือเราจะได้ว่า order ของ a mod n ต้องเป็น
f(p²) = p(p-1) แต่จาก a^n-1 บ 1 (mod n) จะได้ว่า p(p-1)|n-1 ดังนั้น p|n-1 ขัดแย้งกับที่ p²|n
ดังนั้นเราจึงได้ว่า Carmichael numbers เป็น squarefree

ต่อไปจะพิสูจน์ (1)
ให้ (a,n) = 1 ที่ n เป็น squarefree และทุกๆ p|n เรามี p-1|n-1
โดย p|n เราจะได้จากทฤษฎีบทของแฟร์มาว่า a^p-1 บ 1(mod p) แต่ p-1|n-1 ดังนั้น a^n-1 บ 1(mod p) ทุกๆ ตัวประกอบเฉพาะ p ของ n
แต่ n squarefree ดังนั้นโดยการรวมมอดูโลเข้าด้วยกันจะได้ a^n-1 บ 1(mod n) ทุกๆ (a,n)=1
ในทางกลับกัน ให้ n เป็น Carmichael number และ p|n เราเลือก a เป็น primitive root ของ p เพราะฉะนั้น a^n-1 บ 1(mod p) และ p-1|n-1 เนื่องจาก p-1 เป็น order ของ a mod p

พิสูจน์ (2)
สมมติว่า n Carmichael number ที่เป็นจำนวนคู่ ถ้า n มีจำนวนเฉพาะคี่เป็นตัวประกอบ จะได้จาก (1) ว่า p-1|n-1 ซึ่งเป็นไปไม่ได้เพราะว่า p-1 เป็นจำนวนคู่ แต่ n-1 เป็นจำนวนคี่ ดังนั้น n ไม่มีตัวประกอบเฉพาะที่เป็นจำนวนคี่ แต่ n เป็น squarefree ดังนั้น n = 2 (นิยามส่วนใหญ่จะไม่ถือว่า 2 เป็น Carmichael number)

พิสูจน์ (3)
สมมติว่า n = pq ซึ่ง 1 < p < q เป็นจำนวนเฉพาะ เราทราบแล้วว่า q-1|n-1
ให้ n = d(q-1) + 1 = pq เมื่อ d > 1 (เพราะว่า p>1)
พิจารณาสมการบน mod q จะได้ว่า d บ 1(mod q) ดังนั้นมี e ซึ่ง d =eq+1 และ e>1 (เพราะว่า d>1)
ดังนั้น n = (eq+1)(q-1) + 1 = eq²-eq+q = (eq-e+1)q
และจะได้ว่า p = eq-e+1 = e(q-1) + 1 > e(p-1) + 1 > (p-1) + 1 = p จาก q > p และ e > 1 ทำให้ได้ข้อขัดแย้ง
ดังนั้น Carmichael numbers ไม่สามารถมีตัวประกอบเฉพาะแค่สองตัวได้ แต่จากความเป็น squarefree ด้วย จึงทำให้มันต้องมีตัวประกอบเฉพาะอย่างน้อย 3 ตัว

หมายเหตุ : 1. ถ้า 6k+1, 12k+1, 18k+1 เป็นจำนวนเฉพาะทั้งหมดแล้วจะได้ว่า n=(6k+1)(12k+1)(18k+1) เป็น Carmichael number เนื่องจาก (6k+1)(12k+1)(18k+1) = 1296k³+396k²+36k+1บ1(mod 36k) และพิสูจน์ต่อไปได้ว่า n ดังกล่าวเป็น Carmichael number
2.มีการพิสูจน์แล้วว่ามี Carmichael number เป็นจำนวนอนันต์ โดยที่พิสูจน์ว่า C(n) > n^2/7 สำหรับ n ที่มีค่ามากพอ

[warut]

ว้าว...สุดยอด แต่ขอเพิ่มเติมนิดนึงนะครับ

ข้อความเดิมของคุณ chikage - a thousand shadows:
(นิยามส่วนใหญ่จะไม่ถือว่า 2 เป็น Carmichael number)

2 ไม่ใช่ Carmichael number เพราะ 2 เป็นจำนวนเฉพาะครับ

[chikage - a thousand shadows]

อา...ใช่จริงๆ ด้วย...ลืมไปเลยว่า 2 เป็นจำนวนเฉพาะ ก็เลยไม่เป็น Carmichael number...ขอบคุณๆ