求有关初等数论的所有知识```
第一章 有关数论的算法
1.1 最大公约数与最小公倍数
1.2 有关素数的算法
1.3 方程ax+by=c的整数解及应用
1.4 求a^b mod n
1.1最大公约数与最小公倍数
1.算法1: 欧几里德算法求a,b的最大公约数
function gcd(a,b:longint):longint;
begin
if b=0 then gcdd:=a
else gcd:=gcd(b,a mod b);
end;
2.算法2:最小公倍数acm=a*b div gcd(a,b);
3.算法3:扩展的欧几里德算法,求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y
function exgcd(a,b:longint;var x,y:longint):longint;
var
t:longint;
begin
if b=0 then
begin
result:=a;
x:=1;
y:=0;
end
else
begin
result:=exgcd(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
(理论依据:gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1))
1. 2有关素数的算法
1.算法4:求前n个素数:
program BasicMath_Prime;
const
maxn=1000;
var
pnum,n:longint;
p:array[1..maxn] of longint;
function IsPrime(x:longint):boolean;
var i:integer;
begin
for i:=1 to pnum do
if sqr(p[i])<=x then
begin
if x mod p[i]=0 then
begin
IsPrime:=false;
exit;
end;
end
else
begin
IsPrime:=true;
exit;
end;
IsPrime:=true;
end;
procedure main;
var x:longint;
begin
pnum:=0;
x:=1;
while(pnum<n) do
begin
inc(x);
if IsPrime(x) then
begin
inc(pnum);
p[pnum]:=x;
end;
end;
end;
procedure out;
var i,t:integer;
begin
for i:=1 to n do
begin
write(p[i]:5);t:=t+1;
if t mod 10=0 then writeln;
end;
end;
begin
readln(n);
main;
out;
end.
2.算法5:求不大于n的所有素数
program sushu3;
const maxn=10000;
var
i,k,n:integer;
a:array[1..maxn] of integer;
begin
readln(n);
for i:=1 to n do a[i]:=i;
a[1]:=0;
i:=2;
while i<n do
begin
k:=2*i;
while k<=n do
begin
a[k]:=0;
k:=k+i;
end;
i:=i+1;
while (a[i]=0) and (i<n) do i:=i+1;
end;
k:=0;
for i:=1 to n do
if a[i]0 then
begin
write(a[i]:5); k:=k+1;
if k mod 10 =0 then writeln;
end
end.
3.算法6:将整数分解质因数的积
program BasicMath_PolynomialFactors;
const
maxp=1000;
var
pnum,n:longint;
num,p:array[1..maxp] of longint;
procedure main;
var x:longint;
begin
fillchar(num,sizeof(num),0);
fillchar(p,sizeof(p),0);
pnum:=0;
x:=1;
while(n>1) do
begin
inc(x);
if n mod x=0 then
begin
inc(pnum);
p[pnum]:=x;
while(n mod x=0) do
begin
n:=n div x;
inc(num[pnum]);
end;
end;
end;
end;
procedure out;
var j,i:integer;
begin
for i:=1 to pnum do
for j:=1 to num[i] do
write(p[i]:5);
writeln;
end;
begin
main;
out;
end.
1.3方程ax+by=c的整数解及应用
1.算法7:求方程ax+by=c的整数解
procedure equation(a,b,c:longint;var x0,y0:longint);
var d,x,y:longint;
begin
d:=exgcd(a,b,x,y);
if c mod d>0 then
begin
writeln('no answer');
halt;
end else
begin
x0:=x*(c div d);
y0:=y*(c div d);
end;
end;
2.方程ax+by=c整数解的应用
例1:有三个分别装有a升水、b升水和c升水的量筒(gcd(a,b)=1,c>b>a>0),现c筒装满水,
问能否在c筒个量出d升水(c>d>0)。若能,请列出一种方案。
算法分析:
量水过程实际上就是倒来倒去,每次倒的时候总有如下几个持点:
1.总有一个筒中的水没有变动;
2.不是一个筒被倒满就是另一个筒被倒光;
3.c筒仅起中转作用,而本身容积除了必须足够装下a简和b简的全部水外,别无其
它限制。
程序如下:
program mw;
type
node=array[0..1] of longint;
var
a,b,c:node;
d,step,x,y:longint;
function exgcd(a,b:longint;var x,y:longint):longint;
var t:longint;
begin
if b=0 then
begin
exgcd:=a;;x:=1;y:=0;
end
else
begin
exgcd:=exgcd(b,a mod b,x,y);
t:=x;x:=y;y:=t-(a div b)*y
end;
end;
procedure equation(a,b,c:longint;var x0,y0:longint);
var d,x,y:longint;
begin
d:=exgcd(a,b,x,y);
if c mod d>0 then
begin
writeln('no answer');
halt;
end else
begin
x0:=x*(c div d);
y0:=y*(c div d);
end;
end;
procedure fill(var a,b:node);
var t:longint;
begin
if a[1]<b[0]-b[1] then t:=a[1]
else t:=b[0]-b[1];
a[1]:=a[1]-t;
b[1]:=b[1]+t
end;
begin
write('a,b,c,d=');
readln(a[0],b[0],c[0],d);
equation(a[0],b[0],d,x,y);
step:=0;
a[1]:=0;b[1]:=0;c[1]:=c[0];
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
if x>0 then
repeat
if a[1]=0 then fill(c,a) else
if b[1]=b[0] then fill(b,c) else fill(a,b);
inc(step);
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
until c[1]=d
else
repeat
if b[1]=0 then fill(c,b) else
if a[1]=a[0] then fill(a,c) else fill(b,a);
inc(step);
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
until c[1]=d;
end.
1.4 求a^b mod n
1.算法8:直接叠代法求a^b mod n
function f(a,b,n:longint): longint;
var d,i:longint;
begin
d:=a;
for i:=2 to b do d:=d mod n*a;
d:=d mod n;
f:=d;
end;
2.算法9:加速叠代法
function f(a,b,n:longint):longint;
var d,t:longint;
begin
d:=1;t:=a;
while b>0 do
begin
if t=1 then begin
f:=d;exit end ;
if b mod 2 =1 then d:=d*t mod n;
b:=b div 2;
t:=t*t mod n;
end;
f:=d
end;
练习:
1.熟记并默写以上算法.
《奥赛经典·专题研究系列-奥林匹克数学中的数论问题》
朱春荔的《初中数学竞赛中的数论问题》
这两本可以,单遵那本是从系统出发对数论理论的阐述,适合你以后有兴趣打基础慢慢学。
竞赛的功利性强,对知识的应用考察多,基础就没太高的要求啦,有点像拔苗助长呵。
没有特别的必要,别去参加什么奥数竞赛,那玩意纯粹是某些老师为了搞培训赚外快鼓动你的。填鸭式教学打乱了学生的正常学习节奏,在整个的知识系统没有得到质的改变前盲目突击某一学科、领域,最轻微最好的结果是偏科,绝大多数情况下都会打击到学生的积极性,湮灭以后学习的兴趣,可谓百害而微一利。中国的教育本就方向错误,再去钻牛角尖还有得活吗?
研究数的规律,特别是整数性质的数学分支。是数论的一个最古老的分支。它以算术方法为主要研究方法,主要内容有整数的整除理论、不定方程、同余式等。古希腊毕达哥拉斯是初等数论的先驱。他与他的学派致力于一些特殊整数(如亲和数、完全数、多边形数)及特殊不定方程的研究。公元前4世纪,欧几里德的《几何原本》通过102个命题,初步建立了整数的整除理论。他关于“素数有无穷多个”的证明,被认为是数学证明的典范。公元3世纪,丢番图研究了若干不定方程,并分别设计巧妙解法,故后人称不定方程为丢番图方程。17世纪以来,P.de费马、L.欧拉、C.F.高斯 等人的工作大大丰富和发展了初等数论的内容。中国古代对初等数论的研究有着光辉的成就,《周髀算经》、《孙子算经》、《张邱建算经》、《数书九章》等古文献上都有记载。孙子定理比欧洲早500年, 西方常称此定理为中国剩余定理,秦九韶的大衍求一术也驰名世界。初等数论不仅是研究纯数学的基础,也是许多学科的重要工具。它的应用是多方面的,如计算机科学、组合数学、密码学、信息论等。如公开密钥体制的提出是数论在密码学中的重要应用。
初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论(用解析的方法研究数论。)、代数数论(用代数结构的方法研究数论)。
素数
数论刚开始的时候是用朴素的推理方法去研究整数的性质,又以素数最令人神往。古今不知道多少数学家都为了它而呕心沥血!研究素数的性质是数论中一个非常重要的方面!
所谓素数,就是一个正整数,它除了本身和 1 以外并没有任何其他因子。素数就好象是正整数的原子一样,著名的高斯「唯一分解定理」说,任何一个整数。可以写成一串质数相乘的积。但是至今仍然没有一个一般的特别使用的式子可以表示所有的素数。所以数论里关于素数的两个著名猜想非常困难:
1哥德巴赫猜想 :(Goldbach Conjecture)
内容为“所有的大于2的偶数,都可以表示为两个素数”
这个问题是德国数学家哥德巴赫(C.Goldbach,1690-1764)于1742年6月7日在给大数学家欧拉的信中提出的,所以被称作哥德巴赫猜想。同年6月30日,欧拉在回信中认为这个猜想可能是真的,但他无法证明。从此,这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可即的“明珠”。“用当代语言来叙述,哥德巴赫猜想有两个内容,第一部分叫做奇数的猜想,第二部分叫做偶数的猜想。奇数的猜想指出,任何一个大于等于7的奇数都是三个素数的和。偶数的猜想是说,大于等于4的偶数一定是两个素数的和。”(引自《哥德巴赫猜想与潘承洞》)
哥德巴赫猜想貌似简单,要证明它却着实不易,成为数学中一个著名的难题。18、19世纪,所有的数论专家对这个猜想的证明都没有作出实质性的推进,直到 20世纪才有所突破。直接证明哥德巴赫猜想不行,人们采取了“迂回战术”,就是先考虑把偶数表为两数之和,而每一个数又是若干素数之积。如果把命题"每一个大偶数可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b",那么哥氏猜想就是要证明"1+1"成立。
1900年,20世纪最伟大的数学家希尔伯特,在国际数学会议上把“哥德巴赫猜想”列为23个数学难题之一。此后,20世纪的数学家们在世界范围内“联手”进攻“哥德巴赫猜想”堡垒,终于取得了辉煌的成果。
到了20世纪20年代,有人开始向它靠近。1920年,挪威数学家布爵用一种古老的筛选法证明,得出了一个结论:每一个比6大的偶数都可以表示为(9+ 9)。这种缩小包围圈的办法很管用,科学家们于是从(9十9)开始,逐步减少每个数里所含质数因子的个数,直到最后使每个数里都是一个质数为止,这样就证明了“哥德巴赫猜想”。
1920年,挪威的布朗(Brun)证明了 “9+9 ”。
1924年,德国的拉特马赫(Rademacher)证明了“7+7 ”。
1932年,英国的埃斯特曼(Estermann)证明了 “6+6 ”。
1937年,意大利的蕾西(Ricei)先后证明了“5+7 ”, “4+9 ”, “3+15 ”和“2+366 ”。
1938年,苏联的布赫 夕太勃(Byxwrao)证明了“5+5 ”。
1940年,苏联的布赫 夕太勃(Byxwrao)证明了 “4+4 ”。
1948年,匈牙利的瑞尼(Renyi)证明了“1+c ”,其中c是一很大的自然数。
1956年,中国的王元证明了 “3+4 ”。
1957年,中国的王元先后证明了 “3+3 ”和 “2+3 ”。
1962年,中国的潘承洞和苏联的巴尔巴恩(BapoaH)证明了 “1+5 ”, 中国的王元证明了“1+4 ”。
1965年,苏联的布赫 夕太勃(Byxwrao)和小维诺格拉多夫(BHHopappB),及 意大利的朋比利(Bombieri)证明了“1+3 ”。
1966年,中国的陈景润证明了 “1+2 ”[用通俗的话说,就是大偶数=素数+素数*素数或大偶数=素数+素数(注:组成大偶数的素数不可能是偶素数,只能是奇素数。因为在素数中只有一个偶素数,那就是2。)]。
其中“s + t ”问题是指: s个质数的乘积 与t个质数的乘积之和
20世纪的数学家们研究哥德巴赫猜想所采用的主要方法,是筛法、圆法、密率法和三角和法等等高深的数学方法。解决这个猜想的思路,就像“缩小包围圈”一样,逐步逼近最后的结果。
由于陈景润的贡献,人类距离哥德巴赫猜想的最后结果“1+1”仅有一步之遥了。但为了实现这最后的一步,也许还要历经一个漫长的探索过程。有许多数学家认为,要想证明“1+1”,必须通过创造新的数学方法,以往的路很可能都是走不通的。
2孪生素数猜想:所谓孪生素数指的就是这种间隔为 2 的相邻素数,它们之间的距离已经近得不能再近了,就象孪生兄弟一样。最小的孪生素数是 (3, 5),在 100 以内的孪生素数还有 (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) 和 (71, 73),总计有 8 组。但是随着数字的增大,孪生素数的分布变得越来越稀疏,寻找孪生素数也变得越来越困难。那么会不会在超过某个界限之后就再也不存在孪生素数了呢?
我们知道,素数本身的分布也是随着数字的增大而越来越稀疏,不过幸运的是早在古希腊时代,Euclid 就证明了素数有无穷多个 (否则今天许多数论学家就得另谋生路)。长期以来人们猜测孪生素数也有无穷多组,这就是与 Goldbach 猜想齐名、集令人惊异的简单表述和令人惊异的复杂证明于一身的著名猜想 - 孪生素数猜想:
存在无穷多个素数 p, 使得 p+2 也是素数。
究竟谁最早明确提出这一猜想我没有考证过,但是一八四九年法国数学 Alphonse de Polignac 提出猜想:对于任何偶数 2k, 存在无穷多组以 2k 为间隔的素数。对于 k=1,这就是孪生素数猜想,因此人们有时把 Alphonse de Polignac 作为孪生素数猜想的提出者。不同的 k 对应的素数对的命名也很有趣,k=1 我们已经知道叫做孪生素数, k=2 (即间隔为 4) 的素数对被称为 cousin prime (比 twin 远一点),而 k=3 (即间隔为 6) 的素数对竟然被称为 sexy prime (这回该相信 “书中自有颜如玉” 了)!不过别想歪了,之所以称为 sexy prime 其实是因为 sex 正好是拉丁文中的 6。:-)
孪生素数猜想还有一个更强的形式,由英国数学家 Hardy 和 Littlewood 于一九二三年提出,现在通常称为 Hardy-Littlewood 猜想或强孪生素数猜想[注一]。这一猜想不仅提出孪生素数有无穷多组,而且还给出其渐近分布形式为:
x
π2(x)~2C2∫dt/(lnt)^2
2
其中 π2(x) 表示小于 x 的孪生素数的数目, C2 被称为孪生素数常数 (twin prime constant),其数值为:
C2=∏P(P-2)/(p-1)^2≈0.66016118158468695739278121100145...
p≥3
Hardy-Littlewood 猜想所给出的孪生素数分布的精确程度可以由下表看出:
x 孪生素数数目 Hardy-Littlewood 猜想
100,000 1224 1249
1,000,000 8,169 8,248
10,000,000 58,980 58,754
100,000,000 440,312 440,368
10,000,000,000 27,412,679 27,411,417
很明显,Hardy-Littlewood 猜想的对孪生素数分布的拟合程度是惊人的。 如此精彩的拟合堪与自然科学史上 Adams 和 Leverrier 运用天体摄动规律对海王星位置的预言以及 Einstein 对光线引力偏转的预言相媲美,是理性思维的动人篇章。这种数据对于纯数学的证明虽没有实质的帮助,但是它大大增强了人们对孪生素数猜想的信心。
顺便说一下,Hardy-Littlewood 猜想所给出的孪生素数分布规律可以通过一个简单的定性分析 “得到”:我们知道素数定理 (prime number theorem) 表明对于足够大的 x, 在 x 附近素数的分布密度大约为 1/ln(x),因此两个素数处于区间 2 以内的概率大约为 2/ln2(x)。这几乎正好就是 Hardy-Littlewood 猜想中的被积函数!当然其中还差了一个孪生素数常数 C2,而这个常数很显然正是 Handy 与 Littlewood 的功力深厚之处!
除了 Hardy-Littlewood 猜想与孪生素数实际分布之间的拟合外,对孪生素数猜想的另一类 “实验” 支持来自于对越来越大的孪生素数的直接寻找。就象对于大素数的寻找一样,这种寻找在很大程度上成为对计算机运算能力的一种检验,一九九四年十月三十日,这种寻找竟然导致发现了 Intel Pentium 处理器浮点除法运算的一个 bug,在工程界引起了不小的震动。截至二零零二年底,人们发现的最大的孪生素数是:
(33218925×2169690-1, 33218925×2169690+1)
这对素数中的每一个都长达 51090 位!许多年来这种记录一直被持续而成功地刷新着。
好了,介绍了这么多关于孪生素数的资料,现在该说说人们在证明孪生素数猜想上所走过的路了。
迄今为止在证明孪生素数猜想上的成果大体可以分为两类。第一类是非估算性的结果,这一方面迄今最好的结果是一九六六年由已故的我国数学家陈景润 (顺便说一下,美国数学学会在介绍 Goldston 和 Yildirim 成果的简报中提到陈景润时所用的称呼是 “伟大的中国数学家陈”) 利用筛法 (sieve method) 所取得的。陈景润证明了:存在无穷多个素数 p, 使得 p+2 要么是素数,要么是两个素数的乘积。这个结果和他关于 Goldbach 猜想的结果很类似。目前一般认为,由于筛法本身的局限性,这一结果在筛法范围内很难被超越。
证明孪生素数猜想的另一类结果是估算性的,Goldston 和 Yildirim 所取得的结果也属于这一类。这类结果估算的是相邻素数之间的最小间隔,更确切地说是:
Δ := lim inf[(P(n+1)-Pn)/ln(Pn)]
n→∞
翻译成白话文,这个表达式定义的是两个相邻素数之间的间隔与其中较小的那个素数的对数值之比在整个素数集合中所取的最小值。很显然孪生素数猜想如果成立,那么 Δ 必须等于 0,因为孪生素数猜想表明 pn+1-pn=2 对无穷多个 n 成立,而 ln(pn)→∞,因此两者之比的最小值对于孪生素数集合 (从而对于整个素数集合也) 趋于零。不过要注意 Δ=0 只是孪生素数猜想成立的必要条件,而不是充份条件。换句话说如果能证明 Δ≠0 则孪生素数猜想就不成立,但证明 Δ=0 却并不意味着孪生素数猜想就一定成立。
对于 Δ 最简单的估算来自于素数定理。按照素数定理,对于足够大的 x, 在 x 附近素数出现的几率为 1/ln(x),这表明素数之间的平均间隔为 ln(x) (这也正是 Δ 的表达式中出现 ln(pn) 的原因),从而 (pn+1-pn)/ln(pn) 给出的其实是相邻素数之间的间隔与平均间隔的比值,其平均值显然为 1。平均值为 1,最小值显然是小于等于 1,因此素数定理给出 Δ≤1。
对 Δ 的进一步估算始于 Hardy 和 Littlewood。一九二六年,他们运用圆法 (circle method) 证明了假如广义 Riemann 猜想成立,则 Δ≤2/3。这一结果后来被被 Rankin 改进为 Δ≤3/5。但是这两个结果都有赖于本身尚未得到证明的广义 Riemann 猜想,因此只能算是有条件的结果。一九四零年,Erdös 利用筛法首先给出了一个不带条件的结果:Δ<1 (即把素数定理给出的结果中的等号部分去掉了)。此后 Ricci 于一九五五年, Bombieri 和 Davenport 于一九六六年,Huxley 于一九七七年, 分别把这一结果推进到 Δ≤15/16, Δ≤(2+√3)/8≈0.4665 及 Δ≤0.4425。 Goldston 和 Yildirim 之前最好的结果是 Maier 在一九八六年取得的 Δ≤0.2486。
以上这些结果都是在小数点后做文章, Goldston 和 Yildirim 的结果把这一系列的努力大大推进了一步,并且 - 如果得到证实的话 - 将在一定意义上终结对 Δ 进行数值估算的长达几十年的征途,因为 Goldston 和 Yildirim 证明了 Δ=0。当然如我们前面所说,Δ=0 只是孪生素数猜想成立的必要条件,而非充份条件,因此 Goldston 和 Yildirim 的结果离最终证明孪生素数猜想还远得很,但它无疑是近十几年来这一领域中最引人注目的结果。
一旦 Δ=0 被证明,人们的注意力自然就转到了研究 Δ 趋于 0 的方式上来。孪生素数猜想要求 Δ ~ [log(pn)]-1 (因为 pn+1-pn=2 对无穷多个 n 成立)。 Goldston 和 Yildirim 的证明给出的是 Δ ~ [log(pn)]-1/9,两者之间还有相当距离。但是看过 Goldston 和 Yildirim 手稿的一些数学家认为 Goldston 和 Yildirim 所用的方法明显存在改进的空间,也就是说对 Δ 趋于 0 的方式可以给出更强的估计。因此 Goldston 和 Yildirim 的证明其价值不仅仅在于结果本身,更在于它很有可能成为未来一系列研究的起点。这种系列研究对于数学来说有着双重的价值,因为一方面这种研究所获得的新结果是对数学的直接贡献,另一方面这种研究对 Goldston 和 Yildirim 的证明会起到反复推敲和核实的作用。现代数学早已超越了一两个评审花一两个小时就可以对一个数学证明做出评判的时代。以前四色定理和 Fermat 大定理都曾有过一个证明时隔几年 (甚至十几年) 才被发现错误的例子。因此一个复杂的数学结果能够成为进一步研究的起点,吸引其它数学家的参与对于最终判定该结果的正确性具有极其正面的意义。
这两个猜想还一直在吸引着数学家们!
有无穷多个素数
这个古老的命题最初是由古希腊数学家欧几里德(Euclid of Alexandria,生活在亚历山大城,约前330~约前275,是古希腊最享有盛名的数学家)在他的不朽著作《几何原本》里给出的一个反证法:
假设命题不真,则只有有限多个素数,设所有的素数是2=a1<a2<……<an.
此时,令N=a1*a2*……*an+1,那么所有的ai(i=1,2,……,n)显然都不是N的因子,那么有两个可能:或者N有另外的素数真因子,或者N本身就是一个素数,但是显然有N>ai(i=1,2……n).无论是哪种情况,都将和假设矛盾。这个矛盾就完成了我们的证明,所以确实有无穷多个素数!
这个证明简短而又有力,充分体现了证明者的智慧,也体现出数学的概括性和美丽!
其实,后人还发现了很多方法去证明这个命题,例如:用费马数(Fn=2^(2^n)+1)可以给出一个证明,但是都不如欧几里德的证明简单,所以人们比较熟悉的就是这个证明。
费马(Fermat):数论大师
费马在数论领域中的成果是巨大的,其中主要有:(费马大定理 、费马小定理)
费马大定理:n>2是整数,则方程x^n+y^n=z^n没有满足xyz≠0的整数解。这个是不定方程,它已经由美国数学家证明了(1995年),证明的过程是相当艰深的!
费马小定理:a^p-a≡0(mod p),其中p是一个素数,a是正整数,它的证明比较简单。事实上它是Euler定理的一个特殊情况,Euler定理是说:a^φ(n)-1≡0(mod n),a,n都是正整数,φ(n)是Euler函数,表示和n互素的小于n的正整数的个数(它的表达式欧拉已经得出,可以在“Euler公式"这个词条里找到)。
(1)全部素数可分为4n+1和4n+3两种形式。
(2)形如4n+1的素数能够,而且只能够以一种方式表为两个平方数之和。
(3)没有一个形如4n+3的素数,能表示为两个平方数之和。
(4)形如4n+1的素数能够且只能够作为一个直角边为整数的直角三角形的斜边;4n+1的平方是且只能是两个这种直角三角形的斜边;类似地,4n+1的m次方是且只能是m个这种直角三角形的斜边。
(5)边长为有理数的直角三角形的面积不可能是一个平方数。
(6)4n+1形的素数与它的平方都只能以一种方式表达为两个平方数之和;它的3次和4次方都只能以两种表达为两个平方数之和;5次和6次方都只能以3种方式表达为两个平方数之和,以此类推,直至无穷。
(7)发现了第二对亲和数:17296和18416。
http://baike.baidu.com/view/17568.htm
坨to,你看龙门不就完了
初等数论中有关最大公因数的问题:25a+b=125, d=(a,a+b),则d等于多少...
125是25的倍数,所以b应当是25的倍数,其因子有5、25。设b=25c,则a+c=5 a=0,a+b=125,d=1 a=1,a+b=101,d=1 a=2,a+b=77,d=1 a=3,a+b=78,d=1 a=4,a+b=29,d=1 a=5,a+b=5,d=5 所以当(a,5)=1,即a不为5时,d=1 ...
初等数论 设p是单质数,证明:关于模p的两个平方非剩余的乘积是平方剩余...
定理 x是模p 的二次剩余充要条件是x^[(p-1)\/2]≡1 mod p x是模p 的二次非剩余充要条件是x^[(p-1)\/2]≡ -1 mod p设 a b是两个二次非剩余.则(ab)^[(p-1)\/2]≡a^[(p-1)\/2] *b^[(p-1)\/2]≡(-1)*(-1)≡1mod p所以...
关于《初等数论》中“最小自然数原理”证明的问题,中括号里的是问题...
首先,要明白“最小自然数原理"(亦称良序原理),说的是自然数集的每个非空子集都有个最小元素。所以,【1. 为什么要说明S非空?】应该没有什么疑问了吧。【2. 为什么t1+1比t1大了就不能属于S? 比如说t1+1是{t1+n:n≥1,n∈N}中最小的,t1+1照样可以被放置在集合S中啊,难道是我想法...
有一本关于数论的书,封面是黄色的,谁知道名字吗
人教版数学选修4-6初等数论初步。
求有关数学概论的经典书目...
《运筹学》这是讲规划最优化问题的 《实变函数》&《泛函分析》这两门没学,不加评论 还有的话就是《初等数论》,也没学这门,不过这门讲一些比较考你思维的数学题,有点奥赛的感觉 接着还有《点击拓扑》,这本比近代还要抽象,纯理论的,不过对于拓展一下思维还是可以看看。另外还有很多很多...《...
初等数论关于最小公倍数定理证明的问题
懒得去翻潘老的这本书了。太厚了。也就不管在这之前讲过哪些了,总之避开算数基本定理和带余数除法吧。以下证明分为几步,我用分隔线来书写。———引理:lcm运算满足结合律。(此引理若需证明,追问。)———首先,易证n=2时,a(1)|c,a(2)|c的充要条件是lcm{a(1),a(2)}|c 用短...
关于初等数论的同余
a≡b(mod m)所以a=km+b k是整数 所以a-b=km+b-b=km 所以m|(a-b)
论初等数论与小学数学的关系
定理和循环小数等几个知识点。在没接触初等数论学习之前,我们对同余这个概念很陌生,其实同余在我们小学数学学习,奥数中已经有了很深入的运用。在小学中主要体现在余数的运用上,余数是小学数学中的重要概念,也是数学竞赛的热门话题,其中有关概念多,方法性强。在小学,关于余数问题我们知道:如果整数a...
几何和初等数论有哪些联系?
最后,从应用领域来看,几何和数论都有着广泛的应用价值。例如,在计算机科学中,密码学、图像处理等领域都涉及到大量的几何和数论知识;在物理学中,量子力学、相对论等领域也离不开几何和数论的支持。总之,几何和初等数论之间存在着紧密的联系。它们不仅在历史发展、研究对象、研究方法和应用领域上相互...
古今数学思想与初等数论有关吗
等。《古今数学思想》这部经典著作中,作者重点关注数学家的思想,描述了数学家在高度抽象的数学世界里开疆拓土的冒险历程。该书的中译本分为四册:第一册重点讲述古埃及、古巴比伦的原始数学乃至古希腊数学体系的初步建立,突出了欧几里德《几何原本》,兼顾了中世纪和文艺复兴的代数学和数论。
笃谈盐酸:[答案] 第一章 有关数论的算法 1.1 最大公约数与最小公倍数 1.2 有关素数的算法 1.3 方程ax+by=c的整数解及应用 1.4 求a^b mod n 1.1最大公约数与最小公倍数 1.算法1:欧几里德算法求a,b的最大公约数 function gcd(a,b:longint):longint; begin if b=0 then ...
兴仁县17887147455: 谁能告诉我“初等数论”的全部内容? - ?
笃谈盐酸: 研究数的规律,特别是整数性质的数学分支.是数论的一个最古老的分支.它以算术方法为主要研究方法,主要内容有整数的整除理论、不定方程、同余式等.古希腊毕达哥拉斯是初等数论的先驱.他与他的学派致力于一些特殊整数(如亲和数...
兴仁县17887147455: 关于数论的一些基础知识! - ?
笃谈盐酸: 如果只是限定在初等数论中,那么初等数论的研究对象就比较窄,一般就是整数,甚至是自然数.高级一点的研究连分数就突破这方面的限制.从原则上来讲,初等数论是研究负整数的,比如丢番图方程.而如果只讲最基础的整除、素数,研...
兴仁县17887147455: 初等数论里最简单的定理有哪些? - ?
笃谈盐酸:[答案] 基础知识定义(欧拉(Euler)函数)一组数称为是模的既约剩余系,如果对任意的,且对于任意的,若=1,则有且仅有一个是对模的剩余,即.并定义中和互质的数的个数,称为欧拉(Euler)函数.这是数论中的非常重要的一个函...
兴仁县17887147455: 关于初等数论1.求证任意两个整数的最大公约数存在.2.求221,236,334的最小公倍数. - ?
笃谈盐酸:[答案] 假设存在两个整数a和b不存在最大公约数,则其一定不存在公约数(因为有限个整数中一定有最大的数,而一个数的因数小于这个数,故必定是有限个的),可任何两个数都可以同时被1整除,及两个整数一定存在公约数1,故假设不成立,原命题得...
兴仁县17887147455: 什么是负数集合,整数集合 - ?
笃谈盐酸:[答案] 整数集合 Z = {...,-3,-2,-1,0,1,2,3,...} 一、初等数论 1.1 介绍 1.1.1 什么是数论?高斯说过,数学是科学的皇后,数论是数学的皇后. 数论作为数学里的一个方向,是最阳春白雪的,上帝创造了整数,人们来研究它,于是就有了数论.基本上就是类似1+1...
兴仁县17887147455: 初等数论 求详细解答 - ?
笃谈盐酸: 分类讨论: (1)如果x,y,z被3除的余数互不相同,即余数分别是0,1,2,则它们的和能被3整除, 即等式(x-y)(y-z)(z-x)=x+y+z(*)的右边能被3整除,从而左边也能被3整除, 于是x-y, y-z, z-x中至少有一个能被3整除,这与x,y,z余数不同矛...
兴仁县17887147455: 关于初等数论的8道题目~谢谢250分1.求证:若a^k≡1(mod m),a^n ≡1(mod m),且(k,n)=d,则a^d ≡ 1(mod m).2.设s(a)表示不大于a且与a互质的全体正整... - ?
笃谈盐酸:[答案] 1.因为(k,n)=d,则存在整数s,t,使得ks+nt=d. 所以a^(ks)=1(mod m) a^(nt)=1(mod m) a^d=a^(ks+nt)=1(mod m) 2.因为当(b,a)=1当且仅当(a-b,a)=1. 用如同高斯求1+2+.+100相同的方法可知: 和=1/2 *(a-b+b) *φ(a)=1/2 *a*φ(a). 3.需要证ax+b(x取...
兴仁县17887147455: 关于初等数论的几点问题,整除代表有余数吗?C|A,C|B 那么C|(MA+NB)这结论成立吗?举个例子 15|3 ,15|5 15|(3+5)能整出吗?这是根据定义得来的推论,... - ?
笃谈盐酸:[答案] 整除的意思就是两个整数相除,余数是0.所以如果有非零的余数,那么当然不是整除.至于你说的,你试试几个就知道了.15÷3=5,余数是0,是整除.15÷5=3,余数是0,是整除.15÷(3+5)=15÷8=1余7,余数不是0,不能整除.所以你的...
兴仁县17887147455: 数论的内容是什么? - ?
笃谈盐酸: 数论分为四个部分1初等数论 2解析数论 3代数数论 4几何数论