[中學] n^2-n-1能被31整除

[RAINDD (I'm Kenino.)]

某正整數n，31可以整除n^2-n-1。試解n之值。

答案：

n的解集合為{13,19,13+31,19+31,13+31*2,19+31*2,…}

請問大家應如何下手或有提示。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.171.10.250
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1447348970.A.8C0.html
→ softseaweed : => 31 = k(n^2 -n -1), k為某正整數
→ softseaweed : => 0 = k*n^2 -k*n -(k+31)
→ softseaweed : 導入quadratic formula
→ softseaweed : 等等 我笨了= =
→ softseaweed : 把上面的k改成1/k
→ kerwinhui   : (n-19)(n-13)=n^2-n-1-31(n-8)能被質數31整除…
推 Desperato   : 推樓上
推 Tiderus     : 樓上那個是怎麼想到的？
→ Desperato   : 餘數集 let k* = { x is integer | x = k ( mod 31)
→ Desperato   : 則 Z_32 = {0*, 1*, 2*, ... ,30*}
→ Desperato   : 是Z_31, 可以定義a*+b* = (a+b)*和a*b* = (ab)*
→ Desperato   : 在這個東西上做 n*^2 - n* - 1* = 0* 會得到 n*=13*
→ Desperato   : r 19*
→ Desperato   : 詳細的作法就是k大的式子 列(n-a)(n-b) 爆開看有沒
推 LPH66       : 31 是質數所以其實可以直接配方爆開: 1*/2*=16*
→ LPH66       : 16*x16*=8* 所以配方成 (n*-16*)^2=9*
→ LPH66       : 9* 開平方根得 ±3*, 加 16* 得 13* or 19*
推 kuromu      :
推 Desperato   : 噢噢噢居然可以這樣 推推
→ LPH66       : 想了想, 應該只有偶模數不能/2配方
→ LPH66       : 而如果開平方失敗就表示無解
→ LPH66       : 所以不一定限質數模數, 奇模數應該都能這樣做
推 Tiderus     : n*是 n除31的餘數嗎？
→ Tiderus     : n*^2 - n* - 1* = 0* 會得到 n≡13(mod 31) or
→ Tiderus     : n≡19(mod 31) ？看不懂。
→ Tiderus     : n*^2 - n* - 1* = 0* 為什麼會變成13* or 19*？
→ Desperato   : 你可以參考LPH的做法
→ Desperato   : 因為31是質數 所以對任何非0*的a* 存在一個b*使得a*
→ Desperato   : =1*
→ Desperato   : 使得a*b*=1*, 因此可以作除法 c*/a*=c*b* 類似倒數
→ Desperato   : 念（反元素）
→ Desperato   : 所以可以拿1*除以2* 然後配方
→ Tiderus     : 真是轉好幾個彎阿，終於看懂了。