Euclid's Algorithm And Related Problems

The main aim of this doctoral dissertation is to study Euclid's algorithm and re-lated problems.In Chapter 1, we give a brief introduction of Euclid's algorithm and its applica-tions.Using Euclid's algorithm, one can determine whether there is an integer ai (1≤i≤m) among a1,…,am (1 1) random positive integers are pairwise relatively prime is 1/ζ(m), whereζ(.) is Riemann's Zeta function. The probability that there is an integer ai among several random positive integers a1,…,am such that ai is relatively prime with all of the others is (1/ζ(2))m-1 If there is a positive integer r with 1≤r≤m such that ar and each of the rest numbers are coprime, we call a1,…,am (11, m>1, if there is a prime in m+1,…, m+n, then this sequence is a W sequence. Thus, in order to determine whether a consecutive positive integer sequence is a W sequence, it is enough to consider the case of consecutive composite numbers. For consecutive composite numbers, Grimm conjectured in 1969:if m+1,…,m+n are consecutive composite numbers, then there exist n distinct prime numbers p1,…,pn such that m+j is divisible by pj,1≤j≤n. This implies that the product of any n consecutive composite numbers must have at least n distinct prime factors.Grimm proved that his conjecture holds when m>nn-1. This was improved to m>nπ(n) by Erdos and Selfridge who used Hall's theorem in 1971. Using the properties of binomial coefficients and Gauss function, we prove that when m>∏p≤n p[logpn] the binomial coefficient ((?)) has the representation: where ai (1≤i≤n) satisfyNote that nπ(n)>∏p≤np[logpn].Thus, we refine the result of Erdos and Selfridge.In the case of arithmetic progression, Langevin proved in 1977 that for n>1, gcd(a, b)=1, and for any i=1,…,n, if a+bi is not divisible by∏p≤n-1 p[logp(n-1)], then there exist n distinct prime numbers p1,…,pn such that a+bj is divisible by pj, 1≤j≤n.Furthermore, we prove that for n>1, gcd(a,b)=1, and for any i=1,…,n, if a+bi is not divisible by∏p≤n-1 p[logp(n-1)],∏i=1na+bi/i has the representation: where A=∏i=1n ai, gcd(A, B)=1 and ai (1≤i≤n) satisfyTherefore, we also refine the result of Langevin.W sequences in the non-consecutive case, enable us to study the relations between Goldbach's conjecture and the least prime number in an arithmetic progression. In 1742, Goldbach conjectured that every even integer 2n≥4 is the sum of two primes. Due to it is trivial that it is true for infinitely many even integers:2p=p+p (for every prime p), we give Goldbach's conjecture a slightly different expression that every even integer 2n> 6 is the sum of two distinct primes, which implies that for integer n> 5, there exists a natural number r such that 2n-pr is coprime to each of 2n-p1,…,2n-pr-1,2n-pr+1,…,2n-pk, where p1,…,pr-1,pr,pr+1,…,pk are all old primes smaller than n, pr satisfies gcd(pr,n)=1 and 1≤r≤k=π(n-1)-1. Namely, is a W sequence.Let k, l denote positive integers with (k,l)=1 and 1≤l≤k-1. Denote by p(k, l) the least prime p=l(mod k). Let p(k) be the maximum value of p(k, l) for all l with (k, l)=1 and 1≤l≤k-1. In 1944, Linnik[42] proved that p(k) 1. Chowla has observed that p(k)< 0 assuming the Generalized Riemann Hypothesis. Furthermore, he conjectured p(k)< 0. Thus, Chowla's conjecture implies that there is an absolute constant c1 such that when k>c1, p(k)c2, p(k) 5, and p(k)c1, then every sufficiently large even integer can be written as the sum of two distinct primes.Furthermore, we prove that for any givenεwith 0<ε<0.5, there is a positive integer c3 such that for every integer n≥c3 and any positive integer m 5, and p(k)< k2-εfor k>c2, then every sufficiently large even integer can be written as the sum of two distinct primes. Note that if 2n-p1,…, 2n-pr-1,2n-pr, In-pr+1,…,2n-pk is a W sequence for n> 5, and p(k)< k2 for k> 1, then every even integer 2n≥4 can be written as the sum of a prime and the product of at most two primes.Let k, l be given positive integers satisfying (k,l)=1 and 1≤l< k. Let Qi be the ith prime of the form kx+l. We propose an analogy of Goldbach's conjecture in the case of arithmetic progression:for every sufficiently large integer n,2(kn+l) can be written as the sum of two distinct primes p, q of the form kx+l.This analogy implies that there is a positive constant c4 such that every integer n>c4, there exists r>1 such that kn+l> Qr, gcd(kn+l, Qr)=1, and 2(kn+l)-Qr is coprime to every 2{kn+l)-Q when Q≤kn+l ranges the primes of the kx+l and different from Qr. Namely, when n> c4, is a W sequence, where Qh≤kn+l is the largest prime of the form kx+l.We prove that for any givenεwith 0<ε<0.5, there is a positive integer Cε,κdepending onε,κsuch that for every prime p≥Cε,κand any positive integer m< k3-εp2-ε, we have where Q(m) is the least prime of the form kx+l coprime to m.Based on this result, we prove that if 2{kn+l)-Q1,…,2(kn+l)-Qr,…,2{kn+ l)-Qh is a W sequence for n>c4, and p(k)c2, then for every sufficiently large integer n,2{kn+l) can be written as the sum of two distinct primes p, q of the form kx+l.In the chapter 3, we give much attention on the problem of infinitude of primes. We view an integer x as the simplest polynomial map on Z:f(x)=x from Z to Z, which takes infinitely many primes. More generally, let's consider the map F where x=(x1,…, xn)∈Zn, f1,…,fm∈Z[x1,…,xn]. How to determine whether f1(x),…,fm(x) represent simultaneously primes for infinitely many integral points x? This motivates the research about the sufficient condition that several multivariable in-tegral polynomials represent simultaneously primes for infinitely many integral points.When f(x) is on N, in 1857, Bouniakowsky conjectured:if f(x) is an irre-ducible polynomial with integral coefficients, positive leading coefficient and degree at least 2, and for every positive integer k, there exists a positive integer n such that gcd(f(n), k)=1, then f(x) is prime for an infinite number of positive integers x. In 1904, Dickson conjectured the following:Dickson's conjecture:Let m≥1, fi(x)=ai+bix (i=1,…,m)with ai and bi integers, bi≥1. If for every positive integer k, there exists a positive integer n such that gcd(∏i=1mfi(n), k)=1, then there exist infinitely many positive numbers x such that all numbers f1(x),…, fm(x) are primes.In 1958, A. Schinzel and W. Sierpinski generalized Dickson's conjecture to the nonlinear case. However, there are little relevant literatures published for the case of polynomial maps on Zn.In 2006, Green and Tao generalized the conjecture of Hardy and Littlewood to the multivariable case:If f1(x1,…,xn)=a11x1+…+a1nxn+b1,…,fm(x1,…,xn)= am1x1+…+amnxn+bm represent simultaneously primes for infinitely many integral points x=(x1,…,xn)∈Zn, then there is a positive constant CF depending on such that when h→∞, where P is the set of all positive primes, f1,…, fm is in Z[x1,…,xn].Based on the work of Green and Tao, one might look forward to a similar Prime Number Theorem in the high-dimension case. But, we would like to consider the more fundamental question:look for the sufficient condition that F=(f1,…, fm) represents infinitely many prime points. We mainly focus on the case of linear polynomial maps.By using the following principle:Let M a matrix with n rows and n+1 columns. If there is at most an element in each row has the property P, there is at least a column in which each element has no the property P, we give an equivalent form of Dickson's conjecture as following:The equivalent form of Dickson's conjecture:Let m≥1,fi(x)= ai+bix (i=1,…,m) with ai and bi integers, if there is a positive integer c5 such that for every positive integer k≥c5, there exists a positive integer y such that f1(y)>1,…, fm(y)>1 are all in Zk*={x|1≤x0 or bi< 0, and for every positive integer k, there exists an integer n such that gcd(∏i=1m fi(n),k)=1, then there exist infinitely many integers x such that all numbers f1(x),…, fm(x) are primes.We prove that Dickson's conjecture on Z is equivalent to the following:The equivalent form of Dickson's conjecture on Z:Let m≥1, fi(x)=ai+bix (i=1,…,m) with ai and bi integers, if there is a positive integer c6 such that for every positive integer k≥c6, there exists an integer y such that f1(y)>1,…,fm(y)>1 are all in Zk*={x|11 for 1≤i≤m. Clearly, if F represents infinitely many prime points, then F is admissible. Dickson conjectured that if F on N is admissible, then F represents infinitely many prime points.We call the polynomial map F on Zn strongly admissible if there is a positive integer C such that for every positive integer k≥C, there exists an integral point x=(x1,…,xn) such that f1(x)> 1,…,fm(x)> 1 are all in Zk*. Thus, "F is strongly admissible" implies that F is admissible.Notice that is admissible if and only if it is strongly admissible. Furthermore, we prove that is admissible if and only if it is strongly admissible.Our contribution:1,We studied the relations between Goldbach's conjecture and the problem of the least prime number in an arithmetic progression; Proposed an analogy of Goldbach's conjecture in the case of arithmetic progression:For every sufficiently large integer n,2(kn+l) can be written as the sum of two distinct primes p, q of the form kx+l. (Chapter 2).2,We proposed W sequences; Refined a result of Erdos and Selfridge on Grimm's conjecture; We also refined the result of Langevin on the arithmetic progression (Chap-ter 2).3,We obtained an equivalent form of Dickson's conjecture and proved that the linear polynomial map F=(f1(x),…,fm(x)) on Zn is admissible if and only if it is strongly admissible (Chapter 3).