[seqfan] Re: Mapping problem

[israel at math.ubc.ca]

As W. Edwin Clark pointed out to me, p=2 must be treated specially because 
the multiplicative group mod 2^e is not cyclic if e>2. However, the result 
will be the same: f(2^e) = phi(2^e)/2^(e-1) + 1 = 2. In this case repeated 
squaring mod 2^e will eventually reach 0 (for an even number) or 1 (for an 
odd number), because the group's order is a power of 2.

Cheers,
Robert

On Nov 9 2016, israel at math.ubc.ca wrote:

> The multiplicative group mod p^e (for prime p) is cyclic of order 
> phi(p^e). If the 2-adic order of this is d, the terms that are 2^k'th 
> powers for all of the form g^(k*2^d) where g is a generator. Including 0, 
> we should get f(p^e) = phi(p^e)/2^d +1. Since the function is 
> multiplicative, the following Maple function produces this sequence:
>
>f:= proc(n) local F;
>   F:= ifactors(n)[2];
>   convert(map(proc(t) local p; p:=numtheory:-phi(t[1]^t[2]); 
>1+p/2^padic:-ordp(p,2) end proc,F),`*`) end proc:
>
>For n=1..100, I get
>
> 1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 6, 4, 4, 8, 4, 2, 2, 8, 10, 4, 8, 12, 12, 
> 4, 6, 8, 10, 8, 8, 8, 16, 2, 12, 4, 8, 8, 10, 20, 8, 4, 6, 16, 22, 12, 8, 
> 24, 24, 4, 22, 12, 4, 8, 14, 20, 12, 8, 20, 16, 30, 8, 16, 32, 16, 2, 8, 
> 24, 34, 4, 24, 16, 36, 8, 10, 20, 12, 20, 24, 16, 40, 4, 28, 12, 42, 16, 
> 4, 44, 16, 12, 12, 16, 16, 24, 32, 48, 20, 4, 4, 44, 24, 12
>
>Cheers,
>Robert
>
>On Nov 9 2016, Joerg Arndt wrote:
>
>>* David Wilson <davidwwilson at comcast.net> [Nov 09. 2016 10:32]:
>>> Let S(n) be the largest subset of Z(n) fixed by the mapping n -> n^2, 
>>> and let f(n) = |Z(n)|. For example, S(25) = {0, 1, 6, 11, 16, 21} is 
>>> the largest set of residues modulo 25 fixed by the mapping n -> n^2, so 
>>> f(25) = |S(25)| = 6. Can you find a formula for f(n) in terms of n?
>>>
>>
>>I speculate that all fourth powers give the set.
>>Here I only look at the multiplicative group (units mod n).
>>
>>The following is a quick shot:
>>(PARI) a(n)=my(p=eulerphi(n)); sumdiv(p,d,if((p/d)%4!=0,0,eulerphi(d)))
>>
>> vector(25,n,a(n)) gives [0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 3, 0, 2, 2, 
>> 4, 0, 0, 2, 3, 0, 0, 2, 5] The final 5 for all elements you gave, except 
>> 0.
>>
>>The singly generated multiplicative groups (those having a primitive root)
>>are isomorphic to additive groups of the same cardinality.
>>Squaring in the mult. group maps to doubling in the additive group.
>>From the(se) elements (of the form 2*? mod cardinality) we only
>>take those that are mapped to from said set via doubling.
>>So we are left with all elements 4*? mod cardinality.
>>
>>That should give the same result.
>>
>>Example: (mult. group mod 13 isom. to add. group mod 12)
>>There are 3 elements that are a multiple of 4:
>>m=12; vector(m,j, (4*j)%m )
>>[4, 8, 0, 4, 8, 0, 4, 8, 0, 4, 8, 0]
>>This checks the value for 13 above.
>>
>>But for 11 (add. gr. 10) I get 5 elements:
>>? m=10; vector(m,j, (4*j)%m )
>>[4, 8, 2, 6, 0, 4, 8, 2, 6, 0]
>>That does not match the 0 above...
>>
>>So shurely shome mishtake shomwhere.
>>
>>Best regards,   jj
>>
>>
>>> 
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>--
>>Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>