Samuel G. Walters' Congruence
Problem
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$,
$(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.
Fractions
- What Is Fraction?
- Operations on Fractions
- Equivalent Fractions
- Fraction Comparison: An Interactive Illustration
- Compare Fractions: Interactive Practice
- Fraction Comparison Sped up
- Counting and Equivalent Fractions
- Product of Simple Fractions
- What's a number? (Rational number in particular)
- Why 1/3 + 1/4 = 7/12?
- Fractions on a Binary Tree
- Fractions on a Binary Tree II
- Archimedes' Law of the Lever
|Contact| |Up| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny71935720