Re: Puzzled (4^162 mod 100)

In article <49baidFntrgfU1@news.dfncis.de>,
Sebastian Gottschalk <seppi@seppig.de> wrote:

  [.snip.]

  [The powers of 4 in Z/100Z]

>The multiplicative identity of this subgroup is 76.

There was a related paper recently on either the American Mathematical
Monthly or the Mathematics Magazine, can't remember which. Not exactly
this, though...

In any case: suppose a,n are positive integers, a|n, (a,n/a)=1.
This is the situation with a=4, n=100, for example.

Then the powers of a form a group under multiplication in Z/nZ, and
the order is the same as the order of the subgroup generated by a in
the units modulo n/a.

If a^r = 1 (mod n/a) then a^{r+1}=a (mod n).
If a^k = a^m (mod n), with k,m>0, then a^{k}=a^{m} (mod n/a), and
since we are assuming (a,n/a)=1, we deduce a^{k-1}=a^{m-1} (mod n/a);
so a^k=a^m (mod n) if and only if m=k (mod r), where r is the order of
a modulo n/a.

The claim is that a^r is the identity of the multiplicative
subsemigroup generated by a in Z/nZ. Indeed, a*a^r=a by assumption,
and for any k>1, a^r*a^k = a^{r+k} = a^{r+1}*a^{k-1} =
a*a^{k-1}=a^k. In particular, the inverse of a^k, 1<= k < r is
a^{r-k}, and the inverse of a^r is a^r.

Things get more complicated if gcd(a,n)=k>1, but k is not a.

-- 
======================================================================
"It's not denial. I'm just very selective about
 what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu