256 5 Number Theory
We proceed with a problem from the 35th International Mathematical Olympiad,
1994, followed by several others that are left to the reader.
Example.Prove that there exists a setAof positive integers with the property that for
any infinite setSof primes, there exist two positive integersm∈Aandn/∈Aeach of
which is a product ofkdistinct elements ofSfor somek≥2.
Solution.The proof is constructive. Letp 1 <p 2 <···<pn<···be the increasing
sequence of all prime numbers. DefineAto be the set of numbers of the formpi 1 pi 2 ···pik,
wherei 1 <i 2 <···<ikandk=pi 1. For example, 3· 5 · 7 ∈Aand 5· 7 · 11 · 13 · 17 ∈A,
but 5· 7 ∈/A.
Let us show thatAsatisfies the desired condition. Consider an infinite set of prime
numbers, sayq 1 <q 2 <···<qn<···.Takem=q 2 q 3 ···qq 2 andn=q 3 q 4 ···qq 2 + 1.
Thenm∈A, whilen/∈Abecauseq 2 ≥3 and soq 2 + 1 =q 3.
733.Prove that there are infinitely many prime numbers of the form 4m+3, where
m≥0 is an integer.
734.Letkbe a positive integer such that the numberp= 3 k+1 is prime and let
1
1 · 2+
1
3 · 4
+···+
1
( 2 k− 1 ) 2 k=
m
nfor some coprime positive integersmandn. Prove thatpdividesm.735.Solve in positive integers the equation
xx+y=yy−x.736.Show that each positive integer can be written as the difference of two positive
integers having the same number of prime factors.
737.Find all composite positive integersnfor which it is possible to arrange all divisors
ofnthat are greater than 1 in a circle such that no two adjacent divisors are relatively
prime.
738.Is it possible to place 1995 different positive integers around a circle so that for any
two adjacent numbers, the ratio of the greater to the smaller is a prime?
739.Letpbe a prime number. Prove that there are infinitely many multiples ofpwhose
last ten digits are all distinct.
740.LetAbe the set of positive integers representable in the forma^2 + 2 b^2 for integers
a, bwithb =0. Show that ifp^2 ∈Afor a primep, thenp∈A.