Question

帮我证明一道数论方面的题目。

已知：n为奇合数，2<r | (n-1)，e,k,n两两互素，且e和k都小于n^0.5
e^(2r) mod n = -1; k^(2r) mod n = -1;
证明：(ek)^(r) mod n = 1或-1
(ek)^(2r)mod n = 1 ---->(ek)^(r)mod n = ±1
如果n是素数，可以这样直接推导。但是在这里，n是合数。

（下面第一个证明都是错误的！
2010.11.25）

Answer 1

e^(2r) mod n = -1; k^(2r) mod n = -1

e^(2r)k^(2r)mod n = 1
(ek)^(2r)mod n = 1

(ek)^(r)mod n = ±1

Answer 2

啊 不好意思 按照题目的条件我证不出来
但若把r|(n-1) 改为r|n 好像就能得出结论
因为
(e)^(2r)≡-1(mod n);
(k)^(2r)≡-1(mod n);
做n的 质分解 令n=p1*p2*...
则易知
e^(2r)≡-1(mod p1);
e^(2r)≡-1(mod p2);
...
k^(2r)≡-1(mod p1);
k^(2r)≡-1(mod p2);
...
pi为奇质数
则又因为（2r,pi-1)=2
则解数为2
所以
e≡k(mod p1)或e≡-k(mod p1);
e≡k(mod p2)或e≡-k(mod p2);
...
这里用到高次剩余
若左半边全部成立
易得e≡k(mod n)
若右半边全部成立
易得e≡-k(mod n)
（不可能出现有正有负的情况
因为 e,k 小于n^0.5 可知e≡k(modpi..) e≡-k(modpj..) n=pi*...*pj...
其中max[pi...与pj..]>e,k 所以e=k或e=-k 会出现矛盾
）
所以 e^r≡k^r(mod n)
(ek)^(r)≡e^(2r)≡-1(mod n)
或e^r≡(-k)^r≡-k^r(mod n)
(ek)^(r)≡-e^(2r)≡1(mod n)
可得出结论
ps 如果按原题的结论 2<r | (n-1) 与e和k都小于n^0.5
不知如何同时使用 望高手前来指教