The Art and Craft of Problem Solving

240 CHAPTER 7 NUMBER THEORY

7.3.30 The above equation used an arbitrary func­

tion g. If we replace g with /1, we can use some

special properties such as 7.3.12. This leads to

the Mobius inversion formula, which states that if

F(n) := 2,dlnf(d), then

f(n) = )/1(d)F (�).

am

7.3.31 An Application. Consider all possible n-Ietter

"words" that use the 26-letter alphabet. Call a word

"prime" if it cannot be expressed as a concatenation

7.4 Diophantine Equations

of identical smaller words. For example, booboo is

not prime, while booby is prime. Let p(n) denote the

number of prime words of length n. Show that

p(n) = )./1(d) 26 n/d.

am

For example, this formula shows that p(1) = /1(1)·

261 = 26, which makes sense, since every single-letter

word is prime. Likewise, p(2) = /1(1). 262 + /1(2).

261 = 262 - 26, which also makes sense since there

are 26^2 two-letter words, and all are prime except for

the 26 words aa, bb, ... , zz.

A diophantine equation is any equation whose variables assume only integral values.

You encountered linear diophantine equations in Problem 7.1.13 on page 228, a class

of equations for which there is a "complete theory." By this we mean that given any

linear diophantine equation, one can determine if there are solutions or not, and if there

are solutions, there is an algorithm for finding all solutions. For example, the linear

diophantine equation 3x+ 21y = 19 has no solution, since GCD( 3,21) does not divide

19. On the other hand, the equation 3x+ 19 y = 4 has infinitely many solutions, namely

x = - (^24) + 19 t, 4 -3t, as t ranges through all integers.
Most higher-degree diophantine equations do not possess complete theories. In­
stead, there is a menagerie of different types of problems with diverse methods for
understanding them, and sometimes only partial understanding is possible. We will
just scratch the surface of this rich and messy topic, concentrating on a few types of
equations that can sometimes be understood, and a few useful tactics that you will use
again and again on many sorts of problems.

General Strategy and Tactics

Given any diophantine equation, there are four questions that you must ask:

• Is the problem in "simple" fo rm? Always make sure that you have divided out

all common factors, or assume the variables share no common factors, etc. See

Example 7.2.3 on page 230 for a brief discussion of this.

• Do there exist solutions? Sometimes you cannot actually solve the equation,

but you can show that at least one solution exists.

• Are there no solutions? Quite frequently, this is the first question to ask. As with

argument by contradiction, it is sometimes rather easy to prove that an equation

has no solutions. It is always worth spending some time on this question when

you begin your investigation.

• Can we find all solutions? Once one solution is found, we try to understand

how we can generate more solutions. It is sometimes quite tricky to prove that

the solutions found are the complete set.