数论相关问题

数论相关问题

只是这个结论的话其实和前面的条件没关系.
A和α都是确定的,所以A^α也是确定的.
满足B ≡ A^α (mod n),0 ≤ B < n的整数B就是A^α除以n的余数,
所以是存在唯一的 (带余除法).
会用到前面条件的是如下结论:
当A与n互素时,存在唯一的整数B,满足B^β ≡ A (mod n),0 ≤ B < n.
存在性:取B为A^α除以n的余数,则B ≡ A^α (mod n),0 ≤ B < n,且B也与n互素.
B^β ≡ A^(αβ) ≡ A (mod n) (由Fermat-Euler定理,A^φ(n) ≡ 1 (mod n)).
唯一性:由B^β ≡ A (mod n),B也与n互素.
于是B ≡ B^(αβ) ≡ A^α (mod n),又0 ≤ B < n,即得B是A^α除以n的余数,故唯一.
再问： 这里还有一个结论，对任一整数k有k^αβ≡k(mod n)这个结论是怎样得出的呢
再答： 首先由αβ ≡ 1 (mod φ(n)), 可设αβ = m·φ(n)+1. 根据Fermat-Euler定理, 若(k,n) = 1, 则k^φ(n) ≡ 1 (mod n). 于是k^(αβ) = k·(k^φ(n))^m ≡ k (mod n). 不互素的情况需要用到n = pq. 若(k,n) = p, 则k ≡ 0 (mod p), k^(αβ) ≡ 0 ≡ k (mod p). 又由(k,q) = 1, 有k^(q-1) ≡ 1 (mod q) (Fermat小定理). 由q-1 | φ(n), k^φ(n) ≡ 1 (mod q). 进而k^(αβ) = k·(k^φ(n))^m ≡ k (mod q). 而p, q互素, 可得k^(αβ) = k·(k^φ(n))^m ≡ k (mod n). 若(k,n) = q, 同理可证. 而若(k,n) = n, 易得k^(αβ) ≡ 0 ≡ k (mod n).
再问： k^(αβ) = k·(k^φ(n))^m ≡ k (mod q). p, q互素, 可得k^(αβ) = k·(k^φ(n))^m ≡ k (mod n). 这两个结论分别是怎么推出的呢。 p, q不互素, 好像也可得到k^(αβ) = k·(k^φ(n))^m ≡ k (mod n).
再答： 上面的结论: ∵已证k^φ(n) ≡ 1 (mod q), ∴(k^φ(n))^m ≡ 1 (mod q), ∴k^(αβ) = k·(k^φ(n))^m ≡ k (mod q). 下面的结论(= k·(k^φ(n))^m那步应该去掉): ∵已证k^(αβ) ≡ k (mod p), k^(αβ) ≡ k (mod q), 又∵p, q互素, n = pq, ∴k^(αβ) ≡ k (mod n). 这里还是需要p, q互素(也即p, q为不同素数)的条件的. 否则p = q = 3, n = 9, φ(n) = 6, 取αβ = 7, k = 3. 可知k^(αβ) ≡ 0 (mod n)但k ≡ 3 (mod n).
再问： 第一个结论应该是用到这个结果：若(k,q) = 1, 有k^(q-1) ≡ 1 (mod q) ，如果再有（q-1)|Q则 k^Q≡ 1 (mod q)成立 这时q-1)|Q推出k^Q≡ 1 (mod q) 这样的结论是否是成立的呢
再答： 由k^(q-1) ≡ 1 (mod q), (q-1) | Q当然能推出k^Q ≡ 1 (mod q). 因为可设Q = (q-1)t, 所以k^Q = (k^(q-1))^t ≡ 1^t = 1 (mod q).