Samuel G. Walters' Congruence


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 from $a$ being 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$,


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$.


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.



|Contact| |Up| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny