Steps and Footprints

Date: 5/31/96 at 8:37:10
From: Anonymous
Subject: Down the staircase

I've tried to solve this problem by logic and doing a drawing to see 
it more clearly.  I haven't had any success.

Four friends race side by side down a dusty staircase.  Peter goes 
down two steps at a time, Bruce three steps at a time, Jessica four 
steps at a time, and Wiz five steps at a time. If the only steps with 
footprints from all four friends are at the top and bottom, how many 
steps have just one person's foot prints?

Date: 5/31/96 at 16:4:34
From: Doctor Darrin
Subject: Re: Down the staircase

Let's call the top step step 0, and number the steps counting 
downward. Then Peter will step on all the even-numbered steps, Bruce 
will step on all the steps which are numbered with a multiple of 
three, Jessica on all the multiples of four, and Wiz on all the steps 
that are multiples of 5.

First we will see how many steps there are.  Since all four people 
will step on the last step, the number of the last step must be a 
multiple of 2, 3, 4, and 5.  3*4*5 = 60 is the smallest such number 
(the least common multiple of 2, 3, 4, and 5), so the last step is 
number 60.

Now we will count the steps that only Peter steps on.  These will
be given by even numbers which are not multiples of 3, 4, or 5.  We 
can write such a number as 2*n with n between 1 and 30, and n 
relatively prime to 30 (so that n is not divisible by 2, 3, or 5).  
There are 8 numbers below thirty relatively prime to 30, so Peter 
steps on eight steps that nobody else steps on.  (We could also just 
count which of the even-numbered steps have numbers not divisible by 
3, 4, or 5.  They are steps 2, 14, 22, 26, 34, 38, 46, 58, and there 
are 8 of them.)

Now let's count the steps that only Bruce steps on.  He steps on 
multiples of three which are not multiples of 2, 4, or 5.  The steps 
he steps on are given by 3*n where n is between 1 and 20 and n is 
relatively prime to 20 (so that n is not divisible by 2, 4, or 5).  
There are 8 such numbers, so he steps on 8 steps that nobody else 
steps on. (Steps 3, 9, 21, 27, 33, 39, 51, 57).

Every step that Jessica steps on is an even-numbered step that Bruce 
also steps on, so Jessica steps on 0 steps that nobody else steps on.

Wiz steps on steps numbered 5*n with n between 1 and 12, and n 
relatively prime to 12 (so that n is not divisible by 2, 3, or 4).  
There are 4 numbers relatively prime  to twelve below twelve, so Bruce 
steps on 4 steps that nobody else steps on.

Thus there are 20 steps that are stepped on by only one person.  
Notice that we counted the numbers relatively prime to a certain 
number and less than the number several times.  There is a special 
name for this - it is called the Euler phi function.  Basically 
phi(n) = the number of numbers between 1 and n relatively prime to n.  
It is a very important function in number theory (and in solving fun 
number problems like this one).

-Doctor Darrin,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/