# Lattice Points on the Fermat Factorization Method

Authors: Regis Freguin Babindamana; Gilda Rech Bansimba; Basile Guy Richard Bossoto
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this paper, we study algebraic properties of lattice points of the arc on the conicsx2−dy2=N especially for d=1, which is the Fermat factorization equation that is the main idea of many important factorization methods like the quadratic field sieve, using arithmetical results of a particular hyperbola parametrization. As a result, we present a generalization of the forms, the cardinal, and the distribution of its lattice points over the integers. In particular, we prove that if N−6≡0mod4, Fermat’s method fails. Otherwise, in terms of cardinality, it has, respectively, 4, 8, 2α+1, 1−δ2pi2n+1, and 2∏i=1nαi+1 lattice pointts if N is an odd prime, N=Na×Nb with Na and Nb being odd primes, N=Naα with Na being prime, N=∏i=1npi with pi being distinct primes, and N=∏i=1nNiαi with Ni being odd primes. These results are important since they provide further arithmetical understanding and information on the integer solutions revealing factors of N. These results could be particularly investigated for the purpose of improving the underlying integer factorization methods.


---

## Body

## 1. Introduction

Diophantine equations have been for many decades a very important subject of research in number theory, and lattice points on curves have been studied in the literature particularly by Gauss, and bounds on arcs of conics have also been studied since then (see [1–6]). However, the necessity of representing an integer as difference of two squares, i.e., for a given N∈Z, finding nontrivial couples x,y∈Z2 such that x2−y2=N, appears in the literature as the main idea of many factorization methods (see [7, 8]) as suggested by Fermat (see [9, 10]). While being not hard to observe, its lattice points are easily computable if one knows the factorization of N, and in contrast, this gets exponentially harder when it comes to special cases of N, mainly when N=∏i=1jpi, where pi are large primes, in which case this problem becomes equivalent to factoring the parameter N.For this reason, one of fundamental research problems on conics is to find integral solutions of particular hyperbola parametrizations mainlyx2−y2=N over the integers, particularly when N is a large semiprime, in which case if a computationally efficient algorithm is found, cryptosystems like RSA [11] would no longer be secured.Reviewing the literature, some results on various hyperbola parametrizations and their applications have been studied. Particularly in [1], Javier and Jorge used ideals in quadratic field Qd to find an upper bound for the number of lattice points on Pell’s equation x2−dy2=N, while in [12], Jin et al. used results from the forms of integral solutions of the hyperbola bx2−abxy+ay2=k to solve the same equation where d is of the form p2−q>0. In [13], the author studied a special case of hyperbola and presented the forms of its integral points over Z, and in [14], Yeonok investigated some behaviors of integral points on the hyperbola bx2−abxy+ay2=−bkk∈Z>0 to the generalizations of Binet formula and Catalan’s identity, while in [15], the authors gave an application of group law on affine conics to cryptography. Still, in the previous works, algebraic properties and distribution of lattice points and cardinalities on Fermat’s equation are not presented. More recently, in [16], Gilda et al. investigated algebraic and arithmetical properties on the group structure BNx,y=x,y∈Q×Q/y2=x2−4Nx, mainly isomorphisms, integral solutions, and a description of a factorization method with no generalization to the Fermat factorization equation.In this paper, we use the hyperbola parametrization introduced in [16] to study algebraic properties of lattice points and their distribution for Fermat’s factorization equation for which we find exact upper and lower bounds and we present the forms and cardinalities with a generalization of results for most of special cases of N, using results from the particular hyperbola parametrization.The article is organized as follows:(i)
In Section 1, we give an introduction(ii)
In Section 2, we present the particular hyperbola parametrization and related arithmetical results(iii)
In Section 3, we present the application of the hyperbola parametrization to the study of lattice points on the Fermat equation(iv)
In Section 4, In Section 4, we do a discussion on the likelihood of finding solutions to the Fermat factorization equation(v)
In Section 5, we finally concludeHere is a list of the commonly used nomenclature in this paper:BNx,yQ=x,y∈Q×Q/y2=x2−4Nx: algebraic set of all rational points on BNx,y.BNx,yZ=x,y∈Z×Z/y2=x2−4Nx: algebraic set of all integral points on BNx,y.BNx,yx≥4N=x,y∈Z≥4N×Z≥0/y2=x2−4Nx: algebraic set of integral points on BNx,y whose x−coordinates are greater or equal to 4N.χNa⟶Nb: an injective homomorphism from BNax,y to BNbx,y.CardBNx,y: the cardinal of BNx,y.DivNa: set of divisors of Na.πpn: the set of all prime divisors of n.HN=x,y∈Z2/x2−y2=N: the Fermat factorization equation.δij: the Kronecker symbol.


## 2. BN Hyperbola Parametrization

