Cubic residue

[Thamma]

ขอถามเป็นความรู้นะคะ

วิธีหา cubic residue modulo composite number เช่น

$ x^3 \equiv a \mod 2^7 $

$ x^3 \equiv a \mod 221 $

ว่ามีทั้งหมดกี่จำนวน และจำนวนอะไรบ้าง ในรูป congruences

ขอบคุณค่ะ

[Thamma]

ทราบวิธีการคิดแล้วค่ะ

[กขฃคฅฆง]

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

ทราบวิธีการคิดแล้วค่ะ

ทำยังไงครับ

[Thamma]

ถ้าพบที่ไม่ถูกต้องก็บอกนะคะ


$ x^3 \equiv a \mod 221$

$ x^3 \equiv a \mod 13\cdot17 $

หา solution ของแต่ละ prime congruence

$ x^3 \equiv a \mod 13 $

$ a \equiv 0, 1, 5, 8, 12 \mod 13 $ ----- 1

$ x^3 \equiv a \mod 17 $

$ a \equiv 0, 1, 2, ..., 16 \mod 17 $ ----- 2

จาก 1 และ 2 , ใช้ Chinese remainder theorem หา solution ( mod 221)

ยกตัวอย่างเช่น

$ a \equiv 0 \mod 13 $

$ a \equiv 2 \mod 17 $

จะได้ $ a \equiv 78 \mod 221 $

ดังนั้น 78 เป็นหนึ่งใน cubic residues ของ 221


คิดว่าในบางกรณี การรู้จำนวน cubic residues ทั้งหมด ก็มีประโยชน์

$ x^3 \equiv a \mod 10 $

$ x^3 \equiv 0, 1 \mod 2 $

$ x^3 \equiv 0, 1, 2, 3, 4 \mod 5 $

จำนวน cubic residue modulo 10 ทั้งหมด ( นับรวม 0 ด้วย ) จะมี 2 x 5 = 10 จำนวน

นั่นคือ a = 0, 1, 2 ,..., 9

-----------

$ x^3 \equiv a \mod 2^7 $

มีทฤษฎี (ลองพิสูจน์ดูนะ )

$ x^k \equiv a \mod 2^n $

If $k \geq 3 $ is odd, then every odd integer a satisfying $ 1\leq a < 2^n, n\in \unicode {8469}$ , is a $k^{th}$-power residue modulo $2^n$.

k = 3, n = 7
a = 1, 3, 5, ..., 127

คิดว่าไม่ใช่ complete list, เป็นกรณีที่ x เป็นเลขคี่

แต่ก็ยังไม่ทราบว่า ถ้า x เป็นเลขคู่ จะมีวิธีหา a อย่างไรค่ะ