Modified Fermat's theorem

[Dr Sardonicus]

Originally Posted by devarajkandadai

Sure: consider Mod(x,x^2+97). Let this be %1. You have to calculate ((2+%1)^(101^2-1)/101.
Thank you.

Apart from your command not parsing, your polmod is not prime to p = 101 as per your hypothesis

Originally Posted by devarajkandadai

Of course a and p have to be coprime.

Obviously 2 + Mod(x, x^2 + 97) = Mod(x + 2, x^2 + 97), and

Mod(x + 2, x^2 + 97)*Mod(x - 2, x^2 + 97) = Mod(x^2 - 4, x^2 + 97) = Mod(-101, x^2 + 97).

[CRGreathouse]

Originally Posted by devarajkandadai

Sure: consider Mod(x,x^2+97). Let this be %1. You have to calculate ((2+%1)^(101^2-1)/101.
Thank you.

You are doing this:

Mod(x+2,x^2+97)^(101^2-1)/101

But you should be doing this instead:

Mod(Mod(x+2,x^2+97), 101)^(101^2-1)

which shows that the result does have a remainder and so is not divisible by 101. This is much faster and won't cause the stack to explode.

[Dr Sardonicus]

Originally Posted by CRGreathouse

You are doing this:

Mod(x+2,x^2+97)^(101^2-1)/101

But you should be doing this instead:

Mod(Mod(x+2,x^2+97), 101)^(101^2-1)

which shows that the result does have a remainder and so is not divisible by 101. This is much faster and won't cause the stack to explode.

Hmm. I tried the command

r=Mod(x+2,x^2+97)^(101^2 - 1);

(the last semicolon prevents PARI from barfing r all over the screen), and it completed without error in less time than could be reported. I checked, and trace(r) had over 10,000 decimal digits, so yeah, it's unnecessarily big.

My old version balked at Mod(Mod(x+2,x^2+97), 101), but Mod(x+2,x^2+97)*Mod(1,101) was fine:

? Mod(Mod(x+2,x^2+97),101)
  *** Mod: incorrect type in Rg_to_Fl.

? Mod(x+2,x^2+97)*Mod(1,101)
%1 = Mod(Mod(1, 101)*x + Mod(2, 101), x^2 + 97)

? %^(101^2 - 1)
%2 = Mod(Mod(76, 101)*x + Mod(51, 101), x^2 + 97)

As can be seen, it isn't 1...

[CRGreathouse]

Originally Posted by Dr Sardonicus

My old version balked at Mod(Mod(x+2,x^2+97), 101), but Mod(x+2,x^2+97)*Mod(1,101) was fine

Oh yes, I forgot that was the old way to do it. It works just as well.