Tag Archives: math

最近因為要讀密碼學相關的論文，會用到不少數論的東西，而我的個性是沒真正推導過的東西用起來總很不放心，而且我很笨，沒有平鋪直述的思路推導就很難理解，我討厭那種神來一筆，我記得以前在PTT上問過一個微積分的問題，我看到一個有三角函樹的式子被上下同乘某個三角函數得到另一個式子，我一直覺得很納悶，書上只這樣寫，我想知道的不是結果，而是思路，結果有個的同學就回答了”阿不就上下同乘X函數”，我差點沒暈倒，老兄，你不說我看書也知道是上下同乘那函數，結果對我來說只是一個點，但思路是一條路徑，沒有思路的話，數學式子對我來說也不過是幾個文字而已 雖然有些東西以前可能有想過是怎樣推導出來，但因為太少用所以很容易忘記，每次都重新想起，所以我決定將整個思路寫下來，這樣以後忘記時就不用重新看，所以主要只是給自己看的筆記，寫在紙上時間久了一樣會不見，所以想一想寫到部落格裡好了，順便練習用LaTeX編數學公式，可能會對某些人有幫助，但我突然腦殘想錯的機會不小，所以讀者請自重囉 今天要證的是，若m為質數，w為任一與m互質之整數，則 主要證明是參考 數論在密碼上的應用 （第 2 頁） 這雖然不是Euler定理，但我覺得對之後證明很有用，太少接觸所以先從簡單的開始 一開始由該網頁所提到的方式，拆開成多項式來看 接著就得先從多項式定理複習起 其實可以被視為是 如果把每一個垂直列開來，就會發現其實 我們可以把這樣展開的式子，視為從上到下每行挑一個的連乘，因為要從2個選擇中挑n次，這樣所有的組合可能為 但是我們比較在意的是某些組合出現的次數，我們可能會想知道n個a出現幾次，也就是它的系數，而這要算出不同可能情況的系數又扯到了排列組合，複習一下排列組合的思路，如果我們有ABC三個東西要排列 最直觀的想法就是，先關注在ABC三個東西所佔的地方，直接先把它們當成位置來看 先從最左邊的位置開始，此時我們手裡有ABC三種選擇，接著來到第二個位置，前面已經挑走了一個選擇，所以我們只剩兩個，接著最後一格，挑剩下的就只有一種選擇，所以可能的選擇有 種，也就是 接著來考慮重覆的部份，先一樣當成都不同來看，可能性展開有這麼多6種 在此時，我們被告知B和C其實是同一種 把B和C都替換成X來看 我們會發現其實原本的可能性數量其實重覆了一次，所以應該除以二，而二這個數字其實就是B和C排列的可能性，由此我們可以知道，當N個東西任意排列，其可能情況是 而當我們被告知，這裡面其實有a個東西是一樣的，那麼我們就將重覆的情況除掉 當我們又被告知，裡面有b個東西是一樣的，此時我們又可以去掉重覆的，得到的結果就是 但是，理所當然的，裡面不一樣的東西數量加起來不可能會大於N，有了基本的排列公式複習，我們回到二項式定理 利用我們剛才排列的公式，我們知道個個系數其實是 以 來解釋的話，因為有k-2個相同的a和2個相同的b，所以k!要除掉相同的部份，有了這個部份我們可以回到先前把w拆成1來看的部份 在這裡，我們把每個1都當做不一樣的數來看待，套用多項式公式我們會發現裡面有w項的 每項都是1，加總起來是w，而剩下的部份，形式像這樣 這些數全都因為包含m為因數可以被m整除，在此有個疑點就是，那為什麼分子就不可能把m給除掉，剩下的不會是m-1之類的嗎? 原因很簡單，因為m是質數記得嗎? 以這一項來看 m!的很多項都會被消掉，像這個會被消成 下面的2!會是(m-1)或m的因數，但是因為m是質數，除了它自己以外只有1是因數，因此不管下面放些什麼，m總會是這些項目的系數中的一部份，得到這結論後，我們就能將之前的式子兩邊同除m，這樣除了w以外的項目都會被整除，得到 這時離我們目標不遠了，兩邊同除w 就證出來了，最後有個疑問，就是w為什麼得和m互質，因為在倒數第二個式子，如果它們不互質，w一除m就會被變成其它的數 to read Haitian … Continue reading →