什么叫互质数 (n+1)/n(n+2) 证明这...

来源：蜘蛛抓取(WebSpider) 时间：2011-09-21 19:54 标签： 什么叫互质数
求出并予证明：所有大于1的整数n,使(2^n+1)/n^2为整数.
pizza侂鼪就
默认你熟悉同余的语言和基本性质, 这样可以写得简单点.假设你知道Fermat小定理: 若p是质数, 且不整除a, 则a^(p-1) ≡ 1 (mod p).然后这类问题有个常用的引理:若正整数a, b, x, y满足a^x ≡ a^y ≡ 1 (mod b), 设d = (x,y) (最大公约数), 则a^d ≡ 1 (mod b).证明不难: ∵存在正整数u, v使ux-vy = d, ∴a^(vy+d) = a^(ux) ≡ 1 ≡ a^(vy) (mod b).而易见(a,b) = 1, 提出与b互质的a^(vy), 即得a^d ≡ 1 (mod b).再做一点准备工作, 证明2^(3^k)+1被3^(k+1)恰好整除 (即被3^(k+1)整除, 但不能被3^(k+2)整除).k = 0, 1时可验证成立, 然后由2^(3^(k+1))+1 = (2^(3^k)+1)³-3·2^(3^k)·(2^(3^k)+1)归纳即得.回到原题.∵n是正整数, ∴2^n+1为奇数, ∴n也是奇数.∵n > 1, 可设n的最小质因数为p > 2.可得2^(p-1) ≡ 1 (mod p) (Fermat小定理).∵(2^n+1)/n²为整数, ∴2^n ≡ -1 (mod p), ∴2^(2n) ≡ 1 (mod p).而∵p是n的最小质因数, ∴(2n,p-1) = 2, 由引理得2² ≡ 1 (mod p), 即p = 3.设n = 3^k·m, k ≥ 1且3不整除m.∵(2^n+1)/n²为整数, ∴2^n ≡ -1 (mod 3^(2k)), ∴2^(2n) ≡ 1 (mod 3^(2k)).又∵已证3^(2k) | 2^(3^(2k-1))+1, 即2^(3^(2k-1)) ≡ -1 (mod 3^(2k)),∴2^(2·3^(2k-1)) ≡ 1 (mod 3^(2k)).而∵k ≥ 1, ∴(2n, 2·3^(2k-1)) = 2·3^k, 由引理得2^(2·3^k) ≡ 1 (mod 3^(2k)).2^(2·3^k)-1 = (2^(3^k)-1)(2^(3^k)+1).已证2^(3^k)+1被3^(k+1)恰好整除, 故2^(3^k)-1 = (2^(3^k)+1)-2不被3整除.∴2^(2·3^k)-1也被3^(k+1)恰好整除, 由3^(2k) | 2^(2·3^k)-1, 只有k = 1, n = 3m.若m = 1, 可验证(2^n+1)/n²为整数.若m > 1, 可设m的最小质因数为q > 3.可得2^(q-1) ≡ 1 (mod q) (Fermat小定理).∵(2^n+1)/n²为整数, ∴2^n ≡ -1 (mod q), ∴2^(2n) ≡ 1 (mod q).而∵n = 3m, q是m的最小质因数, ∴(2n,q-1) = 2或6.由引理得2^6 ≡ 1 (mod q), 但q > 3, 只有q = 7.但2^n = 2^(3m) = 8^m ≡ 1 (mod 7), 与2^n ≡ -1 (mod q)矛盾.于是只有n = 3满足要求.证明也许绕了远路, 有疑问或改进意见欢迎追问.
为您推荐：
其他类似问题
wo我擦 目测这题不对 当N=2时，(2^n+1)/n^2=5/4？？
注意前面求出二字
那是求还是证明啊 二项式定理拆开
这个。。。。把2带进去就不对呀
注意前面求出二字
目测可用数学归纳法，自己写吧
扫描下载二维码试证：每个大于6的自然数n，都可以表示为两个大于1且互质的自然数之和．
证明：直观上可以这样看，当n＞6时，在2，3，…，n-2中，必有一个数A与n互质（2≤A≤n-2），记B=n-A≥2，有n=A+B，此时，A与B必互质，否则A与B有公约数d＞1，则d也是n的约数，从而A与n有大于1的公约数，与A、n互质矛盾．（1）当n为奇数时，n=2+（n-2），或n=+（2）当n为偶数，但不是4的倍数时，n=+，由n＞6知＞1，且、均为奇数，（，）=（，4）=1．（3）当n为偶数，且又是4的倍数时，有n=+，由n＞6知＞1，且、均为奇数，（，）=（，2）=1．
为您推荐：
其他类似问题
写出n＞6时的自然数，得到必有一个数A与n互质，然后分三种情况讨论：（1）当n为奇数时；（2）当n为偶数，但不是4的倍数时；（3）当n为偶数，且又是4的倍数时．
本题考点：
质数与合数．
考点点评：
此题考查了自然数中互质的数的判定，分类讨论在解题中起着至关重要的作用，不可轻视．
若N为奇数，则它可以表示为2n+1的形式，而2n+1又可以表示为n与n+1的和，是两个连续自然数，两个连续自然数一定互质。（n不等于1时也行） 若N为偶数，则它可以表示为2n的形式，若2n/2为偶数，2n可以表示为n-1与n+1的和，是两个连续奇数，一定为自然数，互质；若2n/2为奇数，2n可以表示为n-2与n+2的和，是两个相差4的奇数，奇数（除1外）加4一定为自然数，互质。...
扫描下载二维码您的举报已经提交成功，我们将尽快处理，谢谢！
ln[n(n+1)/2+1]&= ln(n/2+1)&=n/2;
等号成立条件为 n=0;
因此不等式无解。
大家还关注1644人阅读
数论（64）
给出一个N，求1..N中与N互质的数的和
ifgcd(n,i)=1 then gcd(n,n-i)=1 (1&=i&=n)
&&&&&&&&如果存在K!=1使gcd(n,n-i)=k,那么(n-i)%k==0
&&&&&&&&而n%k=0
&&&&&&&&那么必须保证i%k=0
&&&&&&&&k是n的因子,如果i%k=0那么&gcd(n,i)=k,矛盾出现;
&&&&&&&&于是问题变的非常简单： ANS=N*phi(N)/2
&&&&&&& i,n-i总是成对出现，并且和是n
&&&&&&&于是可能就有人问了，如果存在n-i=i那不是重复计算？
&&&&&&&&答案是不会
&&&&&&&&因为:
&&&&&&&&&&&&&&&&n=2*i-&i=n/2
1.如果n是奇数，那么n!=2*i,自然也不存在&n-i=i和重复计算之说
2.如果n是偶数,n=2*i成立,gcd(n,n/2)必然为n的一个因子,这个因子为1当且仅当n==2
3.于是对于n&2的偶数，绝对不存在gcd(n,n/2)=1所以更别说什么重复计算了
&&&&&&&&对于n==2
&&&&&&&&ans=2*1/2=1，正好也满足
&&&&&&&&所以得到最终公式：
&&&&&&&　　　　　　　　　　&ans=N*phi(N)/2&
#include&iostream&
#include&cmath&
const int MM=;
__int64 euler(__int64 x)
__int64 i,res=x;
for(i=2;i&(__int64)sqrt(x*1.0)+1;i++)
if(x%i==0)
res=res/i*(i-1);
while(x%i==0)
res=res/x*(x-1);
int main()
__int64 n,sum,
while(scanf(&%I64d&,&n)!=EOF && n)
sum=n*(n+1)/2-n;
ans=sum-euler(n)*n/2;
printf(&%I64d\n&,ans%MM);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：223552次
积分：5133
积分：5133
排名：第3659名
原创：282篇
转载：31篇
评论：55条
(8)(1)(2)(2)(10)(4)(1)(22)(58)(26)(53)(6)(10)(35)(63)(12)n为任何整数,求证n(n+1)(n+2)/6是整数.请看清楚题目是(n+2)不是(2n+1)
尹ゼ黙0238
证明:当n=0时,3/6=1/2不是整数,因此n=0除外除0之外的任何整数,有n＝1时,显然成立.假设当n＝k（k为大于或等于1的正整数）,命题成立；则当 n ＝k+1时,n(n+1)(2n+1)＝(k+1)(k+2)(2k＋3)＝(k+1)*[k(2k+1)+6(k+1)]＝k(k+1)(2k+1)+6(k+1)(k+1) 由假设,k(k+1)(2k+1)是6的倍数,而显然6(k+1)(k+1)也是6的倍数,所以n ＝k+1时,n(n+1)(2n+1)也是6的倍数.综合1和2.可知当n为任何整数时,n(n+1)(2n+1)/6是整数 同理可以证明当n＝k（k为小于或等于-1的负整数）时的情况.
为您推荐：
其他类似问题
证明，因为连续三个整数中，必有一个偶数和一个3的倍数，即三个连续整数的积必是6的倍数。所以，n(n+1)(n+2)/6必是整数。
因为n,n+1,n+2是三个连续的整数，而三个连续整数中必定有一个是3的倍数，至少有一个是偶数，所以n(n+1)(n+2)必定是6的倍数，所以n(n+1)(n+2)/6是整数.
证明：1.n＝1时，显然成立。 2.假设当n＝k（k为大于或等于1的正整数），命题成立；则当 n ＝k+1时，n(n+1)(2n+1)＝(k+1)(k+2)(2k＋3)＝(k+1)*[k(2k+1)+6(k+1)]＝k(k+1)(2k+1)+6(k+1)(k+1) 由假设，k(k+1)(2k+1)是6的倍数，而显然6(k+1)(k+1)也是6的倍数，所以n ＝k+1时，n(n+...
扫描下载二维码

我要回帖

更多关于 什么叫互质数 的文章

 

随机推荐