費馬小定理

Question

你如何計算出以下使用Fermat's Little Theorem？

2^1,000,006 mod 101 
2^-1,000,005 mod 11 

Answer 1

你知道一個^（P-1）=== 1模p，所以...

2^10 === 1個模11
2 ^（ - 1000005）= （ - 1,000,000）* 2 ^（ - 5）= 1 * 2 ^（ - 5）= 2 ^（ - 5）* 2 ^（10）= 32 mod 11 = -1 = 10

從這，你能看到如何處理更大的數字嗎？這個過程是一樣的。

這FLT一路。我搞砸了。

Answer 2

由於101和11是素數，則（分別）2^100和2^10是一致的，以1個模101和11

試圖表達2^1000006中的2^100和2而言^以2^10計算-1000005。您應該能夠將每個問題簡化爲易於計算的內容。