第二章數論輕鬆遊

pages 13 - 41

例題01 用指令PrimeQ確認第五個費馬數真是質數，但第六則否。首先在定義函數 (Subscript[F, n])=F[n], 然後列出 F[n], n=4,5 再判斷之。

F[n_] := 2^(2^n) + 1; {F[4], F[5]}

PrimeQ[{F[4], F[5]}]

例題02 由Out[1]知第五個費馬數是5位數，但第六則變成10位數。這並不稀奇，因為從定義就可看出來後一個大約是前一個的平方。試列出前八個一起觀察並判斷是否為質數。

Table[F[n], {n, 0, 7}]

Table[F[n], {n, 0, 7}] // PrimeQ

例題05 試分解 (Subscript[F, 5]), (Subscript[F, 6]), (Subscript[F, 7]) 三個費馬數。

FactorInteger[Table[F[n], {n, 5, 7}]] // ColumnForm

例題06 試計算 gcd(123456789, 987654321)。

GCD[123456789, 987654321]

例題07 試求 gcd(482,1180) 並表示成此二數的一個線性組合。

ExtendedGCD[482, 1180]

例題08 試求方程式 123456789 x + 987654321 y=9 的整數解。

ExtendedGCD[123456789, 987654321]

例題13 試計算 1111111*1058206 mod 1234567。

Mod[1111111*1058206, 1234567]

例題15 試計算 234567\(TraditionalForm\`\^876543\) mod 565656565。

PowerMod[234567, 876543, 565656565]

例題16 試計算87878787在模9191919191之下的乘法反元素。

PowerMod[87878787, -1, 9191919191]

例題17 試求同餘方程式 7654x\equiv 2389 mod{65537} 的解。

Solve[{7654*x == 2389, Modulus == 65537}, x, 
      Mode -> Modular]

Mod[PowerMod[7654, -1, 65537]*2389, 65537]

例題18 試用Mathematica將第一章習題 2 再計算一次。

PowerMod[{443, 221, 35, 1047, 513, 226}, 169, 1081]

例題20 解下列聯立同餘方程組：x \equiv 7  mod{1234567},  x \equiv 11 mod{1111111}

a = 7; b = 11; m = 1234567; n = 1111111;
PowerMod[n, -1, m] - m

k = Mod[%*(a - b), m]

{Mod[b + n*k, m*n], m*n}

例題21 試解韓信點兵問題： x \equiv 2 mod{3}, x \equiv 3 mod{5}, x \equiv 2 mod{7}

<< NumberTheory`NumberTheoryFunctions`
ChineseRemainderTheorem[{2, 3, 2}, {3, 5, 7}]

例題22 試解同餘方程組：x \equiv 2 mod{78}, x \equiv 5 mod{97}, x \equiv 1 mod{119}

ChineseRemainderTheorem[{2, 5, 1}, {78, 97, 119}]

Mod[{23, 647480}, {{3, 5, 7}, {78, 97, 119}}]

FactorInteger[{561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 
        29341}]

EulerPhi[1000]

PrimitiveRoot[65537]
PrimitiveRoot[11]
PrimitiveRoot[23]

Mod[Inverse[{{13, 12, 35}, {41, 53, 62}, {71, 68, 10}}], 
      999]

PolynomialMod[Inverse[{{13, 12, 35}, {41, 53, 62}, {71, 68, 10}}], 
      999]