Re: Competition problem in number theory

On Wed, 31 May 2006 04:43:15 -0400, quasi <quasi@xxxxxxxx> wrote:

On 31 May 2006 00:13:31 -0700, "Larry Hammick"
<larryhammick@xxxxxxxxx> wrote:

quasi wrote:

On 31 May 2006 00:01:31 -0700, "Larry Hammick"
<larryhammick@xxxxxxxxx> wrote:

From this year's Bulgarian National Olympiad:

Let p be a prime such that p^2 divides 2^(p-1). Show that for any n>0,
the number
(p - 1)(p! + 2^n)
has at least three distinct prime factors.

You probably meant to write "p^2 divides (2^p)-1".

Yes, sorry. I think I've got some form of late-onset dyslexia. Next
time I'll play it safe and say "Let p be a Weiferich prime..." :)

Ok, with that correction, here's a proof ...

If p-1 has at least 3 distinct prime factors then the result is
immediate.

Suppose p-1 has at most 2 disticnt prime factors.

We consider 2 cases:

case (1): p-1 has exactly 1 distinct prime factor.

Since p^2 divides (2^p)-1, p must be odd. It follows that (since p-1
is even) p-1 must be a power of 2.

Thus, write p-1=2^k.

Then (p-1)^p = 2^(k*p)

Reducing mod p^2, we get

-1 = 1 mod p^2, contradiction.

case (2): p-1 has exactly 2 distinct prime factors.

Let the distinct prime factors of p-1 be a,b with a<b.

By asumption the product (p - 1)(p! + 2^n) can have no additional
prime factors other than a and/or b, hence the only dprime factors of
p! +2^n are a and/or b.

Both a and b divide p! but b must be odd (since a<b), hence b can't
divide 2^n. It follows that a=2 and p! + 2^n must be a power of 2.

Write p! + 2^n = 2^m.

Clearly m>n.

Then p! = 2^n * (2^(m-n) -1)

It follows that 2^(m-n) = 1 mod p

But 2^p = 1 mod p^2 implies p is the least positive integer such that
2^p=1 mod p. Therefore p divides m-n.

But p divides m-n implies 2^(m-n) = 1 mod p^2 so the equation

p! = 2^n * (2^(m-n) -1) yields p! = 0 mod p^2, contradiction (since p
is prime).

It follows that the product (p - 1)(p! + 2^n) has at least 3 prime
factors, as was to be shown.

quasi

Looking back at my proof, I just realized something.

It's not that my proof is wrong. Rather, the hypothesis is always
false.

2^p=1 mod p^2

implies 2(2^(p-1)) = 1 mod p^2,

which implies 2 = 1 mod p^2, contradiction.

Obviously, the problem is still misstated.

I think the intended hypothesis is probably

p^2 divides 2^(p-1) - 1.

With this revised hypothesis, certain parts of my proof need to be
revised. I'll rethink it (although I'm bleary eyed tired, so maybe
I'll leave it for now).

quasi
.

Relevant Pages

  • Re: Competition problem in number theory
    ... Let p be a prime such that p^2 divides 2^. ... If p-1 has at least 3 distinct prime factors then ... Suppose p-1 has at most 2 disticnt prime factors. ...
    (sci.math)
  • Re: Competition problem in number theory
    ... You probably meant to write "p^2 divides -1". ... If p-1 has at least 3 distinct prime factors then the result is ... Suppose p-1 has at most 2 disticnt prime factors. ...
    (sci.math)
  • Re: Competition problem in number theory
    ... You probably meant to write "p^2 divides -1". ... If p-1 has at least 3 distinct prime factors then the result is ... Suppose p-1 has at most 2 disticnt prime factors. ... but b must be odd, ...
    (sci.math)
  • Re: Competition problem in number theory
    ... quasi wrote: ... has at least three distinct prime factors. ... You probably meant to write "p^2 divides -1". ... time I'll play it safe and say "Let p be a Weiferich prime..." ...
    (sci.math)