作业帮数论相关问题
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 14:04:08
数论相关问题
数论相关问题
数论相关问题
只是这个结论的话其实和前面的条件没关系.
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的余数,故唯一.