second time puzzled.

Last post we inched closer to the proof that

For prime p ,

( p-1)! + 1 = p^a ------(1)

is only possible for p <=5. We will consider four cases of primes p = 8n±1 and p = 8n+3 and p = 8n+5 to study how 2^r powers of p behave `mod` 2^f(p).

For p = 8n±1 we extract all powers of 2 from n and write

p = 2^x * (2*m+1) ± 1

p^2 = ( 2^(x+1) + 1 ) `mod` 2^(x+2)

p^2^r = (2^(x+r) + 1) `mod` 2^(x+r+1) where r > 0.

Now substitute y = x+r+1 in the above

p^2^(y-x-1) = (2^(y-1) + 1) `mod` 2^y

holds provided y > x+1

For p = 8*n + 5 and p = 8*n+3,

p^2 = (2^3 + 1 ) `mod` 2^4
p^2^r = ( 2^(2+r) + 1 ) `mod` 2^(3+r)

Now substitute y = 3+r,

 p^2^(y-3) = ( 2^(y-1) + 1 ) `mod` 2^y 

and so

 p^2^(y-3) = ( 2^(y-1) + 1 ) `mod` 2^y 

Lets gets back to the proof to where we had left it that is to get a lower bound on 's' such that

 p^s = 1 mod 2^f(p) 

If we find a number 2^r such that p^2^r ≠ 1 mod 2^f(p) it would mean s > 2^r.

From what we saw above, if 2^y is some power of 2 that divides (p-1)!,
for p = 2^x*(2*m+1)± 1

 p^2^(y-x-1) = (2^(y-1) + 1) `mod` 2^y 

and integer y > x+1, x >= 3

 s > 2^(y-x-1) 

and since `a' is a multiple of s,

 a > 2^(y-x-1)

and so

p^2^(y-3) = (2^(y-1) + 1 ) `mod` 2^y 

for p of the form 8n+3 or 8*n+5

s > 2^(y-3)

and since `a' is a multiple of s,

a > 2^(y-3)

From my previous post , y could be chosen

 y = (p - 1 - 2^n)/2 + (2^n -1 )

where 2^n is greatest 2 power less than or equal to (p-1)

for p = 2^x*(2*m+1) ± 1,

 a >= s > 2^( (p - 1 - 2^n)/2 + (2^n -1 ) - x -1 ) = 2^(2^(n-1) + (p-1)/2 - 2 - x ) 

and for p = 8n+3,8*n+5

 a >= s> 2^( (p - 1 - 2^n)/2 + (2^n -1 ) - 3 ) = 2^( 2^(n-1) + (p-1)/2 - 4 ) 

for p = 11 = 8*1 + 3 n = 3 ,

  a > 2 ^( 1 + 8 -1 -3) = 16 

for p = 13 = 8*1 + 5 , n = 3

 a > 2 ^( 2 + 8 -1 -3) = 32 

for p = 17 w = 4 , x = 4

a > 2^( 16 - 1 - 4 -1 ) > 2^10

In fact for all primes p >= 17 and p < 32 , a > 2^10 and likewise for primes p between 33 and p < 64 ,

 a > 2^(32 - 2 - 5 )= 2^25 

and in general for primes

 p >= 2^x+1 and p >2^(x+1)

a > 2^(2^x-x-2)

So all we now need show is

 2^x > 2*x+3

for x = 4 it is obviously true.
if it true for some m.

 2^m > 2*m+3

we show it is true for m+1, as

 2^(m+1) = 2 * (2^m) > 4*m+6 = 2*(m+1) + 3 + (2*m+1) > 2*(m+1) + 3.

2^x > 2*x+3 is true for x >=4

then

2^x - x - 2 > x + 1

raising both sides to 2 power

2^(2^x-x-2) > 2^(x+1)

Now since p lies betwen 2^x + 1 and 2^(x+1)

a > 2^(2^x-x-2) > 2^(x+1) > p

which is too large for p^a = (p-1)!+1.

█

We still need a proof for case p > 7 to show that for prime p

(p-1)! + 1 = p^a ------(1)

is only possible for p <=5.

In my last post , we have an estimate greatest power of 2 dividing (p-1)!.

f(p) >= (p - 1 - 2^n)/2 + (2^n -1 )


We must also have for (1) to hold that

p^a = 1 `mod` 2^f(p)

Our efforts will be to try to get a lower bound on a and if that proves to be too large (> p) for (p-1)!+1 to be equal to p^a then we are done.

We also know from Euler that

p^2^(f(p)-1) = 1 `mod` 2^f(p) since EulerPhi(2^(f(p)) = 2^(f(p)-1)

The smallest power s on p that leaves 1 as remainder mod 2^f(p)
should divide 2^(f(p)-1). Which means s is a power of 2. Most importantly, s should divide 'a' as well. All we need to prove then is that s becomes too large for p > 7.

So why is 's' special?
If 2^r >= s,
p^2^r = 1 `mod` 2^(f(p))

and if 2^r < s then
p^2^r /= 1 `mod` 2^(f(p))

We need not find 's' to prove that 'a' > 's' becomes too large. We could just find a number 2^r less than 's' but is still large enough so that p^2^r becomes too large for (p-1)!+1. For that, we need to study some properties of 2^r powers of p mod 2^f(p).

The problem were trying to prove is if (p-1)!+1 is a power of p
for p > 7. We have already seen the proof for p=7 here

In the spirit of the proof for p = 7 , we'll show that a is greater
than p, but first we need to answer this question:

If 2^f(p) is the greatest 2 power that divides (p-1)! then

p^a = 1 `mod` 2^f(p)

but what is the value of f(p) ?

If 2^n is the greatest power of 2 less than or equal to (p-1) then

f(p) = floor(( p -1 )/2) + floor(( p -1 )/4) + floor(( p -1 )/8) + ... floor((p-1)/2^n)

We will satisfy ourselves with a lower bound on f(p)

since 2^(n+1) > p-1 >= 2^n

2 > (p-1)/2^n >= 1

=> floor((p-1) / 2^n) = 1

so f(p) >= 1 + 2 + 2^2.......2^(n-1) = (2^n-1 )

But wait, we are overlooking many 2 factors between 2^n and p-1.

which is atleast (p - 1 - 2^n)/2

and hence f(p) >= (p - 1 - 2^n)/2 + (2^n -1 ).

Thats enough for the proof which is to follow in the next post.

(p-1)! + 1 is not a power for p for prime p > 5.

Couple of weekends back , I was bored and was aching to get out of the drudge of bug fixing. I was going through the exercises in Niven's chapter on congruences looking for some problem that would make my day. I picked this one as it seemed hard but was not marked hard in the exercises. It took two weekends to bring this problem down. At this rate i am worried I would never would finish niven's book.

But first a proof for the case p = 7, which is simple

let (p-1)! +1 = p^a

We know that 6! is divisible by 16. The first step is the hardest but how it hides the vain attempts before this.

We must have
7^a = 1 mod 16

We also know that since 7^2 = 1 mod 16 and 2 is the least
such positive power, `a' must be a multiple of 2.

6! is divisible by 9

7^a = 1 mod 9
but 7^3 = 1 mod 9 ( 3 being the least such power)

a is a multiple of 2 and of 3
a is a multiple of the lcm (2 , 3) = 6

but makes 7^a too large to be equal to 6! + 1.

The next post will contain the proof for p > 7 .( not because of lack of margin space in this post :-)