A conic is an algebraic set satisfying an equation of the formα1x2+2α2xy+α2y2+2α3x+2α4y+α5=0,α1,α2,α3,α4,α5∈R5 where α1,α2,α3≠0,0,0. Setting BN the parametrization defined by x,y∈Q×Q/y2=x2−4Nx, in the projective space P2Q, we have BnX,Y,Z=X:Y:Z∈P2Q/Y2/Z2=X2/Z2−4NX/Z⇔BNX,Y,Z=X:Y:Z∈P2Q/Y2=X2−4NXZ.At infinity, settingZ=0 and considering X,Y>0, we obtain Y2=X2, and the equivalence class X:Y:Z∼X:X:0∼X1:1:0, and hence one of the points at infinity is P∞=1:1:0.From now on,∀N∈Z>0, BNx,y denotes BNx,y over the field Q BNx,yx≥4N denotes BNx,y over Z≥4N×Z≥0 and BNx,yZ denotes BNx,y over the integers, i.e., BNx,y=x,y∈Q×Q/y2=x2−4Nx; and BNx,yx≥4N=x,y∈Z≥4N×Z≥0/y2=x2−4Nx and BNx,yZ=x,y∈Z2/y2=x2−4Nx.Proposition 1.
Consider the application(1)+:BNx,y×BNx,y⟶BNx,yP,Q↦P+Q.
P+Q is defined ∀P=xp,yp, Q=xq,yq∈BNx,y, by(2)xp+q=12Nxp−2Nxq−2N+ypyq+2N,yp+q=12Nypxq−2N+yqxp−2N,x2p=12Nxp−2N2+yp2+2N,y2p=1Nypxp−2N.
Then,BNx,y,+ is an abelian group with neutral element O=4N,0.Proof.
Let us consider the affine spaceQ2x,y.
BN is a hyperbola of equation XY=1, where X=x−y−2N/2N,Y=x+y−2N/2N, i.e., x−2N/2N2−y/2N2=1, with N∈Z>0. Set(3)x−2N=2Ncoshty=2Nsinht⇒x2N−1=coshty2N=sinhtsincecosh2t−sinh2t=1,t1+t2∈t∈Z/cosh2t−sinh2t=1wherecosht1+t2=cosht1cosht2+sinht1sinht2,sinht1+t2=sinht1cosht2+cosht1sinht2.
Given two pointsP=xp,ypandQ=xq,yq∈BNx,y,(4)SetX1=xp2N−1=cosht1,Y1=yp2N=sinht1,X2=xq2N−1=cosht2,Y2=yq2N=sinht2,We then havecosht1+t2=X1X2+Y1Y2,sinht1+t2=Y1X2+X1Y2.
We easily verify thatX1X2+Y1Y22−Y1X2+X1Y22=1.(5)xp+q2N−1=X1X2+Y1Y2yp+q2N=Y1X2+X1Y2⇒xp+q2N=X1X2+Y1Y2+1yp+q2N=Y1X2+X1Y2⇒xp+q=2NX1X2+Y1Y2+1yp+q=2NY1X2+X1Y2,X1X2+Y1Y2+1=xp2N−1xq2N−1+yp2Nyq2N+1=xp−2Nxq−2N+ypyq4N2+1,⇒xp+q=2NX1X2+Y1Y2+1=12Nxp−2Nxq−2N+ypyq+2N,Y1X2+X1Y2=yp2Nxq2N−1+yq2Nxp2N−1=14N2ypxq−2N+yqxp−2N⇒yp+q=2NY1X2+X1Y2=12Nypxq−2N+yqxp−2N.
We have both(6)xp+q=12Nxp−2Nxq−2N+ypyq+2N,yp+q=12Nypxq−2N+yqxp−2N,x2p=12Nxp−2N2+yp2+2N,y2p=1Nypxp−2N.
We denote+ as the above defined additive law. This addition law is strongly unified since point doubling does exist and is well defined.
Now let us consider the application(7)+:BNx,y×BNx,y⟶BNx,yP,Q↦P+Q.
This application is an internal composition law sinceP+Q∈BNx,y, yp+q2=xp+q2−4Nxp+q.(i)
Associativity: given 3 pointsP=xp,yp,Q=xq,yq,T=xt,yt∈BNx,y, here we show that P+Q+T=P+Q+T.
Note that this can be shown either geometrically or analytically, but here we give just the analytic proof.
ConsiderP+Q+T.(8)P+Q+T=xp+q+t=12Nxp+q−2Nxt−2N+yp+qyt+2Nyp+q+t=12Nyp+qxt−2N+ytxp+q−2N=xp+q+t=12N12Nxp−2Nxq−2N+ypyq+2N−2Nxt−2N+12Nypxq−2N+yqxp−2Nyt+2Nyp+q+t=12N12Nypxq−2N+yqxp−2Nxt−2N+yt12Nxp−2Nxq−2N+ypyq+2N−2N=xp+q+t=12N12Nxp−2Nxq−2N+ypyqxt−2N+12Nypxq−2N+yqxp−2Nyt+2Nyp+q+t=12N12Nypxq−2N+yqxp−2Nxt−2N+yt12Nxp−2Nxq−2N+ypyq.(9)9=xp+q+t=12N12Nxp−2Nxq−2Nxt−2N+12Nypyqxt−2N+12Nypytxq−2N+12Nyqytxp−2N+2N,yp+q+t=12N12Nypxq−2Nxt−2N+12Nyqxp−2Nxt−2N+12Nytxp−2Nxq−2N+12Nypyqyt,(10)Secondly we considerP+Q+T=xp+q+t=12Nxp−2Nxq+t−2N+ypyq+t+2Nyp+q+t=12Nypxq+t−2N+yq+txp−2N=xp+q+t=12Nxp−2N12Nxq−2Nxt−2N+yqyt+2N−2N+yp12Nyqxt−2N+ytxq−2N+2Nyp+q+t=12Nyp12Nxq−2Nxt−2N+yqyt+2N−2N+12Nyqxt−2N+ytxq−2Nxp−2N=xp+q+t=12Nxp−2N12Nxq−2Nxt−2N+yqyt+yp12Nyqxt−2N+ytxq−2N+2Nyp+q+t=12Nyp12Nxq−2Nxt−2N+yqyt+12Nyqxt−2N+ytxq−2Nxp−2N,(11)11=xp+q+t=12N12Nxp−2Nxq−2Nxt−2N+12Nyqytxp−2N+12Nypyqxt−2N+12Nypytxq−2N+2Nyp+q+t=12N12Nypxq−2Nxt−2N+12Nypyqyt+12Nyqxt−2Nxp−2N+12Nytxq−2Nxp−2N.
We clearly see by identification that9=11⇒P+Q+T=P+Q+T.(i)
Neutral element:O=4N,0. It is obvious to see that O=4N,0∈BNx,y. Given any point P=xp,yp∈Bx,y, from (3), we have(12)P+O=xp+O=12nxp−2N4N−2N+yp×0+2N=12N2Nxp−2N+2N=xpyp+O=12Nyp4N−2N+0×xp−2N=12N2Nyp=yp,O+P=xO+p=12N4N−2Nxp−2N+0×yp+2N=12N2Nxp−2N+2N=xpyO+p=12N0×xp−2N+yp4N−2N=12N2Nyp=yp.Hence,∀P∈BNx,y,P+O=O+P=P.(ii)
Symmetric element:∀P=xp,yp∈Bx,y,P′=xp,−yp is the symmetric element of P. It is obvious to see that xp,−yp∈BNx,y. Then, we have(13)P+P′=xp+p′=12Nxp−2N2−yp2+2N=12Nxp2−4Nxp+4N2−yp2+2N=12N4N2+2N=4Nyp+p′=12Nypxp−2N−ypxp−2N=12N0=0,P′+P=xp′+p=12Nxp−2N2−yp2+2N=12Nxp2−4Nxp+4N2−yp2+2N=12N4N2+2N=4Nyp′+p=12N−ypxp−2N+ypxp−2N=12N0=0.Hence,∀P=xp,yp,P′=xp,−yp∈BNx,y,P+P′=P′+P=O.(iii)
Commutativity:(14)P+Q=xp+q=12Nxp−2Nxq−2N+ypyq+2N=12Nxq−2Nxp−2N+yqyp+2N=xq+p,yp+q=12Nypxq−2N+yqxp−2N=12Nyqxp−2N+ypxq−2N=yq+p.
Hence,∀P,Q∈BNx,y,P+Q=Q+P.Proposition 2.
LetBNax,y=x,y∈Q×Q/y2=x2−4Nax and BNbx,y=x,y∈Q×Q/y2=x2−4Nbx. Then, the following map:(15)χ:BNax,y⟶BNbx,yx,y↦xNbNa,yNbNa,defines a group homomorphism.Proof.
∀P=xp,yp∈BNax,y, χP=χxp,yp=xpNb/Na,ypNb/Na∈?BNbx,y. xpNb/Na,ypNb/Na∈BNbx,y⇔ypNb/Na2=xpNb/Na2−4NbxpNb/Na=xpNb2/Naxp/Na−4=Nb2xp2−4Naxp/Na2⇒ypNb/Na2=Nb2yp2/Na2=ypNb/Na2. Thus, xpNb/Na,ypNb/Na∈BNbx,y.
ConsiderOBNa=4Na,0 and OBNb=4Nb,0.(16)χOBNa=χ4Na,0=4NaNbNa,0NbNa=4Nb,0=OBNb⇒χOBNa=OBNbi1.
SetP′ the inverse of P in BNax,y; by definition, P′=xp,−yp.
Then,χP′=χxp,−yp=xpNb/Na,−ypNb/Na=χP′⇒χP′=χP′i2.(17)χP+Q=χ12Naxp−2Naxq−2Na+ypyq+2Na,12Naypxq−2Na+yqxp−2Na,=Nb2Na2xp−2Naxq−2Na+ypyq+2Nb,Nb2Na2ypxq−2Na+yqxp−2Na.(18)χP+χQ=xpNbNa,ypNbNa+xqNbNa,yqNbNa=12NbxpNbNa−2NbxqNbNa−2Nb+Nb2Na2ypyq+2Nb,12NbypNbNaxqNbNa−2Nb+yqNbNaxpNbNa−2Na=12NbNbNaxp−2NaNbNaxq−2Na+Nb2Na2ypyq+2Nb,12NbypNb2Na2xq−2Na+yqNb2Na2xp−2Na=NbNa2xp−2Naxq−2Na+ypyq+2Nb,NbNa2ypxq−2Na+yqxp−2Na.
χP+Q=χP+χQi3, (it is the relation i3). Then, relations i1, i2, and (i3) imply that X is a group morphism
Furthermore,Kerχ=x,y∈BNax,y/χx,y=OBNb=OBNa. χ is then injective and Imχ=x′,y′∈BNbx,y/x′,y′=χx,y∀x,y∈BNax,y=BNbx,y since ∀x′,y′∈BNbx,y,∃x,y∈BNax,y such that x′,y′=χx,y. χ is also surjective. ⇒χ is bijective.
Sinceχ is a homomorphism of group and bijective, then χ defines an isomorphism of groups. Thus, BNax,y and BNbx,y are isomorphic.Definition 1.
Given an integerN, we define DivN as the set of all divisors of N. That is to say, DivN=x∈Z/xN.Example 1.
N=18: DivN=1,2,3,6,9,18; ∀Nprime,DivN=1,N.Proposition 3.
(i)
Ifki, kj∈DivN such that ki×kj=N, then ki+kj2,ki2−kj2, kikj+12,kikj2−1∈BNx,y.(ii)
Ifki, kj∈DivN∖1,N with ki, kj primes, then kj/kiN and kj+2kiNα+kiNβ,kj2−ki2Nγ∈BNx,y where Nα=N/ki, Nβ=n/kj, Nγ=N/kikj.(iii)
More generally, ifkN⇔k+2N+N/k,k2−1/kN∈BNx,y.Proof.
(i)
Ifki, kj∈DivN, ki×kj=N. ki+kj2,ki2−kj2∈BNx,yki2−kj22=ki+kj22−4Nki+kj2=ki+kj2ki2+kj2+2N−4N=ki+kj2ki−kj2=ki2−kj22. Also, kikj+12,kikj2−1∈BNx,y⇔kikj2−12=kikj+122−4Nkikj+12=ki2kj+12kj+12−4N/ki=ki2kj+12kj+12−4kj=ki2kj+12kj2+2kj−4kj+1=ki2kj+12kj−12=ki2kj2−12=kikj2−12.(ii)
Ifki, kj∈Divn∖1,N, kj/kiN⇒kj+2kiNα+kiNβ,kj2−ki2Nγ∈BNx,y where Nα=N/ki, Nβ=N/kj, Nγ=N/kikj. It comes to verify that kj+2kiNα+kinβ,kj2−ki2Nγ verifies the equation y2=x2−4Nx. As N=kj×ki, kj,ki being prime and DivN=1,kj,ki,N, then Nα=N/ki=kj, Nβ=N/kj=ki, Nγ=N/kjki=1. We have kj+2kiNα+kiNβ,kj2−ki2Nγ=kj+2kiNα+kiNβ,kj2−ki2Nγ=kj+2kikj+ki2,kj2−ki2×1=kj+ki2,kj2−ki2∈BNx,y⇔kj2−ki22=kj+ki22−4Nkj+ki2=kj+ki4−4Nkj+ki2=kj+ki2kj+ki2−4N=kj+ki2kj2+ki2+2N−4N=kj+ki2kj2+ki2−2N=kj+ki2kj−ki2=kj2−ki22kj+2kikj+ki2,kj2−ki2×1=kj+ki2,kj2−ki2∈BNx,y⇔kj2−ki22=kj+ki22−4Nkj+ki2=kj+ki4−4Nkj+ki2=kj+ki2kj+ki2−4N=kj+ki2kj2+ki2+2N−4N=kj+ki2kj2+ki2−2N=kj+ki2kj−ki2=kj2−ki22. Hence, kj+2kiNα+kiNβ,kj2−ki2Nγ∈BNx,y.(iii)
More generally, ifkN, k+2N+N/k,k2−1/kN∈BNx,y⇔k2−1/kN2=k+2N+N/k2−4Nk+2N+N/k⇔k2−1/kN2=k2+2k+1/kN2−4Nk2+2k+1/kN⇔k2−1/kN2=k2+2k+1/kNk2+2k+1/kN−4N⇔k2−1/kN2=k2+2k+1/kNk2+2k+1−4k/kN⇔k2−1/k2=k2+2k+1/kNk2−2k+1/kN=k+12/kNk−12/kN=k2−12/k2N2=k2−1/kN2.Proposition 4.
IfP=xp,yp∈BNx,yx≥4N, then the following holds:(i)
xp,−yp∈BNx,y.(ii)
−xp+4N,yp∈BNx,y.(iii)
−xp+4N,−yp∈BNx,y.Proof.
(i)
xp,−yp∈BNx,y is straightforward since it results from the symmetry of BNx,y with respect to the Ox axis.(ii)
At the point−xp+4n,yp, we have yp2=−xp+4N2−4N−xp+4N⇔yp2=xp2−8Nxp+16N2+4Nxp−16N2⇔yp2=xp2−4Nxp, ⇒−xp+4N,yp∈BNx,y.(iii)
From the symmetry ofBNx,y with respect to the Ox axis, we obtain −xp+4N,−yp∈BNx,y.Lemma 1.
∀a∈Z, set x=N+a2; then, x,y∈BNx,y if and only if a=1.Proof.
Setx=N+a2; then, y2=N+a4+4NN+a2=N+a2N+a2−4N=N+a2N2+2a−2N+a2 which is square if and only if δ′=a−22−a2=0, which is impossible except for a=1, since a−22−a2=0⇔a2−4a+4−a2=0⇔4a=4⇔a=1. This yields that ∀a∈Z, x=N+a2 satisfies y2=x2−4Nx if and only if a=1.Remark 1.
OverZ, x2−4Nx is square only if either x and x−4N are squares or x−4Nx such that x/x−4N=k2, k∈Z.Theorem 1.
ConsiderBN over Z≥4N×Z≥0 denoted as BNx,yx≥4N. Then, ∀P=xp,yp∈BNx,yx≥4N, xp,yp∈4N,NN+2+1×0,N2−1.Proof.
It is not difficult to see thaty2=x2−4Nx≥0⇔x∈−∞,0∪4N,∞. From the Remark 1, a given x satisfies the condition only if either both x and x−4N are squares or x−4Nx with x/x−4N=k2, k∈Z. Considering the fact that any integer i can be written as a function of N, that is to say i=N+a, where a=i−N, if x is square, then ∃a∈Z such that x=N+a2. From Lemma 1, this holds if and only if a=1. Now assume there exists x>N+12; in this case, ∃b∈Z≥0 such that x=N+12+b. Then,(19)xx−4N=N+12+bN+12+b−4N=N+14+2b−2NN+12+bb−4N=b2+2N+12−4Nb+N+14−4NN+12,and (19) is a square if and only if δ′=b−2N2−bb−4N=0⇔b2−4Nb+4N2−b2+4Nb=0⇔4N2=0⇔N=0, which is absurd since N≠0.
Also, (19) is a square if and only if δ′=N+12−2N2−N+14+4NN+12=0⇔N+14−4NN+12+4N2−N+14+4NN+12=0⇔4N2=0⇔N=0, which is once more absurd since N≠0. ⇒∄b∈Z≥0/x=N+12+b satisfying y2=x2−4Nx, ⇒x∈4N,N+12.
Ifx=4N, y2=16N2−4N4N=0, ⇒y=0. Also, if x=N+12, y2=N+12N+12−4N=N+12N2+2N+1−4N=N+12N−12=N2−12, ⇒y=N2−1, and thus y∈4N,N+12.
Hence,∀P=xp,yp∈BNx,yx≥4N, xp,yp∈4N,NN+2+1×0,N2−1.Proposition 5.
p1 If N=Na×Nb, then there exists an injective homomorphism(20)χNa×Nb⟶N2:BNax,y×BNbx,y⟶BNx,y×BNx,y∀xa,ya∈BNax,y,xb,yb∈BNbx,y,χNa⟶Nxa,ya=Nbxa,Nbya∈BN,χNb⟶Nxb,yb=Naxb,Nayb∈BN.p2 More generally, there is an injective homomorphism(21)χ∏i=1zN⟶Nz:BNax,y×BNbx,y×⋯×BNzx,y⟶∏i=1zBNx,y∀xNi,yNi∈BNix,y,χ∏i=1zNi⟶nzxNi,yNi=∏i=1,j^zNixNi,yNi.Proof.
p1 Set N=Na×Nb and consider BNax,y, BNbx,y and BNx,y and consider the following morphism:(22)χNa×Nb⟶N2:BNax,y×BNbx,y⟶BNx,y×BNx,yxa,ya,xb,yb↦xaNna,yaNNa,xbNNb,ybNNb.We clearly see that it is a morphism since it splits into morphismsχNa⟶N and χNa⟶N that are already known to be group morphisms from Proposition 2. It stays now to prove the injection. Given P1,P2∈BNax,y×BNbx,y, P1′,P2′∈BNax,y×BNbx,y such that χNa×Nb⟶N2P1,P2=χNa×Nb⟶N2P1′,P2′ where P1=xa,ya,P2=xb,yb,P1′=xa′,ya′ and P2′=xb′,yb′. Then,(23)xaNNa,yaNNa,xbNNb,ybNNb=xa′NNa,ya′NNa,xb′NNb,yb′NNb⇒xaNNa,yaNNa=xa′NNa,ya′NNaxbNNb,ybNNb=xb′NNb,yb′NNb⇔xaNNa=xa′NNaxbNNb=xb′NNb,yaNNa=ya′NNaybNNb=yb′Nnb⇒xa=xa′,ya=ya′,xb=xb′,yb=yb′.Hence,χNa×Nb⟶N2P1,P2=χNa×Nb⟶N2P1′,P2′⇔P1=P1′ and P2=P2′, hence the injection.p2 This comes straightforward from p1.Example 2.
We consider the two hyperbolas plotted in Figure1.(i)
N=221=Na×Nb=13×17:(24)B221x,yx≥4N=884,0,900,120,3332,2856,4212,3744,49284,48840,B13x,yx≥4N=52,0,196,168,B17x,y=68,0,324,288,χ13×17⟶2212:B13x,yx≥4N×B17x,yx≥4N⟶B221x,yx≥4N×B221x,yx≥4Nxa,ya,xb,yb↦17x1,17y1,13xb,13yb,χ13⟶22152,0=17×52,17×0=884,0∈B221x,y,χ13⟶221196,168=17×196,17×168=3332,2856∈B221x,y,χ17⟶22168,0=13×68,13×0=884,0∈B221x,y,χ17⟶221324,288=13×324,13×288=4212,3744∈B221x,y.(ii)
N=210=2×3×5×7:(25)B210x,yx≥4N=840,0,841,29,845,65,847,77,864,144,867,153,875,175,896,224,945,315,961,341,968,3521000,400,1029,441,1083,513,1120,560,1183,637,1215,675,1352,832,1369,851,1445,935,1512,1008,1681,1189,1715,1225,1920,1440,2023,1547,2209,1739,2541,2079,2645,2185,2888,2432,3375,2925,3584,3136,4107,3663,4840,4400,5329,4891,6727,6293,7776,7344,9245,8815,11449,11021,15123,14697,22472,22048,44521,44099B2x,yx≥4N=8,0,9,3,B3x,y=12,0,16,8,B5x,y=20,0,36,24B7x,y=28,0,64,48,χ2×3×5×7⟶2104:B2x,y×B3x,y×B5x,y×B7x,y⟶∏i=14B210x,y=B210x,y×⋯×B210x,yxa,ya,xb,yb,xc,yc,xd,yd↦105x1,105y1,70x2,70y2,42x3,42y3,30x4,30y4,χ2⟶2108,0=105×8,105×0=840,0∈B210x,y,χ2⟶2109,3=105×9,105×3=945,315∈B210x,y,χ3⟶21012,0=70×12,70×0=840,0∈B210x,y,χ3⟶21016,8=70×16,70×8=1120,560∈B210x,y,χ5⟶21020,0=42×20,42×0=840,0∈B210x,y,χ5⟶21036,24=42×36,42×24=1512,1008∈B210x,y,χ7⟶21028,0=30×28,30×0=840,0∈B210x,y,χ7⟶21064,48=30×64,30×48=1920,1440∈B210x,y.Figure 1
B13x,yx≥52 and B221x,yx≥884.Definition 2.
A prime divisor of an integern is any prime number p∈Divn. We denote πpn as the set of all prime divisors of n and πpn as the number of prime divisors of n.Example 3.
5 is a prime divisor of 40 since5∈Div40=1,2,4,5,8,10,20,40. πp40=2,5 and πp40=2.Proposition 6.
SetN=∏i=1δpi, pi primes and consider BNx,yx≥4N=x,y∈Z≥4N×Z≥0/y2=x2−4Nx. Set n=πpN and Un as the cardinal of BNx,yx≥4N. Then, Un=3Un−1−1∀n≥1 with U0=1. In this case, we have the induction relation Un+2=2Un+1+3Un−2 and the sum of cardinals of BNix,yx≥4Ni given by the general term Un is Sn=∑i=1nUi=1/2n−3/41−3n.Proof.
n=πpN, Un=BNx,yx≥4N=3Un−1−1 where U0=1, i.e., Bmx,yx≥4m=Uπpm=3Uπpm−1−1.
By induction onn, we haveForn=1, U1=3U0−1=2 (true).Forn=2, U2=3U1−1=5 (true).
Assume the relation to be true forn, i.e., Un=3Un−1−1, and let us show the relation to be true for n+1.(26)Uπpm+1=33Uπpm−1−1−1=3Uπpm−1=3Un−1=Un+1.
By the same,(27)Un+1=3Un−1+2=3Un−1,(28)Un+2=3Un+1−1+2=3Un+1−1.
By substituting (27) and (28), we obtain(29)Un+2+Un+1=3Un+1−1+3Un−1=3Un+1+3Un−2⇒Un+2=2Un+1+3Un−2.
ForSn:(30)U1=3U0−1,U2=3U1−1=33U0−1−1=32U0−3−1,U3=3U2−1=332U0−3−1−1=33U0−32−3−1,U4=3U3−1=333U0−32−3−1−1=34U0−33−32−3−1,U5=3U4−1=334U0−33−32−3−1−1=35U0−34−33−32−3−1,U6=3U5−1=335U0−34−33−32−3−1−1=36U0−35−34−33−32−3−1,⋮Un=3Un−1−1=3nU0−∑i=0n−13i=3n−∑i=0n−13isinceU0=1∑j=1nUj=∑j=1n3Uj−1−1=∑j=1n3j−∑i=0j−13i=∑j=1n3j−∑j=1n∑i=0j−13i=∑j=1n3j−∑j=1n1−3j1−3=∑j=1n3j+12∑j=1n1−3j=∑j=1n3j+12n−12∑j=1n3j=12n+12∑j=1n3j=12n−321−3n⇒Sn=∑j=1nUj=12n−341−3n.Example 4.
(i)
m=253, n=πpm=2, and U2=3U1−1, knowing U1=3U0−1=31−1=2 since U0=1. Thus, U2=32−1=5⇒B253x,yx≥4m=5.Verification:(31)B253x,yx≥4m=1012,0,1156,408,3312,2760,6336,5808,64516,64008,B253x,yx≥4m=5.(ii)
m=30 and n=πpm=3, U3=3U2−1 knowing U2=5, and thus U3=35−1=14⇒B30x,yx≥4m=14.Verification:(32)B30x,yx≥4m=120,0,121,11,125,25,128,32,135,45,147,63,160,80,169,91,216,144,245,175,289,221,363,297,512,448,961,899,and thusB30x,yx≥4m=14.(iii)
m=2002, n=πpm=4, and U4=3U3−1 knowing U3=14, and thus U4=314−1=41⇒B2002x,yx≥4m=41.Verification:(33)B2002x,yx≥4m=8008,0,8019,297,8064,672,8125,975,8424,1872,8575,2205,8800,2640,9009,3003,9583,3885,10609,5253,10933,5655,11583,6435,11979,6897,12769,7797,15379,10647,16200,11520,17325,12705,18304,13728,20808,16320,24649,20253,26208,21840,27889,23547,30184,25872,32175,27885,37249,33003,45000,40800,48139,43953,56133,51975,81133,77025,85849,81747,95139,91047,147175,143115,158184,154128,186208,182160,290304,286272,312325,308295,368379,364353,576583,572565,1006009,1001997,2008008,2004000,4012009,4008003,and thus B2002x,yx≥4m=41.Theorem 2.
(1)
N is prime if and only if BNx,yx≥4N=2.(2)
IfN=Na×Nb where Na and Nb are distinct primes, then CardBNx,yx≥4N=5.(3)
IfN=Na×Nb×Nc where Na, Nb and Nc are distinct primes, then CardBNx,yx≥4N=14.(4)
IfN=Na×Nb×Nc×Nd where Na, Nb, Nc, and Nd are distinct primes, then CardBNx,yx≥4N=41.(5)
CardBNx,yx∈Z=4CardBNx,yx≥4N−1+14N,0+10,0=4CardBNx,yx≥4N−2.(6)
SetNa as a prime number, and α∈Z≥0 such that N=Naα. Then, CardBNx,yx≥4N=α+1, and CardBNx,yx∈Z=4α+2.(7)
IfN≠Naα,p,α∈Z≥02, CardBNx,yx≥4N=CardDivN+∑i,j∈DivN∖1,N/i×j=N1−δij.
More generally,CardBNx,yx∈Z=4CardDivN+∑i,j∈DivN∖1,N/i×j=N1−δij−2.Proof.
(i)
(2), (3), (6), and (9) come straightforward from the Proposition 6. Nevertheless, we give other proofs for (2) and (3) using injective homomorphisms.(1)
AssumeNa prime; then, DivNa=1,Na. The only injective homomorphisms in BNax,yx≥4Na are χ1⟶Na giving the point 4Na,0 and the trivial automorphism χNa⟶Na giving the point NaNa+2+1,Na2−1 from Proposition 3. As 1Na and NaNa⇒BNax,yx≥4Na=4Na,0,NaNa+2+1,Na2−1, BNax,yx≥4Na=2. Now assume BNax,yx≥4Na=2, and we know that 4Na,0 and Na+12,Na2−1∈BNax,yx≥4Na; that is to say, BNax,yx≥4Na=4Na,0,Na+12,Na2−1. From Proposition 6, Un=3Un−1−1∀n≥1 with U0=1, and since the cardinal Un=2, ⇒n=1, i.e., Un=3U0−1=2, Na is prime.(2)
IfN=Na×Nb where Na and Nb are distinct primes, then DivN=1,Na,Nb,N. We then have the following injective morphisms χ1⟶N, χNa⟶N, χNb⟶N and the trivial automorphism χN⟶N. As DivNa=1,Na and DivNb=1,Nb, then BNax,yx≥4Na=2 and BNbx,yx≥4Nb=2; in this case, BNax,yx≥4Na=4Na,0,NaNa+2+1,Na2−1=PNa, BNbx,yx≥4Nb=4Nb,0,NbNb+2+1,Nb2−1=PNb. χN⟶Nx,y=NN+2+1,N2−1=PN, χ1⟶Nx,y=χNa⟶N4Na,0=χNb⟶N4Nb,0=4N,0=P0,χNa⟶NPNa=P1,χNb⟶NPNb=P2, and from the Proposition 3, PNa+Nb=Na+Nb2,Na2−Nb2=P3⇒BNx,yx≥4N=P0,P1,P2,P3,PN. Hence, CardBNx,yx≥4N=5.(5)
From Proposition4, ∀P=xp,yp∈Z≥4N2×Z≥0, P∈BNx,y; then, xp,−yp,−xp+4N,yp,−xp+4N,−yp∈BN3x,y; as ∀xp≥4N, −xp+4N≤0 except for the point 4N,0 which gives the point itself and the point 0,0, then each point on BNx,yx≥4N∖4N,0 leads to 4 points on BNx,yZ⇒CardBNx,yx∈Z=4CardBNx,yx≥4N−14N,0+14N,0+10,0, i.e., CardBNx,yx∈Z=4CardBNx,yx≥4N−2.(6)
By induction: ifα=1, N=Na, then from (2), BNax,yx≥4Na=2=α+1 (true). If α=2, N=Na2, from Proposition 3, since DivN=DivNaα=1,Na,N, we have the following injective morphisms χ1⟶N, χNa⟶N and the trivial automorphism χN⟶N yielding to respectively 3 points 4N,0, NaNa+12,NaNa2−1, and N+12,N2−1. Thus, BNx,yx≥4N=3=α+1 (true). Now assume the assumption to be true for α, i.e., for N=Naα with DivN=1,Na,…,Naα−1,N, BNx,yx≥4N=α+1. Let us prove that to be also true for α+1. If N=Naα⇒N⋅Na=Naα+1. In this case, DivN=1,Na,…,Naα−1,Naα,N. To the injective morphisms obtained with α from the induction hypothesis, there is now the new injective homomorphism got with the multiplication of N by Na. In this case, BNx,yx≥4N=α+1+1=α+2. One deduces from (11) that CardBNx,yx∈Z=4CardBNx,yx≥4N−2=4α+1−2=4α+2.(7)
From Proposition5, ∀i∈DivN,∃χi⟶N:Bix,y⟶BNx,y, it is clear that CardDivN≤CardBNx,yx≥4N. By the same, we have injective homomorphisms obtained by composition ∀i,j∈DivN∖1,N,i×j=N⇒i+j2,i2−j2∈BNx,y and we have the injective homomorphisms χi×j⟶N for each case. Therefore, CardBNx,yx≥4N=CardDivN+Cardi,j∈DivN2/i⋅j=N.
Then, for eachi,j verifying this condition, we can express this condition according to the Kronecker symbol. Indeed for the injective homomorphism χi⋅j⟶N, if i=j, there is no point since i⋅j=N. If i≠j, we have a point since i⋅jN. Hence, CardBNx,yx≥4N=CardDivN+∑i,j∈DivN∖1,N/i×j=N1−δij. From (11), we deduce that CardBNx,yx∈Z=4CardDivN+∑i,j∈DivN∖1,N/i×j=N1−δij−2.Proposition 7.
The cardinal ofBN over Z is given by the sequence Un∗=62Un−1−1, and the sum of this sequence is Sn∗=2n−31−3n.Proof.
These results are straightforward from Theorem2. Un∗=4Un−2 from the Proposition 6. Then, Un∗=43Un−1−1−2=12Un−1−6=62Un−1−1. Also, Sn∗=4Sn=41/2n−3/41−3n=2n−31−3n.Plots ofUn,Sn,Un∗and,Sn∗for different values of nare based on the dataset given by Table 1 for different distinct primes.Comment on the plots on Figure2 plotted with data from Table 1, from the first plot on the left corresponding to cardinals and sums of cardinals of Bnx,yx≥4n, we observe that the number of solutions grow quasi-exponentially with the number of distinct prime factors o n. In other words, the more distinct the prime factors of n, the bigger the algebraic set of Bn. Also, from the second plot (on the right), we observe that asymptotically, Bnx,yx≥4n and Bnx,yx∈Z have the same behavior. In other words, knowing Bn over positive integers gives as much information as knowing Bn over the whole integers.Figure 2
CardBnx,yx≥4n (a) and CardBnx,yx∈Z (b) over a sample of n’s up to a product of 15 distinct primes.
(a)(b)Table 1
Un,Sn;Un∗,Sn∗ based on a dataset of up to 15 distinct prime factors.
n123456789101112131415Un25144112236510943281984229 52588 574265 721797 1622391 4857174 454Sn2721621845491643492414 76644 291132 865398 5861195 7483587 23310 761 687Un⋆820561644881460437613 12439 368118 100354 2961062 8843188 6489565 94028 697 816Sn⋆828842487362196657219 69659 064177 164531 4601594 3444782 99214 348 93243 046 748Theorem 3.
IfN=Na×Nb, Na and Nb are primes, then BNx,yx≥4N=P1,P2=P0,P1,P2,P3,P4 with P3=P1+P2, P4=P2+P3=P1+2P2 where P1=Na+Nb2,Na2−Nb2,P2=NbNa+12,NbNa2−1, P3=NaNb+12,NaNb2−1,P4=N+12,N2−1.Proof.
N=Na⋅Nb, with Na and Nb primes, then DivN=1,Na,Nb,N and DivN=4. By Proposition 6 and Theorem 2, CardBNx,yx≥4N=U2=5⇒BNx,yx≥4N=P0,P1,P2,P3,P4. Furthermore, from Proposition 3, Na+Nb2,Na2−Nb2,NbNa+12,NbNa2−1,NaNb+12,NaNb2−1,N+12,N2−1∈BNx,yx≥4N. Considering the addition law on BNx,yx≥4N given by Proposition 1 and setting P1=Na+Nb2,Na2−Nb2,P2=NbNa+12,NbNa2−1,P3=NaNb+12,NaNb2−1,P4=N+12,N2−1, one verifies as well in the polynomial ring QNa,Nb,N that P1+P2=P3, P2+P3=P1+2P2=P4.
Thus,BNx,yx≥4N=P1,P2. It is not hard to see that BNx,yx≥4N,+,⋅ is then a 2−dimensional Q−vector space with basis P1,P2.


