【若n为合数,n|x^2-1,则gcd(x+1,n)|ngcd(x-1,n)|n且gcd(x+1,n)>1与gcd(x-1,n)>1意思是说：若n为合数,且n整除(x^2-1),则gcd(x+1,n)与gcd(x-1,n)都是n的约数且约数大于1.意思是说：若n为合数，且n整除(x^2-1),x^2≡1(modn)】
1人问答
问题描述：
若n为合数,n|x^2-1,则gcd(x+1,n)|ngcd(x-1,n)|n且gcd(x+1,n)>1与gcd(x-1,n)>1
意思是说：若n为合数,且n整除(x^2-1),则gcd(x+1,n)与gcd(x-1,n)都是n的约数且约数大于1.
意思是说：若n为合数，且n整除(x^2-1),x^2≡1(modn),|x|存在大于1的解，则gcd(x+1,n)与gcd(x-1,n)都是n的约数且约数大于1.
林润生回答：
对于模n意义下的非平凡平方根x,
反设gcd(x+1,n)=1,即n与x+1互素,
由n|(x²-1)=(x+1)(x-1),知n|x-1,即x≡1(modn),
这与x非平凡矛盾,故gcd(x+1,n)＞1,
同理有gcd(x-1,n)=1.
数学推荐
数学推荐
最新更新
精品分类
优秀数学推荐
热门数学
邮箱： 