[seqfan] Re: Period lengths of k^2 mod n not in OEIS ?

franktaw at netscape.net franktaw at netscape.net
Thu Feb 24 21:03:33 CET 2011


Clearly if gcd(n,m) = 1, a(nm) = lcm(a(n),a(m)), so it suffices to 
establish this for prime powers.

If p is a prime, the period must divide p, but k^2 mod p is not 
constant, so a(p) = p.

a(p^e), e > 1, must be divisible by a(p^(e-1)), and must divide p^e. If 
p != 2, (p^(e-1)+1)^2 =  p^(2e-2)+2p^(e-1)+1 == 2p^(e-1)+1 (mod p^2), 
so a(p^e) != p^(e-1); it must then be e.

By inspection, a(4) = 2 and a(8) = 4.

This leaves a(2^e), e > 3. But then (2^(e-2)+1)^2 = 2^(2e-4)+2^(e-1)+1 
== 2^(e-1)+1 (mod 2^e), so a(n) > 2^(e-2). On the other hand, 
(2^(e-1)+c)^2 = 2^(2e-2)+c2^e+c^2 == c^2 (mod 2^e). Hence the period is 


Franklin T. Adams-Watters

-----Original Message-----
From: Alois Heinz <heinz at hs-heilbronn.de>

It seems that this sequence has n/a(n) = period: 1,1,1,2 
Can you confirm this? 
Am 24.02.2011 20:03, schrieb Charles Greathouse: 
> I concur with your results.  (I read as little of your post as 
> possible and wrote my own code to minimize the chance of sharing an 
> error.) 
> You should certainly submit this!  It's worth mentioning that a(n) is 
> a multiple of A019554(n). 
> Charles Greathouse 
> Analyst/Programmer 
> Case Western Reserve University 
> On Thu, Feb 24, 2011 at 1:30 PM, Richard Mathar 
> <mathar at strw.leidenuniv.nl>  wrote: 
>> In conjunction with A182865 the following topic arose: 
>> The sequence k^2 mod n for some fixed n has a period length not 
>> than n (that is fundamental, k^2 is a polynomial...). 

More information about the SeqFan mailing list