Number Theory 689f( 2 n+ 1 )= 3 f (n)+ 1 ,
f( 2 n)= 3 f (n).At this moment it is not hard to guess the explicit formula forf; it associates to a number in
binary representation the number with the same digits but read in ternary representation.
For example,f( 5 )=f( 1012 )= 1013 =10.
733.It is better to rephrase the problem and prove that there are infinitely many prime
numbers of the form 4m−1. Euclid’s proof of the existence of infinitely many primes,
presented in the first section of the book, works in this situation, too. Assume that there
exist only finitely many prime numbers of the form 4m−1, and let these numbers be
p 1 ,p 2 ,...,pn. ConsiderM= 4 p 1 p 2 p 3 ···pn−1. This number is of the form 4m−1,
so it has a prime divisor of the same form, for otherwiseMwould be a product of numbers
of the form 4m+1 and itself would be of the form 4m+1. ButMis not divisible by
any of the primesp 1 ,p 2 ,...,pn, so it must be divisible by some other prime of the form
4 m−1. This contradicts our assumption thatp 1 ,p 2 ,...,pnare all primes of the form
4 m−1, showing that it was false. We conclude that there exist infinitely many prime
numbers of the form 4m+3,man integer.
Remark.A highly nonelementary theorem of Dirichlet shows that for any two coprime
numbersaandb, the arithmetic progressionan+b,n≥0 contains infinitely many
prime terms.734.We have
m
n=
1
1
−
1
2
+
1
3
−
1
4
+···+
1
2 k− 1−
1
2 k
= 1 +1
2
+
1
3
+···+
1
2 k− 2
(
1
2
+
1
4
+···+
1
2 k)
= 1 +
1
2
+
1
3
+···+
1
2 k−
(
1 +
1
2
+···+
1
k)
=
1
k+ 1+
1
k+ 2+···+
1
2 k− 1+
1
2 k
=(
1
k+ 1+
1
2 k)
+
(
1
k+ 2+
1
2 k− 1)
+···
=
3 k+ 1
(k+ 1 ) 2 k+
3 k+ 1
(k+ 2 )( 2 k− 1+···.
It follows thatm( 2 k)!=n( 3 k+ 1 )qfor some positive integerq; hencep= 3 k+ 1
dividesm( 2 k)!. Butpis a prime greater than 2k, so it is coprime to( 2 k)!. Thuspdivides
m, and we are done.
(Mathematical Reflections, proposed by T. Andreescu)