# Samuel G. Walters' Congruence

### Solution 1

\begin{align}1+(a-1)^{a^n}&=1+(a-1)^{a^{n-1}\cdot a}\\ &=(1+(a-1)^{a^{n-1}})(\ldots). \end{align}

Use induction. The first bracket is divisible by $a^n$ and the second bracket by $a$ (using that $a$ is odd), so the product is divisible by $a^{n+1}.$

Similarly, it proves a more general $(ab-1)^{a^n}\equiv\,-1\mod a^{n+1},$ $a$ odd, $b$ integer.

### Solution 2

We prove a more general statement:

Let $a,n$ be positive integers, then

$\displaystyle 1+(a-1)^{a^n} \equiv (-1)^a \mod a^{n+1}.$

The binomial theorem gives

$\displaystyle (a-1)^{a^n} =\sum_{l=0}^{a^n} \binom{a^n}{l}a^l(-1)^{a^n-l} \equiv (-1)^a\sum_{l=0}^{n} \binom{a^n}{l}(-a)^{l} \mod a^{n+1}$

So it remains to show that, for $l\gt 0$ the following holds:

$\displaystyle 0 \equiv \binom{a^n}{l}a^{l} \mod a^{n+1}$

We can rewrite the binomial coefficient as

$\displaystyle \binom{a^n}{l}a^{l} = a^{n+1}\frac{a^{l-1}}{l}\binom{a^n-1}{l-1}$

We are done if we can show that $l$ divides $\displaystyle a^{l-1}\binom{a^n-1}{l-1}.$ Consider the prime decomposition $l=p^mq^s\ldots$ We shall prove that, for a generic prime factor $p,$ $p^m$ divides $\displaystyle a^{l-1}\binom{a^n-1}{l-1}.$

• If $p \not| a$ then $\displaystyle p^m | \binom{a^n-1}{l-1} = l\cdot \frac{1}{a^n}\binom{a^n}{l}.$

• If $p | a$ then, obviously, $m \lt l$, i.e., $m\le l-1,$ and so $p^m | a^m | a^{l-1}.$

### Solution 3

If $a=1$, the proposition is trivially satisfied. Consider the case $a\gt 1$. We use the method of induction and start by noting the following property (henceforth referred to as property I) for any non-negative integers $p$ and $q$:

$\displaystyle \sum_{k=0}^{(a-1)}(-1)^k (pa^{q+1}-1)^k\equiv \left[\sum_{k=0}^{(a-1)}(-1)^{2k}\right]~(mod~a)\equiv a~(mod~a)\equiv 0~(mod~a).$

For $n=1$,

\displaystyle \begin{align} (a-1)^a+1&=a\sum_{k=0}^{(a-1)} (-1)^k (a-1)^k,~\text{(expansion follows fromabeing odd)} \\ &\equiv 0~(mod~a^2). ~\text{(Using property I)}. \end{align}

and the proposition is satisfied.

Suppose the proposition is true for $n=m$. Thus, for some integer $s$,

$(a-1)^{a^m}+1=sa^{m+1}.$

For $n=m+1$,

\displaystyle \begin{align} (a-1)^{a^{m+1}}+1&=[(a-1)^{a^m}]^a+1=[sa^{m+1}-1]^a+1 \\ &=sa^{m+1}\sum_{k=0}^{(a-1)}(-1)^k (sa^{m+1}-1)^k \\ &\text{(expansion similar to the one used before)},\\ &\equiv 0~(mod~a^{m+2}). ~\text{(Using property I)}. \end{align}

Thus, by induction, the proposition is true for all positive integers $n$.

### Acknowledgment

Sam Walters posted that problem in response to an earlier question. Solution 1 is by Bogdan Latanianu; Solution 2 is by Long Huynh Huu; Solution 3 is by Amit Itagi.