大一数学题

philip_z

求求大神们 帮帮忙第四题
谢谢！！

ccmmjj

看了，英语不是很懂，大概是指两个正整数的最大公约数问题。不过还有些字眼弄不清，你解释翻译一下，我看看能不能帮你。

ccmmjj

是初等数论的题目，不难，用辗转相除法就可以做完了。

luyuanhong

如果两个自然数的最大公约数（gcd）等于 1 ，我们就说这两个数互质。

例如，9 与 14 互质，而 12 与 15 则不互质（因为 gcd(12,15)=3 ）。

设 a 和 n 是两个自然数。证明：如果 a 与 n 互质，则存在一个唯一的

自然数 b＜n 使得 ab≡1(mod n) 。

（a）首先证明 ∃b∈ℕ ，b＜n∧ab≡1(mod n) 。

（b）添加一个等式（1），可以将 b 唯一地表达出来。

（c）这样就可以证明 b 是唯一的。

ccmmjj126

原来是这样的，用辗转相除法不好。用剩余系的概念吧，0，1，……，n-1.是对模n的完全剩余系，若a与n互质，则a*i(i=0，1，……，n-1)也是模n的完全剩余系。也就是说，存在唯一的数0<b<n使ab≡1(mod n).若有两个不同的数b，使ab1≡1(mod n),ab2≡1(mod n).那么a(b1-b2)≡0(mod n).若(b1-b2)≡1(mod n)则a≡0(mod n).不合题意，若1<b1-b2<n-1,则(b1-b2）整除n，这说明了a整除n/(b1-b2)>1，即gcd(a,n)>1矛盾。