254 5 Number Theory726.The sequencea 1 ,a 2 ,a 3 ,...of positive integers satisfies gcd(ai,aj)=gcd(i, j )
fori =j. Prove thatai=ifor alli.
727.Letn, a, bbe positive integers. Prove thatgcd(na− 1 ,nb− 1 )=ngcd(a,b)− 1.728.Letaandbbe positive integers. Prove that the greatest common divisor of 2a+ 1
and 2b+1 divides 2gcd(a,b)+1.
729.Fix a positive integerkand define the sequence(an)nbya 1 =k+1 andan+ 1 =
an^2 −kan+kforn≥1. Prove that for any distinct positive integersmandnthe
numbersamandanare coprime.
730.Leta, b, c, d, e,andfbe positive integers. Suppose thatS=a+b+c+d+e+f
divides bothabc+defandab+bc+ca−de−ef−fd. Prove thatSis composite.
731.Letnbe an integer greater than 2. Prove thatn(n− 1 )^4 +1 is the product of two
integers greater than 1.
732.Determine the functionsf:{ 0 , 1 , 2 ...}→{ 0 , 1 , 2 ,...}satisfying
(i)f( 2 n+ 1 )^2 −f( 2 n)^2 = 6 f (n)+1 and
(ii)f( 2 n)≥f (n)for alln≥0.5.2.2 Prime Numbers..........................................
A positive integer is called prime if it has no other divisors than 1 and the number itself.
Equivalently, a number is prime if whenever it divides a product it divides one of the
factors. Any positive integer can be written as a product of primes in a unique way up to
a permutation of the factors.
Euclid’s theorem.There are infinitely many prime numbers.Proof.From the more than one hundred proofs of this theorem we selected the fascinating
topological proof given in 1955 by H. Furstenberg. By definition, a topology on a setX
is a collectionT of sets satisfying
(i)∅,X∈T;
(ii) for any family(Ui)i∈Iof sets fromT, the union∪i∈IUiis also inT;
(iii) for anyU 1 ,U 2 ,...,UninT, the intersectionU 1 ∩U 2 ∩···∩Unis inT.
The elements ofT are called open sets; their complements are called closed sets.
This definition is the abstraction, in the spirit of Bourbaki, of the properties of open sets
on the real axis.
Furstenberg’s idea was to introduce a topology onZ, namely the smallest topology in
which any set consisting of all terms of a nonconstant arithmetic progression is open. As