April 13, 1998

A c k a n o m i c   C y c l o p e d i a   o f   K n o w l e d g e
Volume 1, issue 3

This issue follows up a topic from the first issue of ACK and which was
discussed on Ackanomic IRC recently.

I was trying to prove that 2^p != 1 mod 5^n for integers n and p,
with 0<p<4*5^(n-1) and n>0 to complete my proof of one of the problems
in Douglas Zare's math contest.  [The number 4*5^(n-1) here is the
totient number of 5^n: the number of integers from 0 to 5^n which
are relatively prime to 5^n -- in this case, simply all the ones not
divisible by 5.]  (If this doesn't look like one of the problems on the
test to you, don't worry, it's an intermediate step I believed true
without proof, which I had used to prove one of the problems, and
which I was now trying to prove.)

I had hoped there was some general method that would apply, but looking at
5^2 = 1 mod 2^3 while totient(2^3)=4 discouraged me, and set me to trying
to prove it by induction.  [What are the requirements on a, b, and n for
a^p != 1 mod b^n for 0<p<totient(b^n) to hold?  Relatively prime a and b
is not enough!]

I broke it down into two sub-cases; since I knew 2^[4*5^(n-1)] = 1 mod 5^n,
any lesser number equal to 1 mod 5^n would result in either 2^[2*5^(n-1)]
or 2^[4*5^(n-2)] being equal to 1 mod 5^n.  I eliminated the 2^[2*5^(n-1)]
case easily since all those numbers equal 4 mod 5.  The other case was
tougher, but I proved the trend I saw in the first few numbers -- that
2^[4*5^(n-2)] = 3*5^(n-1)+1 mod 5^n.  I am omitting the details here, but
I'll note that I expanded a binomial raised to the 5th power and knocked
out terms divisible by 5 sufficiently many times.  Figuring out how to
increase the modulus at each step was tricky.

This makes 17 of the 20 problems in that contest which I have now proved.
I didn't expect to get anywhere near this far, but here I am.  There are
also bonus points for generalizations of the problems, which I have very
few of so far, and which I suspect may be the key to winning this contest.
Unfortunately, since I didn't have a general way to prove this step, I
don't have a generalization for this problem.  [In fact, the first
problem in the contest is the only one where I have made a good solid
generalization so far, but I have made a couple other attempts, and there
was one problem I found could be interpreted two different ways, which I
solved both ways -- a proof in one case and a disproof in the other.]

Unless I come up with some more generalizations, what I have done so
far will likely be the end of my work on this contest, though I have a
month and a half left before the deadline.  Wish me luck!