Re: Puzzled (4^162 mod 100)

In article <4430f032$0$19022$626a54ce@news.free.fr>, mm <mm@nospam.net> wrote:
>Paul Rubin a écrit :

>> The powers of 4 mod 100 are
>>
>> 4**1 = 4
>> 4**2 = 16
>> 4**3 = 64
>> 4**4 = 56
>> 4**5 = 24
>> 4**6 = 96
>> 4**7 = 84
>> 4**8 = 36
>> 4**9 = 44
>> 4**10 = 76
>> 4**11 = 4
>>
>> I.e. that pattern cycles with length 10, not 20. The multiplicative
>> identity 1 doesn't occur in the list of powers, so it's not a subgroup.
>
>In fact, the sequence you gave can be obtained by multiplying by 4,
>in Z/100Z, the elements of the group {4^k (mod 25)}. And the length
>is smaller than 20 simply because 4 is not a generator of U(Z/25Z).

Yes, though one should note that this bijection is not a group
morphism.

More generally, you have a generalization of Euler's Theorem:

   Theorem. Let a,n be positive integers, n>1, and let (a,n)=k. The
   powers of a form a multiplicative subgroup of the multiplicative
   semigroup of Z/nZ if and only if (k,n/k)=1. In that case, the order
   of the subgroup is the same as the order of a modulo n/k, and in
   particular a^{phi(n/k)+1} = a (mod n), and a^{phi(n/k)} is the
   identity of the group.

   Proof. If {a,a^2,...,a^m,...} forms a group, then there exists an
   r such that a = a^{r+1} (mod n). Then a(a^r-1) is a multiple
   of n, so (n/k) | (a/k)(a^r-1). Since (n/k,a/k)=1, it follows that
   (n/k)|a^r-1, so a is a unit modulo n/k. Therefore, (a,n/k)=1, and
   so (k,n/k)=1. Conversely, if (k,n/k)=1, then (k*(a/k),n/k)=1, so a
   is a unit modulo n/k. Thus a^r=1 (mod n/k) for some r, so ka^r=k
   (mod n), hence a^{r+1}=a (mod n). Then a^r is an identity element
   for the powers of a, and a^{r-u} is a multiplicative inverse for
   a^u, u=1,...,r-1, proving the powers of a form a group.

   From the above, it is clear that a=a^{r+1} (mod n) if and only if
   a^r=1 (mod n/k), thus the order of this group is equal to the order
   of a in Z/(n/k)Z. Finally, a^{phi(n/k)}=1 (mod n/k), so
   a^{phi(n/k)} is the identity element of the group. //

-- 
======================================================================
"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