wolstenholme定理的证明wolstenholme定理是一个数论中的有趣结论,其内容如下:
如果p为素数且p>3,那么对于任意自然数a,都有a^(p-1)≡1(mod p^2)成立,其中(mod p^2)表示取模p^2的余数。
这个定理的证明可以用组合数计数的方式来完成。
证明步骤如下:
1. 考虑p的阶乘,即p!的值。
根据威尔逊定理,我们有(p-1)! ≡ -1 (mod p)。
由此可推出:
p! ≡ -1 (mod p)
2. 计算p!中有多少个p^2的因子。
由于p!的每一个数都可以写成p 个不同的余数(模p),即有p!/(p^2)个不同的余数是被p^2整除的。
因此p!中有p!/(p^2)个p^2因子。
3. 由于p!中有p!/(p^2)个p^2因子,因此p!可以被p^(p!/(p^2))整除,即:
p! ≡ 0 (mod p^(p!/(p^2)))
4. 注意到p!/(p^2) = (p-1)!,将它代入上式,得到:
p! ≡ 0 (mod p^((p-1)!))
5. 将步骤1中的结果代入,可得:
-1 ≡ 0 (m od p^((p-1)!))
6. 由模运算的性质,我们有a^((p-1)!) ≡ 1 (mod p^((p-1)!))
7. 由于p^((p-1)!)能被p^2整除,因此也有:
a^((p-1)!) ≡ 1 (mod p^2)
证毕。
这个证明利用了阶乘、模运算和组合数计数的方法,是一个巧妙而优雅的证明过程。
wolstenholme定理在数论和算术几何中有重要应用,例如在有限域和椭圆曲线的研究中会使用到。
梅森公式
1. 简介
梅森公式（Mersenne formula），是指由法国数学家梅森（Marin Mersenne）在17世纪提出的一种用于生成素数的公式。
梅森公式的基本形式为2^n - 1，其中n是一个自然数。
如果2^n - 1是一个素数，则称之为梅森素数。
梅森公式产生的素数被广泛应用在密码学、计算机科学、通信领域等。
由于其计算简单、结构规律清晰，梅森公式较早被发现，至今为止已知的最大梅森素数为2^82,589,933 - 1。
本文将介绍梅森公式的原理、应用以及一些相关的数学定理。
2. 梅森公式的原理
梅森公式是基于二进制表示的思想，通过将2的幂次方相减得到一个整数，并判断该整数是否为素数。
其基本形式为：
M(n) = 2^n - 1
其中，M(n)为梅森素数。
梅森公式的原理是因为2^n - 1可以通过一种高效的算法进行计算，被称为。
On the order of points on curves overfinitefieldsJos´e Felipe VolochAbstract:We discuss the problem of constructing elements of multiplicative high order infinitefields of large degree over their primefield.We prove that for points on a plane curve,one of the coordinates has to have high order.We also discuss a conjecture of Poonen for subvarieties of semiabelian varieties for which our result is a weak special case.Finally,we look at some special cases where we obtain sharper bounds.0.IntroductionWe prove a theorem which gives information on the multiplicative orders of the coor-dinates of points on plane curves overfinitefields.In the special case where the curve is given by x+y=1our result is related to the main results of[GS]and[ASV],although the results there have stronger hypotheses and stronger conclusions,see section5.Some of our arguments extend those of the aforementioned papers.Our result can also be viewed as a weak form a conjecture of Poonen in the case of two dimensional tori.We discuss Poonen’s conjecture in section4.Throughout this paper F q is afield of q elements where q is a power of the prime p. Our main result is as follows:Theorem.Let F(x,y)∈F q[x,y]be an absolutely irreducible polynomial such that F(x,0)is not a monomial.Given >0,there existsδ>0such that,for d sufficiently large if a,b∈¯F∗q satisfy F(a,b)=0and d=[F q(a):F q]and r,the multiplicative order of a,satisfies r<d2− then b has multiplicative order at least exp(δ(log d)2).1.Elementary estimatesThe following lemma is well-known and stated for convenience.1Lemma1.For any >0we have that#{1≤n≤N|(n,r)=1}=Nφ(r)/r+O(r ).Lemma2.Forfixed integers m,q≥2and real >0If r≥2,(r,mq)=1is an integer and d is the order of q mod r,then,given N<d,there is a cosetΓof q ⊂(Z/r)∗with#{n|1≤n≤N,(n,m)=1,n mod r∈Γ} Nd1− /r−rProof:There areφ(r)/d cosets of q in(Z/r)∗,so there exists a cosetΓ1of q with#{n|1≤n≤N,n mod r∈Γ1}≥(d/φ(r))#{n|1≤n≤N,(n,r)=1}.For each n,1≤n≤N,n mod r∈Γ1we can write n=un ,(n ,m)=1and n maximal.So u is divisible only by primes dividing m and,since u≤n≤N≤d,there are O(d )possibilities for u,hence n belongs to one of O(d )cosets of q ⊂(Z/r)∗and select forΓthe coset among these cosets with the most values of n obtained from the above n. Note also that each n gives rise to at most O(d )values of n,again because this in an upper bound for the number of possible u’s.It follows that#{n|1≤n≤N,(n,m)=1,n mod r∈Γ} (d/φ(r))#{n|1≤n≤N,(n,r)=1}/d2and lemma2now follows from lemma1.2.Some functionfieldsLet K be the functionfield of F(x,y)=0(as in Section0)contained in an algebraic closure of F q(x).Within this algebraic closure,for each n,(n,p)=1,select an n-th root of x,x1/n and consider K n=K(x1/n).We now need to switch viewpoint as follows. Identify all the F q(x1/n)with F q(t)by sending x1/n to t and embed the K n in afixed algebraic closure of F q(t)and denote the image of y∈K n under this embedding by y n,2thus F (t n ,y n )=0.Let m be the degree of the divisor of zeros of x in K .If (n,mp )=1then the extension K n /K is separable of degree n and F (t n ,y )is absolutely irreducible.For those values of n ,the divisor of zeros of y n is supported at the places where t n =αwhere αruns through the roots of F (x,0)=0in ¯Fq .Note that,by hypothesis,one of these roots is nonzero.Lemma 3.The algebraic functions y n ,(n,pm )=1,are multiplicatively independent.Proof:It is enough to show that if L is a function field containing the y n ,n ≤N,(n,pm )=1,that the divisors of the y n in L are Z -linearly independent.This fol-lows by induction on N ,since if (N,p )=1,not all the N -th roots of αare n -th roots of αfor n <N ,for α=0.For a function field L/F q and an element z of L ,denote by deg L z the degree of the divisor of zeros of z in L ,which is also [L :F q (z )]if z in non-constant.We have that deg K n y n n .3.Proof of the main TheoremWith notation as in the statement of the theorem,let N =[d 1− ]and Γ=γ q bethe coset given by lemma 2.Choose an element c ∈¯Fq such that a =c γ.Note that c is also of multiplicative order r .If n ≤N,(n,q )=1,n mod r ∈Γthen n ≡γq j (mod r )for some j and let J be the set of all such j .Thus,for j ∈J ,0=F (a,b )q j =F (a q j ,b q j)and a q j =c n j ,where n j ≤N,(n j ,q )=1,n j mod r ∈Γgives rise to j .It follows that there is a place of K n j above t =c where y n j takes the value b q j .Let T =[ηlog d ],where η>0will be chosen later.If I ⊂J ,let b I = j ∈I b q j .We now claim that the b I are distinct for distinct I ⊂J,|I |≤T .If b I =b I fortwo distinct such subsets I,I ,then the algebraic function z =( j ∈I y n j / j ∈I y n j )−1vanishes at a place of the field L ,compositum of the K n j ,j ∈I ∪I above t =c ,but,denoting by D the degree of F ,3deg L z ≤j ∈I ∪I deg L y n j = j ∈I ∪I [L :K n j ]deg K n jy n j T D 2T N which is smaller than d =[F q (c ):F q ]for a suitably small choice of ηand all d sufficiently large and that is not possible,unless z =0and therefore the y n j ,j ∈I ∪I are multiplica-tively dependent.This contradicts lemma 3.It follows that there are at least |J |T distinct powers of b .Now lemma 2(with /3instead of )gives that|J | d 2− /3/r −r /3 d 2 /3−(d 3/2− ) /3 d 2 /3,hence |J |T ≥(|J |/T −1)T exp(δ(log d )2),for some suitably small δ>0,proving the theorem.4.A conjecture of PoonenConjecture (Poonen).Let A be a semiabelian variety defined over a finite field F q and X a closed subvariety of A .Let Z be the union of all translates of positive-dimensionalsemiabelian varieties (over ¯Fq )contained in X .Then there exists a constant c >0such that for every nonzero x in (X −Z )(¯Fq ),the order of x in A (¯F q )is at least (#F q (x ))c ,where F q (x )is the field generated over F q by the coordinates of x .Our result corresponds to the special case A =G m ×G m but our bound is much weaker than the prediction of the conjecture.Our hypothesis that F (x,0)is not a monomial is a bit stronger than requiring that X =Z ,which would have been a more natural condition.Finally,our result is not symmetric in the x and y coordinates.A symmetric result would be that the order of (a,b )as in the theorem is at least d 3/2− ,which follows immediately from our theorem.However,it follows from the proof of Liardet’s theorem (as e.g.given in [L]),that the order of (a,b )is at least d 2.5.Rational functionsIn this section we discuss the special case where our plane curve can be described by y =R (x ),R (x )∈F q (x ),R (x )not a monomial.In this case,we can obtain much4better bounds.Indeed,following the proof of the theorem,we have that y n=R(t n)so K n=F q(t)and we get the much smaller estimate deg L z T DN.We can,therefore choose a much larger value of T,say T=[dη]for some smallη>0and the proof of the theorem yields that b has multiplicative order at least exp(dδ)with the same notation and assumptions.In[GS]and[ASV]better estimates are obtained(essentiallyδ=1/2)when R(x)=1−x and r=d+16.Gauss PeriodsLet r be prime and a a primitive r-th root of unity in¯F q of degree r−1over F q.If His a subgroup of Z/r we define the Gauss period b=h∈Ha h and we’d like to estimatethe order of b by the above methods.We need the following lemma proved in[BR]. Lemma4.There existsγ∈Z such that,for all h∈H,there exists u h≡γh mod r,|u h|≤r1−1/#H.By choosing c with cγ=a we can write b=h∈Hc u h.We now use the samestrategy as been used twice before and,as in the previous section,obtain the estimate deg z T DN with D≤r1−1/#H.So we choose N=[r1/(2#H)]and lemma2yields J with#J r1/(2#H)− and we can take T=#J so we get that the order of b is at least 2#J,i.e.,2r1/(2#H)− .Acknowledgements:The author would like to thank Bjorn Poonen and Igor Sh-parlinski.References[ASV]O.Ahmadi,I.Shparlinski and J.F.Voloch,Multiplicative order of Gauss periods, preprint2007.[BR]Brauer,Alfred;Reynolds,R.L.,On a theorem of Aubry-Thue.Canadian J.Math. 3,(1951).367–374.5[GS]J.von zur Gathen and I.E.Shparlinski,‘Orders of Gauss periods infinitefields’, Appl.Algebra in Engin.,Commun.and Comp.,9(1998),15–24.[L]ng,Fundamentals of Diophantine Geometry,Springer,New York1983.Dept.of Mathematics,Univ.of Texas,Austin,TX78712,USAe-mail:voloch@6。
CG算法的预处理技术：、为什么要对A进行预处理：其收敛速度依赖于对称正定阵A的特征值分布特征值如何影响收敛性：特征值分布在较小的范围内，从而加速CG的收敛性特征值和特征向量的定义是什么？（见笔记本以及收藏的网页）求解特征值和特征向量的方法：Davidson方法：Davidson 方法是用矩阵( D - θI)- 1( A - θI) 产生子空间，这里D 是A 的对角元所组成的对角矩阵。
θ是由Rayleigh-Ritz 过程所得到的A的近似特征值。
什么是子空间法：Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi 的迭代形式来求解。
这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。
如何取正定矩阵Mk为：Span是什么？:设x_(1,)...,x_m∈V ,称它们的线性组合∑_(i=1)^m?〖k_i x_i \|k_i∈K,i=1,2...m〗为向量x_(1,)...,x_m的生成子空间，也称为由x_(1,)...,x_m张成的子空间。
记为L（x_(1,)...,x_m），也可以记为Span（x_(1,)...,x_m）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：什么是可约矩阵与不可约矩阵？：不可约矩阵（irreducible matrix）和可约矩阵（reducible matrix）两个相对的概念。
定义1：对于n 阶方阵A 而言，如果存在一个排列阵P 使得P'AP 为一个分块上三角阵，我们就称矩阵A 是可约的；否则称矩阵A 是不可约的。
定义2：对于n 阶方阵A=(aij) 而言，如果指标集{1，2，...，n} 能够被划分成两个不相交的非空指标集J 和K，使得对任意的j∈J 和任意的k∈K 都有ajk=0, 则称矩阵 A 是可约的；否则称矩阵A 是不可约的。
