โจทย์จากค่าย Olympic

[alpha]

จงพิสูจน์ว่า
ถ้า f(a) congruence กับ k(mod m) แล้ว f(a+tm) congruence กับ k(mod m)

f(a) เป็นฟังก์ชันพหุนาม สปส.เป็นจำนวนเต็มนะ

ข้อนี้ ค่ายหาดใหญ่ทั้งค่ายคิดได้ไม่ถึง 7 คน

[warut]

a นี่เป็นค่าคงที่หรือตัวแปรครับ

ค่ายโอลิมปิคไหนอ่ะน้อง สอวน. รึเปล่า เดี๋ยวนี้รู้สึกสับสนเพราะบางคนจะเรียก สอวน. ว่าโอลิมปิคหรือไม่ก็มีโครงการ มีค่ายต่างๆเพิ่มขึ้นมามากมาย แต่ค่ายโอลิมปิคจริงๆ จะเป็นของ สสวท. เข้าค่ายกันที่ สสวท. ดิ คือรู้สึกจะสับสนกันบ่อย ชักจะงง มันต่างกันพอสมควรนะ ลองตอบให้เคลียร์หน่อย แต่ก็เอาเหอะจะทำโจทย์ให้
ข้อนี้ f(x) น่าจะเป็นพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็มมากกว่านะ
ให้ f(x) = [:Sum]c_ixⁱ เมื่อ i = 0,1,2,...,n โดย c_i ฮ Z
ได้ f(a+tm) - f(a) = [:Sum]c_i[(a+tm)ⁱ -(a)ⁱ เมื่อ i = 0,1,...,n
จะเห็นว่าพจน์ c₀ จะหายไป แล้ว (a+tm) - (a) จะหาร (a+tm))ⁱ - (a))ⁱ ลงตัวทุก i = 1,2,...,n จึงได้ tm หาร f(a+tm) - f(a) ลงตัว นั่นคือ f(a) บ f(a+tm) (mod m)

เห็นโจทย์แล้วรู้สึกว่าทำไมค่ายของสอวน.มันต่างกับสสวท.มากจังเลย

[alpha]

โทษนะครับที่บอกชนิดฟังก์ชันผิด จริงๆ แล้วเป็นฟังก์ชันพหุนาม สปส.เป็นจำนวนเต็ม แล้วถ้าเป็นไปได้ ช่วยเขียนคำตอบด้วย UBB Code ให้ด้วยนะครับ (จะได้อ่านรู้เรื่องง่ายขึ้น)

คำว่า Congruence นั้น ใช้สัญลักษณ์การเท่ากันทุก
ประการแทนก็ได้ (มันจะเป็นขีดตรง 3 ขีด แนวนนอน แต่รู้สึกว่า UBB Code จะไม่มี) แต่ถ้าจะใช้เครื่องหมายอื่น กรุณาระบุด้วยนะครับว่าหมายถึงคเรื่องหมาย Congruence

คือก็ใช้ UBB code นะ แต่มันไม่ออกมาเป็นรูปที่ต้องการง่ะ งงเหมือนกัน ไอ้ S คือสัญลักษณ์ ซิกมา ฮ คือสัญลักษณ์เป็นสมาชิก บ คือสัญลักษณ์คอนกรูเอนซ์

[alpha]

ก็ คุณ TripleSix ไม่สมัครเป็นสมาชิกทีนี่นา

[mathcenter]

ใช่ครับ
รู้กันซักทีซิครับว่า
ถ้าไม่เป็นสมาชิกสัญลักษณ์
ตัวประหลาด ๆ มันจะใช้ไม่ได้

[alpha]

อ่านแล้วก็งง ทำไม f(a)บf(a+tm)(mod m)
แล้วเราสรุปได้ด้วยหรือว่า f(a+tm)บk(modm)
อยากให้ช่วยอธิบายต่อนะครับ
โจทย์ให้พิสูจน์ว่า f(a+tm)บk(modm) นะครับ
ไม่ใช่ f(a)บf(a+tm)(mod m)

[Penpen]

Because f(a) is a polynomial function therefore it can be written
in the form
f(a) = b_naⁿ+b_n-1a^n-1+. . .+b₁a+b₀
where b₀, . . . , b_n are integers
Consider the term f_i(a) = b_iaⁱ where 0 ฃi ฃn
f_i(a+tm) = b_i(a+tm)ⁱ
= b_i(aⁱ+_iC₁a^i-1m+. . . + mⁱ)
= b_iaⁱ+b_i(_iC₁a^i-1m+. . . + mⁱ)
= b_iaⁱ+b_im(_iC₁a^i-1+. . . + m^i-1)
f_i(a+tm) = b_iaⁱ+mP_i(a)
when P_i(a) = b_i(_iC₁a^i-1+. . . + m^i-1)
Therefore f(a+tm) = Sf_i(a) + mSP_i(a)
because Sf_i(a) = f(a) and mSP_i(a) is divisible by m
f(a+tm) = f(a)+mG(a) when G(a) = SP_i(a)
f(a+tm)mod m บ [f(a)+mG(a)]mod m
f(a+tm)mod m บ f(a)mod m+mG(a)mod m
f(a+tm)mod m บ f(a)mod m
f(a+tm)mod m บ k mod m