搜搜考试网如果a^n和b^n模m同余,且(m,n)=1,那么能否推出a和b模m同余?
来源：学生作业帮 编辑：搜搜考试网作业帮 分类：数学作业 时间：2024/08/08 21:16:53
如果a^n和b^n模m同余,且(m,n)=1,那么能否推出a和b模m同余?
不能,至少需要(n,φ(m)) = 1,其中φ是Euler函数.
例如n = 2,m = 5,a = 2,b = 3,
满足2^2 ≡ 3^2 (mod 5)但2与3 mod 5不同余.
可以证明的是:若(n,φ(m)) = 1,a^n ≡ b^n (mod m)且(a^n,m) = 1 (这蕴含a,b均与m互素),
则a ≡ b (mod m).
证明使用Bezout定理和Fermat-Euler定理:
由(n,φ(m)) = 1,存在正整数u,v使nu-φ(m)v = 1.
而由(a,m) = 1,a^φ(m) ≡ 1 (mod m),从而a^(nu) = a^(φ(m)v+1) ≡ a (mod m)
同理b^(nu) ≡ b (mod m).
又a^n ≡ b^n (mod m),故a ≡ a^(nu) ≡ b^(nu) ≡ b (mod m).
即所求证.
再问： 十分感谢！
再问： 能再问您一道题吗？
再答： 我试试看吧.
再问： 已知n|(a^n–b^n),那么如何证明n|(a^n–b^n)/(a–b)?
再答： 没想到简单方法, 只好用LTE了.
先证明n是素数方幂的情况:
设n = p^e, 若(n,a-b) = 1, 则结论显然成立.
而若(n,a-b) > 1, 由LTE引理, n = p^e | (a^n-b^n)/(a-b),
结论也成立.
对一般的n = p1^e1·p2^e2·...·pt^et.
只需证明pi^ei | (a^n-b^n)/(a-b).
记ni = pi^ei, mi = n/ni, A = a^mi, B = b^mi.
则由条件得ni | A^ni-B^ni, 而ni是素数方幂,
故ni | (A^ni-B^ni)/(A-B) = (a^n-b^n)/(A-B) | (a^n-b^n)/(a-b).
于是n | (a^n-b^n)/(a-b).
关于LTE引理, 请参看:
http://tieba.baidu.com/p/3037016992
再问： 谢谢啦
再答： 有两点需要补充:
一个是LTE对p = 2成立大于等于号,
因此上面用到的整除性仍然成立.
另一方面p | a时不适用LTE引理,
需要尽量把a, b中p的方幂提出来讨论.
有点繁琐但不算很难.
再问： 嗯，我会尝试着看懂的
再答： 遇到问题可以再来追问.
再问： 懂咯，LTE只要p|a或者p|b就行了吧？
再问： 说错了←_←应该是只要p和a或b互素就可以了吧
再答： 是的, 而由另一个条件p | a-b,
所以实际上是需要p与a, b都互素.
不过(p,a-b) = 1的情况是简单的,
所以剩下的只有a, b都被p整除的情况.
要花点功夫讨论v[p](a^n-b^n)-v[p](a-b).
再问： 嗯
例如n = 2,m = 5,a = 2,b = 3,
满足2^2 ≡ 3^2 (mod 5)但2与3 mod 5不同余.
可以证明的是:若(n,φ(m)) = 1,a^n ≡ b^n (mod m)且(a^n,m) = 1 (这蕴含a,b均与m互素),
则a ≡ b (mod m).
证明使用Bezout定理和Fermat-Euler定理:
由(n,φ(m)) = 1,存在正整数u,v使nu-φ(m)v = 1.
而由(a,m) = 1,a^φ(m) ≡ 1 (mod m),从而a^(nu) = a^(φ(m)v+1) ≡ a (mod m)
同理b^(nu) ≡ b (mod m).
又a^n ≡ b^n (mod m),故a ≡ a^(nu) ≡ b^(nu) ≡ b (mod m).
即所求证.
再问： 十分感谢！
再问： 能再问您一道题吗？
再答： 我试试看吧.
再问： 已知n|(a^n–b^n),那么如何证明n|(a^n–b^n)/(a–b)?
再答： 没想到简单方法, 只好用LTE了.
先证明n是素数方幂的情况:
设n = p^e, 若(n,a-b) = 1, 则结论显然成立.
而若(n,a-b) > 1, 由LTE引理, n = p^e | (a^n-b^n)/(a-b),
结论也成立.
对一般的n = p1^e1·p2^e2·...·pt^et.
只需证明pi^ei | (a^n-b^n)/(a-b).
记ni = pi^ei, mi = n/ni, A = a^mi, B = b^mi.
则由条件得ni | A^ni-B^ni, 而ni是素数方幂,
故ni | (A^ni-B^ni)/(A-B) = (a^n-b^n)/(A-B) | (a^n-b^n)/(a-b).
于是n | (a^n-b^n)/(a-b).
关于LTE引理, 请参看:
http://tieba.baidu.com/p/3037016992
再问： 谢谢啦
再答： 有两点需要补充:
一个是LTE对p = 2成立大于等于号,
因此上面用到的整除性仍然成立.
另一方面p | a时不适用LTE引理,
需要尽量把a, b中p的方幂提出来讨论.
有点繁琐但不算很难.
再问： 嗯，我会尝试着看懂的
再答： 遇到问题可以再来追问.
再问： 懂咯，LTE只要p|a或者p|b就行了吧？
再问： 说错了←_←应该是只要p和a或b互素就可以了吧
再答： 是的, 而由另一个条件p | a-b,
所以实际上是需要p与a, b都互素.
不过(p,a-b) = 1的情况是简单的,
所以剩下的只有a, b都被p整除的情况.
要花点功夫讨论v[p](a^n-b^n)-v[p](a-b).
再问： 嗯
举例证明同余的乘方性质：如果a ≡ b (mod m),那么a^n ≡ b^n (mod m)
（线性代数）同维同个数向量组A,b等价能否推出其组成矩阵(m*n)列等价?
基本同余定理证明【定义】设m是大于1的正整数,a,b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mo
证明如果（a,b）=1且m,n是自然数,那么（a^m,b^n)=1
（线性代数追问）同维同个数向量组A,b等价能否推出其组成矩阵(m*n)列等价?
如果点A(m+4,n)和点B(n-1,2m+1)关于Y轴对称,那么M=,N=
已知a＞0,且不等于1,m＞n＞0,比较A=a^m+a^--m和B=a^n +a^-n
设a、b、m为整数(m>0),若a和b被m除得的余数相同,则称a和b对模m同余.记为a≡b(mod
已知向量a和向量b不共线,且m+n=a,m-n=b,则m=?n=?(用a,b表示)
如果a：b=m:n,b:c=n:k,那么,a:b:c=（
如果 a:b=m:n,b:c=n:k那么a:b:c=?
设a,b,m为整数(m>0),若a和b被m除得的余数相同,则 称a和b对m同余记为a=b(modm