[seqfan] Re: A092188

[Max Alekseyev]

I suggest the following approach:
Split m into powers of primes, compute a^b modulo each such power of
prime, and combine the results using CRT.

If prime p does not divide a, then mod(a^b,p^k) is computed by the formula.
To compute mod(a^b,p^k) when prime p divides a, represent a as p^m*c
where p does not divide c, and
if m*b >= k, then mod(a^b,p^k) = 0;
if m*b < k, then mod(a^b,p^k) = p^(m*b) * mod(c^b,p^(k-mb)).

Regards,
Max

On Fri, Jun 1, 2012 at 1:28 PM, Jean-François Alcover
<jf.alcover at gmail.com> wrote:
> Thanks Max, for a quick and luminiferous response.
> [ I have to say I'm almost an ignoramus in higher arithmetic ]
> Is there a way (other than the given algorithm) you could suggest
> for me to fix the program in case gcd(a,m) > 1 ?
> 2012/6/1 Max Alekseyev <maxale at gmail.com>
>
>> 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/
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/