A theorem of Charles Babbage’s extended

A theorem of Charles Babbage's extended

F.L. Bauer [0] told me that Charles Babbage has shown that

$$ \binom {2 p - 1} {p - 1} \equiv 1 (\mod p ^ {2}) \quad \mathrm {i f a n d o n l y i f} p \mathrm {i s a n o d d p r i m e .} $$

He furthermore transmitted to me his conjecture that

$$ \binom {(k + 1) p - 1} {p - 1} \equiv 1 (\mod p ^ {3}) \quad \mathrm {f o r n a t u r a l k a n d p r i m e p > 5 ,} $$

which will be proved in this note.

Conventions All through this note

$\bullet k$ is a natural number $\therefore p$ is a prime satisfying $p \geq 5$ $\therefore n$ satisfies $p = {2n} + 1$ F satis $f$ ies $F = {\left( p - 1\right) }^{!}$ - (S dummies: range: term) is the format used to denote summation (P dummies: range: factor) is the format used to denote multiplication. (End of Conventions)

On account of the definition of binomial coefficients, the demonstrandum is equivalent to

$$ (P i: 1 \leqslant i < p: k p + i) / F \equiv 1 (\mod p ^ {3}) $$

or equivalently, since $F$ has no factor $p$ .

$$ (\underline {{P}} _ {i}: 1 \leq i < p: k p + i) \equiv F (\mod p ^ {3}). $$

To begin with, we therefore expand the left-hand side in powers of $kp$ . This yields

$$ (P _ {i}: 1 \leq i < p: k p + i) = F _ {i} + C \cdot (k p) + D \cdot (k p) ^ {2} + h i g h e r p o w e r s o f k p $$

$$ \begin{array}{l} w i t h C = (\sum_ {i: 1 \leq i < p: F / i}) \ a n d D = (\sum i, j: 1 \leq i < j < p: F / i j) \ \end{array} $$

In view of the expansion, the demonstrandum follows from (the stronger)

(0) $C \equiv 0\left( {\;\operatorname{mod}\;{p}^{2}}\right)$ and (1) $D \equiv 0\left( {\;\operatorname{mod}\;p}\right)$

Let us tackle proof obligation (0) first. We observe

