Boole noticed that the Binary (excluded middle) Logic of Aristoteles is modeled by idempotent arithmetic: x^2=x hence x.(x-1)=0, which for reals and integers yields x=0 and x=1 as the only (idempotent or 'invariant') roots [George Boole: The Laws of Thought 1854]. For finite multiplication (.) mod m, it is easy to see that if m has q prime divisors then there are 2^q invariants, ordered in a Boolean lattice ( a >= b if a is identity for b, so a.b = b.a = b ).

Mod 10 there are four invariants {1, 5, 6, 0}, and mod 30 = 2.3.5 has 2^3 invariants {1; 16,-9,-5; 6, 10,15; 0}. So only finite arithmetic with a prime power modulus has two invariants 0 and 1 mod p^k (prime p, any k>0), which is k-digit p-ary arithmetic, and successive powers n^i for each n eventually generate either 1 in a periodic cyclic fashion (a group), or 0 in a monotone way that ends in 0 and stays there (by German mathematicians last century called an ideal, just a matter of interpretation : 'beautiful closure' stuck@zero).

Modulo arithmetic (Gauss, 1800) mod m is only half the story, since the carry (multiple of the modulus) is ignored. Integer arithmetic has two components : [more-, less-] significant m-ary digits = [msd, lsd] = [carry, residue]. Carry propagation impedes fast computation, as any hardware designer will tell you. The known arithmetic laws: associative (a.bc=ab.c) and commutative (ab=ba) for (+) and (.), with distribution of (^) over (.), and (.) over (+), remain valid in arithmetic mod m. Unfortunately the carry spoils all that, and so does exponentiation (^), which is not associative nor commutative, nor does it distribute over (+).

So the carry is ignored and exponentiation is avoided, in favour of nice closure laws. Clearly, this stuck@closure (mod m) approach does not suffice in practice. Some light on the matter would be useful : exploring the other half of arithmetic, including the role of carries and ex-ponents. --- Consider the cyclic group G of all roots of 1 mod p^k (prime p), which has order |G| = (p-1).p^{k-1}, obtained from p^k by removing all p^{k-1} multiples m.p of p (= 0 mod p). The two factors are relative prime, so G = A.B is a direct product, where core A is a p-1 cycle. And extension group B has order p^{k-1}, with generator p+1, so B = (p+1)* mod p^k, which is easily verified by induction on k, starting at (p+1)^p = p^2 +1 . . mod p^3, and then (p+1)^{p^m} = p^{m+1} +1 . . mod p^{m+2}. This simple structure of units group G is invaluable, and opens up new ways of exploring arithmetic, including (^) and carry, see [1] (including a short and direct proof of FLT):
[1] "Additive structure of the group of units mod p^k,
with Core and Carry concepts for extension to integers."
published Nov.2005 in Acta Mathematica of Univ. Bratislava full text (pgs. 169 - 184)

The powers n* (mod p^k), odd prime p, of any element in G (n \neqv 0 mod p) generate a cycle that eventually produces 1. As subgroup of G its order divides |G|, so period(n)= r.p^i where r devides p-1. Actually, Fermat discovered this p-1 cycle (mod p): his small theorem (FST) says: n^p = n mod p, for all n. Or better known as: n^{p-1}=1 mod p, which for all n \neqv 0 (mod p) yields the subgroup B={mp+1} mod p^2, with m=0..p-1: a p-cycle generated as (p+1)^m mod p^2. And mod p^k (any k>0): B=(p+1)* of order p^{k-1}.

There is a simple structure for exponents, for instance all p-th powers {n^p} in G form a cycle F of order |F| = |G|/p, relevant to Fermat's problem, for which their additive properties must be studied. Furthermore, induction on FST mod p^k for k>1 yields successor p+1 to be a powerful generator: (p+1)* produces all residues mod p^k that are 1 mod p, of which there are p^{k-1}. They form an 'extension subgroup' B in G, sothat in fact G = A.B is the product of two cycles: |A|=p-1 and |B|=p^{k-1}, with A = { n^|B| } and B = { n^|A| }. . (all n in G).

One of the toughest arithmetic problems is to prove the FLT inequality: x^p + y^p <> z^p for integers x,y,z and prime exponent p>2. It involves only (^) and (+), the first NOT distributing over the last, and p-th powers which mod p^k form a cyclic subgroup of G. Not surprisingly, serious consideration of exponentiation and FLT solutions mod p^k does help. Especially exponent p distributing over the sum x+y, hence x^p + y^p = (x+y)^p mod p^k, turns out to be a clue [1].

Indeed, there are solutions to FLT for residues (1): x^p + y^p = z^p (mod p^k). And in fact necessarily z = x+y mod p^2, sothat for FLT-roots: x^p + y^p = (x+y)^p mod p^2, where the exponent does distribute over a sum, but only for the FLT roots. Normation, a scaling by the inverse in G of one of the terms in (1), makes one term equal to 1, for instance (2): a^p +1 = b^p (mod p^k), with solution b = a+1 (mod p^k), if p=6m+1, with a^3=1 and b= 1/a = a^2 (<>1) mod p^k, so: a + 1/a = -1 (mod p^k) . . the cubic root-pair (<>1) of unity solve FLT mod p^k if p=1 mod 6. . . The only other type of FLT-roots have the triplet form of three 'stacked' inverse pairs: n_i +1 = 1/n_(i+1) . . (indices mod 3), forming a 3-loop, for some primes p>=59. . [1], of which the cubic-root-pair is a special case.

