Re: Puzzled (4^162 mod 100)

In article <4430f032$0$19022$626a54ce@xxxxxxxxxxxx>, mm <mm@xxxxxxxxxx> 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@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • Re: The beauty of Ruby through examples
    ... i am referring of course, not to the factorial, but of the idiom, ... and more fun using blocks.. ...
    (comp.lang.ruby)
  • Re: FLTAA: Field structure p = 2, p>2
    ... The powers of a single element are always a cyclic ... but that group has no such cyclic subgroup, ... And we have divisibility by p as soon as either n is divisible by p^2 ... How can I show M2p </= Mxyz? ...
    (sci.math)
  • ::Cyclic subgroups -- finite vs. infinite::
    ... subgroup of G, using the subgroup criterion. ... i.e. when not all powers of x are ... inverses accordingly, in my opinion. ... Wouldn't it make sense first to list all ...
    (sci.math)