Re: [理工] 104 交大離散 對答案

[tzutengweng (神奇的湯姆)]

※ 引述《tzutengweng (神奇的湯姆)》之銘言：
: 1 (a)不會   版上好像有參考解答
: (b)  1.|A|<|B|
:      2.|A|=|B|
: (c) 0
這題我修改成 240/559<----是錯的喔!!  是319/559才對   感謝w大指點

https://zh.wikipedia.org/wiki/%E5%8D%A1%E9%82%81%E5%85%8B%E7%88%BE%E6%95%B8

E(n)為Euler's function

E(561)=561(1-1/3)(1-1/11)(1-1/17)=320

因為561不是質數   所以若gcd(m, 561)=1, m^320=1(mod 561)

也就是說2~560中

與561互質的數中   b^560=\=1 (mod 561)  會return false

所以題目問的是return true

2~560中  與561互質的數共有

[]表示取下界

560-[560/3]-[560/11]-[560/17]+[560/33]+[560/187]+[560/51]-[560/561]-1(不含1)
=319

(559-319)/559 =240/559即為所求





: (d) -30+42k, k屬於 Z
: 2.   a0=1
:      an=a(n-1)+2  n屬於Z
: 3. (a)2881
: (b)4
: (c)512463
: 4.(a)  a1=1  ; an=a(n-1)+(2^(n-1)-a(n-1))=2^(n-1)
: (b)164
: (c)2^(n(n+1)/2)
: (d) 4

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.247.23
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484663613.A.1DB.html
推 yupog2003: b^560=\=1(mod 561)會return false，代表b與561不互質
→ yupog2003: 的話會return false，相反的，若b與561互質的話，會
→ yupog2003: return true，那這樣應該是要算與561互質的機率才對？
→ yupog2003: 費瑪小定理:gcd(m,p)=1 => m^(p-1)=1(mod p)
→ yupog2003: <=> m^(p-1)=\=1(mod p) => gcd(m,p)=\=1 => m,p不互質
→ yupog2003: 用了若p則q，非q則非p轉換一下
→ tzutengweng: 費馬小定理的p 要是質數  可是561不是質數
→ yupog2003: 阿對吼...那應該你是正確的
→ w181496: 561是carmichael numbers 也適用費馬小定理
推 yupog2003: 我沒念到carmichael number，看來我是賽到的...
→ k2shouai: 4(a)改An=2(An-1) for all n>=2 就是遞迴了
→ yupog2003: 嗯嗯解答也是這樣寫的沒錯，當時沒想到...
※ 編輯: tzutengweng (59.125.97.119), 01/18/2017 13:49:20