[seqfan] Re: successive powers of 2 modulo n

[Alonso Del Arte]

David,

Even a very large prime is still finite. Let's say p is a titanic prime.
There are only (p – 1) possibilities for 2^n mod p. Using Fermat's "little"
theorem you can probably reduce this further still. The number of possible
combinations of (p – 1) or fewer possibilities might be a rather large
number, but certainly not infinity. From this I think you can figure out the
proof on your own or recall where you have seen it.

And instead of Wikipedia look at the MathWorld article linked from its
external links section. With the latter, you don't have to worry about
someone pranking you with planted falsehoods (or worse, innocent
misunderstandings). If you still need convincing Mathworld is much, much
better, consider that the Mathworld article has links to several sequences
in the OEIS.

Al

On Fri, Jun 10, 2011 at 9:30 AM, RGWv <rgwv at rgwv.com> wrote:

> David,
>
>   Use PowerMod to calculate your terms, i.e.; PowerMod[2, k, 29].
>
> Bob.
>
> -----Original Message----- From: David Scambler
> Sent: Friday, June 10, 2011 3:22 AM
> To: seqfan at list.seqfan.eu
> Subject: [seqfan] successive powers of 2 modulo n
>
>
> I am just playing around with this - not sure if it is of interest to
> others.
>
> Take the successive powers of 2 modulo n and the sequence apparently always
> enters a cycle.
> Is this true? Proof?
>
> e.g. Successive powers of 2 modulo 7 -> 1 2 4 1 2 4 1 2 4 1 2 4 ... - a
> cycle of length 3.
>
> For some numbers n the cycle length is n-1 e.g. moduli 2,3,5,11,13,19,29...
> have cycle lengths 1,2,4,10,12,18,28... respectively.
> Is this the maximum length?
>
> For n >= 1 the cycle lengths are
>
> a(n) = 1,1,2,1,4,2,3,1,6,4,10,2,12,3,4,1,8,6,18,4,6, ...
>
> And finally,
>
> Is there an efficient way to calculate successive 2^k mod n without
> actually evaluating 2^k and dividing by n?
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>