## 3. Application ofBN Parametrization to the Lattice Points on x2−y2=N Fermat Equation

In this section, we present results related to the lattice points on the arc of the hyperbolax2−y2=N using results from BN parametrization.Theorem 4.
∀a,b∈BNx,yx≥4N, if ∃x∈Z such that a=4x2, then x verifies x2−y2=N. In this case, for positive lattice points, N is the lower bound for x.Proof.
ConsiderXY=N, with X=x+y and Y=x−y which yields x2−y2=N.(34)x+y−x−y2=x+y2+x−y2−2N=x+y+x−y2−2N−2N=2x2−4N.
Set2x2=a; then, 4x2=a.
a−4N and a are squares, yielding aa−4N to be also a square.
Then, there existsb∈Z/b2=aa−4N=a2−4Na=BNx,yx≥4N. Hence, ∀a,b∈BNx,yx≥4N, if ∃x∈Z/a=4x2, ⇒∃y∈Z/x2−y2=N. Also, as a≥4N, then 4x2≥4N, considering positive x, ⇒x≥N.From now on, we denoteHN=x,y∈Z2/x2−y2=N and S as the algebraic set of HN over the integers.Theorem 5.
∀x,y∈Z≥02, x,y∈HN; then, x,y∈⌈N1/2⌉,1/2N+1×0,1/2N−1.Proof.
Assumex,y∈Z≥02 and x,y∈HN.
From Theorem1, ∀a,b∈BNx,yx≥4N, a,b∈4N,NN+2+1×0,N2−1. From Theorem 4, a=4x2, where x,y verifies HN. If a=4N, then x2=N, ⇒x=N1/2 taking into account the assumption. Since we work over the integers, we take the ceiling for x. By the same, y2=x2−N=0, ⇒y=0. If a=N+12, then x2=1/4N+12, ⇒x=1/2N+1. By the same, y2=x2−N=1/4N+12−N=1/4N−12, ⇒y=1/2N−1 taking into account the assumption.
Hence, the bounds forx,y, x,y∈⌈N1/2⌉,1/2N+1×0,1/2N−1.Lemma 2.
Given the sequence(35)Nk=6+4k,ifk≥1,4,ifk=0.Any term of this sequence and, respectively, any number of this form cannot be represented as difference of two squares.Proof.
Ifk=0,N0=N=4, as Div4=1,2,4, we have from Proposition 5, the following homomorphisms χ1⟶N,χ2⟶N,χN⟶N. From Theorem 2, (17), CardB4x,yx≥4N=2+1=3, and considering Proposition 5, we have χ1⟶N⟶4N,0=16,0; χ2⟶N:B2x,y⟶BNx,y,9,3↦2×9,2×3=18,6 where 9,3∈B2x,y and χN⟶N⟶N+12,N2−1=25,15⇒B4x,yx≥16=16,0,18,6,25,15, ∄a,b∈B4x,yx≥16/a=4x2,x∈Z. Hence, 4 cannot be written as difference of two squares.
∀k>0,Nk=N=6+4k=23+2k, and DivN=1,2,3+2k∪Div3+2k∖1,3+2k. By Proposition 3, since 2N, then 4N+N/2,3N/2=4N+3+2k,33+2k∈BNx,y. Also, as 3+2kN, then 3+2kN+2,23+2k2−2∈BNx,y.
By induction, fork=1,N1=N=10,DivN=1,2,5,10. From Theorem 2, CardBnx,yx≥4n=5. We have from Proposition 5 the following homomorphisms: χ1⟶N,χ2⟶N,χ5⟶N,χ10⟶N, and from Proposition 3, the following points: 1N⟶4N,0=40,0∈B10x,y, 2N⟶4N+N/2,3N/2=45,15∈B10x,y, 5N⟶7N+N/5,24N/5=72,48∈B10x,y, NN⟶N+2N+1,N2−1=121,99∈B10x,y, and since 2×5=10, then 5+22,52−22=49,21∈B10x,y. Thus, B10x,yx≥40=40,0,45,15,49,21,72,48,121,99. ∄a,b∈B10x,yx≥16/a=4x2,x∈Z. Hence, 10 cannot be represented as difference of two squares.
Fork=2,N2=N=14,DivN=1,2,7,14. From Theorem 2, CardBNx,yx≥4N=5. We have from Proposition 5 the following homomorphisms: χ1⟶N,χ2⟶N,χ7⟶N,χ14⟶N, and from Proposition 3, the following points: 1N⟶4N,0=56,0∈B14x,y, 2N⟶4N+N/2,3N/2=63,21∈B14x,y, 7N⟶9N+N/7,72−1N/7=128,96∈B14x,y, NN⟶N+2N+1,N2−1=225,195∈B14x,y, and since 2×7=14, then 7+22,72−22=81,45∈B14x,y. Thus, B14x,yx≥56=56,0,63,21,81,45,128,96,225,195. ∄a,b∈B14x,yx≥56/a=4x2,x∈Z. Hence, 14 cannot be represented as difference of two squares.
Assume the assumption to be true fork, i.e., for the term Nk, and let us show that it is true for k+1.(36)Nk+1=N=6+4k+1=23+2k+1=23+2k+22=Nk+4.
SinceNk=6+4k⇒Nk+1=6+4k+4=6+4k+1. Set k′=k+1; then, Nk′=6+4k′ (true by assumption).
Hence,∄x∈Z/4x2,y∈BNk+1x,yx≥Nk+1.Theorem 6.
Consider the Fermat–Diophantine equationx2−y2=N. If 4N−6, i.e., N−6≡0 mod 4, then S=∅.Proof.
This result is straightforward from Lemma2.Proposition 8.
IfN is an odd prime, then CardHN=4. In this case,(37)S=12N+1,12N−1,−12N+1,−12N−1,−12N+1,12N−1,12N+1,−12N−1.Proof.
IfN is prime, from Theorem 2,(1)
CardBNx,yx≥4N=2.(2)
CardBNx,yZ=42−2=6. From Proposition 5, through injective homomorphisms, we have BNx,yx≥4N=4N,0,N+12,N2−1.
Now sinceN is an odd prime, N+1 is even, and 4N+12. Setting a=N+12, ∃x∈Z/a=4x2⇔x=1/2N+1 (we first consider the positive values of x and y), and as x satisfies x2−y2=N, ⇒y=1/2N−1. Then, over Z+, HN=1/2N+1,1/2N−1. Taking into account symmetric properties of HN, x,y∈HN⇒−x,y,x,−yand−x,−y∈HN. Hence, CardHN=4 and S=1/2N+1,1/2N−1,−1/2N+1,−1/2N−1,−1/2N+1,1/2N−1,1/2N+1,−1/2N−1.Remark 2.
IfN is an even prime, i.e., N=2, then CardHN=0. This result is straightforward from Theorem 5, since 4N−6.Proposition 9.
IfN=Naα, Na is prime. Then, CardHN=2α+1. In this case,(38)S=12Naα−i+Nai,12Naα−i−Nai,−12Naα−i+Nai,12Naα−i−Nai,12Naα−i+Nai,−12Naα−i−Nai,−12Naα−i+Nai,−12Naα−i−Naii=0,1…α¯.Proof.
IfN=Naα, Na is prime, from Theorem 2,(1)
CardBNx,yx≥4N=α+1.(2)
CardBNx,yZ=4α+2. From Proposition 5, through injective homomorphisms, we have BNx,yx≥4N=4N,0,Naα−i+Nai2,Na2α−i−Na2i,NaiNaα−i+12,NaiNa2α−i−1i=0,1…α. It is obvious to see that NaiNaα−i+12 is not square ∀i=0,1,…,α¯. Now since Na is prime, then Naα−i+Nai is even ∀i=0,1,…,α¯, ⇒Naα−i+Nai2 is a multiple of 4. From Theorem 4, for this case, ∃x∈Z such that a=Naα−i+Nai2=4x2⇒BNx,yx≥4N has a total of α+1 such terms since i=0,1,…,α¯. Now considering the redundant terms each time i=α−i, since i ranges from 0 to a, then each term Naα−i+Nai is the same as Nai+Nαα−i because of the commutativity of the additive law. Then, we have exactly α+1/2 such terms after removing the redundant terms for each of the α+1 terms.
Then, overZ+, CardHN=1/2α+1. Taking into account the symmetry of HN, x,y∈HN⇒−x,y,x,−yand−x,−y∈HN, then over Z, we have CardHN=4×1/2α+1=2α+1.
Sincea=Naα−i+Nai2=4x2, ⇒x2=1/4Naα−i+Nai2, then considering the positive values of x and y, x=1/2Naα−i+Nai and y2=x2−N=1/4Naα−i+Nai2−Naα=1/4Na2α−i+2Naα−4Naα+Na2i=1/4Naα−i−Nai2, y=1/2Naα−i−Nai.
Hence,S=1/2Naα−i+Nai,1/2Naα−i−Nai,−1/2Naα−i+Nai,1/2Naα−i−Nai,1/2Naα−i+Nai,−1/2Naα−i−Nai,−1/2Naα−i+Nai,−1/2Naα−i−Naii=0,1…α¯.Proposition 10.
LetN=Na×Nb, with Na, Nb odd primes. Then, CardHN=8. In this case,(39)S=12Na+Nb,12Na−Nb,−12Na+Nb,12Na−Nb,12Na+Nb,−12Na−Nb,−12Na+Nb,−12Na−Nb,12N+1,12N−1,−12N+1,−12N−1,−12N+1,12N−1,12N+1,−12N−1.Proof.
LetN=Na×NbwithNaNb odd primes, from Theorem 2,(1)
CardBNx,yx≥4N=5.(2)
CardBNx,yZ=45−2=18.
From Proposition5, through injective homomorphisms, we have BNx,yx≥4N=4N,0,Na+Nb2,Na2−Nb2,NaNb+12,NaNb2−1,,NbNa+12,NbNa2−1,,N+12,N2−1.
Now sinceNa, Nb, N=NaNb are an odd, Na+Nb and N+1 are even. Then, 4Na+Nb2 means 4 divides and 4N+12. Set a1=Na+Nb2, ∃x∈Z/a1=4x2⇔x=1/2Na+Nb, since x satisfies x2−y2=N, ⇒y=1/2Na−Nb and a2=N+12, ∃x∈Z/a2=4x2⇔x=1/2N+1 (we first consider the positive values of x and y), since x satisfies x2−y2=N, ⇒y=1/2N−1. Then, over Z+, HN=1/2Na+Nb,1/2Na−Nb,1/2N+1,1/2N−1. Taking into account symmetric properties of HN, x,y∈HN⇒−x,y,x,−yand−x,−y∈HN. Hence, CardHN=8 and S=1/2Na+Nb,1/2Na−Nb,−1/2Na+Nb,1/2Na−Nb,1/2Na+Nb,−1/2Na−Nb,−1/2Na+Nb,−1/2Na−Nb,1/2N+1,1/2N−1,−1/2N+1,−1/2N−1,−1/2N+1,1/2N−1,1/2N+1,−1/2N−1.Proposition 11.
LetN=∏i=1npi with, pi odd primes, then CardHN=Un=2Un−1=2n+1, and more generally, CardHN=1−δ2pi2n+1 for all distinct primes pi, with δ2pi being the Kronecker symbol which is given by(40)δ2pi=1,ifpi=20,else,∀i=1…n¯.Proof.
We give a proof by induction.
Forn=1, if p1=2, CardHN=0 (true) from Remark 2 and if p1≠2, CardHN=4 (true) from Proposition 8.
Now assume the proposition is true forn, and let us prove it to be also true for n+1.
Forn+1, CardHN=Un+1=2Un. From the recurrence hypothesis, Un=2Un−1=1−δ2pi2n+1; then, CardHN=Un+1=4Un−1=21−δ2pi2n+1=1−δ2pi2n+2, hence the result.Remark 3.
IfN=Na×Nb, Na, Nb primes Set Na=2, then S=∅ and CardHN=0. Indeed, N−6=2Nb−6=2Nb−3. Since Nb is prime, ⇒Nb−3 is even. Then, ∃A∈Z such that Nb−3=2A, ⇒N−6=22A=4A. Since 4N−6, From Theorem 5, S=∅.Example 5.
Solvex2−y2=352706. Here, N=352706=2⋅176353. From Proposition 11, CardHN=1−δ2pi2n+1. Here, δ2pi=1 since ∃pi: pi=2. In this case, CardHN=1−122+1=0. This algebraic set is empty over the integers.Proposition 12.
LetN=Naα×Nbβ with Na and Nb odd primes Then, CardHN=2α+1β+1. In this case,(41)S=12Naα−iNbβ−j+NaiNbj,12Naα−iNbβ−j−NaiNbj,12Naα−iNbβ−j+NaiNbj−12Naα−iNbβ−j−NaiNbj,12Naα−iNbβ−j+NaiNbj,−12Naα−iNbβ−j−NaiNbj,−12Naα−iNbβ−j+NaiNbj,−12Naα−iNbβ−j−NaiNbji=0,…,αj=0,…,β.Proof.
From Proposition5, through injective homomorphisms, we have BNx,yx≥4N=4N,0,Naα−iNbβ−j+NaiNbj2,Na2α−iNb2β−j−Na2iNb2j,NaiNbjNaα−iNbβ−j+12,NaiNbjNa2α−iNb2β−j−1i=0,…,α;j=0,…,β. For each value of i, the value of j covers 0,β.
It is obvious to see thatNaiNbjNaα−iNbβ−j+12 is not square ∀i=0,1,…,α¯ and j=0,1…β¯. Now since Na and Nb are primes, then Naα−iNbβ−j+NaiNbj is even ∀i=0,1…α¯ and j=0,1…β¯, ⇒Naα−iNbβ−j+NaiNbj2 is a multiple of 4. From Theorem 4, for this case, ∃x∈Z such that a=Naα−iNbβ−j+NaiNbj2=4x2. ⇒BNx,yx≥4N has a total of α+1β+1 such terms since i=0,1…α¯ and j=0,1…β¯. Now, considering the redundant terms each time i=α−i and j=β−j then this leads each term Naα−iNbβ−j+NaiNbj to be the same as NaiNbj+Naα−iNbβ−j, which is the same due to the commutativity of the common addition law, and then we have exactly 1/2α+1β+1 such terms without any redundancy, since all of the α+1β+1 terms represent all terms together with their doublet.
Then, overZ+, CardHN=1/2α+1β+1. Taking into account the symmetry of HN, x,y∈HN⇒−x,y,x,−y and −x,−y∈HN, then over Z, we have CardHN=4×1/2α+1β+1=2α+1β+1.
Sincea=Naα−iNbβ−j+NaiNbj2=4x2, ⇒x2=1/4Naα−iNbβ−j+NaiNbj2; then, considering the positive values of x and y, x=1/2Naα−iNbβ−j+NaiNbj and y2=x2−N=1/4Naα−iNbβ−j+NaiNbj2−N=1/4Naα−iNbβ−j+NaiNbj2−NaαNbβ=1/4Na2α−iNb2β−j+Na2iNb2j−2NaαNbβ=1/4Naα−iNbβ−j−NaiNbj2, y=1/2Naα−iNbβ−j−NaiNbj. Hence, S=1/2Naα−iNbβ−j+NaiNbj,1/2Naα−iNbβ−j−NaiNbj,1/2Naα−iNbβ−j+NaiNbj,−1/2Naα−iNbβ−j−NaiNbj,1/2Naα−iNbβ−j+NaiNbj,−1/2Naα−iNbβ−j−NaiNbj,−1/2Naα−iNbβ−j+NaiNbj,−1/2Naα−iNbβ−j−NaiNbji=0,…,α;j=0,…,βProposition 13.
IfN=∏i=1nNiαi, with Ni odd primes. Then, CardHN=2∏i=1nαi+1. In this case,(42)S=±12∏i=1jNiαi+∏i=j+1nNiαi,±12∏i=1jNiαi−∏i=j+1nNiαii≤j≤n.Proof.
We prove this by induction.
Forn=1, N=∏i=11Niαi=N1α1=2∏i=11αi+1=2α1+1 which is true, since from Proposition 9, CardHN=2α1+1.
Forn=2, N=∏i=12Niαi=N1α1N2α2=2∏i=12αi+1=2α1+1α2+1 which is also true, since from Proposition 8, CardHN=2α1+1α2+1.
Now assume the assumption to be true forn, and let us prove it to be true for n+1.
N⋅Nn+1αn+1=∏i=1nNiαi⋅Nn+1αn+1=∏i=1n+1Niαi, taking into account the assumption ⇒CardHN=2∏i=1n+1αi+1.
From Proposition5, through injective homomorphisms, we have(43)BNx,yx≥4N=∏i=1jNiαi+∏i=j+1nNiαi2,∏i=1jNi2αi−∏i=j+1nNi2αi,∏i=1jNiαi∏i=j+1nNiαi+12,∏i=1jNiαi∏i=j+1nNi2αi−1i≤j≤n.
It is obvious to see that∏i=1jNiαi∏i=1nNiαi+12 is not square ∀i=1,…n¯ and j=1,…n¯. Now since Niαi is prime ∀i=1,…n¯, then ∏i=1jNiαi+∏i=j+1nNiαi is even and ∏i=1jNiαi+∏i=j+1nNiαi2 is a multiple of 4. From Theorem 4, for this case, ∃x∈Z such that a=∏i=1jNiαi+∏i=j+1nNiαi2=4x2. ⇒x2=1/4∏i=1jNiαi+∏i=j+1nNiαi2; then, considering the positive values of x and y, x=1/2∏i=1jNiαi+∏i=j+1nNiαi and y2=x2−N=1/4∏i=1jNiαi+∏i=1nNiαi2−∏i=1nNiαi. Since ∏i=1nNiαi=∏i=1jNiαi+∏i=j+1nNiαi, then(44)y2=14∏i=1jNi2αi+∏i=j+1nNi2αi+2∏i=1jNiαi∏i=j+1nNiαi−4∏i=1jNiαi∏i=j+1nNiαi=14∏i=1jNiαi−∏i=j+1nNiαi2.
y=1/2∏i=1jNiαi−∏i=j+1nNiαi. Taking into account the symmetry of HN, x,y∈HN⇒−x,y,x,−y and −x,−y∈HN; then, over Z, we have(45)S=±12∏i=1jNiαi+∏i=j+1nNiαi,±12∏i=1jNiαi−∏i=j+1nNiαii≤j≤n.


