[seqfan] Re: A092188

Max Alekseyev maxale at gmail.com
Fri Jun 1 11:11:16 CEST 2012


The equality mod(a^b,m) = mod(a^(mod(b,phi(m)), m) works only when a
is coprime to m.
E.g., take a=2, b=2, m=4:
mod(a^b,m) = mod(2^2,4) = 0
mod(a^(mod(b,phi(m)), m) = mod(2^(mod(2,2), 4) = mod(2^0, 4) = 1

Regards,
Max

On Fri, Jun 1, 2012 at 11:28 AM, Jean-François Alcover
<jf.alcover at gmail.com> wrote:
> Hello Seqfans,
>
> My trouble is about sequence A092188.
> a(n) = smallest positive integer m such that 2^3^4^5^...^n == m mod n.
>
> I wanted to generate it sans using the algorithm given by Robert Munafo,
> and using the equality mod(a^b,m) = mod(a^(mod(b,phi(m)), m)
> This way with this Mathematica one-liner:
>
> a[n_] := Fold[ PowerMod[#2, #1, Nest[EulerPhi, n, #2-2]] &, n, Range[n-1,
> 2, -1]];
>
> Unfortunately it goes wrong for about 10% of the cases
> such as a(10)=8 instead of 2
> Any help or hint is welcome.
>
> jfa
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/



More information about the SeqFan mailing list