(e) Likewise, show that 2 - Rand 2 + R are
F-primes.
(f) Conclude that F does not possess unique factor
ization.7.1.15 Prove that consecutive Fibonacci numbers are
always relatively prime.
7.1.16 It is possible to prove that (a,b)[a,b] = ab
without using PPF, but instead just using the defini
tions of GCD and LCM. Try it!
7.1.17 (USAMO 1972) Let a,b,e EN. Show that
[a,b,eJ^2 (a,b,ci
[a, b][b, e][c,a] (a,b)(b,e)(c,a)'
7.1.18 Show that the sum of two consecutive primes
is never twice a prime.
7.1.19 Is it possible for four consecutive integers to be
composite? How about five? More than five? Arbitrar
ily many?
7.1. 20 Show that
I I I
1+-+-+ .. ·+-
2 3 n
can never be an integer.7.1.21 Show that (�) is a multiple of p for all 0 <
k <p.
7.1.22 Show that lOoo! ends with 249 zeros. Gener
alize!
7.1.23 Let r E N. Show that (�") is a multiple of p
for O < k < pro
7.1. 24 Show that if n divides a single Fibonacci num
ber, then it will divide infinitely many Fibonacci num
bers.
7.1.25 Prove that there are infinitely many primes
of the form 4k + 3; i.e., that the sequence
{3,7,11, 19, ... } is infinite.
7.1.26 Prove that there are infinitely many primes of
the form 6n -1.
7.1.27 (Bay Area Mathematical Olympiad 1999)
Prove that among any 12 consecutive positive integers
there is at least one which is smaller than the sum of
its proper divisors. (The proper divisors of a positive
integer n are all positive integers other than I and n
which divide n. For example, the proper divisors of 14
7.1 PRIMES AND DIVISIBILITY 229are 2 and 7.)
7.1.28 (Bay Area Mathematical Olympiad 2000)
Prove that any integer greater than or equal to 7 can be
written as a sum of two relatively prime integers, both
greater than 1. For example, 22 and IS are relatively
prime, and thus 37 = 22 + 15 represents the number 37
in the desired way.
7.1.29 (Bay Area Mathematical Olympiad 2006)
Since 24 = 3 + 5 + 7 + 9, the number 24 can be writ
ten as the sum of at least two consecutive odd positive
integers.
(a) Can 2005 be written as the sum of at least two
consecutive odd positive integers? If yes, give
an example of how it can be done. If no, provide
a proof why not.
(b) Can 2006 be written as the sum of at least two
consecutive odd positive integers? If yes, give
an example of how it can be done. If no, provide
a proof why not.
7.1. 30 A polynomial with integer coefficients is called
primitive if its coefficients are relatively prime. For
example, 3x^2 +9x+ 7 is primitive while IOx^2 -5x+ IS
is not.
(a) Prove that the product of two primitive polyno
mials is primitive. Hint: extreme principle.
(b) Use this to prove Gauss's Lemma: If a poly
nomial with integer coefficients can be factored
into polynomials with rational coefficients, it
can also be factored into primitive polynomials
with integer coefficients. (See also page 170.)
7.1.31 True or false and why:
(a) The product of two consecutive positive inte
gers cannot be equal to a perfect square.
(b) The product of three consecutive positive inte
gers cannot be equal to a perfect square.
7.1.32 (Russia 1995) The sequence at ,a 2 ,'" ofnatu
ral numbers satisfies
GCD(ai,aj) = GCD(i ,j)
for all i i= j. Prove that ai = i for all i.
7.1.33 (USAMO 1973) Show that the cube roots of
three distinct prime numbers cannot be three terms
(not necessarily consecutive) of an arithmetic progres
sion.