Subject:      Re: JSH: Discovery is messy, eh?   -- On the Hensel lift & FLT(case-1)  --
Author:       Nico Benschop 
Date:         16 Sep 99 06:06:21 -0400 (EDT)    -- news:sci.math
---------
James Harris  on  Wed, 15 Sep 1999 17:08:19 -0400 wrote:

>Nico Benschop wrote in message
>>
>> ******** So, why not bring_in the forgotten "carry" here? ********
>>
>>      x^p + y^p = z^p  ...[1]
>> Assume we do have a solution of [1] mod p^2 (higher power
>> than 2 is not necessary), so:   x^p + y^p = z^p  mod p^2.
>> Now each p-th power mod p^2 in the units group G,
>> of order |G|=(p-1)p, satisfies:
>>           (n^p)^p = n^p (mod p^2)
>>   --- since each n^p is in a p-1 cycle: the 'core' A_2 of G.
>
> Nico, not to get on your case or anything, but how do you figure
> proving FLT mod p when there are all those p-adic solutions? --JSH
             ^^^^^^
Not mod p, James! With FST (Fermat Small Thm) we have n^p=n mod p
for all n, so: x^p + y^p = z^p mod p   has plenty of solutions,
since by  FST:   x + y   = z   mod p   is the only requirement!

Now, modulo p^k, that is: k-digit representation (k>1, base p) there
are still solutions for *some* primes p, but if there is no solution
mod p^2, then neither for any k>2, so k=2 is the crucial case (Hensel
lemma). For instance: p=3 and p=5 have no solutions mod p^2 (easily
veryfied  by complete inspection) so NO solution in integers of [1].
Can you prove that simpler, James ?-)

On the other hand: if ther is a solution mod p^2, then this implies
an infinity of solutions mod p^k for all k>2. This is quite easy to
see for FLT_case1 (x,y,z coprime to p), because then we work in a group
-- meaning that each residue has a unique inverse, so [1] mod p^k
   can be scaled via division (scaling) by the inverse of any of
   the three terms, which becomes 1. Say: a + b == -1 mod p^k ...[2]
where a=(-x/z)^p and b=(-y/z)^p.   Recall that -1 == p^k -1 mod p^k,
so residue -1 mod p^k has k digits (base p) all equal to p-1.

Any solution of [2] only requires a_i + b_i = p-1 ..[3] per digit place!
Hence: given a solution mod p^2 of [1]  you scale it to normal form [2],
    and then EVERY  extension according to [3] will yield an
    extended solution in k+1 digits: free choice of a_{k+1} from 0..p-1
and adjust b_{k+1} to satisfy [3]. So p extra solutions for each
extra msd (more signif. digit): in total p^{k-2} solutions for
every [2] mod p^2 solution. OK?

This in essence is Hensel's "infinite extension" lemma, or more
commonly called: the "Hensel lift".   In his p-adic number theory
(of early this century, IIRC) this is the clue: allow an infinite
(but countable;-) precision: k --> inf, and do "arithmetic" in that
abstract representation.  On the other hand, for any finite precision
some useful info can come of that p-adic stuff, but it confuses you
more than it solves, I think (although I admit not being an p-adict;-)
[essentially: Hensel's p-adics are residues mod p^inf.]

I had a LOT of trouble with this Hensel-lift argument, being used
as the main objection against any approach via residues mod p^k,
sometimes called a "direct" approach to proving  the FLT inequality -
which is claimed to be impossible for the wrong reason
   (as I hope to have explained properly, for the ump-th time).

Again, in TWO steps
     (first residue solution, than integers with carries):

1. Find (if possible for p) a solution mod p^2;
   --> such solution of [1] mod p^2 is necessarily "in core"
       (core A2 is a p-1 order subcycle of units group G2, so
        n^p = n mod p^2, for all n in core A2: extended FST !)
   So (x+y)^p = x+y = x^p + y^p  mod p^2

2. Interprete that 2-digit solution (x,y) as integers X,Y < p^2
   of which you take the p-th powers, but now AS INTEGERS.
   Yielding 2p digit precision numbers (if you like: mod p^{2p} )
   with necessarily INequality, since (X+Y)^p > X^p + Y^p, for
   obvious reasons (binomial expansion, less mixed terms).
  -- And NO other p-th power integers with those last 2 digits can undo
   the inequality (linear transform with scale factor .s^p==1 mod p^2,
   shift +t==0 mod p^2, preserving the assumed FLT integer equality,
   reach all possible extensions: yielding inequality).

In other words: the 2(p-1) carries in producing the p-th powers
"make the difference" you need to prove. Hence: revive the carry,
which was ignored since Gauss' residue arithmetic closure (1801)...
   Thus including the carry: a new(=very_old;-) "generative view"
   of integer arithmetic...  n = cm + r (carry c, modulo m, rest r).

End of FLT_case1 proof (for all primes p>2).   -- NB

> Now, I kept bumping my head against that although folks told me
> about, but now I'm convinced (my current proof used mod q, and
> entirely different animal).
> So, how do you escape the p-adics? Just curious. -- James

See above: take the carry serious again.
Ciao, Nico Benschop - http://www.iae.nl/users/benschop

For the importance of "carry"-step (2.) - breaking the Hensel lift,
  see a short intro at http://www.iae.nl/users/benschop/carry.htm