[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
Yes.
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
2^(e-1).
Q.E.D.
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?
Alois
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
larger
>> than n (that is fundamental, k^2 is a polynomial...).
More information about the SeqFan
mailing list