$$ \begin{array}{l} \complement \ = {\mathrm {d e f i n i t i o n} } \ (\underline {{S}} i: 1 \leq i < p: F / i) \ = {\text {s p l i t i n g t h e r a n g e} } \ (\underline {{\underline {{S i}}}}: 1 \leq i \leq n: F / i) + (\underline {{\underline {{S i}}}}: n < i < p: F / i) \ = {r e n a m i n g t h e s e c o n d d u m m y: j := p - j ^ {3} \ (\underline {{\underline {{S}}}} i: 1 \leq i \leq n: F / i) + (\underline {{\underline {{S}}}} j: 1 \leq j \leq n: F / (p - j)) \ = {\text {c o m b i n g s u m m a t i o n s o v e r e q u a l r a n g e s} } \ (S _ {i}: 1 \leq i \leq n: F / i + F / (p - i)) \ = {\mathrm {a r i t h m e t i c} } \ p \cdot (\subseteq i: 1 \leq i \leq n: F / (i \cdot (p - i))) \ \end{array} $$

Hence, proof obligation (0) can be discharged by demonstrating

(2) $\left( {{S}_{i} : 1 \leq i \leq n : F/\left( {i\left( {p - i}\right) }\right) }\right) \equiv 0\left( {\;\operatorname{mod}\;p}\right)$

further more we deduce from the above

(3) $C \equiv 0\left( {\;\operatorname{mod}\;p}\right)$

For the moment we shelve proof obligation (2) and tackle proof obligation (1). To this end we observe - elementary algebra

${C}^{2} = \left( {\sum i : 1 \leq i < p : {F}^{2}/{i}^{2}}\right) + {2FD}$

which allows us to rewrite (1):

$$ D \equiv 0 (\mod p) $$

$$ \begin{array}{r l} & {= {\mathrm {2 F h a s n o f a c t o r p} }} \ & {\mathrm {2 F D \equiv 0 (m o d p)}} \end{array} $$

$$ = {(\lambda) } $$

$$ C ^ {2} - (S _ {i}: 1 \leq i < p: F ^ {2} / i ^ {2}) \equiv 0 (\mod p) $$

$$ = {3 } $$

$\left( 5\right) - \left( {\underline{S} : 1 < i < p : {F}^{2}/{i}^{2}}\right) \equiv 0\left( {\;\operatorname{mod}\;p}\right)$

Hence, proof obligation (1) can be discharged by demonstrating (5), which is encouragingly similar to (2), our other remaining proof obligation.

Because both (2) and (5) are congruences modulo $p$ , we now resort to the residue calculus modulo $p$ . In what follows, taking the residue class of a (rational) argument is denoted by surrounding the argument by a pair of square brackets.

Interlude We recall

• for integer arguments x and y: $\left\lbrack x\right\rbrack = \left\lbrack y\right\rbrack \equiv p \mid \left( {x - y}\right)$ (for "a|b" read "a divides b") there are p distinct residue classes
• addition, subtraction, and multiplication of residue classes is defined by the distribution of the square brackets over these operators, i.e.

$$ [ x ] + [ y ] = [ x + y ] $$

$$ [ x ] - [ y ] = [ x - y ] $$

$$ [ x ] \cdot [ y ] = [ x \cdot y ] $$

• as $p$ is prime

$$ [ x ] \cdot [ y ] = [ 0 ] \equiv [ x ] = [ 0 ] \vee [ y ] = [ 0 ] $$

• as $p$ is prime,the equation in the unknown residue

has for $\lbrack y\rbrack \neq \left\lbrack 0\right\rbrack$ a unique solution,denoted by $\left\lbrack x\right\rbrack / \left\lbrack y\right\rbrack$

• by letting the square brackets distribute over division as well , i.e.

residue classes for prime $p$ are also assigned to rational fractions x/y with $\left\lbrack y\right\rbrack \neq \left\lbrack 0\right\rbrack$ .

(End of Interlude.)

We tackle (5) first:

(5)

$$ \begin{array}{l} \begin{array}{l} {\mathrm {c l a s s} z} \ {\qquad \qquad z: ([ x ] = [ y ] \cdot z)} \end{array} \ [ x ] / [ y ] = [ x / y ] \ = {\mathrm {d e f i n i t i o n s} o f (5) \mathrm {a n d} o f \mathrm {r e s i d u e c l a s s} } \ [ - (\sum i: 1 \leq i < p: F ^ {2} / i ^ {2}) ] = [ 0 ] \ = {\mathrm {a r i t h m e t i c} } \ [ - F ^ {2} \cdot (\underline {{S i}}: 1 \leq i < p: 1 / i ^ {2}) ] = [ 0 ] \ = {\text {d i s t r i b u t i o n} } \ [ - F ^ {2} ] \cdot [ (\sum i: 1 \leq i < p: 1 / i ^ {2}) ] = [ 0 ] \ = {[ - F ^ {2} ] \neq [ 0 ] } \ [ (\sum i: 1 \leq i < p: 1 / i ^ {2}) ] = [ 0 ] \ = {p = 2 n + 1 } \ [ (\sum i: 1 \leq i \leq n: 1 / i ^ {2} + 1 / (p - i) ^ {2}) ] = [ 0 ] \ = {\text {d i s t r i b u t i o n} } \ (\sum i: 1 \leq i \leq n: [ 1 / i ^ {2} ] + [ 1 / (p ^ {2} - 2 p i + i ^ {2}) ]) = [ 0 ] \ = [ x / y ] = [ x / (y - p) ] \ (\subseteq i: 1 \leq i \leq n: [ 1 / i ^ {2} ] + [ 1 / i ^ {2} ]) = [ 0 ] \ = {\mathrm {d i s t r i b u t i o n} } \ (\underline {{S}} i: 1 \leq i \leq n: [ 2 / i ^ {2} ]) = [ 0 ] \ = {\text {d i s t r i b u t i o n} } \ [ 2 ] \cdot (S i: 1 \leq i \leq n: [ 1 / i ^ {2} ]) = [ 0 ] \ = {[ 2 ] \neq [ 0 ] } \ (6) \quad (\underline {{S}} i: 1 \leq i \leq n: [ 1 / i ^ {2} ]) = [ 0 ] \ \end{array} $$

Now we tackle (2):

(2)

$$ \begin{array}{l} = {\mathrm {d e f i n i t i o n s} (2) \mathrm {a n d} \mathrm {o f r e s i d u e c l a s s} } \ [ (\sum i: 1 \leq i \leq n: F / i \cdot (p - i)) ] = [ 0 ] \ = {\mathrm {a r i t h m e t i c} } \ [ - F \cdot (\le i: 1 \le i \le n: 1 / i \cdot (i - p)) ] = [ 0 ] \ = {\text {d i s t r i b u t i o n} } \ [ - F ] \cdot (\underline {{S}} i: 1 \leq i \leq n: [ 1 / (i ^ {2} - i p) ]) = [ 0 ] \ = {\left[ - F \right] \neq [ 0 ] } \ (\sum i: 1 \leq i \leq n: [ 1 / (i ^ {2} - i p) ]) = [ 0 ] \ = {[ x / y ] = [ x / (y - p) ] } \ \end{array} $$

(6) $\left( {{\underline{\mathrm{S}}}_{i} : 1 \leq i \leq n : \left\lbrack {1/{i}^{2}}\right\rbrack }\right) = [0\rbrack$

and hence our two still outstanding proof obligations

(2) and (5) can both be discharged by showing (6).

Since for integer i and j

$$ \begin{array}{l} [ i ^ {2} ] = [ j ^ {2} ] \ = {\mathrm {r e s i d u e c a l c u l u s} } \ [ i + j ] \cdot [ i - j ] = [ 0 ] \ = {\text {p i s p r i m e} } \ [ i + j ] = [ 0 ] \vee [ i - j ] = [ 0 ] \ \end{array} $$

our $p (= {2n} + 1)$ residue classes fall apart in n nonsquare,square [0] and n "positive squares" and for i ranging over $1 \leq i \leq n,\left\lbrack {i}^{2}\right\rbrack$ ranges over the positive squares.

However, for integer $i$ and $j$ with $\left\lbrack {i,j\rbrack \neq \left\lbrack 0\right\rbrack }\right\rbrack$

$$ \begin{array}{l} [ 1 / i ^ {2} ] = [ 1 / j ^ {2} ] \ = {r e s i d u e c a l c u l u s } [ i + j ] \cdot [ i - j ] \cdot [ 1 / i ^ {2} j ^ {2} ] = [ 0 ] \ = {\left[ 1 / i ^ {2} j ^ {2} \right] \neq [ 0 ] } \ \end{array} $$

$$ E W D 9 9 0 - 5 $$

$$ \begin{array}{l} [ i + j ] \cdot [ i - j ] = [ 0 ] \ = {p \text {i s p r i m e} } \ [ i + j ] = [ 0 ] \vee [ i - j ] = 0 \ \end{array} $$

and, because $[1 / i^2 ]\neq [0]$ , we conclude by the same token that for $i$ ranging over $1\leq i\leq n$ , also

${\left\lbrack 1/1\right\rbrack }^{2}$ ranges over the positive squares, and hence (6)

$$ \begin{array}{l} = {\mathrm {d e f i n i t i o n o f (6) a n d a b o v e r e m a r k s} } \ (\subseteq i: 1 \leq i \leq n: [ i ^ {2} ]) = [ 0 ] \ = {\mathrm {d i s t r i b u t i o n} } \ [ (\sum i: 1 \leq i \leq n: i ^ {2}) ] = [ 0 ] \ = {\mathrm {a l g e b r a} } \ [ n \cdot (n + 1) \cdot (2 n + 1) / 6 ] = [ 0 ] \ = {2 n + 1 = p a n d g c d (p, 6) = 1 3 \ \end{array} $$

true

And this concludes the proof.

[0] F.L. Bauer, Private Communication

Austin, 19 October 1986

pror. dr. Edsger W. Dyksfra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712 - 1188

United States of America