[理工] [離散] 97台大電機

[ceo890710 (Drinking)]

The Euclidean Algorithm is used to product a sequence X1>X2>X3>X4>X5=0

of positive integers,where Xt = Qt+1*Xt+1 + Xt+2,t=1,2,3.The quotients are

q2=3,q3=2,q4=2.which of the following is correct?

(a) gcd(X1,X2)= -2X1 + 6X2 (b) gcd(X1,X2)= -2X1 - 6X2
(c) gcd(X1,X2)= -2X1 - 7X2 (d) gcd(X1,X2)= 2X1 + 7X2
(e) gcd(X1,X2)= -2X1 + 7X2

題目說用Euclidean Algorithm我知道

但解答上面有個地方寫gcd(X1,X2)=X4...然後從這邊開始推導

但為什麼可以知道X1和X2的最大公因數為是X4..

-----------------------------------------------------------------------

Which of the following relation R is not an equivalence relation?

其中b選項
Let V be the set of vertices of a graph G,and for u,v(屬於)V
define (u,v)屬於R if u=v or there exists an edge from u to v.

aRb bRc 不保證有edge = (a,c) if a≠c 所以no transitive

-----------------------------------------------------------------------

The number of primes of the form |n^2-6n+5|,where n is an integer,is
(a)0 (b)1 (c)2 (d)3 (e)4

式子表示primes |(n-1)(n-5)| (n-1)and(n-5)表示這個數的兩個因數
∵要形成prime  ∴ 則因數只能是1或自己 
(n-1)and(n-5) 屬於{1,-1} //因為有絕對值所以必須包含-1
因此符合的n有 0、2、4、6

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.169.181.69
※ 編輯: ceo890710       來自: 1.169.181.69         (08/03 20:45)
推 RichLowkey56:第二題有對稱嗎
→ ceo890710:他的條件是"or"所以如果a跟b有邊相連這樣不就有對稱?
推 PikaRen:第二題沒有transitive
→ PikaRen:第一題 你做輾轉相除得出0之前的那個餘數不就是gcd嗎?
→ ceo890710:aRb bRc a會有邊跟c相連或者a跟c相同不是嗎?
→ ceo890710:還是我哪邊想錯了..請指教..
推 PikaRen:a可以通到c但不一定會有(a,c)這條edge
→ ceo890710:我懂了= =" 我一直以為連通就可以..謝謝!
推 RichLowkey56:抱歉我以為是有向圖=  =a
推 RichLowkey56:最後一題答案4個吧  n=0,2,4,6
→ ceo890710:我想知道為什麼是屬於1和-1..
→ RichLowkey56:因為她的意思是說 (n-1)跟(n-5)其中一個要1or-1
→ RichLowkey56:這樣絕對值-->1  質數的因數1&自己
→ ceo890710:喔喔~所以|n^2-6n+5|這個式子會形成質數然後找n是嗎?
→ RichLowkey56:恩
→ ceo890710:了解..被題目弄暈了..謝謝!
推 genius945:第一題還是不太懂...Orz  原PO可以指導一下嗎= =
※ 編輯: ceo890710       來自: 1.169.181.69         (08/03 23:40)
→ ceo890710:第一題我不太會..可以請高手把觀念細說嗎 ~ 感恩
推 kiwidoit:應該求GCD的linear combination的那個過程
推 kiwidoit:ex: GCD(46,20)
→ kiwidoit:46=2*20+6(xt)
推 kiwidoit:上面打錯= =
→ kiwidoit:我用另一個例子比較好XD
→ kiwidoit:GCD(1001,224)
→ kiwidoit:1001=4*224+105
→ kiwidoit:224=2*105+14
→ kiwidoit:105=7*14+7
→ kiwidoit:14=2*7+0
→ kiwidoit:上面等式左的數字就是xt，右式第一個數字是qt+1
→ kiwidoit:第二個數字是Xt+1, 第三個數字是Xt+2
→ kiwidoit:題目是Xt=  Qt+1  *  Xt+1  +  Xt+2 吧= ="
推 kiwidoit:所以這一題列式子的話如下:
→ kiwidoit:X1=3*X2+X3
→ kiwidoit:X2=2*X3+X4
→ kiwidoit:X3=2*X4+X5
→ kiwidoit:然後用倒推的方式就可以把X3,X4,X5都變成X1跟X2的組合
推 kiwidoit:因為X5=0，所以X4一定是X1跟X2的GCD，所以答案是e吧@@?
※ 編輯: ceo890710       來自: 1.169.181.69         (08/04 08:57)
→ ceo890710:抱歉題目打錯~已修正
推 genius945:改過題目後就懂了...之前那樣差很多XD
推 toughdick:最後一題是不是3和5兩個質數嗎
※ 編輯: ceo890710       來自: 1.169.173.40         (08/05 10:01)
→ ceo890710:有人知道最後一題是求prime個數還是n的個數嗎..
→ ceo890710:The number of primes..應該是求質數個數..但解答是4個
→ ceo890710:所以是解答錯還是題目解讀錯誤..
推 genius945:是問n吧  前面那段是說form裡面的數字是prime
→ genius945:我的破英文是這樣認知啦..
→ ceo890710:了解XD
→ sneak: 喔喔~所以|n^2-6 https://daxiv.com