## 4. Discussion

We have exposed the forms of the Fermat equationx2−y2=N, dependently on the different forms of N, for which we have proved the cardinal over the integers to be 0, 4, and 8, of the form 2∏i=1nαi+1 or 1−δ2pi2n+1.OverZ>0, x2−y2=N has only one nontrivial solution for a RSA modulus N.Proposition 14.
∀x,y∈⌈N1/2⌉,1/2N+1×0,1/2N−1, x,y∈HN with the probability P=∏i=1nαi+1/N+1−2⌈N1/2⌉.Proof.
SetN=∏i=1nNiαi, with Ni odd primes. From Proposition 13, over Z≥0, CardHN=1/2∏i=1nαi+1 and from Theorem 5, the length of the x interval is l=N+1/2−⌈N1/2⌉=N+1−2⌈N⌉/2. ⇒P=CardHNZ≥0/l=1/2∏i=1nαi+1/N+1−2⌈N⌉/2=∏i=1nαi+1/N+1−2⌈N⌉.


## 5. Conclusion

In this paper, we have presented algebraic results on lattice points of the arc on the conicsx2−dy2=N for d=1, which is the Fermat factorization equation for which cardinals, forms of the algebraic set and exact upper and lower bounds are given using a particular hyperbola parametrization. These results provide further information on the structure of the algebraic set of this equation by exposing particularly the following.(i)
The general forms of lattice points.(ii)
The cardinals and the exact number of solutions.(iii)
The distribution of its lattice points over the integers.As a future work, we shall apply these results in the square sieving methods of factorization (mainly the quadratic sieve) and evaluate any resulting impact and performance.



---

*Source: 6360264-2022-01-28.xml*