本科生院软件工程学院信息安全数学导论2024-2025学年上学期期末_A_回忆本页总览2024-2025学年上学期期末_A_回忆 3×10 选择题 3×10 填空题 有一道考关于 m 个两两不互素的中国剩余定理计算。 10×2 计算题 中国剩余定理 解一次同余式 17x≡14(mod21)17x \equiv 14 \pmod{21}17x≡14(mod21) 10×2 证明题 已知 a,ba, ba,b 是正整数，ccc 是 A={ax+by∣x,y∈Z}A=\{ax+by \mid x,y\in \mathbb Z\}A={ax+by∣x,y∈Z} 中的最小正整数，证明：∀d∈A, c∣d\forall d\in A,\; c\mid d∀d∈A,c∣d 提示：由带余除法可知 c=a+bq(a>b, q∈Z+, c∈[0,b))c=a+bq(a>b,\; q\in \mathbb Z^+,\; c\in [0,b))c=a+bq(a>b,q∈Z+,c∈[0,b)) 由辗转相除法可知 c=(a,b)c=(a,b)c=(a,b) 又 ax+by=dax+by=dax+by=d 有解的充要条件为 (a,b)∣d(a,b)\mid d(a,b)∣d 故 c∣dc\mid dc∣d 再另讨论 a=ba=ba=b 时即可。 如果 mmm 和 nnn 是不同的素数，证明：mφ(n)+nφ(m)≡1(modmn)m^{\varphi(n)}+n^{\varphi(m)}\equiv 1 \pmod{mn}mφ(n)+nφ(m)≡1(modmn) 考试时间为 2 小时，若不卡壳可做到写完+完全检查。 2024.11.13 15:00 - 17:00